Online Multi-Agent Pathfinding

Jirí Svancara, Marek Vlk, Roni Stern, Dor Atzmon, Roman BartákAAAI 2019 · DOI

Abstract

Multi-Agent Pathfinding (MAPF) is a critical challenge in robotics, typically addressed as an offline problem where all agent start and end points are known a priori. However, real-world applications like autonomous intersections and warehouse logistics require an "online" approach where agents enter and exit the system dynamically. This paper formalizes the Online MAPF problem, demonstrates that a theoretically optimal online solver is impossible, and introduces Online Independence Detection (OID) and its suboptimal variant (SubID) to balance path efficiency with plan stability.

Introduction

Moving a single robot from point A to point B is a well-understood problem. However, coordinating hundreds of robots simultaneously without collisions—Multi-Agent Pathfinding (MAPF)—is significantly more complex. Most existing research treats MAPF as a static, offline problem. In dynamic environments, such as autonomous warehouses or traffic intersections, new agents can appear at any time, requiring the system to adjust on the fly without causing cascading delays or computational bottlenecks.

Problem Formalization

The core challenge of Online MAPF is deciding how to integrate a newcomer without unnecessarily disrupting existing agents. Frequent re-routing is computationally expensive and physically disruptive. The authors define several variants of the problem based on agent appearance (in-grid vs. garage) and behavior at the goal (staying vs. disappearing).

Table 1: Classification of Online MAPF problem variants and their feasibility.

As shown in the table above, the authors conclude that the most robust and complete setting involves agents appearing in "garages" (private starting areas) and disappearing upon reaching their goals. Without a garage, it is impossible to guarantee a collision-free solution, as a new agent might appear in a cell already occupied by another agent.

Proposed Methodologies

The researchers compared four primary algorithmic strategies to handle dynamic arrivals:

  1. Replan Single (RS): The newcomer finds the best path that avoids all existing, fixed plans. While computationally efficient, it often leads to poor overall traffic flow.
  2. Replan All (RA): The system recalculates optimal paths for all agents whenever a newcomer arrives. This yields the best path quality but is slow and highly disruptive to existing plans.
  3. Online Independence Detection (OID): Based on Standley’s Independence Detection, this algorithm only replans for agents whose current paths conflict with the newcomer. It aims for "Snapshot Optimality"—the best solution for the current set of agents.
  4. Suboptimal OID (SubID): A relaxed version of OID that allows agents to take slightly longer paths (within a factor $D$) if it prevents other agents from having to change their original routes.

Experimental Evaluation

The algorithms were evaluated across two primary setups: small, dense grids for autonomous intersections (solved via SAT-based solvers) and large grids with obstacles for warehouse simulations (solved via Conflict-Based Search).

Figure 1: A large grid environment with obstacles used to simulate warehouse robotics scenarios.

Key Results

  • The Optimality Gap: The authors proved that no online solver can guarantee the same "sum of costs" as an offline solver. Because the future is unknown, an online solver might block a corridor that becomes vital later.
  • Stability vs. Quality: While Replan All (RA) and OID both achieved Snapshot Optimality, OID significantly reduced the number of required re-routes.
  • SubID Performance: In large grids with 66 agents, RA required an average of 32 agents to change their plans per arrival. SubID (with a 1.1 suboptimality factor) reduced this to just 5 re-routes, maintaining a path cost nearly identical to the optimal OID.

Conclusion

This work highlights that "re-routing" is a critical metric for real-world MAPF. OID and SubID provide a framework to achieve high-quality paths while maintaining system stability. Future work may involve predictive modeling to leave high-traffic corridors clear based on the probability of future agent appearances, further narrowing the gap between online and offline performance.

Summary updated

BibTeX
@inproceedings{svancara2019online,
  author = {Jirí Svancara and Marek Vlk and Roni Stern and Dor Atzmon and Roman Barták},
  title = {{Online Multi-Agent Pathfinding}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017732},
}
Figure