多智能体路径规划的可扩展机制设计
内容提要
多智能体路径规划（MAPF）研究涵盖多个方向：SocialMAPF引入机制设计，兼顾个体私人激励与全局目标；MAPF-DP提出两层搜索与鲁棒执行策略；部分研究结合启发式搜索与强化学习，提升吞吐量和泛化能力；另有工作提供统一术语与基准、分析时间最优复杂性、用答案集编程处理多模态转型，并探讨现实应用挑战。
延伸解读
机制设计如何融入MAPF
SocialMAPF将机制设计引入多智能体路径规划，旨在协调个体私人激励与全局系统目标。传统MAPF通常假设智能体完全合作，而SocialMAPF允许智能体考虑自身私人效用，通过机制设计提升整体效用。实验表明，该方法比传统方法更高效，且可应用于静态环境。这为MAPF研究开辟了兼顾个体理性与集体效率的新方向。
不完美执行下的鲁棒规划
MAPF-DP针对执行不完美的问题，提出两层搜索框架和鲁棒执行策略。两层搜索分别处理规划与执行，期望值最小化近似求解器能生成有效计划。鲁棒执行策略控制每个代理的行动，以应对执行偏差。该工作强调在实际部署中，规划需考虑执行不确定性，而非假设完美执行。
启发式搜索与强化学习的结合
一项研究集成启发式搜索与强化学习，解决分布式多智能体路径规划问题。该方法在吞吐量和泛化能力上表现优越，且比基于规则和基于搜索的方法快一个数量级。这表明混合方法能兼顾搜索的精确性与学习的适应性，为复杂场景提供可扩展方案。
现实应用与评估基准
MAPF技术已应用于自动仓库、火车调度和非完整机器人导航等领域。然而，现实场景存在通用性问题，研究强调不应仅追求更快的标准求解器。同时，社区推出统一术语、新基准和可视化工具，以降低新研究者门槛，促进大规模比较，清晰衡量进展与挑战。
Q&A
SocialMAPF 是什么？它如何考虑智能体的私人激励？
SocialMAPF 是一种路径规划算法，适用于考虑代理人个体私人激励因素的约束环境。它使用机制设计来提高个体的私人效用和全局系统目标，使机器人能在考虑自身私人激励的情况下达到更高的整体效用。
MAPF-DP 解决方案的核心组成部分是什么？
MAPF-DP 解决方案基于两层搜索，包括规划具有不完美执行计划的有效 MAPF-DP 解决方案，提出具有鲁棒性的计划执行策略以控制每个代理的行动，并展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器（称为期望值最小化近似）。
有哪些方法可以提升多智能体路径规划的吞吐量和泛化能力？
通过集成启发式搜索和强化学习方法，提出了一种解决复杂问题的方法。该方法在广泛的设置中得到了验证，在吞吐量和泛化能力上表现优越，同时比现有的基于规则和基于搜索的解决方法快一个数量级。
多智能体路径规划在现实世界中有哪些应用？
多智能体路径规划是解决自动仓库实现、火车调度和非完整机器人导航等多个应用领域重要方面的关键技术。
MAPF 社区有哪些统一的术语和基准？
有研究提供了统一的术语来描述常见的 MAPF 假设和目标，并指向两个 MAPF 基准，还介绍了一个新的基于网格的 MAPF 基准，并试验性地证明它对当代 MAPF 算法提出了挑战。
时间最优多智能体路径规划在二维网格中的复杂性有什么新发现？
通过对二维网格中时间最优多智能体路径规划的细粒度复杂性分析，揭示了新的可解性界限，并在只有两个方向时，提出了找到最优解的有效算法，从而帮助指导算法设计。
如何用答案集编程处理多模态转型的多智能体路径规划？
有研究介绍了一种基于答案集编程的方法，用于解决涉及多模态转型模式的多智能体路径规划问题（mMAPF），并生成可解释性的解决方案、观察结果、最优路径以及不存在解决方案的查询。
