基于耦合度矩阵的安全区间多机器人路径k鲁棒规划算法  

Safe interval multi-robot path k robust planning algorithm based on coupling degree matrix

作　　者：毛剑琳[1] 李昊楠 张凯翔 张书凡 付丽霞[1] MAO Jian-lin;LI Hao-nan;ZHANG Kai-xiang;ZHANG Shu-fan;FU Li-xia(Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming 650500,China;Faculty of Mechanical and Electrical Engineering,Kunming University of Science and Technology,Kunming 650500,China)

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

出　　处：《控制与决策》2025年第2期488-496,共9页Control and Decision

基　　金：国家自然科学基金项目(62263017)。

摘　　要：针对多机器人路径鲁棒规划时存在节点耦合度高导致求解方案可靠性低的问题,提出耦合度矩阵概念并给出基于耦合度矩阵的安全区间多机器人路径k鲁棒规划(Ck R-SIPP)算法.首先,根据路径规划方案统计全局地图节点耦合度信息形成耦合度矩阵,在规划过程中不断更新该矩阵.其次,引入安全区间避免机器人之间发生冲突,采用带k时间扩展的A^(*)算法作为多机器人底层路径规划算法,其中k为设定的鲁棒因子,可在多机器人的时空关系中处理鲁棒规划问题.同时,以耦合度矩阵中的信息作为寻路约束反馈给带k时间扩展的A^(*)算法,尽量避免耦合度高的节点.最后,按照高优先级到低优先级的顺序,完成所有机器人的路径规划.在Benchmark地图上进行仿真测试,结果表明,所提出的Ck R-SIPP算法均优于k R-CBS以及Ik R-CBS算法,较k R-SIPP算法平均提高19.2%,可以有效提高多机器人路径k鲁棒规划系统的方案可靠性.In order to solve the problem of low success rate due to high coupling degree,the concept of a coupling degree matrix is proposed and a safe interval multi-robot path k robust planning(CkR-SIPP)algorithm based on coupling degree matrix is presented.Firstly,according to the path planning scheme,the coupling degree information of global map nodes is collected to form the coupling degree matrix,which is constantly updated during the planning process.Secondly,a safe interval is introduced to avoid conflicts between robots,and the A^(*)algorithm with k time expansion is used as the lowlevel path planning algorithm for multi-robots,where k is the set robust factor,which can deal with the robust planning problem in the spatio-temporal relationship of multi-robots.At the same time,the information in the coupling degree matrix is fed back to the A^(*)algorithm with k time extension as a routing constraint,and the nodes with high coupling degree are avoided as far as possible.Finally,the path planning of all robots is completed in the order of high priority to low priority.Simulation tests on the Benchmark map show that the proposed CkR-SIPP algorithm is superior to both the kR-CBS algorithm and the IkR-CBS algorithm,with an average improvement of 19.2%over the kR-SIPP algorithm,which can effectively improve the scheme reliability of the multi-robot path k-robust planning system.

关 键 词：多机器人 路径规划 安全区间 耦合度矩阵 鲁棒规划 

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