基于冲突优先级变次优因子的EECBS多机器人路径规划  

EECBS Multi-robot Path Planning Based on Variable Suboptimal Factors of Prioritizing Conflicts

作　　者：闫星宇 王妮娅[1] 毛剑琳[1] 贺志刚 李大焱[1] Yan Xingyu;Wang Niya;Mao Jianlin;He Zhigang;Li Dayan(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China)

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

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

基　　金：国家自然科学基金(62263017);云南省重大科技专项计划(202002AC080001)。

摘　　要：在多机器人路径规划(multi robot path planning,MRPP)过程中,最优路径之间无法规避的关键冲突对路径求解效率具有较大影响。为解决这一问题,提出一种基于冲突优先级变次优因子的多机器人路径规划方法。在融合显式估计的冲突搜索(explicit estimation conflict-based search,EECBS)算法下层执行路径搜索;在EECBS算法框架的上层对冲突优先级进行判断,并自适应增加关键冲突机器人的次优因子;通过分析关键冲突周围邻域的障碍物分布影响路径节点自由度情况,进一步调整关键冲突机器人的次优因子。在多个标准地图下的实验结果表明,相较于EECBS算法,本文方法的求解时间改善了8.35%~49.14%,上层冲突节点的二叉约束树(constraint tree,CT)拓展量改善了3.79%~55.22%,验证了本文方法的有效性。In the process of multi-robot path planning(MRPP),the unavoidable key conflicts between the optimal paths have a significant impact on the efficiency of path solving.To address this issue,an MRPP method based on variable suboptimal factors of prioritizing conflicts(PC)was proposed.Path search was performed at the lower layer of the explicit estimation conflict-based search(EECBS)algorithm;in the upper layer of the EECBS algorithm framework,the PC was determined,and the suboptimal factor of the robot with key conflicts was adaptively increased;by analyzing the distribution of obstacles in the surrounding neighborhoods of key conflicts,the degree of freedom of path nodes was affected,and the suboptimal factor of the robot with key conflicts could be further adjusted.The results under multiple standard maps indicate that compared to the EECBS algorithm,the algorithm proposed in this paper has shortened the solving time by 8.35%~49.14%,and the expansion of the binary constraint tree(CT)of the upper conflict nodes has improved by 3.79%~55.22%,verifying the effectiveness of the proposed algorithm.

关 键 词：多机器人路径规划 自适应次优因子 冲突优先级 约束树 路径自由度 

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