Classical Multi-Agent Path Finding (MAPF) computes collision-free paths for multiple agents in a shared environment while assuming that static obstacles are known accurately in advance. In real deployments, a fallen object, a closed passage, or a spill can make locations inaccessible and invalidate a plan. This paper considers map discrepancies that are unknown before execution but fixed once execution begins, with agents discovering them through local observations. The setting is especially concerned with spatially correlated uncertainty, where observing one location changes the estimated traversability of nearby locations that have not yet been observed. The objective is therefore not only to resolve conflicts among agents, but also to select routes that account for uncertain future availability.
Prior approaches to uncertain MAPF either construct contingent plans branching on future observations or interleave execution with replanning after direct observations. The paper argues that these approaches do not use spatial dependence to infer the state of nearby unobserved locations, so they may discover a hidden obstacle only after an expensive rerouting decision becomes necessary. It introduces Multi-Agent Gaussian belief Inference for Coordination, or MAGIC, as a framework for maintaining and sharing a spatial belief over traversability during execution. MAGIC represents correlations with a Gaussian Markov Random Field and approximately updates the belief with Gaussian Belief Propagation. It then exposes uncertainty to existing MAPF planners through traversal costs that account for the likely consequences of using a location and needing an alternative route. Thus, the claimed novelty is an integration of spatial probabilistic inference with scalable MAPF planning and explicit collision resolution rather than a replacement for every underlying planner.
MAGIC repeatedly solves a deterministic, weighted MAPF problem using the observations collected so far instead of directly optimizing the full decision problem over hidden states and future observation histories. First, it infers a shared posterior belief about the traversability of locations that remain unobserved. The Gaussian Markov Random Field uses a prior-anchoring term and a penalty on differences between adjacent latent scores, thereby encoding spatial correlation. Gaussian Belief Propagation approximately propagates the effect of new agent observations through that field. The resulting beliefs are translated into detour-aware traversal costs, so a route through an uncertain location can be weighed against the cost of recovering if that location is blocked. Agents execute the current plan until new observations trigger another belief update and planning update. Under the stated observation model, adjacent uncertain destinations are observed before entry and observations are noiseless; consequently, a sound planner produces actions that are valid in the realized environment.
The evaluation uses standard MAPF benchmark maps covering open, random, maze, room, warehouse, game, and city layouts. Four scale tiers range from small teams to teams of up to 800 agents. The study evaluates several planner families, including CBS, EECBS, PBS, PIBT, PIBT+, and LaCAM, and compares against MAPF-IM adapted to location-based uncertainty. The reported metrics are executed sum of costs and success rate, with additional analysis of scale, uncertainty, and sensitivity to the prior spatial information. The abstract states that MAGIC reduces executed sum of costs compared with existing approaches on 96.3% of instances. The supplied excerpt omits some numerical values, including parts of the parameter ranges, time limits, and detailed method-by-method results, so those facts cannot be established from the evidence provided. A two-TurtleBot demonstration in a fixed indoor environment gives a qualitative physical example of belief-driven route change.
The reported results support the idea that spatially informative observations can allow agents to anticipate nearby hidden obstacles rather than waiting for direct observation and then rerouting. The benefit is reported across multiple planner families and scales, including teams as large as 800 agents, suggesting that the weighted-graph interface can preserve compatibility with different MAPF back ends. However, MAGIC is an approximation: it does not directly optimize the full contingent problem over hidden states and future observation histories, but repeatedly replans a deterministic MAPF instance. Its performance depends on the quality of the prior, because assigning a low prior traversability probability to a useful passage can make that passage artificially expensive. The study is restricted to one-shot MAPF with fixed starts and goals and discrepancies that do not change during execution. The authors identify lifelong tasks and environments whose traversability changes during execution as future work. The excerpt does not establish how the method behaves under noisy observations, badly misspecified priors, dynamic obstacles, or guarantees of global optimality.
MAPF is commonly modeled on an undirected graph whose vertices are locations and whose edges are allowed moves. Each agent has a start and a goal, time is discretized, and agents may wait or move to adjacent locations while avoiding vertex and edge conflicts. MAPF under obstacle uncertainty, referred to in the excerpt as MAPF-OU, constructs contingent plans that branch on future observations, but its computational cost grows as uncertainty grows. MAPF with imperfect maps, or MAPF-IM, interleaves planning and execution and replans when uncertain parts are directly observed, but neither approach uses spatial dependence to infer unobserved traversability. Guidance graphs and related weighted-graph methods provide a practical way to influence routes generated by existing planners, although their weights ordinarily shape traffic rather than represent environmental uncertainty. Other related directions include the Canadian Traveller Problem, macro-actions combining movement and sensing, sparse probabilistic roadmaps, partially observable online planning, and single-agent belief updates over spatially correlated blockage states. The paper positions scalable use of such spatial beliefs together with explicit multi-agent conflict resolution as less explored.
A classical MAPF instance consists of an undirected environment graph and a set of agents with fixed starts and goals. The true traversable graph is determined by a realization of initially unknown location states, while the planner has a distribution over possible realizations. A joint plan must avoid vertex and edge conflicts in addition to coping with the possibility that a planned location is blocked. The paper restricts attention to one-shot MAPF, fixed start and goal positions, initially unknown location states, and environments that remain fixed during execution. Its central problem is how to use local observations and spatial dependence to make better route choices before all relevant locations have been directly observed.
The Gaussian Markov Random Field couples neighboring latent traversability scores, so an observation can change posterior probabilities at unobserved nearby locations. Gaussian Belief Propagation provides an approximate online inference mechanism rather than enumerating every hidden map and observation history. MAGIC turns beliefs into traversal costs that reflect both the chance that a transition remains available and the cost of taking an alternative route after failure. The resulting weighted graph is supplied to a standard MAPF planner, preserving the planner's role in resolving multi-agent conflicts. The stated local, noiseless observation model ensures that an uncertain destination is checked before an agent enters it.
Hidden obstacles are generated with spatial structure around sampled uncertainty centers on benchmark maps. The excerpt says that small-tier experiments use five maps, 25 benchmark scenarios per map, and three independently sampled realizations per scenario, for 375 instances. Medium, large, and huge settings use 25 scenarios per map and one realization per scenario, for 100 instances per setting. Planner families vary by scale: small settings include CBS, EECBS with suboptimality bounds, and PBS, while medium and large settings include PBS, PIBT, PIBT+, and LaCAM; MAPF-IM is also adapted as a comparison. The study reports executed sum of costs and success rate separately, with confidence intervals shown for the relevant curves. A physical demonstration uses two TurtleBots in a fixed indoor environment, restricting planning observations to adjacent locations to match the assumed observation model.
The abstract reports that MAGIC achieves lower executed sum of costs than existing approaches on 96.3% of instances. The reported evaluation spans several planner families and teams of up to 800 agents, supporting the claim that the approach applies beyond a single planner or small team. The study also examines sensitivity to spatial information in the prior and reports that informative spatial structure can improve execution. In the physical demonstration, one robot observes a blocked uncertain location, the shared belief changes at a nearby location unseen by either robot, and the second robot changes its route before directly observing that location. The excerpt does not provide all exact numerical curves, per-baseline gaps, parameter values, or statistical significance details, so those comparisons cannot be reconstructed from the supplied evidence.
The paper formulates Belief-Aware MAPF for fixed environments with initially uncertain traversability and introduces MAGIC for online shared belief inference. MAGIC combines a Gaussian Markov Random Field, Gaussian Belief Propagation, and detour-aware costs with standard MAPF planners. The benchmark results reported in the excerpt indicate lower executed cost on most evaluated instances, including the stated 96.3% figure, across multiple planner families and scales. The central conclusion is that spatially correlated local observations can be operationalized to anticipate hidden obstacles and improve execution. Extending the framework to lifelong tasks and changing traversability is left for future work.
The method assumes that map discrepancies remain fixed and that the task is one-shot with fixed starts and goals. Its observation model is local and noiseless, with adjacent uncertain locations observed before entry. Gaussian Belief Propagation and repeated deterministic replanning are approximations and do not provide a complete solution to the underlying contingent decision problem. Performance can be harmed by an inaccurate prior, including a prior that makes useful passages appear too unlikely. The supplied excerpt does not establish robustness to noisy sensing, dynamic obstacles, severe model misspecification, or exact optimality guarantees.
The work addresses a practical gap between perfectly known-map MAPF and direct-observation replanning by using one observation to anticipate nearby unobserved obstacles. Its interface through weighted traversal costs makes the uncertainty model usable with several existing MAPF planner families instead of requiring a new collision-resolution algorithm for each one. Evaluation at scales up to 800 agents is relevant to warehouse and other shared-space deployments where rerouting can be expensive. More broadly, it shows how spatial probabilistic inference can be connected to multi-agent coordination decisions.
This paper is recommended for researchers studying MAPF with partial observability, uncertain or imperfect maps, warehouse robotics, online replanning, and spatially correlated obstacle states. It is also relevant to readers interested in GMRFs, Gaussian Belief Propagation, belief-to-cost transformations, and interfaces for augmenting existing MAPF planners. Readers whose primary interest is lifelong MAPF with actively changing environments or formal optimality guarantees should treat the paper as a related but limited starting point. The supplied excerpt is sufficient to understand the framework and reported headline result, but not to reproduce every numerical comparison.