MAGIC helps robot teams plan around obstacles they have not seen yet

A robot can discover that an aisle is blocked only after its original route has become inconvenient. With many robots sharing the same space, that discovery can also affect teammates that have not reached the obstruction. A new path-finding study investigates how to use the observation before more agents make the same mistake.
Viraj Parimi and colleagues introduce MAGIC, or Multi-Agent Gaussian Belief Inference for Coordination, in Belief-Aware Multi-Agent Path Finding under Map Uncertainty. The framework combines estimates of unknown obstacles with existing planners that keep agents from colliding.

One observation can change nearby routes

Classical multi-agent path finding assumes the map's static obstacles are already known. The paper studies a different setup: some locations have unknown traversability at the beginning, but the actual map remains fixed while the team moves.
That distinction separates this work from handling obstacles that continuously appear or move during execution. The authors motivate their problem with disturbances such as a fallen object or blocked passage, where nearby locations may also become inaccessible.
MAGIC maintains a shared probabilistic belief over those unknown locations. A Gaussian Markov Random Field models spatial relationships, and Gaussian Belief Propagation updates approximate estimates after agents observe their surroundings. Finding one blocked location can therefore lower confidence in nearby locations that no agent has directly inspected. A traversable observation can update those beliefs too.

The cost of being wrong matters

A risky shortcut is not equally troublesome everywhere. If there is a short alternative route, discovering an obstruction may be cheap. If the alternative requires a long diversion, the same estimated blockage probability deserves more caution.
MAGIC combines traversability estimates with local edge-bypass distances to produce detour-aware traversal costs. It passes the resulting weighted graph to a standard path-finding planner, then repeats inference and planning when new observations arrive.
The paper describes this cost as a local surrogate, not the exact expected cost of every possible future execution. The edge estimate uses the smaller of its endpoints' traversability beliefs, while the bypass distance considers removal of that particular edge. Those approximations help make the scheme usable with several planner families without solving the full joint uncertainty problem.

What the benchmark result establishes

The authors report lower executed sum of costs than existing approaches on 96.3% of tested instances, across multiple planners and teams of up to 800 agents. Here, sum of costs adds the agents' final arrival times. The figure describes how often MAGIC improved that metric, not a 96.3% reduction in travel time.
Tests use standard map layouts, including warehouses, mazes, rooms and city maps, with spatially structured hidden obstacles. The evaluation setup therefore matters when considering how well the result might transfer to a particular facility.
The sensing assumptions are also strong: agents noiselessly observe adjacent uncertain locations before moving, share those observations immediately, and incur no additional sensing cost. Starts and goals are known to be traversable. Under those assumptions and a sound underlying planner, blocked destinations are detected before entry.
MAGIC offers a concrete way to make local discoveries useful to an entire team. Its reported results support that planning strategy in the studied setting; they do not establish equivalent performance with delayed communication, noisy sensors or a map that changes during a run.