Abstract: In multi-agent path finding,to address the problems of long time for high-level conflict resolution and many expansion nodes at the low-level under the Conflict-based Search (CBS) framework,an improved CBS hierarchical solution framework and method based on Conflict Probability Feedback (CPF) named ICBS-CPF was proposed.The conflict probability calculation method of path nodes was defined,and the Jump Point Search (JPS) was introduced to combine with the conflict probability feedback,which was used as the feedback carrier of the conflict probability.The improved jump point search algorithm was added as a guiding level between the high level and the low level of CBS to guide the search direction of A*.The results of testing with benchmark maps of different sizes and structures showed that conflict probability feedback could effectively reduce conflicts between robots.The ICBS-CPF algorithm not only speeded up the conflict resolution process,but also had a significant reduction in the number of expansion nodes at the low level of the algorithm in a large map complex environment.Meanwhile,the algorithm could effectively improve the solution time as well as the solution success rate in multi-agent path finding problems.

Key words: hierarchical solution framework, multi-agent path finding, conflict probability feedback, improved jump point search, guided A* planning

摘要： 在多机器人路径规划中,针对基于冲突搜索(CBS)框架下存在高层冲突消解时间长以及底层扩展节点多的问题,提出了一种基于冲突概率反馈的改进CBS(ICBS-CPF)分层求解框架和方法。首先定义路径节点的冲突概率计算方法,并引入跳点搜索结合冲突概率反馈,将跳点搜索作为冲突概率的反馈载体。其次在CBS的高层和底层之间加入改进后的跳点搜索算法作为引导层来指导A*的搜索方向。通过不同规模和结构的基准地图测试结果表明,冲突概率反馈可以有效减少机器人之间的冲突。ICBS-CPF算法不但能加快冲突的消减过程,而且在大地图复杂环境中,算法底层的扩展节点数量有明显减少。同时,算法能够有效改善多机器人路径规划问题中的求解时间以及求解成功率。

关键词: 分层求解框架, 多机器人路径规划, 冲突概率反馈, 改进跳点搜索, 引导A*规划