基于改进CBS算法的多智能体路径规划

Multi-agent path planning based on improved CBS algorithm

在基于冲突的搜索(conflict-based search,CBS)算法中,冲突的选择具有随机性,导致CBS算法在多智能体路径规划方面的求解效率不佳。为此,本文提出一种改进CBS算法的多智能体路径规划算法。首先,基于冲突子节点的相关信息,提出了一种新的冲突选择策略;然后,为发挥新策略的优势和进一步减少算法的运行时间,采用基于神经网络的RankNet算法来学习新策略,从而得到一个训练好的排序模型;最后,利用训练好的排序模型为CBS算法选择冲突。通过设计实验对改进CBS算法进行仿真验证,结果表明,所提改进算法相比于已有的改进算法,能够有效提高算法的求解效率。

In the conflict-based search(CBS)algorithm,random conflict selection leads to poor solution efficiency in multi-agent path planning.Therefore,an improved CBS-based multi-agent path-planning algorithm is proposed in this paper.First,a new conflict selection strategy is introduced according to the information related to the child nodes associated with the conflict.Next,the RankNet algorithm based on a neural network is used to learn the new strategy and further reduce the running time of the algorithm,obtaining a trained ranking model.Finally,this well-trained ranking model is utilized to select conflicts for the CBS algorithm.Simulation verification of the improved CBS algorithm was performed by designing experiments.Results show that the proposed CBS algorithm effectively enhances the efficiency of the algorithm compared with the existing improved algorithm.