面向多到一任务交接的多机器人协作路径规划算法  

Multi-robot collaborative path planning algorithm for many-to-one task handover

作　　者：毛剑琳[1] 贺志刚 张书凡 李睿祺 张凯翔 Mao Jianlin;He Zhigang;Zhang Shufan;Li Ruiqi;Zhang Kaixiang(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China)

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650500 [2]昆明理工大学机电工程学院,昆明650500

出　　处：《仪器仪表学报》2024年第9期237-248,共12页Chinese Journal of Scientific Instrument

基　　金：国家自然科学基金(62263017)项目资助。

摘　　要：针对传统的多机器人路径规划算法处理任务形式单一、非必要损耗大等问题,本文提出一种多组多到一任务处理方式的协作动态优先级安全间隔路径规划算法(Co-DPSIPP)。首先,该算法以最小化路径总长度为目标,采用模拟退火、扩散搜索等方法确定各组机器人的任务交接点;然后,采用改进的安全间隔路径规划算法为所有机器人进行分段路径规划;进一步针对部分不合理任务交接点会造成区域性拥塞并导致求解失败的问题,设计群组优先级与中间点动态调整规划策略。最后,在4种基准地图上的测试结果显示,相较于协作基于冲突搜索算法(Co-CBS),本文提出的算法在求解成功率上平均可提升73%,在运行时间和路径总长度上平均分别可减少56%和5%。实验结果证明,本文算法为多组多到一任务场景下的多机器人协作路径规划问题提供了更为灵活且扩展性更强的解决方案。To solve the problems of traditional multi-robot path planning algorithms dealing with a single form of task and large non-essential loss,this article proposes a multi-group many-to-one task processing mode of cooperative dynamic priority safe interval path planning algorithm(Co-DPSIPP).Firstly,the algorithm utilizes the simulated annealing and diffusion search to determine the task handover point of each group of robots with the objective of minimizing the total path length.Then,the improved safe interval path planning algorithm is used to carry out the segmented path planning for all the robots.Furthermore,to deal with the problem that some irrational task handover points may cause regional congestion and lead to solution failure,a cluster prioritization and intermediate point dynamic adjustment planning strategy is designed.Finally,the test results on four benchmark maps show that,compared with the cooperative conflict-based search algorithm(Co-CBS),the proposed algorithm can improve the solution success rate by 73%on average,and reduce the running time and total path length by 56%and 5%on average,respectively.The experimental results show that the proposed algorithm provides a more flexible and scalable solution for the collaborative path planning problem of multi-robot in multi-group many-to-one task scenarios.

关 键 词：多机器人 路径规划 安全间隔 任务交接点 群组优先级 中间点 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] TH166[自动化与计算机技术—控制科学与工程]