多智能体中央式协同路径规划算法综述

Overview of multi-agent central collaborative path planning

协同路径规划是实现多智能体协同作业的一项关键技术,需要保证行进至目标点前智能体间无碰撞,同时满足规划轨迹平滑性、规划时间有效性等要求。在明确多智能体协同规划问题的基础上,根据算法原理,将中央式协同路径规划算法分为基于A~*搜索、基于冲突搜索、基于安全间隔路径、基于代价增长树、基于规约算法以及其他算法,简单阐述各算法原理。研究发现,基于冲突搜索的协同路径规划算法因其计算质量及速度优势成为当前的主流算法,以此为基础进行改进成为当前研究热点。单一类型的算法对不同智能体规模及场景下的适应能力有限,多类型算法融合及智能化方法的介入将成为未来多智能体协同规划的发展趋势。

Collaborative path planning is a key technology for achieving multi-agent collaborative work, which requires that there is no collision between agents before moving to the target, while also meeting the requirements of planning trajectory smoothness and planning time effectiveness. On the basis of the problem of multi-agent collaborative planning, the central collaborative path planning algorithms were divided into A*-based search, conflict-based search, safe interval path planning, increasing cost tree search, protocol-based and other algorithms, and then the principles of each algorithm were explained briefly. It was found that conflict-search-based collaborative path planning algorithms became the mainstream algorithm due to their advantages in computational quality and speed, and improving them became a current research hotspot. The adaptability of single-type algorithm to different agent scales and scene was limited. The integration of multiple types of algorithms and the intervention of intelligent methods would become the development trend of multi-agent collaborative planning in the future.