多智能体路径规划（multi-agent path finding，MAPF）是为多个智能体规划路径的问题，关键约束是多个智能体同时沿着规划路径行进而不会发生冲突。
对不同起始位置的多个智能体到他们各自目标位置的路径规划问题，关键约束是在保证智能体之间互相不碰撞的前提下到达目标位置，并保证路径规划的速度和质量。
传统MAPF挑战：环境的动态变化和智能体的数量增加，基于搜索的MAPF算法通过引入优先规划、大领域搜索和复杂的启发式函数来优化改进算法的性能；而基于强化学习的MAPF算法在解决动态和变化环境的MAPF表现出巨大的潜力。
按照规划方式不同：MAPF算法分为集中式规划算法和分布式规划算法。
集中式规划算法是最经典和最常用的MAPF算法，主要分为：基于A*搜索、基于冲突搜索、基于代价增长树和基于规约四种算法；
分布式执行算法分为专家演讲型，改进通信型和任务分解型三种算法
集中式规划
集中式规划方法由一个中央控制器来为所有智能体规划路径，它的前提假设是中央规划器掌握了所有智能体的起始位置、目标位置和障碍物位置等信息。集中式规划算法是最经典和常用的MAPF 算法，在求解的速度和质量上都达到较好的效果。
分布式执行算法
分布式执行算法主要是基于强化学习的算法，前提假设是每个智能体只掌握了视野内（一定范围内）智能体和障碍物的位置等信息，智能体根据当前策略不断和环境进行交互，获取环境下一到达状态和该动作奖励，计算并更新策略，目标是最大化累积奖励，最后找到一个最大化累积奖励的动作序列，完成多智能体路径规划任务。这类算法可以扩展到高密度和动态的部分可观察的环境中，高效解决现实世界中的多智能体路径实时再规划问题。
当前研究
MAPF 的研究主要有两大方向，一是如何改进现有的算法，二是在实际应用中如何处理约束。在实际应用场景中要考虑机器的速度、加速度、转角，以及各种干扰的约束，而多智能体路径规划将这些设定进行抽象化，将运动控制离散为时间步，将研究的重点集中在求解速度和质量上。
经典 MAPF 问题
问题描述
K个智能体的经典MAPF问题定义为一个元组
其中
是一个无向图, 无向图中的节点,
是智能体可以占据的位置，边
表示智能体从节点
移动到
的连线，
代表智能体的数量
,
是初始位置的集合，每个智能体都有一个初始位置
,
是目标位置的集合，每个智能体都有一个目标位置
.
在经典MAPF 问题中，时间被离散为时间步长。在每个时间步长中，每个智能体可以执行一个动作，一般有五种类型的动作：向上、向下、向左、向右和等待。
一个单智能体的路径规划是从起始位置到目标位置一系列动作的集合
k 个智能体的路径规划问题就是 k 条路径的集合
, 其中第
个智能体对应路径
。
输入输出：
输入: 地图+机器人起始位置+机器人目标位置)
输出: 全局路径(多个带时间步的单机规划路径)
假设：
时间离散化为时间步
一个时间步机器人执行一个动作
一个时间步内，机器人占据一个顶点
冲突定义：
需要根据具体问题场景清楚定义出冲突种类和边界
a. 边冲突
b. 顶点冲突
c. 跟随冲突
d. 循环冲突
e. 对向冲突
目标函数：
用来评估 MAPF 解决方案最常见的三个目标函数是：
: 表示最晚到达目标位置的智能体所花费的时间
: 表示所有agents到达目标位置花费的总时间3
: 表示所有智能体到达目标位置的路径长度总和
机器人在终点的状态：
在终点消失(disappear at target)
此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为空白(clear)状态，之后，其他机器人的路径可以经过这个点
在终点保持(stay at target)
此状态下，一旦该机器人到达目标点，该目标点在算法中会设置为障碍物(obstacle)状态，变成障碍物，之后，其他机器人的路径不能经过这个点
主流技术范式
范式类别 核心思想 优点 挑战/适用场景
基于优化/搜索的集中式规划 将多智能体系统视为一个整体，在全局空间内搜索无碰撞的联合路径1。 解的质量高（可最优）；理论上完备。 可扩展性差：状态空间随智能体数量指数级增长4；对动态环境适应性弱。
基于协调的分布式规划 对智能体进行时空解耦，通过协调机制（如优先级、规则）实现避碰1。 计算效率高，可扩展性强；易于实现。 难以保证全局最优；需精心设计协调机制以避免死锁1。
基于学习的规划 智能体通过与动态环境及其他智能体交互，学习出协同策略，典型代表为多智能体强化学习4 8。 适应性强，能处理高动态、不确定环境；具备在线反应能力。 样本效率低、训练难；可解释性弱；仿真到现实的迁移是巨大挑战4。
博弈与控制的融合规划 用微分博弈建模智能体间的交互，结合控制理论进行求解，是近年来的重要趋势 5。 为合作、竞争、混合动机等复杂交互提供了严格的数学框架；能分析系统均衡与稳定性5。 求解复杂，对大规模系统计算负担重；通常需结合学习方法（如RL）求解5。
