基于冲突搜索算法的多机器人路径规划  

Multi-robot Path Planning Based on CBS Algorithm

作　　者：乔乔 王艳 纪志成 Qiao Qiao;Wang Yan;Ji Zhicheng(Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China)

机构地区：[1]江南大学教育部物联网技术应用工程中心,江苏无锡214122

出　　处：《系统仿真学报》2022年第12期2659-2669,共11页Journal of System Simulation

基　　金：国家自然科学基金(61973138);国家重点研发计划(2018YFB1701903)。

摘　　要：针对冲突搜索法(conflict-based search,CBS)在多机器人路径规划(multi-agent path finding,MAPF)过程中规划路径过长、单向搜索运行时间长等缺陷,从搜索方向和搜索方式提出一种改进的双向A^(*)焦点搜索来优化冲突搜索算法。将次优因子ω引入冲突搜索算法的底层搜索函数中,以提高路径搜索的效率;将冲突搜索算法中的单向搜索优化为双向A^(*)搜索。实验结果表明:改进的冲突搜索算法的路径成本缩短了14.82%,总运行时间缩短了10.63%。Aiming at the long multi-robot planning path and long one-way search running time of conflictbased search(CBS) in the multi-agent path finding(MAPF), an improved CBS algorithm is proposed,which in a two-way A^(*) focus search is used to optimize the search direction and search method. The suboptimal factorωis introduced into the underlying search function of the CBS algorithm to improve the efficiency of path search. The one-way search in the conflict search algorithm is optimized to a two-way A^(*) search. The experimental results show that the path cost of the improved CBS algorithm is shortened by 14.82%, and the total running time is shortened by 10.63%.

关 键 词：多机器人路径规划 双向搜索 焦点搜索 路径规划 冲突搜索算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]