The multi-agent path finding (MAPF) problem navigates a large number of agents from start points to end points on a map while avoiding obstacles and collisions. Applications include warehouse logistics, airport logistics, unmanned aerial vehicle traffic management, parking navigation, and video games.
When agents move continuously, such as in automated package delivery in warehouses, this shifts to a new paradigm called lifelong MAPF (L-MAPF). As agents reach a destination, they are immediately assigned a new destination. They must attain high throughput, such as delivered packages, while avoiding collisions with obstacles and other agents.
A wide range of methods have been proposed for this lifelong setting. One important baseline is Priority Inheritance with Backtracking (PIBT), an ultra-fast and scalable method that serves as a strong baseline but can have greedy behavior. In contrast to PIBT, another popular solution is the Rolling-Horizon Collision Resolution (RHCR) framework, which is considered one of the highest-performing solutions in terms of attaining high throughput.
Unfortunately, RHCR has a high computational cost, especially when compared with PIBT. In practical scenarios such as robot navigation in warehouses, RHCR must repeatedly use one-shot MAPF solvers in a short amount of time. Even when using suboptimal solvers such as Priority Based Search (PBS), we observe that RHCR grows exponentially in computational cost. Within the research community, running RHCR as a baseline is considered a computationally expensive part of running simulations and often requires reporting a partial plan before timeouts or running on a smaller subset of problems. In practice, RHCR can be used with a fallback mechanism that switches to another algorithm, such as PIBT, when a timeout is reached.
While it is tempting to speed up RHCR by developing parallelized versions across agents, it remains open how to do so in a theoretically principled way without sacrificing RHCR’s performance.
Contributions
The goal of this work is to develop theoretically principled parallelized RHCR methods that maintain or exceed the high throughput of RHCR while planning with a fraction of its computational cost. Towards this goal, we build a novel theoretical foundation for RHCR, which leads to a theoretically principled parallelization of RHCR called Group Decentralized RHCR (GD-RHCR).
For small agent counts that RHCR can already handle, GD-RHCR achieves similar throughput in many cases with significantly faster planning speed. For large agent counts that only PIBT can handle, GD-RHCR can also solve them while consistently achieving higher throughput.
Experimental Validation
We demonstrate GD-RHCR empirically across a variety of maps. The average planning time can be reduced by a factor of [the reported speedup factor] and match RHCR in performance before RHCR collapses. GD-RHCR also performs well deeper into the large-agent range and shows up to [the reported throughput improvement] improvement in throughput against PIBT and collapsed RHCR.
Related Work
Learning-Based MAPF Methods
Learning-based methods use reinforcement learning or imitation learning directly to solve the MAPF problem. These methods can perform some parallelism through decentralization, yet there is no guarantee on how much performance is lost due to parallelization or decentralization.
Lifelong MAPF
Lifelong MAPF literature is largely divided between slow but high-quality solutions provided by RHCR and fast but greedy solutions such as PIBT.
RHCR enables the conversion of one-shot MAPF solvers to the lifelong setting but may incur a large computation time because one-shot MAPF is NP-hard.
PIBT is a method that can be used in either the one-shot context or the lifelong setting. PIBT and its variations remain fast alternatives, but they are greedy and can often suffer from deadlocks when the graph is not biconnected.
Analogously, multi-agent reinforcement learning and imitation-learning methods have also been developed for this setting.
Grouping in MAPF
Several prior works attempt to speed up computation by grouping agents. A static grouping method can divide the map into subregions and treat agents in each subregion as a group. In another context, more sophisticated methods attempt to dynamically identify independent groupings.
This is done in the context of speeding up an algorithm that maintains completeness guarantees rather than identifying coordination groups that may perform well together.
Locally Interdependent Multi-Agent MDP
Adjacent to the MAPF literature, there has been a recent breakthrough in the study of discounted multi-agent Markov decision process environments with dynamic local dependencies. A model called the Locally Interdependent Multi-Agent MDP (LI-MDP) was proposed as a theoretical model for multi-agent systems with local interactions.
The same works proposed the group decentralized setting, which connects agents transitively based on their visibility. Connected agents are allowed to coordinate. This special observability structure, positioned between centralized and decentralized settings, permits strong theoretical guarantees that are not available in the decentralized setting, including performance exponentially close to optimal with respect to visibility, while still allowing groups of agents to plan in parallel.
The LI-MDP framework provides insight into the effectiveness of existing methods such as RHCR, supports proofs of near optimality, and can be used to propose new methods such as GD-RHCR that integrate this observability structure.
Conclusion and Future Work
This work provides a theoretical grounding for RHCR using methods from the LI-MDP literature. We then use those analytical techniques to motivate the new GD-RHCR framework, which satisfies theoretical guarantees similar to those of RHCR and performs well empirically across many maps at larger agent counts than RHCR.
Group decentralization is a relatively new concept in the MAPF community and can be integrated in various ways. For example, it could be combined with traditional learning-based methods or used to parallelize other methods such as PIBT. This work also creates a simple setup for using different algorithms in different locations or settings, opening many research directions.
Acknowledgements
Guannan Qu is supported by NSF Grants 2339112 and 2512805, Jane Street, and the Pennsylvania Infrastructure Technology Alliance. Jiaoyang Li is supported by NSF Grants 2328671 and 2441629. Alex DeWeese is supported by the Leo Finzi Memorial Fellowship in Electrical & Computer Engineering, the David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship, and the Fritsch Family Fellowship.
Ablation Simulations
The outcome of the ablation simulations on warehouse-10-20-10-2-1 is shown in the paper’s ablation results.
Frequently Asked Questions
What is lifelong multi-agent path finding? Lifelong MAPF continuously assigns agents new destinations as they reach previous destinations while requiring collision avoidance and high throughput.
Why is RHCR computationally expensive? RHCR repeatedly uses one-shot MAPF solvers, whose computational cost can grow exponentially and cause timeouts at larger agent counts.
What is GD-RHCR? GD-RHCR is a group-decentralized parallelization of RHCR that allows groups of agents to coordinate and plan in parallel.
How does GD-RHCR compare with PIBT? GD-RHCR solves larger agent counts than RHCR and achieves consistently higher throughput than PIBT in the reported experiments.