多智能体路径规划技术研究综述

针对多智能体路径规划(multi-agent path finding, MAPF)问题研究的算法在智能仓储物流、户外危险场地和城市道路网络等领域有着广泛的应用。根据不同的求解思路,关于 MAPF 问题研究设计的算法主要可以分为基于搜索的传统算法和基于学习的智能算法 2 类。在基于搜索的传统算法研究中,按照路径规划效果不同,又可分为最优 MAPF 算法和次优 MAPF 算法。最优 MAPF 算法主要分为基于 A*的搜索、基于代价增长树的搜索 (increasing cost tree search, ICTS)和基于冲突的搜索(conflict based search, CBS)这 3 类;次优 MAPF 算法主要分为无边界次优的算法和有边界次优的算法 2 类。基于学习的智能 MAPF 算法可以大致分为结合专家经验的算法和基于图神经网络(graph neural network, GNN)的算法 2 类。根据上述分类介绍了近年来具有代表性的研究成果,分析了各种算法的特点,并对 MAPF 问题未来的研究方向进行了展望。

多智能体路径规划( multi-agent path finding, MAPF)是指在不发生碰撞的前提下对不同起始位置的多个智能体规划到达各自目标位置的路径,同时保证一定的路径质量[1] 。针对该问题的研究在户外危险场地[2-3] 、智能仓储系统[4] 、城市道路网络[5] 、电子游戏[6]和航空航天[7] 等领域有着广泛的应用前景。特别是在物流运输领域,随着电子技术和控制理论的快速发展, 自动导引车 ( automated guided vehicle,AGV)作为一种高度智能化的移动机器人,以较高的可靠性和独特的安全性在实际生活中得到了广泛的发展和应用,将逐渐替代传统的人工运输,进而实现运输的智能化。在部署了大量 AGV 的场景中,高效的 MAPF 算法对于智能体协同完成任务至关重要。因此,该领域的研究得到了学术界和业界的广泛关注。近年来,针对 MAPF 问题的研究取得了众多极具价值的进展。传统的基于搜索的 MAPF 算法通常为集中式路径规划算法,采用在联合状态空间中搜索有效路径的方法,因而计算复杂度较高,需要消耗大量的计算资源,适用于场景地图信息已知且智能体数量较少的场景,在静态环境下有着良好的表现。随着完成任务所需的智能体数量的增加、应用场景规模的扩大以及环境中存在障碍物的动态变化, MAPF 问题变得更加复杂。研究人员进一步引入了优先级规划和重规划来提升 MAPF 算法的有效性和运行效率。近年来,在人工智能以及机器学习算法发展的推动下,基于学习的 MAPF 算法逐渐成为了研究趋势,其在环境信息部分可感知的大规模动态环境的情况下展示出良好的性能与潜力。虽然国内外针对 MAPF 问题的研究已经逐渐成熟,但是对该问题及其派生问题的综述文献较少[8-11] 。最新的相关综述文献只给出了经典 MAPF 问题的定义和静态环境下的小规模问题中传统 MAPF 算法的简单分类,没有涉及最新的基于学习的 MAPF 技术研究。因此,本文对 MAPF 问题的研究发展进程进行了详细的调研,从传统的基于搜索的 MAPF 算法和新兴的基于学习的智能 MAPF 算法 2 个分支对相关研究工作进行了全面的归纳总结, 以便于相关研究人员对 MAPF 问题建立清晰的认识,进而开拓新的发展方向。 MAPF 算法可分为基于搜索的 MAPF 算法和基于学习的 MAPF 算法。基于搜索的传统算法按照路径规划效果不同,又可分为最优 MAPF 算法和次优 MAPF 算法。最优 MAPF 算法主要分为基于 A*的搜索、基于代价增长树的搜索( increasing cost tree search, ICTS ) 和基于冲突的搜索 ( conflict鄄based search, CBS)这3 类算法;次优 MAPF 算法主要分为无边界次优算法和有边界次优算法 2 类。基于学习的智能 MAPF 算法可以大致分为结合专家经验的算法和基于图神经网络( graph neural network, GNN) 的算法 2 类,其中结合专家经验的智能算法又可分为结合多智能体经验和单智能体经验 2 种。本文首先介绍了经典的 MAPF 问题及相关概念,给出了问题定义和问题性质。其次,介绍了传统的基于搜索的 MAPF 算法,主要从求解结果的最优性、次优性进行分类,阐述了相关算法的基本思想。然后,介绍了基于学习的智能 MAPF 算法,按照结合专家经验的算法和基于 GNN 的算法分别进行阐述, 并且对算法设计的独特之处进行提取。在归纳整理现有研究的基础上,总结了现有场景中针对 MAPF 问题所面临的实际挑战,并对未来的研究方向进行了展望。

成为VIP会员查看完整内容