计算机工程 ›› 2020, Vol. 46 ›› Issue (4): 1-10.doi: 10.19678/j.issn.1000-3428.0056738

• 热点与综述 • 上一篇    下一篇

多智能体路径规划研究进展

刘庆周, 吴锋   

  1. 中国科学技术大学 计算机科学与技术学院, 合肥 230027
  • 收稿日期:2019-11-28 修回日期:2020-02-05 出版日期:2020-04-15 发布日期:2020-02-07
  • 作者简介:刘庆周(1994-),男,硕士研究生,主研方向为多智能体路径规划;吴锋,副教授。
  • 基金项目:
    国家自然科学基金青年基金"基于决策理论的半自主智能体决策规划模型和算法研究"(61603368)。

Research Progress of Multi-Agent Path Planning

LIU Qingzhou, WU Feng   

  1. School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China
  • Received:2019-11-28 Revised:2020-02-05 Online:2020-04-15 Published:2020-02-07

摘要: 多智能体路径规划是一类寻找多个智能体从起始位置到目标位置且无冲突的最优路径集合的问题,针对该问题的研究在物流、军事和安防等领域有着大量的应用场景。对国内外关于多智能体路径规划问题的研究进展进行系统整理和分类,按照结果最优性的不同,多智能体路径规划算法被分为最优算法和近似算法2类。最优的多智能体路径规划算法主要分为基于A*搜索、基于代价增长树、基于冲突搜索和基于规约的4种算法。近似的多智能体路径规划算法主要分为无边界次优的算法和有边界次优的算法2类。基于上述分类,分析各种算法的特点,介绍近年来具有代表性的研究成果,并对多智能体路径规划问题未来的研究方向进行展望。

关键词: 多智能体路径规划, 人工智能, 搜索, 最优路径集合, 多机器人

Abstract: Multi-Agent Path Planning(MAPP) is the problem of finding an optimal path set for multiple agents from their starting position to the target position without any collisions.Research on this problem has abundant application scenarios in the fields of logistics,military and security.This paper systematically sorts out and classifies the recent research progress in MAPP both at home and abroad.According to the differences in the optimality of results,the MAPP algorithms are classified into optimal group and approximate group.The optimal MAPP algorithms are mainly divided into four categories,which are based on A* search,cost growth tree,conflict based search and protocol respectively.The approximate MAPP algorithms are mainly divided into two categories:the unbounded suboptimal algorithm and the bounded suboptimal algorithm.Based on the classification mentioned above,this paper analyzes the characteristics of each algorithm,introduces the representative researches in recent years and discusses the future research directions of MAPP problem.

Key words: Multi-Agent Path Planning(MAPP), artificial intelligence, search, optimal path set, multi-robot

中图分类号: