Belief-Aware Multi-Agent Path Finding under Map Uncertainty

📄 arXiv: 2609.40269v1 📥 PDF

作者: Viraj Parimi, Shao-Hung Chan, Han Zhang, Jingkai Chen, Brian Williams

分类: cs.AI, cs.MA, cs.RO

发布日期: 2026-09-30

备注: Under review

💡 一句话要点

提出MAGIC框架以解决MAPF中的地图不确定性问题

🎯 匹配领域: 支柱三：空间感知与语义 (Perception & Semantics)

关键词: 多智能体路径规划 信念感知 高斯信念传播 动态环境 路径规划优化 机器人导航 空间相关性

📋 核心要点

  1. 现有MAPF方法未能有效处理环境中不可预见的障碍物，导致路径规划效率低下。
  2. 本文提出MAGIC框架，通过高斯马尔可夫随机场和高斯信念传播，在线更新可通行性信念，提升路径规划能力。
  3. 实验结果显示，MAGIC在96.3%的测试实例中降低了执行成本，适用于多达800个智能体的场景。

📝 摘要（中文）

多智能体路径规划（MAPF）旨在为多个智能体在共享环境中找到无碰撞路径。传统MAPF假设所有静态障碍物事先已知，但现实环境可能因意外情况而变化。现有方法未能利用空间相关性来推断未观察到位置的可通行性。本文提出了信念感知MAPF，利用多智能体高斯信念推断协调（MAGIC）框架，在线更新共享的可通行性信念，显著提高了路径规划的效率。实验表明，MAGIC在96.3%的实例中减少了执行成本，适用于大规模MAPF问题。

🔬 方法详解

问题定义：本文解决的是在地图不确定性下的多智能体路径规划问题。现有方法无法利用空间相关性推断未观察到位置的可通行性，导致潜在的路径重规划成本增加。

核心思路：论文提出的MAGIC框架通过在线更新共享的可通行性信念，利用智能体的观察信息来推断周围环境的状态，从而提高路径规划的准确性和效率。

技术框架：MAGIC框架包括两个主要模块：高斯马尔可夫随机场用于建模环境的可通行性，和高斯信念传播用于推断和更新信念。整体流程是通过智能体的观察数据不断更新共享信念，并生成适应性路径规划。

关键创新：MAGIC的创新在于其能够利用空间相关性推断未观察区域的可通行性，这一特性使其在处理动态环境时优于传统方法。

关键设计：在MAGIC中，关键参数包括高斯分布的协方差矩阵设置，损失函数设计用于优化信念更新过程，确保路径规划的实时性和准确性。

🖼️ 关键图片

fig_0
fig_1

📊 实验亮点

实验结果表明，MAGIC在96.3%的测试实例中成功减少了执行成本，相较于现有方法，展示了显著的性能提升，尤其是在处理多达800个智能体的复杂场景时，表现出色。

🎯 应用场景

该研究的潜在应用领域包括机器人导航、无人驾驶汽车、智能物流等。MAGIC框架能够在动态和不确定的环境中高效规划路径，具有重要的实际价值和广泛的应用前景，未来可能推动智能体协作和自主决策的进一步发展。

📄 摘要（原文）

Multi-Agent Path Finding (MAPF) aims to find collision-free paths for multiple agents in a shared environment. Classical MAPF assumes that all static obstacles are known in advance, but real-world environments can change unexpectedly due to fallen objects, spills, or other local disturbances. When such changes are spatially correlated, an observation can inform traversability estimates beyond the observed location. Prior approaches address uncertainty in traversability through contingent plans or replanning based on direct observations, but do not leverage this spatial dependence to infer the traversability of nearby unobserved locations. As a result, they cannot use one observation to anticipate nearby unobserved obstacles that may cause costly rerouting later. We focus on Belief-Aware MAPF, where map discrepancies are fixed during execution but initially unknown, and observations can be informative beyond the observed location. We propose Multi-Agent Gaussian belief Inference for Coordination (MAGIC), a framework that updates a shared belief about traversability online based on agents' observations. MAGIC uses a Gaussian Markov Random Field and Gaussian Belief Propagation to approximately infer traversability and construct detour-aware costs for standard MAPF planners. Our experiments on MAPF benchmarks show that MAGIC reduces the executed sum of costs compared to existing approaches on 96.3% of instances, across several planner families and teams of up to 800 agents, demonstrating its applicability to large-scale MAPF problems.