计算机工程

作者：刘庆周, 吴锋

单位：中国科学技术大学 计算机科学与技术学院, 合肥 230027

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

基金：国家自然科学基金青年基金"基于决策理论的半自主智能体决策规划模型和算法研究"（61603368）。

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

来源：2020年第4期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第4期