Two Level Search for Multi Agent Path Finding

118 concepts90 papers1 proposal

Planning collision-free trajectories for a fleet of autonomous agents is a fundamental challenge in robotics. Whether coordinating hundreds of warehouse robots or managing autonomous vehicles at a signal-free intersection, the core mathematical hurdle remains the same: the combinatorial explosion of the joint state space.

If a single robot can choose from 5 possible actions at any given step, a team of 100 robots yields a joint branching factor of $5^{100}$ actions per step. Searching this unified space directly using standard pathfinding algorithms quickly becomes computationally intractable.

To bypass this exponential complexity, modern multi-agent path finding (MAPF) frameworks rely on a powerful insight: decouple individual path planning from multi-agent coordination using a two-level search architecture. Instead of planning for all agents simultaneously, these frameworks assume agents are independent first, and then lazily resolve conflicts as they arise. This approach exploits the spatial sparsity of real-world interactions, transforming an intractable joint optimization problem into a highly efficient, targeted search over localized constraints.

The two-level search paradigm splits the pathfinding problem into two distinct layers that communicate via a feedback loop:

  1. The Low-Level Planner: This layer is responsible for finding a path for a single agent. It treats the agent in isolation, searching a low-dimensional state space (e.g., a 2D grid or a single robot's kinematic configuration). Crucially, the low-level planner accepts a set of spatio-temporal constraints passed down from above, which dictate specific locations or actions the agent must avoid at certain times.
  2. The High-Level Coordinator: This layer takes the individual paths generated by the low-level planner and checks them for collisions. If no collisions are found, the joint plan is valid and the search terminates. If a conflict is detected, the high-level coordinator does not rewrite the entire plan; instead, it formulates constraints to prevent that specific conflict and forces the low-level planner to recalculate paths only for the affected agents.

By isolating individual pathfinding from the coordination logic, the system avoids searching the joint state space entirely. As noted by Sharon in a foundational thesis summary on Optimal Multi-Agent Pathfinding Algorithms, this separation makes optimal pathfinding computationally feasible for significantly larger groups of agents than traditional unified search methods.

Branching on Spatio-Temporal Conflicts

The most prominent realization of this two-level architecture is Conflict-Based Search (CBS), introduced by Sharon et al. in Conflict-Based Search For Optimal Multi-Agent Path Finding.

CBS manages the high level by constructing a Constraint Tree (CT). Each node in the CT represents a set of constraints imposed on the agents. The search proceeds as follows:

  • Root Node: The low-level planner computes an optimal path for every agent independently, assuming an empty environment with zero multi-agent constraints.
  • Conflict Detection: The high-level coordinator reviews these paths. Suppose it finds that Agent $A$ and Agent $B$ both attempt to occupy vertex $v$ at time step $t$. This is a vertex conflict: $(A, B, v, t)$.
  • Branching: To resolve this conflict, the high-level search branches by creating two child nodes, splitting the problem into mutually exclusive avoidance scenarios:
  • Left Child: Adds the constraint that Agent $A$ cannot occupy vertex $v$ at time $t$.
  • Right Child: Adds the constraint that Agent $B$ cannot occupy vertex $v$ at time $t$.
                  [ Root Node: No Constraints ]
                     Paths collide: (A, B, v, t)
                            /           \
                           /             \
  [ Left Child: A cannot be at (v,t) ]   [ Right Child: B cannot be at (v,t) ]
    Low-level replans for Agent A          Low-level replans for Agent B

When a child node is generated, the low-level planner replans only for the single agent receiving the new constraint. The high-level search then explores the tree using a best-first strategy based on the total cost of the paths. Because constraints are added lazily, CBS guarantees optimality while keeping the high-level tree remarkably small when agent interactions are sparse.

To scale this mechanism to denser environments, Boyarski et al. introduced ICBS: Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding. The authors demonstrated that high-level search efficiency drastically improves by prioritizing "cardinal" conflicts—those where resolving the conflict forces an agent to take a longer path, immediately increasing the total solution cost. Furthermore, when agents become too densely packed to be resolved via simple constraints, the framework dynamically groups them into meta-agents to be solved as a single unit, preventing the high-level tree from exploding.

Branching on Ranks and Priorities

While CBS branches on specific spatio-temporal points, an alternative approach branches on relative priority orderings. Traditional prioritized planning, as discussed by Yakovlev et al. in Planning and Learning in Multi-Agent Path Finding, assigns a fixed rank to each agent. Higher-priority agents plan their paths first, and lower-priority agents treat those completed trajectories as moving obstacles (Andreychuk et al. in Two Techniques That Enhance the Performance of Multi-robot Prioritized Path Planning). However, finding a single fixed priority sequence that avoids deadlocks is an NP-hard problem.

To resolve this, Priority-Based Search (PBS), proposed by Ma et al. in Searching with Consistent Prioritization for Multi-Agent Path Finding and expanded in Extended Abstract: Searching with Consistent Prioritization for Multi-Agent Path Finding by Harabor et al., treats the priority ordering itself as the high-level search space.

When the high-level coordinator detects a collision between Agent $A$ and Agent $B$, PBS does not forbid them from a specific tile. Instead, it branches on their priority relationship:

  • Branch 1: Enforces that Agent $A$ has priority over Agent $B$ ($A \prec B$). Agent $B$ must now replan its entire trajectory to avoid Agent $A$.
  • Branch 2: Enforces that Agent $B$ has priority over Agent $A$ ($B \prec A$). Agent $A$ must replan to avoid Agent $B$.

This conflict-driven branching builds a partial priority ordering dynamically. A single priority constraint can resolve multiple downstream collisions between two agents simultaneously, drastically reducing the depth of the high-level search tree and enabling rapid pathfinding for hundreds of agents.

Bridging the Gap to Physical Dynamics

The elegance of the two-level search architecture lies in its adaptability. While originally designed for discrete grid abstractions, the same high-level coordination logic can govern continuous, physically constrained systems. Real robots cannot stop instantaneously or turn on a dime; they are bound by kinodynamic constraints like velocity limits, acceleration bounds, and momentum.

Hönig demonstrated in Summary: Multi-Agent Path Finding with Kinematic Constraints that by separating the NP-hard pathfinding problem from continuous-time scheduling, we can generate feasible real-world trajectories significantly faster than through simultaneous optimization.

This decoupling has been integrated directly into two-level search variants:

  • Kinodynamic CBS (K-CBS): Kottinger et al. in Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints replaced the discrete low-level grid planner with a sampling-based motion planner capable of generating physically executable trajectories. The high level continues to detect spatial overlaps and impose spatio-temporal constraints, keeping the coordination logic independent of the underlying vehicle physics.
  • Conflict-Based Model Predictive Control (CB-MPC): Tajbakhsh et al. in Conflict-Based Model Predictive Control for Scalable Multi-Robot Motion Planning paired a high-level search tree with low-level Model Predictive Control (MPC). The high level isolates specific collision scenarios and passes down localized avoidance constraints to individual local controllers. This structure achieves nearly constant average solve times, enabling real-time performance where joint optimization methods experience exponential complexity growth.

Scaling to Complex Logistics Pipelines

The utility of two-level decoupling extends beyond pathfinding into broader multi-agent orchestration, such as coupling task allocation with routing. In large-scale logistics operations, robots must not only avoid collisions but also determine which tasks to execute and in what order.

In Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding, Li et al. introduced a hierarchical framework that manages a forest of constraint trees at the high level to handle task assignments, while the low level resolves the resulting spatio-temporal conflicts. Similarly, Huang developed an algorithm in Deadline-Aware Multi-Agent Tour Planning that separates high-level task sequencing from low-level collision-free pathfinding, making the coordination of hundreds of agents within strict operational deadlines computationally viable.

By structuring multi-agent coordination as a two-level hierarchy, these diverse frameworks share a common core advantage: they isolate the complex, system-wide problem of conflict resolution from the localized problem of single-agent execution. Whether applied to grid-based robots, continuous kinodynamic vehicles, or complex task schedules, the two-level search architecture successfully tames the curse of dimensionality by planning globally only where agents conflict locally.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hierarchical_conflict_resolution_862e1fff,
  title = {hierarchical conflict resolution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-conflict-resolution/rdr_862e1fff10eb4eb1a7c09dc7dc21e351},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_hierarchical_conflict_resolution_862e1fff_v1,
  title = {hierarchical conflict resolution},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-conflict-resolution/rdr_862e1fff10eb4eb1a7c09dc7dc21e351/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake