本文是关于AGV调度与路径规划问题中的MAPF问题，包括MAPF问题背景、描述、类型与冲突类型、求解算法类型等内容。
01 MAPF问题的背景
传统的车辆路径规划问题（Vehicle Routing Problem, VRP）是物流领域最常见的一类路径规划问题，要求在满足一定条件下为多个车辆设计路径，以最低成本完成任务，比如配送货物到多个客户点。VRP的复杂性主要源于全局任务分配、调度优化以及资源限制，是一类经典的组合优化问题，通常采用全局优化算法，如遗传算法、禁忌搜索、模拟退火、混合启发式等，寻找一个满足所有约束条件的最优解或近似最优解。
然而，随着物流自动化和智能机器人技术的不断发展，特别是无人驾驶车辆（AGV, Automated Guided Vehicle）的广泛应用，路径规划的挑战不再仅仅是全局任务的优化，而是如何在复杂、动态的环境中协调多个自主智能体的行动。这意味着，不仅要考虑车辆的最优路径，还要确保多个智能体在同一空间内移动时不会发生冲突，实时协作成为了新的难题。
正是在这样的背景下，一类更微观的路径规划问题走入我们的生活中：多智能体路径规划问题（Multi-Agent Path Finding, MAPF）。多智能体路径规划（MAPF）是一个在共享环境中为多个智能体规划无碰撞路径的问题，近年来，MAPF的研究蓬勃发展，其应用包括自动化仓库和自动驾驶车辆。智能体在共享空间中移动，每一个时间点、每一条路径都有可能与其他智能体或是静态障碍物产生碰撞，因此MAPF更多的是一类实时协调问题，关键约束是多个智能体同时沿着规划路径行进而不会发生冲突，其复杂性来自于时空维度的智能体协作，特别是在大规模智能体环境下，如何在有限的空间和时间内为每个智能体设计无冲突的路径，是其主要的难点。
02 MAPF问题的描述
具有k个智能体的经典MAPF问题的描述是：
定义一个元组 (G,s,t )。其中 G=(V,E) 是一个无向图，无向图中的节点 v ∈V 是智能体可以占据的位置，边 (n,n’) ∈ E 表示智能体从节点 n 移动到 n’ 的连线。s 是初始位置的集合，每个智能体都有一个起始位置 si ∈ s；t 是目标位置的集合，每个智能体都有一个目标位置 ti ∈ t 。假设时间和空间都被离散化为固定的步长和网格，同时假设智能体的动作也是离散的。在每个时间步长中，每个智能体位于图节点之一并可以执行一个动作，一般有五种类型的动作：向上、向下、向左、向右和等待，其中移动动作只能从当前节点 v 移动到图中的相邻节点 v’ （ ( v, v’ ) ∈ E），移动时不考虑智能体的运动速度以及体力消耗等影响因素。定义动作为函数 a : V → V，即 a(v)=v’ 表示如果智能体位于顶点 v 并执行动作 a，那么它将在下一个时间步中位于顶点 v’ 。一个单智能体的路径规划是从起始位置到目标位置一系列动作的集合 π= (a1, a2, ... , an )，k 个智能体的路径规划问题就是 k 条路径的集合 Π={π1,π2, ... ,πk}，其中第 i 个智能体对应路径πi。
03 MAPF的冲突类型
当且仅当任何两个单智能体的路径规划之间不存在冲突时，MAPF的求解方案才称为有效。经典MAPF问题中常见的冲突类型有：
边冲突：πi 和 πj 之间发生边冲突，当且仅当智能体i和智能体j在相同时间步沿相同方向遍历相同的边。
顶点冲突：πi 和 πj 之间发生顶点冲突，当且仅当智能体i和智能体j在同一时间步占据同一顶点。
跟随冲突：如果一个智能体计划占据前一个时间步中另一个智能体占据的顶点，则 πi 和 πj 之间会发生跟随冲突。
循环冲突：一组单智能体路径 πi,πi+1, ... ,πj 之间发生循环冲突，当且仅当每个智能体移动到前一个时间步中被另一个智能体占据的顶点并形成“旋转循环”模式。
交换冲突：πi 和 πj 之间发生交换冲突，当且仅当智能体i和智能体j在单个时间步内交换位置。
图 1：常见冲突类型的说明。从左到右：边冲突、顶点冲突、跟随冲突、循环冲突、交换冲突。
04 MAPF的类型
在经典MAPF问题中，每个智能体根据分配的任务已知起点和目标终点。按照任务分配的不同，经典MAPF问题可以拓展为以下三类：
匿名MAPF：在此MAPF变体中，目标是将智能体移动到一组目标顶点，但哪个智能体到达哪个目标并不重要，即其中每个智能体都可以分配给任何目标，但它必须满足智能体和目标之间一对一映射的关系。类似于滴滴打车场景。
分组MAPF：在此MAPF变体中，智能体被分组为团队，每个团队都有一组目标顶点，需要将每个团队中的智能体移动到他们的目标顶点，其中每个智能体只能从为其团队指定的目标顶点集中分配到目标。类似于外卖分区域性派单场景。
动态MAPF：在此MAPF变体中，智能体在到达目标顶点时接收新任务，并且随着时间的推移图中可以出现新的智能体，所有智能体会不断接收新的任务并持续行动，规划不仅仅是针对单次任务，而是终生优化。
05 MAPF求解算法的类型
按照规划方式不同，MAPF算法分为集中式规划算法和分布式规划算法。集中式规划算法需要获悉所有智能体的起始位置、目标位置以及障碍物位置等信息，在集中调度中，地图信息由与每台智能体通信的中央服务器存储，中央服务器掌握所有智能体的状态与路径信息，负责将任务分配给各台智能体、下达任务指令并为每台智能体规划无碰撞的最优路径。集中式规划算法可以分为基于A*搜索、基于冲突搜索（Conflict Based Search, CBS）、基于代价增长树和基于规约四类，其在求解过程中更注重解的质量。后续我们将会为大家详细介绍基于A*搜索和基于冲突搜索的两种多智能体路径规划算法。
分布式规划算法是人工智能领域兴起的基于强化学习的MAPF算法，其采用去中心化的思想，在智能体与环境交互过程中，每台智能体均可以与一定范围内的其他智能体通信，前提假设每台智能体只掌握了视野内智能体和障碍物的位置等信息，智能体根据当前策略不断和环境进行交互，获取环境下一个时刻的状态并更新其动作策略。分布式规划算法按照改进技术不同可以分为专家演示型、改进通信型和任务分解型三类，其适用于高密度和动态的部分可观察的环境，能高效解决实时再规划的问题。
参考文献
[1] R. Stern et al., “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks,” SOCS, vol. 10, no. 1, pp. 151–158, Sep. 2021, doi: 10.1609/socs.v10i1.18510.
作者 | 杨颖
本文转载自久章智能微信公众号（原文发布于 2024-10-20），内容保持原貌。扫码关注公众号「久章智能」，第一时间获取智能决策系列文章。阅读原文 ↗