基于解空间裁剪度的多智能体路径规划算法  

A Multi-agents Pathfinding Algorithm Based on Solution Space Clipping Degree

作　　者：岳荣康 龙吟 YUE Rongkang;LONG Yin(School of Computer Science and Technology,Southwest University of Science and Technology,Mianyang 621000)

机构地区：[1]西南科技大学计算机科学与技术学院,绵阳621000

出　　处：《计算机与数字工程》2025年第2期389-394,共6页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号:62101467)资助。

摘　　要：基于冲突的搜索算法(Conflict Base Search,CBS)是当前多智能体路径规划的主要方法之一,并且它与互斥锁传播(Mutex Propagation,MP)方法结合还能够进一步提升搜索无冲突路径的性能。然而,基于冲突与互斥锁传播的搜索算法(CBS-MP)存在难以准确区分次要冲突和一般冲突的问题。为此,提出基于解空间裁剪程度的CBS-MP算法。该方法通过设定不同互斥锁对于解空间的裁剪程度为启发值,搜索出对于其他智能体解空间影响程度最小的路径解,然后将得到的路径解作为其他智能体的约束,搜索彼此无冲突的解。相比于现有CBS-MP算法,该方法不仅完善了对于不同碰撞类型的处理,还进一步提升路径搜索性能。实验结果表明在一般冲突和次要冲突频发的无障碍环境中该方法的性能优势较为明显。Conflict Base Search(CBS)is one of the methods of current multi-agent path planning,and it can be combined with Mutex Propagation(MP)method to improve the performance of searching for conflict-free paths.However,CBS-MP has the problem that it is difficult to accurately distinguish non-cardinal conflicts and semi-cardinal conflicts.To this end,CBS-CMP is proposed.By setting the degree of tailoring of the solution space of different mutex as the heuristic value,the method searches for the path solution with the least influence on the solution space of other agents,and then uses the obtained path solution as the con⁃straint of other agents,and searches for the path solutions without conflicts.Compared with the existing CBS-MP algorithm,this method not only improves the processing of different collision types,but also further improves the path search performance.The re⁃sults show that the performance advantage of this method is obvious in the barrier-free environment where non-cardinal conflicts fre⁃quently occur.

关 键 词：多智能体 路径规划 互斥锁传播 无障碍环境 多值决策图 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]