💻 computer science

Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

This paper introduces Anytime Closed-Loop Conflict-Based Search (ACCBS), a novel algorithm that dynamically adjusts its planning horizon and reuses a constraint tree to provide high-quality, asymptotically optimal solutions for multi-agent path finding with low latency and robustness to online disturbances.

Original authors: Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

Published 2026-06-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive, automated warehouse filled with hundreds of tiny robots, all trying to move boxes from point A to point B without bumping into each other. This is the Multi-Agent Path Finding (MAPF) problem. It's like trying to coordinate a dance where everyone has a different destination, and if two dancers try to occupy the same spot at the same time, the whole show stops.

For a long time, robot planners faced a frustrating "Goldilocks" problem:

The "Perfect Plan" approach: These algorithms try to map out the entire journey for every robot before anyone moves a single step. It's like a conductor writing out a 3-hour symphony before the first note is played. The problem? If the warehouse is huge or crowded, it takes so long to write the symphony that the robots stand there waiting forever.
The "Quick Fix" approach: These algorithms just look at the very next step and decide what to do. It's like a driver who only looks at the bumper in front of them. It's fast, but they often get stuck in traffic jams or make poor long-term decisions because they can't see around the corner.

This paper introduces a new method called ACCBS (Anytime Closed-Loop Conflict-Based Search) that tries to get the best of both worlds. Here is how it works, using simple analogies:

The Core Idea: The "Growing Telescope"

Imagine you are driving a car in fog.

Old Method: You wait until the fog clears completely so you can see the entire destination before you start the engine. (Too slow).
Simple Method: You only look at the road immediately in front of your tires. (Too risky).
ACCBS Method: You start by looking just a few feet ahead to get moving immediately. But as soon as you have a spare second, you "zoom out" your telescope to see a bit further. If you have even more time, you zoom out again.

ACCBS does exactly this. It starts by planning just the next step for all robots so they can move instantly. Then, it uses any remaining computer time to extend its "view" (the planning horizon) to see 2 steps ahead, then 3, then 4, and so on.

The Magic Trick: Reusing the "Map"

You might think, "If I keep zooming out, don't I have to redraw the whole map every time?" That would be too slow.

The paper's clever innovation is Constraint Tree Reuse.
Think of the planning process as building a tree of "what-if" scenarios.

When ACCBS looks 1 step ahead, it builds a small tree of possibilities.
When it decides to look 2 steps ahead, it doesn't throw that tree away. It simply adds new branches to the top of the existing tree.
Because the math works out a specific way (called "Cost Invariance"), the value of the old branches doesn't change when you add new ones.

This is like building a tower of blocks. You don't knock the tower down to make it taller; you just keep stacking new blocks on top. This means the computer doesn't waste time recalculating what it already figured out.

Why "Anytime" Matters

The term "Anytime" is crucial here. It means the algorithm is interruptible.

If the computer is asked to make a decision in 0.5 seconds, it gives you the best plan it could find in that half-second (which is usually just the next safe step).
If it has 5 seconds, it gives you a much better plan that looks further ahead.
If the robots encounter a surprise (like a box falling or a robot moving slower than expected), ACCBS doesn't panic. It simply stops the current plan, looks at the new reality, and starts its "zooming out" process again from the current position.

The Results

The authors tested this on various maps, from empty rooms to crowded warehouses with hundreds of robots.

Speed: It is much faster than trying to plan the whole journey at once.
Quality: As you give it more time to "think," the paths it finds get better and closer to the perfect solution.
Reliability: Unlike other methods that might crash or time out if the situation gets too complex, ACCBS always has something to say because it starts with a simple, safe first step.

In Summary

ACCBS is like a smart traffic controller who doesn't wait for a perfect, long-term schedule. Instead, they get the cars moving immediately with a safe, short-term plan, and then continuously refine the plan as they get more information and more time, all without ever having to start from scratch. It balances the need for speed with the need for a good solution, making it ideal for busy, real-world robot fleets.

Technical Summary: Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

Problem Statement

Multi-Agent Path Finding (MAPF) is a fundamental coordination problem for large robot fleets in automated warehouses and logistics, requiring agents to move from start to goal vertices on a graph without collisions. While optimal MAPF is NP-hard, existing solvers face a trade-off between scalability and performance guarantees.

Open-loop planners (e.g., standard Conflict-Based Search, CBS) compute complete trajectories before execution. While they offer optimality guarantees, they suffer from high planning latency and poor scalability on dense, long-horizon instances, delaying action execution.
Closed-loop heuristics reduce latency by replanning from the current state but often lack reliable performance guarantees, limiting their utility in safety-critical deployments.
Finite-horizon approaches (e.g., Windowed CBS/RHCR) attempt to bridge this gap but face a "horizon selection dilemma": a fixed planning horizon must be chosen a priori. A small horizon is efficient but myopic, while a large horizon improves solution quality at the cost of exponential search growth. Furthermore, fixed-window methods often lose the completeness and asymptotic optimality guarantees of standard CBS.

Methodology: Anytime Closed-Loop Conflict-Based Search (ACCBS)

The paper proposes ACCBS, a closed-loop MAPF algorithm that combines finite-horizon CBS with a dynamic horizon mechanism inspired by Model Predictive Control (MPC).

Core Mechanisms

Finite-Horizon Closed-Loop CBS:
- Instead of solving for the full trajectory, the algorithm plans over a finite lookahead horizon $H$ .
- It optimizes a cost function comprising a running cost (steps taken to reach the goal) and a terminal cost (admissible heuristic estimating the remaining distance to the goal).
- At each time step $t$ , it resolves conflicts only within the lookahead window, executes the first movement, and replans from the new state.
Adaptive Horizon via Iterative Deepening:
- ACCBS does not fix the horizon $H$ in advance. Instead, it maintains a running horizon $h_r$ that starts at 1 and grows incrementally up to a maximum $H_{max}$ as long as the computational time budget permits.
- This allows the algorithm to return a feasible, low-latency solution immediately (with $h_r=1$ ) and refine it with longer lookaheads if time remains, exhibiting anytime behavior.
Active Prefix and Constraint-Tree Reuse:
- To avoid the prohibitive cost of restarting the search every time the horizon increases, ACCBS introduces the concept of an active prefix. Conflicts are only resolved within the current active prefix of length $h_r$ ; conflicts beyond this prefix are temporarily ignored.
- Cost Invariance (Lemma III.1): The paper proves that under specific low-level planner assumptions (suffixes follow shortest paths), the cost of a node remains invariant when the horizon is extended.
- Constraint-Tree Reuse (Proposition III.1): Because costs and parent-child relationships are preserved, the constraint tree built for a smaller horizon $h$ is a valid subtree for $h+1$ . This allows ACCBS to seamlessly expand the horizon without restarting the search, making the cumulative computational effort comparable to a single run at the maximum horizon.

Theoretical Guarantees

Completeness and Optimality: Theorem III.1 establishes that if the time budget is infinite and $H_{max}$ is at least the makespan of an optimal solution, ACCBS is complete and returns a globally optimal solution (Sum of Costs, SOC).
Anytime Property: As the runtime increases, the cost of the best solution found is monotonically non-decreasing (bounded by the optimal cost) and converges to the optimum.
Single-Step Feasibility: The algorithm guarantees a collision-free single-step command at every timestep by construction, as it always executes the first step of a node with a conflict-free active prefix (where $h_r \ge 1$ ).

Experimental Results

The authors evaluated ACCBS against baselines including PIBT, EECBS, MAPF-LNS2, LaCAM2/3, and RHCR across one-shot, lifelong, and stochastic execution settings.

One-Shot MAPF: ACCBS achieves a favorable balance between computational efficiency and solution quality. As the per-step time budget increases, ACCBS lowers the Sum of Costs (SOC) and approaches optimality, outperforming fast heuristics like PIBT and avoiding the timeout failures of full-trajectory solvers like EECBS on dense maps.
Lifelong MAPF: In scenarios with changing goals, ACCBS demonstrates competitive throughput. Its adaptive horizon allows it to scale to larger fleets where fixed-window methods (RHCR) time out.
Stochastic Uncertainties: In simulations with execution delays and agent arrivals, ACCBS outperforms open-loop baselines. Open-loop methods are bottlenecked by the need to replan full trajectories upon disturbance, whereas ACCBS naturally absorbs disturbances by replanning from the current state.
Ablation Study: The paper notes that adding prioritized-conflict (PC) selection to ACCBS can sometimes reduce solution quality under fixed budgets, as the overhead of conflict classification outweighs the benefits of reduced tree expansions.

Significance and Claims

The paper claims that ACCBS addresses the critical trade-off between planning latency and solution quality in multi-agent systems. Its primary contributions are:

Elimination of Brittle Design Choices: By adapting the horizon online, ACCBS removes the need to manually tune a fixed horizon that depends on specific instance characteristics and time budgets.
Efficient Horizon Expansion: Through cost invariance and constraint-tree reuse, the algorithm achieves the benefits of iterative deepening without the associated computational penalty of restarting searches.
Restoration of Guarantees: Unlike fixed-window closed-loop methods, ACCBS recovers the asymptotic optimality and completeness guarantees of standard CBS.
Robustness: The closed-loop formulation naturally accommodates online disturbances (delays, new agents) without requiring full trajectory replanning.

The authors position ACCBS as a practical solution for safety-critical, large-scale deployments where both execution flexibility and performance guarantees are required.