基于分布式拍卖机制的多移动机器人动态任务分配算法
PDF下载 (287)许佳杰,陈思鲁,张子栋,邵兵兵,刘 强,张 驰,杨桂林.基于分布式拍卖机制的多移动机器人动态任务分配算法[J].宁波大学学报(理工版),2023,36(3):29-35.DOI:
XU Jiajie,CHEN Silu,ZHANG Zidong,SHAO Bingbing,LIU Qiang,ZHANG Chi,YANG Guilin.Dynamic task assignment algorithm for multi-mobile robots based on distributed auction mechanism[J].Journal of Ningbo University(Natural Science & Engineering Edition),2023,36(3):29-35.DOI:
| Title: | Dynamic task assignment algorithm for multi-mobile robots based on distributed auction mechanism |
| 作者: | 许佳杰, 陈思鲁, 张子栋, 邵兵兵, 刘 强, 张 驰, 杨桂林 |
| Author(s): | XU Jiajie, CHEN Silu, ZHANG Zidong, SHAO Bingbing, LIU Qiang, ZHANG Chi, YANG Guilin |
| 关键词: | 多移动机器人调度系统; 动态任务分配; 拍卖机制; 分布式控制 |
| Keywords: | multi-mobile robot scheduling system; dynamic task assignment; auction mechanism; distributed control |
| 分类号: | TP242.6 |
| 文献标识码: | A |
| 摘要: | 任务分配是多移动机器人调度系统的关键问题之一, 为了提高任务整体完成效率, 提出了一种基于分布式拍卖机制的多移动机器人动态任务分配算法. 该方法对机器人群体采用分布式控制方法, 彼此共享且动态更新任务集, 采用分布式的拍卖机制竞拍任务, 增加了调整任务执行顺序环节, 考虑任务整体完成效率, 最后在Linux系统下搭建了多机器人和障碍物的仿真环境. 结果表明, 该算法分配效率高于线性(CLP)算法和混合整数求解(CBC)算法, 且具有稳定性, 相比执行效率高的深度强化学习(DQN)算法和空缺链(VC)算法, 执行效率稳定, 移动代价降低了55％, 实现了较高执行效率和低移动代价之间的平衡, 可应用于实际仿真环境, 具有可行性. |
| Abstract: | Task allocation is one of the key issues in multi-mobile robot scheduling system. The existing methods tend to focus on improving the efficiency of task assignment without considering the task execution time, ignoring the overall task completion efficiency and the computational cost. In addition, they usually adopt a centralized control architecture, which requires the robot to be in a stable and reliable communication environment. In order to solve the above problems, a distributed auction mechanism-based dynamic task assignment algorithm for multiple mobile robots is proposed. The method adopts a distributed control method for robot groups, shares and dynamically updates task sets with each other, bids for tasks using a distributed auction mechanism, adds a link to adjust the task execution order, and considers the overall task completion efficiency. Finally, a simulation environment with multiple robots and obstacles is built under Linux system and relevant experiments are conducted. The experimental results show that the algorithm has higher allocation efficiency than the linear and mixed integer solving algorithms CLP and CBC, and has stability. Comparing with the Deep Reinforcement Learning (DQN) and Vacancy Chain (VC) algorithms, the execution efficiency remains stable while the movement cost is significantly reduced by 55％, which achieves a balance between the efficiency and cost in operation. This study, as believed, can be put to the real-world applications with promising outlook. |
| 参考文献 /References: | [1] D’Emidio M, Khan I. Multi-robot task allocation problem: Current trends and new ideas[EB/OL]. [2022-07-10]. https://ceur-ws.org/Vol-1949/ICTCSpaper07.pdf. [2] Gerkey B P, Matari? M J. A formal analysis and taxonomy of task allocation in multi-robot systems[J]. The International Journal of Robotics Research, 2004, 23(9):939-954. [3] Korsah G A, Stentz A, Dias M B. A comprehensive taxonomy for multi-robot task allocation[J]. The Inter- national Journal of Robotics Research, 2013, 32(12): 1495-1512. [4] Tsang K F E, Ni Y Q, Wong C F R, et al. A novel warehouse multi-robot automation system with semi- complete and computationally efficient path planning and adaptive genetic task allocation algorithms[C]//2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), Singapore, 2018:1671- 1676. [5] Luo L. Distributed algorithm design for constrained multirobot task assignment[EB/OL]. [2022-07-10]. https:// www.ri.cmu.edu/pub_files/2014/8/Lingzhi_Luo_robotics_ [6] 2014.pdf. [7] 杨博, 王叶群, 黄国策, 等. 基于冲突分解的短波频点真实在线双拍卖算法[J]. 系统工程与电子技术, 2022, 44(9):2947-2954. [8] Schneider E, Sklar E I, Parsons S. Mechanism selection for multi-robot task allocation[C]//Gao Y, Fallah S, Jin Y, et al. Annual Conference Towards Autonomous Robotic Systems, Cham: Springer, 2017:421-435. [9] 郑阳超, 李珍妮. 面向资源最优分配的深度学习双边拍卖算法[EB/OL]. [2022-07-10]. https://www.doc88. com/p-39999494108107.html. [10] Dai X F, Wang J Z, Zhao J Q. Research on multi-robot task allocation based on BP neural network optimized by genetic algorithm[C]//2018 5th International Conference on Information Science and Control Engineering (ICISCE), Zhengzhou, China, 2019:478-481. [11] Sarkar C, Paul H S, Pal A. A scalable multi-robot task allocation algorithm[C]//2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, Australia, 2018:5022-5027. [12] Bertsekas D P. Auction algorithms for network flow problems: A tutorial introduction[J]. Computational Optimization and Applications, 1992, 1(1):7-66. [13] Otte M, Kuhlman M J, Sofge D. Auctions for multi-robot task allocation in communication limited environments[J]. Autonomous Robots, 2020, 44(3/4):547-584. [14] Whitbrook A, Meng Q G, Chung P W H. Addressing robustness in time-critical, distributed, task allocation algorithms[J]. Applied Intelligence, 2019, 49(1):1-15. [15] Zhou X, Wang H M, Ding B, et al. Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm[J]. Expert Systems with Applications, 2019, 116:10-20. [16] Menouer T, Le Cun B. A parallelization mixing OR- tools/gecode solvers on top of the bobpp framework [C]//2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, Compiegne, France, 2013:242-246. [17] Dai W, Lu H M, Xiao J H, et al. Multi-robot dynamic task allocation for exploration and destruction[J]. Journal of Intelligent & Robotic Systems, 2020, 98(2):455-479. |
| 备注/Memo: | 收稿日期:2022-09-21.宁波大学学报（理工版）网址:http://journallg.nbu.edu.cn/ 基金项目:国家自然科学基金（U1509202）;浙江省基础公益研究计划（LGG19E050007）;浙江省机器人与智能制造装备技术重点实验室（2015E10011）;宁波市“科技创新2025”重大专项（2018B10010,2020Z020）. 第一作者:许佳杰（1997－）,男,浙江杭州人,在读硕士研究生,主要研究方向:多移动机器人调度.E-mail:xujiajie@nimte.ac.cn *通信作者:陈思鲁（1982－）,男,福建福州人,研究员,主要研究方向:高速、高精度运动控制及工业自动化.E-mail:chensilu@nimte.ac.cn 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/ |
