💻 computer science

Certificate-Driven Closed-Loop Multi-Agent Path Finding with Inheritable Factorization

This paper introduces Certificate-Driven Conflict-Based Search (CDCBS), a novel framework that enhances the scalability and solution quality of closed-loop Multi-Agent Path Finding in dense environments by utilizing certificate trajectories to ensure completeness and enable inheritable global factorization.

Original authors: Jiarui Li, Runyu Zhang, Gioele Zardini

Published 2026-04-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiarui Li, 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, bustling warehouse filled with hundreds of autonomous robots (agents) trying to move boxes from one side of the room to the other. The challenge? They all share the same floor, and if two robots bump into each other, the whole operation grinds to a halt. This is the Multi-Agent Path Finding (MAPF) problem.

For a long time, computer scientists have struggled with a trade-off:

The "Perfect Planner" approach: Calculates the entire route for every robot from start to finish before anyone moves. This guarantees no crashes and the shortest paths, but it's so slow and complex that it breaks down when you have too many robots or a crowded room.
The "Look-Ahead" approach: Robots only plan their very next step and then re-plan immediately after. This is fast and reactive, but it's "short-sighted." A robot might make a great move for the next second, only to get stuck in a dead end five seconds later because it didn't see the traffic jam coming.

This paper introduces a new system called CDCBS (Certificate-Driven Conflict-Based Search) that tries to get the best of both worlds. Here is how it works, using some everyday analogies.

1. The "Safety Net" (The Certificate)

Imagine you are driving a car in heavy traffic.

Old Way (Short-sighted): You only look at the car directly in front of you. You swerve left to avoid it, but you didn't notice the wall on the left, so you crash.
The Paper's Way (The Certificate): Before you even start moving, you have a Safety Net Plan. This is a pre-approved, crash-free route that gets you to your destination, even if it's not the absolute fastest one. You call this your "Certificate."

Now, as you drive, you can try to take a shortcut or a faster route. But here is the rule: You are only allowed to take that new shortcut if it is guaranteed to be better than your Safety Net Plan. If you can't prove it's better, you stick to the Safety Net.

Why is this cool?

It prevents panic: Even if your computer gets overwhelmed trying to find the perfect route, you never get stuck. You always have a valid "fallback" plan (the Certificate) to fall back on.
It guarantees progress: Every time you successfully switch to a new plan, you are mathematically guaranteed to be closer to your goal than you were before. You can never go backward.

2. The "Budget" (The Fleet Budget)

Think of the "Fleet Budget" as a travel allowance.

The "Safety Net" plan costs a certain amount of "energy" (time or distance). Let's say the budget is 100 points.
Every time a robot moves, it "spends" points.
The system only allows a new move if the total cost of the new plan is lower than the current budget.
Because the budget can only go down (you can't spend more than you have), the system is mathematically guaranteed to finish the job eventually. It's like a countdown timer that ensures you will reach the finish line.

3. The "Traffic Jam Breaker" (Inheritable Factorization)

In a crowded warehouse, robots often get stuck in a "tug-of-war" where they all need to move at the same time to avoid each other. This creates a giant, messy knot that is hard to untangle.

The paper introduces a clever trick called Factorization.

The Old Way: The computer treats all 100 robots as one giant, tangled group. It tries to solve the puzzle for everyone at once. This is like trying to untangle 100 headphones all knotted together.
The New Way (Factorization): The system looks at the "Budget" and realizes: "Hey, Robot A is far away from Robot B. They don't need to talk to each other right now. They are in different 'zones'."
It splits the 100 robots into smaller, independent groups (like splitting the 100 headphones into 10 separate piles).
The Magic: Because the "Safety Net" is so strict, these groups stay independent as they move. You don't have to re-check if they are independent every second. The groups you found at the start of the minute are still valid groups at the end of the minute. This allows the computer to solve 10 small puzzles in parallel (at the same time) instead of one giant, impossible puzzle.

The Result: CDCBS

By combining these ideas, the new algorithm (CDCBS) acts like a smart traffic controller:

It always keeps a Safety Net (Certificate) ready so no robot ever gets stuck.
It only accepts better moves if they improve the overall plan.
It splits the crowd into smaller, independent groups that can be solved simultaneously, making the whole process much faster.

In simple terms:
Previous methods were like a driver who only looks one second ahead and often gets stuck. This new method is like a driver who always has a backup map in the glovebox, only takes detours if they are proven to be faster, and realizes that the cars on the other side of the highway don't need to be part of their immediate traffic calculation.

The experiments showed that in crowded warehouses, this new method is much more reliable and produces smoother, faster results than previous methods, especially when things get chaotic.

1. Problem Statement

The paper addresses the Multi-Agent Path Finding (MAPF) problem, specifically within the context of closed-loop control for automated warehouses and logistics.

Context: In closed-loop MAPF, a controller outputs only the next movement for agents and replans online based on the current state, rather than computing a full trajectory upfront.
The Challenge: Existing closed-loop algorithms, such as Anytime Closed-Loop Conflict-Based Search (ACCBS), suffer from a "finite-horizon" limitation. They plan only a short "active prefix" of the trajectory.
- Shortsightedness: In dense environments, finite computational budgets often force the algorithm to terminate with a very short planning horizon. This leads to poor solution quality and unstable behavior because future conflicts are ignored.
- Loss of Structure: Because the planning horizon is short and constantly changing, it is difficult to exploit the compositional structure of the problem (i.e., decomposing the fleet into independent groups). Existing factorization methods are often local and must be recomputed at every timestep, losing global consistency.
Goal: To develop a closed-loop MAPF framework that maintains global guarantees (completeness and solution quality) and enables inheritable factorization (decomposing the fleet into independent groups that persist over time) despite finite computational budgets.

2. Methodology

The authors propose a general framework centered on Certificate Trajectories and Fleet Budgets, instantiated as the Certificate-Driven Conflict-Based Search (CDCBS) algorithm.

A. Certificate Trajectories and Fleet Budget

Certificate: At every timestep $t$ , the system maintains a certificate, which is a set of conflict-free trajectories from the current state to the goals for all agents.
Fleet Budget ( $B_t$ ): The total cost (Sum of Costs, SOC) of the certificate trajectories.
Mechanism:
1. Fallback: The certificate acts as a feasible fallback plan. If the online search fails to find a better plan, the system executes the first step of the current certificate.
2. Filtering: A new plan generated by the closed-loop search is only accepted if it results in a strictly lower fleet budget than the current certificate.
3. Completeness: Since the fleet budget is an integer and must strictly decrease with every accepted update (or agent reaching a goal), the system is guaranteed to terminate with all agents reaching their goals.

B. Budget-Limited Reachability and Inheritable Factorization

The fleet budget allows the authors to define a budget-limited reachable region for each agent.

Slackness ( $S_t$ ): The difference between the current fleet budget and the sum of the shortest-path costs for all agents. This represents the "excess" cost available for detours.
Reachable Region ( $R_{B_t}$ ): An agent can only occupy vertices that do not cause the total fleet cost to exceed the current budget.
Factorization: If the reachable regions of two agents (or groups of agents) do not intersect, they are independent.
Inheritability: A key theoretical contribution is proving that as the fleet budget decreases (or stays constant), these reachable regions shrink or stay the same. Consequently, if two groups are independent at time $t$ , they remain independent at all future times $t' > t$ . This allows the system to decompose the fleet into parallel subproblems that persist across timesteps, rather than recomputing groupings constantly.

C. The CDCBS Algorithm

The algorithm integrates these concepts into the ACCBS framework:

Initialization: Inherit the certificate and factorization groups from the previous timestep.
Search: Run a finite-horizon CBS search to resolve conflicts within an active prefix.
Certificate Update: When a conflict-free active prefix is found, concatenate it with a "backup rollout" (generated by a complete planner like LaCAM) to form a candidate certificate. If the candidate's cost is lower than the current budget, update the certificate.
Factorization: Periodically check if the reduction in slackness allows for a finer decomposition of the fleet into independent groups using Disjoint Set Union (DSU).
Execution: Output the first step of the current best certificate.

3. Key Contributions

Certificate-Driven Framework: Introduces a mechanism to filter closed-loop updates using a conflict-free fallback plan and a monotone upper bound on cost. This restores global progress guarantees to finite-horizon planning.
Budget-Limited Inheritable Factorization: Derives a method to decompose the multi-agent problem into independent groups based on the fleet budget. Crucially, this decomposition is inheritable across timesteps, enabling efficient parallel planning without repeated re-grouping.
CDCBS Algorithm: Instantiates the framework on ACCBS. It combines the reactivity of closed-loop planning with the robustness of global certificates and the efficiency of compositional decomposition.
Theoretical Guarantees: Proves that the algorithm is complete (guaranteed to find a solution) and, under infinite time, optimal (equivalent to standard CBS).

4. Experimental Results

Experiments were conducted on standard MAPF benchmark maps with varying agent densities.

Solution Quality (SOC): CDCBS consistently outperformed ACCBS, particularly in dense environments. While ACCBS degraded rapidly as occupancy increased (due to shortsightedness), CDCBS maintained stable, high-quality solutions.
Monotonic Improvement: As computational budget increased, CDCBS showed predictable, monotonic improvement in solution quality. ACCBS did not exhibit this behavior, often failing to improve despite more time.
Factorization Efficiency: The budget-limited factorization successfully split the fleet into smaller, independent groups. For example, in a 50-agent scenario, the fleet was often split into 6–27 groups, significantly reducing the effective group size for parallel planning.
Backup Controller Sensitivity: Using a higher-quality backup controller (Engineered LaCAM) produced tighter certificates (lower budgets) but did not always result in proportionally better final solution quality, suggesting a trade-off between certificate generation cost and execution performance.

5. Significance

This work bridges a critical gap between scalability and guarantees in multi-agent robotics:

Robustness: It solves the "shortsightedness" problem of closed-loop planning, making it viable for dense, real-world logistics where collisions are frequent.
Scalability: By enabling inheritable factorization, it allows large fleets to be planned in parallel, addressing the computational bottleneck of joint trajectory planning.
Generalizability: While demonstrated on ACCBS, the certificate-based framework is presented as a general mechanism applicable to other closed-loop MAPF algorithms, potentially serving as a standard interface for certified planning in learning-based or hybrid systems.

In summary, the paper provides a rigorous theoretical foundation and a practical algorithm (CDCBS) that ensures safe, efficient, and scalable coordination for large fleets of autonomous agents in dynamic environments.