Belief-Aware Multi-Agent Path Finding under Map Uncertainty
This arXiv preprint describes MAGIC, a framework that adds online spatial belief inference to multi-agent path finding under unknown map obstacles. On standard MAPF benchmarks it reduces executed sum of costs on 96.3% of instances and scales to 800 agents. The work is relevant for warehouse robot fleets that must route around fallen pallets, spills, or other local map discrepancies without building expensive contingent plans.
The authors ask whether local observations with spatial correlation can be used to infer the traversability of unobserved locations and thereby improve executed cost and success rates in one-shot multi-agent path finding under initially unknown fixed obstacles.
Warehouse and shared-space maps can be wrong at execution time because of fallen objects, spills, or blocked aisles; these discrepancies are often spatially correlated, so one observation should inform nearby unobserved locations. Existing MAPF systems either assume a known static map or replan only on direct observations, so they cannot use that spatial evidence to anticipate costly reroutes.
MAPF-OU builds contingent plans that branch on future observations, but cost grows with uncertainty. MAPF-IM interleaves planning and execution and replans when uncertain spots are directly observed. Optimistic replanning treats unresolved locations as traversable until observed blocked. None of these families propagates an observation to update beliefs about nearby unobserved locations.
MAGIC maintains a shared belief over uncertain traversability with a Gaussian Markov Random Field and Bernoulli probit likelihood. Local noiseless observations are batched and processed by Gaussian Belief Propagation, clamping observed locations to positive or negative latent scores; marginal means and variances are converted to closed-form traversability estimates. Each uncertain edge's cost is a blend of unit traversal and the shortest edge-bypass distance, weighted by the edge traversability estimate. The weighted graph is handed to off-the-shelf MAPF planners such as CBS, EECBS, PBS, PIBT, PIBT+, and LaCAM, and replanning occurs after every new observation with detour caching.
On small-tier benchmarks at an uncertain fraction of 0.30, MAGIC is 3.6% above the full-information optimum, versus 9.4% for optimistic replanning and 14.9% for MAPF-IM. At a blockage rate of 0.30, MAGIC is 2.7% above the optimum, versus 6.7% optimistic and 12.4% MAPF-IM. In the cross-planner study, all 15 MAGIC configurations achieve mean executed-SoC ratios below 1 relative to optimistic replanning: e.g., CBS 0.966±0.004, small-tier PBS 0.963±0.006, medium-tier LaCAM 0.986±0.004, large-tier PIBT+ 0.991±0.003, and huge-tier PIBT+ 0.995±0.001. MAGIC's success rate is sometimes lower because of extra inference and replanning: large-tier PBS 74% for MAGIC versus 95% for optimistic, while huge-tier PIBT+ remains at 100% for both. Aligned spatial priors reduce executed SoC by 3.40% compared with reversed priors and raise success from 88.5% to 90.9%.
The paper is a preprint and has not been peer-reviewed. MAGIC adds computational overhead from GaBP inference and belief-dependent replanning, and in some configurations this lowers success rates compared with optimistic replanning. The evaluation is limited to one-shot tasks with fixed start and goal positions; the authors do not address lifelong or dynamic environments. The real-robot demonstration uses only two TurtleBots and reports qualitative behavior, not quantitative metrics. Variances from GaBP are approximate on cyclic graphs, and the GMRF prior parameters are fixed rather than learned.
Warehouse automation vendors such as Symbotic or other AMR fleet operators can use this to route around unexpected map discrepancies. Near-term adoption is likely 1–3 years: implementation depends on integrating GaBP inference and detour-cost computation with existing centralized MAPF planners, reducing computational overhead, and validating in real facilities before deployment.
The full text is not republished here because the paper's license does not allow it. Read the original on arXiv.