🤖 AI

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

This paper theoretically proves the near-optimality of the Rolling-Horizon Collision Resolution (RHCR) framework for Lifelong Multi-Agent Path Finding and leverages this insight to propose Group Decentralized RHCR (GD-RHCR), a parallel planning approach that partitions agents to achieve high throughput and scalability with significantly lower computational costs while maintaining near-optimal guarantees.

Original authors: Alex DeWeese, Jiaoyang Li, Guannan Qu

Published 2026-08-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Alex DeWeese, Jiaoyang Li, Guannan Qu

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

In the bustling, automated world of modern logistics, a silent challenge plays out on digital maps every second. Imagine a warehouse floor where hundreds of small robots must move packages from one point to another, constantly navigating around shelves, walls, and each other. This is the realm of multi-agent pathfinding, a field dedicated to figuring out how to get many moving things from a start to a finish without them crashing. When these robots are just making a single trip, the problem is difficult but manageable. However, in a real warehouse, the work never stops; as soon as a robot drops off a package, it is immediately assigned a new one. This continuous cycle is known as lifelong pathfinding. The goal is simple: keep the robots moving as fast as possible to maximize the number of packages delivered. The difficulty lies in the math; as more robots are added to the floor, the number of possible ways they can collide grows so fast that the computers trying to plan their routes can become overwhelmed, slowing the entire operation to a halt.

Researchers have long sought a balance between speed and safety. One popular method, called rolling-horizon collision resolution, works by looking a short distance into the future to plan safe paths for all robots at once. This approach is excellent at keeping traffic flowing smoothly and avoiding jams, but it comes with a heavy price: the computer has to do a massive amount of work every few seconds to calculate these paths for every single robot simultaneously. Another method is incredibly fast but often makes greedy, short-sighted decisions that can lead to deadlocks where robots get stuck waiting for each other. The central question for the researchers at Carnegie Mellon University was whether they could keep the high performance of the careful, slow method while making it fast enough to handle hundreds of robots without crashing the computer.

The team, led by Alex DeWeese, Jiaoyang Li, and Guannan Qu, approached this by rethinking how the robots communicate and plan. They started by proving a theoretical point: the careful, slow method works well because it ignores interactions that are too far away in time. If a robot is planning its path for the next twenty steps, it does not need to worry about a collision that might happen in fifty steps. Building on this insight, they proposed a new framework called Group Decentralized Rolling-Horizon Collision Resolution. Instead of treating the entire warehouse as one giant problem to be solved all at once, this new system divides the robots into smaller, independent groups based on how close they are to one another. Robots that are far apart are placed in different groups and are allowed to plan their routes in parallel, effectively ignoring each other for the duration of the plan.

This division is not arbitrary; it is based on a specific distance threshold. If two robots are within a certain range, they are considered part of the same group and must coordinate to avoid hitting each other. If they are outside that range, the system assumes they cannot possibly collide within the planning window, so they can be planned separately. The researchers proved mathematically that this separation does not significantly hurt the quality of the solution. In fact, they showed that the performance of this new group-based method stays extremely close to the optimal solution, just like the original, slower method. The key difference is that by breaking the problem into smaller chunks, the computer can solve each chunk much faster. Furthermore, the system is smart enough to only re-plan for groups when necessary. If a group of robots is moving smoothly on a pre-calculated path, the computer does not waste time recalculating their route until something changes, such as a new robot entering their zone.

To test their idea, the researchers ran extensive simulations on various map layouts, ranging from simple open floors to complex warehouse designs with many obstacles. They compared their new method against the standard careful approach and the fast, greedy approach. The results were striking. In many scenarios, the new method achieved nearly the same high throughput—delivering almost as many packages per hour—as the careful, slow method, but it did so with a fraction of the computing power. In some tests, the time required to calculate a single plan was reduced by a factor of nearly twenty-five. More importantly, the new method did not break down when the number of robots increased. While the standard careful method would eventually become too slow to be useful as the robot count grew, the group-based method continued to perform well, handling hundreds of agents where the old method would fail.

The study also revealed how the physical layout of the environment influences the success of the method. In maps with many obstacles and narrow passages, the robots naturally form smaller, distinct groups because they cannot see or reach each other across the barriers. This topology allows the new method to work even better, as the groups remain small and independent for longer. In contrast, on very open maps with few obstacles, the robots tend to form larger groups, which requires more coordination, but the system still managed to outperform the greedy alternatives. The researchers also found that the system could adapt to congestion by switching to a faster, simpler planning algorithm for specific groups that became too crowded, ensuring that the entire system kept moving even in the most difficult conditions.

This work demonstrates that by understanding the theoretical limits of how far ahead a robot needs to look, engineers can design systems that are both safe and scalable. The new framework offers a way to keep automated warehouses running at peak efficiency without needing supercomputers to manage the traffic. It suggests that the future of large-scale robotics may not rely on a single, massive brain calculating every move for every machine, but rather on a network of smaller, coordinated minds working in parallel. The researchers have shown that it is possible to have the best of both worlds: the safety and smoothness of careful planning, combined with the speed and scalability needed for real-world applications. As automated systems become more common in our daily lives, from delivery drones to factory floors, methods like this will be essential for ensuring that the machines work together seamlessly, turning the complex chaos of a busy warehouse into a fluid, efficient flow.

Technical Summary: A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

1. Problem Statement

The paper addresses the Lifelong Multi-Agent Path Finding (L-MAPF) problem, where agents must continuously navigate from one destination to another on a map while avoiding obstacles and inter-agent collisions. The primary objective is to maximize throughput (e.g., the number of goals achieved per unit time).

While the Rolling-Horizon Collision Resolution (RHCR) framework is widely regarded as a high-performing solution for L-MAPF, it suffers from a significant computational bottleneck. RHCR repeatedly invokes one-shot MAPF solvers (such as Priority Based Search or Conflict Based Search) at short intervals. As the number of agents increases, the computational cost of these solvers grows exponentially, limiting RHCR's applicability to modest agent counts. Conversely, faster, greedy methods like Priority Inheritance with Backtracking (PIBT) scale well but often lack theoretical optimality guarantees and can suffer from deadlocks.

The central challenge is to develop a parallelized version of RHCR that maintains its high throughput and theoretical performance guarantees while drastically reducing computational costs, without resorting to ad-hoc heuristics.

2. Methodology

Theoretical Foundation: LI-MDP

The authors ground their approach in the Locally Interdependent Multi-Agent MDP (LI-MDP) framework (DeWeese and Qu 2024, 2025). They model the L-MAPF problem as a discounted MDP where agents have local interactions defined by a visibility radius.

RHCR Analysis: The paper first proves that vanilla RHCR is near-optimal in this discounted setting. Specifically, the suboptimality gap between RHCR and the optimal policy decreases exponentially as the planning horizon ( $H$ ) increases. Crucially, this guarantee is independent of the replanning window ( $\alpha$ ), providing a theoretical justification for using shorter replanning windows to improve efficiency.
Group Decentralization: The LI-MDP literature suggests that agents can be partitioned into groups based on a transitive communication scheme (connectivity within a distance $V$ ) without sacrificing near-optimality. Agents in different groups cannot collide within a certain number of steps ( $\lfloor V/2 \rfloor$ ), allowing them to plan in parallel.

The Proposed Algorithm: Group Decentralized RHCR (GD-RHCR)

Building on the theoretical duality between time-based restrictions (RHCR) and space-based partitioning (GD-RHCR), the authors propose GD-RHCR. The algorithm operates as follows:

Group Partitioning: At each timestep, agents are partitioned into groups based on connected components within a visibility radius $V$ (using shortest-path distance).
Deferred Evaluation: Instead of replanning all groups at every step, the system employs a "deferred" strategy. Groups only recompute plans if the agents within them disagree on the current plan or if the plan is exhausted. This dynamically adjusts the effective replanning window for different subsets of agents.
Soft Constraints: When planning for a specific group, the algorithm incorporates "soft constraints" based on the planned trajectories of agents in other groups from the previous timestep. This allows the planner to account for potential future collisions without treating other groups as hard obstacles, which would be computationally prohibitive.
Heterogeneous Solvers & Fallback: The framework supports assigning different solvers to different agent groups.
- Small groups are solved using high-quality, potentially slower solvers (e.g., PBS).
- Large, congested groups (exceeding a threshold $K_{threshold}$ ) are immediately handed off to a fast, scalable solver (e.g., PIBT).
- Unlike RHCR, where a fallback is a "failure" mode triggered by timeout, GD-RHCR treats the use of a faster solver for large groups as an integral part of the algorithm, allowing the system to speed up as congestion increases.

3. Key Contributions

Theoretical Proof of RHCR Near-Optimality: The paper establishes that RHCR converges to an optimal solution exponentially fast with respect to the planning horizon in a discounted MDP formulation of L-MAPF.
Theoretical Duality: It demonstrates a theoretical duality between the time-based restrictions of RHCR and the space-based partitioning of GD-RHCR, proving that GD-RHCR satisfies similar near-optimality guarantees (up to constant factors).
GD-RHCR Framework: The introduction of a novel, theoretically principled parallel planning framework that partitions agents into groups, utilizes deferred evaluation, and integrates soft constraints.
Scalability and Efficiency: The method enables the use of different solvers for different agent groups, balancing solution quality and computational efficiency. It significantly reduces the per-plan computational cost compared to vanilla RHCR.

4. Experimental Results

The authors evaluated GD-RHCR across various maps (warehouse, sortation, and random navigation environments) and agent counts, comparing it against RHCR (with PIBT fallback) and PIBT alone.

Performance vs. RHCR: For agent counts where RHCR is viable, GD-RHCR achieves comparable throughput (within $\approx 2\%$ in tested scenarios) but reduces the average plan time by a factor of 24.9x.
Scalability: GD-RHCR extends the viable range of RHCR to much higher agent counts. In dense warehouse scenarios with 800 agents, GD-RHCR achieved a 57.7% improvement in throughput compared to collapsed RHCR/PIBT, while maintaining low per-plan costs.
Topological Influence: The method performs best in maps with dense obstacles and complex topologies (e.g., warehouses) where the shortest path differs significantly from the Manhattan distance, naturally inducing smaller, independent groups. In simpler or smaller maps, the advantage diminishes as groups become larger, but the method still remains computationally efficient.
Robustness and Limitations: The performance of GD-RHCR is sensitive to map topology. In maps that are not biconnected (e.g., random-32-32-20 and room-32-32-var1), PIBT can suffer from deadlocks. Since GD-RHCR relies on PIBT for large groups, it may experience reduced performance in these specific environments if it is forced to rely on PIBT before RHCR would have collapsed. However, in dense maps where groups remain small and separated, GD-RHCR maintains high throughput and avoids these deadlock issues.

5. Significance and Claims

The paper claims that GD-RHCR provides a theoretically grounded solution to the computational limitations of RHCR. By leveraging the LI-MDP framework, the authors move beyond heuristic parallelization, offering a method that:

Retains the high-throughput advantages of RHCR.
Scales to agent counts previously only manageable by greedy, suboptimal methods like PIBT (in suitable topologies).
Offers a modular framework where different planning algorithms can be dynamically assigned based on group size and congestion.

The authors emphasize that this work opens new research directions for integrating group decentralization into other MAPF methods and learning-based approaches, establishing a new paradigm for balancing theoretical guarantees with computational scalability in lifelong multi-agent systems.