机器学习驱动的多智能体路径搜寻算法综述

作者：王祥丰; 李文浩

来源：运筹学学报, 2023, 27(04): 106-135.

DOI：10.15960/j.cnki.issn.1007-6093.2023.04.006

• 机器学习
• 多智能体路径搜寻
• 多智能体强化学习

多智能体路径搜寻(Multi-agent Path Finding,MAPF)问题是多智能体系统中的核心基本问题,被广泛应用于自动化智能仓储、自动驾驶、群体机器人等实际场景。从问题属性来看,其关键难点在于多个智能体能够同时沿着路径行驶,同时保证不发生碰撞,属于NP-难组合优化问题。然而,上述现实世界应用需要算法能够在较短的计算时间内为大量智能体搜索高质量的无碰撞路径,更短的路径将导致更高的系统吞吐量以及更低的操作成本,给经典MAPF运筹算法带来了极大挑战。因此,近年来大量工作开始聚焦于使用机器学习方法赋能多智能体路径搜寻问题的研究,以期加快求解速度、提升求解质量。本文综述内容包括三部分,包括MAPF问题的核心概念、优化目标、基准任务,经典MAPF算法的问题建模、核心思想、算法优劣,并从机器学习赋能程度从低到高分别介绍一系列机器学习赋能的MAPF算法,并给出具体的示意图和伪代码。本文还总结了机器学习驱动的多智能体路径搜寻算法目前面临的主要挑战,并提出未来潜在研究方向,以期可帮助领域内的研究者,并促进机器学习方法在经典多智能体路径搜寻领域的发展。

• 单位
  香港中文大学（深圳）; 华东师范大学