PaperlayerView exact revision on arXiv

Source-linked AI summary

Belief-Aware Multi-Agent Path Finding under Map Uncertainty

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

arXiv:2609.40269v1cs.AIcs.MAcs.RO

TL;DR

MAPF under map uncertainty must plan for traversability that is initially unknown, and spatial dependence can make observations informative beyond the observed location. MAGIC updates a shared belief from local observations and converts inferred traversability into detour-aware costs for standard MAPF planners. It achieves lower executed SoC than existing approaches on 96.3% of instances, with benefits across planner families and teams of up to 800 agents.

  • Problem

    In fixed environments with initially unknown traversability, spatial dependence can make observations informative about nearby unobserved locations, a signal that planning must account for.

    Source: §I · p. 1

  • Method

    MAGIC updates a shared spatial belief from agents’ observations and combines inferred traversability with detour distances to produce online costs for standard MAPF planners.

    Source: §I · p. 1, B. Detour-Aware Traversal Costs · p. 4

  • Results

    MAGIC achieves lower executed SoC than existing approaches on 96.3% of instances across tiers, planner families, and teams up to 800 agents.

    Source: §VI · p. 8

  • Takeaways & Limitations

    The reported benefit persists across several planner families and scales to teams of 800 agents.

    Source: §VI · p. 8

    Additional GaBP inference and belief-dependent planning can cause difficult runs to exhaust planner or total-runtime limits before all agents reach their goals.

    Source: B. Results and Discussion · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Belief-Aware MAPF addresses fixed but initially unknown traversability, where spatial dependence can make observations informative about nearby unobserved locations. MAGIC uses shared belief updates and detour-aware costs to guide standard MAPF planners; across benchmarks, it achieves lower executed sum of costs than existing approaches on 96.3% of instances.

I. INTRODUCTION

  • Spatially structured disturbances can make an observation informative about nearby unobserved locations, motivating inference beyond direct observations.A blocked aisle or displaced object may affect several nearby locations.Source: §I · p. 1

Contributions

  • Belief-Aware MAPF models initially unknown traversability in a fixed environment, with a shared belief capturing spatial dependence among uncertain locations.The setting concerns discrepancies discovered through local observations during execution.Source: §I · p. 1
  • MAGIC uses a shared probabilistic belief to construct detour-aware traversal costs that weigh transition availability against the cost of an alternative route.The framework integrates spatial inference with online MAPF planning, updating costs as agents gather observations.Source: §I · p. 1
  • MAGIC achieves lower executed SoC than existing approaches on 96.3% of instances across benchmark maps, planner families, and teams of up to 800 agents.The evaluation measures executed cost, success rate, and sensitivity to uncertainty and prior information.Source: §I · p. 1

I. INTRODUCTION

  • MAGIC’s overview shows shared posterior beliefs updated through GaBP, then combined with detour distances to guide planned paths.In the depicted example, MAGIC routes Agent 1 through a lower corridor rather than toward an obstacle that would trigger later optimistic replanning.Source: Figure 1 · p. 2

II. RELATED WORK

Prior work addresses map uncertainty through contingent plans or direct-observation replanning, while other methods guide traffic with weighted graphs or defer conflict resolution through repeated replanning. Related work also studies uncertain single-agent routing, specialized uncertain-traversability policies, belief-space planning, and spatial map inference; scalable integration of spatial beliefs with collision-resolving MAPF planners remains less explored.

A. MAPF Under Map Uncertainty and Partial Observability

  • MAPF-OU branches on future observations but grows computationally costly as uncertainty increases; MAPF-IM replans after direct observations, and neither infers unobserved traversability from spatial dependence.These approaches are designed for uncertainty and partial observability but do not exploit spatial dependence for that inference.Source: A. MAPF Under Map Uncertainty and… · p. 2

B. Adaptive Guidance and Incremental Execution

  • Guidance Graph Optimization tunes edge weights for lifelong MAPF throughput, while Rolling-Horizon Collision Resolution and MAPF-IM use repeated replanning to avoid committing to distant conflicts.Their weights shape traffic rather than encode environmental traversability uncertainty.Source: B. Adaptive Guidance and Incremental… · p. 2

C. Planning With Uncertain Traversability

  • The Canadian Traveller Problem minimizes expected travel cost as a single agent discovers edge states, unlike collision-free coordination among multiple agents.Other uncertain-traversability methods use team policies combining movement, sensing, and waiting, or probabilistic roadmaps with uncertain shortcuts and recovery paths.Source: C. Planning With Uncertain… · p. 2

D. Belief-Space Planning and Spatial Map Inference

  • POMDP and multi-robot belief-space planners reason about future actions and observations, but their joint belief and action spaces grow rapidly with agent count.Spatial mapping methods use Gaussian-process correlations or Markov random fields with loopy belief propagation to infer occupancy at unobserved locations; scalable use in MAPF with explicit collision resolution remains less explored.Source: D. Belief-Space Planning and Spatial… · p. 2

III. BELIEF-AWARE MAPF

Classical MAPF represents a shared environment as a graph and assigns each agent a start and goal. A joint plan moves agents through that graph while avoiding vertex and edge conflicts, and its sum of costs aggregates their arrival times.

A. Classical MAPF

  • Each agent has a start and goal on the environment graph, and at each timestep may wait or move along an edge.The graph’s vertices represent locations and its edges represent allowed moves.Source: A. Classical MAPF · p. 2
  • A valid joint plan avoids vertex conflicts, where agents occupy the same location, and edge conflicts, where agents traverse the same edge in opposing directions.The supplied passages define both conflict types over agents and timesteps.Source: A. Classical MAPF · p. 3
  • The sum of costs (SoC) of a joint plan is the sum of agents’ final arrival times.Each arrival time is the point after which that agent remains at its goal.Source: A. Classical MAPF · p. 3

B. Fixed Environment with Unknown Obstacles

Belief-Aware MAPF places initially uncertain traversability in a fixed environment: the realized map is sampled once and remains fixed, while the planner’s prior may differ from the environment distribution. Agents share observations of nearby uncertain locations and plan online under a common observation history; the formulation focuses on one-shot problems with fixed starts and goals.

B. Fixed Environment with Unknown Obstacles

  • Belief-Aware MAPF assigns binary traversability states to initially uncertain locations while treating other locations as known traversable.Starts and goals are required to lie at locations whose traversability is known.Source: B. Fixed Environment with Unknown… · p. 3
  • The environment samples a traversability realization that remains fixed during execution, and the planner’s prior need not match the environment distribution.The environment distribution is restricted to realizations that admit a collision-free solution.Source: B. Fixed Environment with Unknown… · p. 3

C. Observations and Online Objective

  • Sensing is local and cost-free: before each joint move, agents noiselessly observe uncertain locations adjacent to their current positions and share observations.All agents condition on the same history of observations through the current timestep.Source: C. Observations and Online Objective · p. 3
  • The formulation restricts attention to one-shot MAPF with fixed starts and goals because computing the optimal policy requires contingent reasoning over unknown states and histories, while the planner does not know the environment distribution.The cited passage also notes the computational hardness of related single-agent uncertain-edge routing and the additional need for joint conflict resolution in multi-agent planning.Source: C. Observations and Online Objective · p. 3

IV. MAGIC

MAGIC approximates contingent planning by repeatedly solving deterministic MAPF instances informed by observations. Its shared traversability belief uses spatial inference to update estimates for unobserved locations.

IV. MAGIC

  • MAGIC approximates contingent planning by repeatedly solving deterministic MAPF instances informed by observations collected so far.Each update infers beliefs over unobserved locations, converts them to traversal costs, and replans.Source: §IV · p. 3

A. Shared Traversability Belief

  • A GMRF over latent scores, paired with Bernoulli-probit traversability states, encodes spatial correlation and prior anchoring.Higher latent scores indicate greater traversability probability; known traversable locations are fixed to a positive score.Source: A. Shared Traversability Belief · p. 3
  • New observations are clamped to ±c, then batch GaBP estimates latent marginals used to derive traversability probabilities for unobserved locations.Pairwise terms propagate observed values to nearby locations; larger marginal variance shifts estimates toward 0.5.Source: A. Shared Traversability Belief · pp. 3–4
  • After initial inference, MAGIC reruns GaBP only when new observations arrive and reuses previous estimates otherwise.Updates stop when the largest message residual falls below a tolerance or after K sweeps.Source: A. Shared Traversability Belief · p. 4

B. Detour-Aware Traversal Costs

MAGIC converts location beliefs and local bypass distances into detour-aware edge costs for a deterministic MAPF planner. The planning graph removes observed blocked locations but retains locations whose traversability remains unknown.

B. Detour-Aware Traversal Costs

  • The planning graph retains unobserved locations and removes observed blocked locations with their incident edges.The realized traversable graph is a subset of this planning graph.Source: B. Detour-Aware Traversal Costs · p. 4
  • MAGIC estimates edge traversability with the smaller endpoint belief because the marginals do not determine their joint traversability probability.Using the product would assume independence, while a joint estimate requires the pairwise latent posterior.Source: B. Detour-Aware Traversal Costs · p. 4
  • When removing an edge disconnects its endpoints, assigning |V| as the detour exceeds every finite simple-path length and supplies a finite penalty.Source: B. Detour-Aware Traversal Costs · p. 4
  • For edges incident to uncertain locations, MAGIC interpolates unit traversal cost with shortest bypass length, penalizing long detours more than short ones.Other edges and wait actions retain unit cost; the local cost is a surrogate, not the exact expected future execution cost.Source: B. Detour-Aware Traversal Costs · p. 4
  • MAGIC caches detour lengths and paths, recomputing only those invalidated when an observed blocked location removes edges.Surviving cached paths remain shortest as the graph only loses edges and vertices.Source: B. Detour-Aware Traversal Costs · p. 4

C. Planning and Execution

The weighted graph and current agent configuration are passed to a MAPF planner, which uses the costs to guide path search or move selection. New observations trigger replanning, and noiseless observations of adjacent uncertain locations reveal blocked destinations before entry.

C. Planning and Execution

  • MAGIC supplies the current configuration, goals, graph, and edge costs to the MAPF planner.CBS uses the costs as edge costs, while PIBT and LaCAM use them to estimate weighted distance-to-go.Source: C. Planning and Execution · p. 5
  • Any new observation triggers replanning because even a traversable observation can change posterior beliefs and edge costs.A planner returning only one joint action is queried again at the next timestep.Source: C. Planning and Execution · p. 5
  • Noiseless observations of adjacent uncertain locations reveal blocked destinations before entry, so a sound planner's executed actions are valid in the realized graph.Source: C. Planning and Execution · p. 5

V. EXPERIMENTAL EVALUATION

The evaluation is organized around whether MAGIC improves execution under uncertain traversability, generalizes across planner families and problem scales, and depends on the prior's spatial information.

V. EXPERIMENTAL EVALUATION

  • The first evaluation question asks whether MAGIC improves execution under uncertain traversability.Source: §V · p. 5
  • The second question asks whether the benefit persists across planner families and problem scales.Source: §V · p. 5
  • The third question asks how sensitive MAGIC is to the spatial information encoded by the prior p0(X).Source: §V · p. 5

A. Experimental Setup

The experiments generate fixed, spatially structured obstacle realizations and evaluate MAGIC across standard MAPF maps, team sizes, and planner families. Comparisons report executed cost and success under shared experimental limits.

A. Experimental Setup

  • Hidden obstacles are sampled around uncertainty centers; Z comprises locations within radius R, excluding starts and goals, and accepted realizations remain fixed during execution.Realizations are retained only when the resulting map admits a collision-free solution.Source: A. Experimental Setup · p. 5
  • ϕ = 0.20, ρ = 0.30, and R = 3 are the default targets; small-tier experiments vary ϕ and ρ from 0.00 to 0.30.The uncertainty illustration shows that increasing ϕ expands the initially unknown map area, while higher ρ means more uncertain locations are blocked.Source: A. Experimental Setup · p. 5, Figure 2 · p. 5
  • Small-tier settings use 375 instances across five maps, while each medium-, large-, and huge-tier setting uses 100 instances.The evaluation covers open, random, maze, room, warehouse, game, and city maps grouped into four scale tiers; team-size studies range from 10 to 800 agents.Source: A. Experimental Setup · pp. 5–6, Table I · p. 5
  • MAGIC is compared with location-adapted MAPF-IM and optimistic replanning across CBS, EECBS, PBS, PIBT, PIBT+, and LaCAM planner settings.Optimistic replanning uses the same realization, start-goal assignment, and underlying planner as MAGIC, but treats unresolved locations as traversable.Source: A. Experimental Setup · p. 6
  • The evaluation reports executed sum of costs and success rate separately, with cost ratios averaged over jointly completed instances and success rates counting all attempts.Methods within an experimental condition share the stated limits; per-call, total-runtime, and execution-timestep limits vary by tier.Source: A. Experimental Setup · p. 6, Figure 3 · p. 6

B. Results and Discussion

MAGIC’s executed-cost advantage varies with uncertainty, scale, and prior quality. The results also include a two-robot demonstration in which an observation changes another robot’s route before it sees the affected location.

Q1

  • At ϕ = 0.30, MAGIC is 3.6% above the full-information optimum, versus 9.4% for optimistic replanning and 14.9% for MAPF-IM.At ϕ = 0, MAGIC and optimistic replanning both recover the optimum.Source: B. Results and Discussion · pp. 6–7

Q2

  • MAGIC achieves lower executed SoC than MAPF-IM on 96.3% of instances across the small, medium, and large tiers.Table II reports results across planner families and problem scales at ϕ = 0.20, ρ = 0.30, and R = 3.Source: Table II · p. 7, B. Results and Discussion · p. 7

Q1

  • At the largest tested ρ, MAGIC is 2.7% above the optimum, versus 6.7% for optimistic replanning and 12.4% for MAPF-IM.At ρ = 0, MAGIC is 2.9% above the optimum because it still penalizes transitions involving unresolved locations. Its advantage over optimistic replanning narrows as team size increases, and MAPF-IM has no successful run at n = 100.Source: B. Results and Discussion · p. 7

Q2

  • At n = 800, PIBT+ has 100% success under both methods, with a mean SoC ratio of 0.995 for MAGIC against optimistic replanning.Some MAGIC settings have lower success rates because inference and belief-dependent planning add computational work that can exhaust planner or runtime limits.Source: B. Results and Discussion · p. 7

Q1

  • Uncertainty-radius variation has little aggregate effect, but on the large warehouse map MAGIC’s executed SoC is higher at R = 1 and lower for R ≥ 2 than optimistic replanning.Medium- and large-tier sweeps over ϕ and ρ broadly reproduce similar trends.Source: B. Results and Discussion · pp. 7–8

Q3

  • With aligned rather than reversed priors, executed SoC falls 3.40% on successful instances, while success rises from 88.5% to 90.9%.These priors were tested on the same small-tier instances at ϕ = 0.20, ρ = 0.30, and R = 3; alignment does not improve every individual instance, and the aggregate advantage is strongest on maps with constrained routes.Source: B. Results and Discussion · p. 8

Physical robot demonstration

  • In a two-TurtleBot demonstration, one robot’s observation updated belief about a nearby unseen location and caused the second robot to change route before observing it.The demonstration used a fixed indoor environment and restricted planning observations to adjacent locations.Source: B. Results and Discussion · p. 8

VI. CONCLUSION

The conclusion formulates Belief-Aware MAPF and presents MAGIC as a shared-belief method for planning with initially uncertain traversability. Its reported benefit spans planner families and scales, while future work targets lifelong tasks and changing environments.

  • Belief-Aware MAPF concerns fixed environments with initially uncertain traversability; MAGIC updates a shared spatial belief from observations and converts inferred traversability into detour-aware costs for standard MAPF planners.Source: §VI · p. 8
  • MAGIC achieves lower executed SoC than existing approaches on 96.3% of instances, across several planner families and teams of up to 800 agents.Source: §VI · p. 8
  • Future work will extend Belief-Aware MAPF to lifelong tasks and environments whose traversability changes during execution.Source: §VI · p. 8
Loading 2609.40269v1…