基于解空间裁剪度的多智能体路径规划算法
岳荣康
龙吟
西南科技大学计算机科学与技术学院 绵阳 621000
摘要：基于冲突的搜索算法(Conflict Base Search,CBS)是当前多智能体路径规划的主要方法之一,并且它与互斥锁传播(Mutex Propagation,MP)方法结合还能够进一步提升搜索无冲突路径的性能.然而,基于冲突与互斥锁传播的搜索算法(CBS-MP)存在难以准确区分次要冲突和一般冲突的问题.为此,提出基于解空间裁剪程度的CBS-MP算法.该方法通过设定不同互斥锁对于解空间的裁剪程度为启发值,搜索出对于其他智能体解空间影响程度最小的路径解,然后将得到的路径解作为其他智能体的约束,搜索彼此无冲突的解.相比于现有CBS-MP算法,该方法不仅完善了对于不同碰撞类型的处理,还进一步提升路径搜索性能.实验结果表明在一般冲突和次要冲突频发的无障碍环境中该方法的性能优势较为明显.
关键词：多智能体路径规划互斥锁传播无障碍环境多值决策图
分类号：TP391(计算技术、计算机技术)
资助基金：国家自然科学基金(62101467)
论文发表日期：2025-02-20
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 389-394 )
英文信息