基于冲突概率反馈的CBS分层多机器人路径规划

作者：杨邹; 毛剑琳^*; 李大焱; 王妮娅; 张凯翔; 李昊楠

来源：计算机集成制造系统, 2023, 1-16.

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

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

• 单位
  昆明理工大学; 自动化学院; 机电工程学院