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

Multi-robot Path Planning Based on CBS Algorithm

针对冲突搜索法(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%.