基于互斥锁传播的多智能体路径规划算法

基于冲突的搜索(CBS)算法可以应用于连续时间假设下的多智能体路径规划问题,但是仍存在没有相应冲突识别方法与约束生成规则的问题,从而导致算法效率低下。为此,引入并改进人工智能规划领域中的互斥锁传播技术进行路径规划。首先通过多值决策图(MDD)中的终点可达信息判断冲突的基本类型,然后讨论不同MDD的深度,将冲突划分为基数冲突或非基数冲突,最后针对不同类型的冲突直接生成对应的约束集合,使得CBS下层算法根据约束集合一次性规划出最优路径。互斥锁传播技术提供了比特殊规则更加通用的方法,不仅可以识别出离散时间下的矩形冲突、廊道冲突等特殊基数冲突,还可以针对连续时间的情景,将识别出的基数冲突进行分类并自动生成不同冲突类别对应的约束集合。实验结果表明,使用互斥锁传播的CCBS算法相较于CBS框架下的前沿算法平均成功率提升了6.2%,平均运行时间缩短了38.6%,相较于非CBS框架下的前沿算法平均成功率提升了15.3%,平均运行时间缩短了56.8%。