An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auctio...An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.展开更多
针对巡飞弹群协同执行侦察、打击和评估的任务分配问题,考虑任务时序约束、目标属性异构特征以及支持多弹共同执行一个任务的需求,提出一种基于联合投标的一致性包拍卖算法(Joint-bidding-based Consensus Based Bundle Algorithm,JCBB...针对巡飞弹群协同执行侦察、打击和评估的任务分配问题,考虑任务时序约束、目标属性异构特征以及支持多弹共同执行一个任务的需求,提出一种基于联合投标的一致性包拍卖算法(Joint-bidding-based Consensus Based Bundle Algorithm,JCBBA),以实现异构任务分配。在构建弹群协同“察打评”任务分配问题的组合优化模型的基础上,基于CBBA架构,定制任务包构建机制、个体竞标策略和考虑联合投标的边际收益计算方法,实现无中心通信条件下时序任务协同分配的快速鲁棒求解。多场景仿真试验结果表明,JCBBA可以在满足多种约束的前提下实现时序约束任务的合理分配,性能对比试验结果表明JCBBA能够更好地权衡协同任务分配的求解时效性和结果最优性,求解耗时相比一致性联盟算法减少约40%。展开更多
An extension of 2-D assignment approach is proposed for measurement-to-target association for improving multiple targets vector miss distance measurement accuracy. When the multiple targets move so closely, the measur...An extension of 2-D assignment approach is proposed for measurement-to-target association for improving multiple targets vector miss distance measurement accuracy. When the multiple targets move so closely, the measurements can not be fully resolved due to finite resolution. The proposed method adopts an auction algorithm to compute the feasible measurement-to-target assignment with unresolved measurements for solving this 2-D assignment problem. Computer simulation results demonstrate the effectiveness and feasibility of this method.展开更多
Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivate...Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.展开更多
This paper introduces a pioneering dynamic system optimisation for multiagent(DySOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DySOMA is...This paper introduces a pioneering dynamic system optimisation for multiagent(DySOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DySOMA is an advanced auction-based algorithm coupled with a novel task preemption ranking mechanism,seamlessly integrated with an ontology knowledge graph that dynamically updates.This integration not only enhances the efficiency of task allocation among robots but also significantly improves the adaptability of the system to environmental changes.Compared to other advanced algorithms,the DySOMA algorithm shows significant performance improvements,with its RLB 26.8%higher than that of the best-performing Consensus-Based Parallel Auction and Execution(CBPAE)algorithm at 10 robots and 29.7%higher at 20 robots,demonstrating its superior capability in balancing task loads and optimising task completion times in larger,more complex environments.DySOMA sets a new benchmark for intelligent robot task scheduling,promising significant advancements in the autonomy and flexibility of robotic systems in complex evolving environments.展开更多
This paper introduces a pioneering dynamic system optimisation for multiagent(DysOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DysOMA is...This paper introduces a pioneering dynamic system optimisation for multiagent(DysOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DysOMA is an advanced auctionbased algorithm coupled with a novel task preemption ranking mechanism,seamlessly integrated with an ontology knowledge graph that dynamically updates.This integration not only enhances the efficiency of task allocation among robots but also significantly improves the adaptability of the system to environmental changes.Compared to other advanced algorithms,the DySOMA algorithm shows significant performance improvements,with its RLB 26.8%higher than that of the best-performing Consensus-Based Parallel Auction and Execution(CBPAE)algorithm at 10 robots and 29.7%higher at 20 robots,demonstrating its superior capability in balancing task loads and optimising task completion times in larger,more complex environments.DysOMA sets a new benchmark for intelligent robot task scheduling,promising significant advancements in the autonomy and flexibility of robotic systems in complex evolving environments.展开更多
基金Sponsored by Excellent Young Scholars Research Fund of Beijing Institute of Technology(00Y03-13)
文摘An improved genetic algorithm is proposed to solve the problem of bad real-time performance or inability to get a global optimal/better solution when applying single-item auction （SIA） method or combinatorial auction method to multi-robot task allocation. The genetic algorithm based combinatorial auction （GACA） method which combines the basic-genetic algorithm with a new concept of ringed chromosome is used to solve the winner determination problem （WDP） of combinatorial auction. The simulation experiments are conducted in OpenSim, a multi-robot simulator. The results show that GACA can get a satisfying solution in a reasonable shot time, and compared with SIA or parthenogenesis algorithm combinatorial auction （PGACA） method, it is the simplest and has higher search efficiency, also, GACA can get a global better/optimal solution and satisfy the high real-time requirement of multi-robot task allocation.
文摘针对巡飞弹群协同执行侦察、打击和评估的任务分配问题,考虑任务时序约束、目标属性异构特征以及支持多弹共同执行一个任务的需求,提出一种基于联合投标的一致性包拍卖算法(Joint-bidding-based Consensus Based Bundle Algorithm,JCBBA),以实现异构任务分配。在构建弹群协同“察打评”任务分配问题的组合优化模型的基础上,基于CBBA架构,定制任务包构建机制、个体竞标策略和考虑联合投标的边际收益计算方法,实现无中心通信条件下时序任务协同分配的快速鲁棒求解。多场景仿真试验结果表明,JCBBA可以在满足多种约束的前提下实现时序约束任务的合理分配,性能对比试验结果表明JCBBA能够更好地权衡协同任务分配的求解时效性和结果最优性,求解耗时相比一致性联盟算法减少约40%。
文摘An extension of 2-D assignment approach is proposed for measurement-to-target association for improving multiple targets vector miss distance measurement accuracy. When the multiple targets move so closely, the measurements can not be fully resolved due to finite resolution. The proposed method adopts an auction algorithm to compute the feasible measurement-to-target assignment with unresolved measurements for solving this 2-D assignment problem. Computer simulation results demonstrate the effectiveness and feasibility of this method.
文摘Winner determination is one of the main challenges in combinatorial auctions. However, not much work has been done to solve this problem in the case of reverse auctions using evolutionary techniques. This has motivated us to propose an improvement of a genetic algorithm based method, we have previously proposed, to address two important issues in the context of combinatorial reverse auctions: determining the winner(s) in a reasonable processing time, and reducing the procurement cost. In order to evaluate the performance of our proposed method in practice, we conduct several experiments on combinatorial reverse auctions instances. The results we report in this paper clearly demonstrate the efficiency of our new method in terms of processing time and procurement cost.
基金supported by the Natural Science Foundation of Shandong Province(No.ZR2024MF085)the Jinan Science and Technology Bureau(No.2021GXRC026)+1 种基金Young Scholars Program of Shandong University(No.2018WLJH71)the Fundamental Research Funds of Shandong University and the Taishan Scholar Foundation of Shandong Province.
文摘This paper introduces a pioneering dynamic system optimisation for multiagent(DySOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DySOMA is an advanced auction-based algorithm coupled with a novel task preemption ranking mechanism,seamlessly integrated with an ontology knowledge graph that dynamically updates.This integration not only enhances the efficiency of task allocation among robots but also significantly improves the adaptability of the system to environmental changes.Compared to other advanced algorithms,the DySOMA algorithm shows significant performance improvements,with its RLB 26.8%higher than that of the best-performing Consensus-Based Parallel Auction and Execution(CBPAE)algorithm at 10 robots and 29.7%higher at 20 robots,demonstrating its superior capability in balancing task loads and optimising task completion times in larger,more complex environments.DySOMA sets a new benchmark for intelligent robot task scheduling,promising significant advancements in the autonomy and flexibility of robotic systems in complex evolving environments.
基金supported by the Natural Science Foundation of Shandong Province(No.ZR2024MF085)the Jinan Science and Technology Bureau(No.2021GXRC026)+1 种基金Young Scholars Program ofShandong University(No.2018WLJH71)the Fundamental Research Funds of Shandong University and the Taishan Scholar Foundation of Shandong Province.
文摘This paper introduces a pioneering dynamic system optimisation for multiagent(DysOMA)framework,revolutionising task scheduling in dynamic intelligent spaces with an emphasis on multirobot systems.The core of DysOMA is an advanced auctionbased algorithm coupled with a novel task preemption ranking mechanism,seamlessly integrated with an ontology knowledge graph that dynamically updates.This integration not only enhances the efficiency of task allocation among robots but also significantly improves the adaptability of the system to environmental changes.Compared to other advanced algorithms,the DySOMA algorithm shows significant performance improvements,with its RLB 26.8%higher than that of the best-performing Consensus-Based Parallel Auction and Execution(CBPAE)algorithm at 10 robots and 29.7%higher at 20 robots,demonstrating its superior capability in balancing task loads and optimising task completion times in larger,more complex environments.DysOMA sets a new benchmark for intelligent robot task scheduling,promising significant advancements in the autonomy and flexibility of robotic systems in complex evolving environments.
