A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning
Authors: Alex DeWeese, Jiaoyang Li, Guannan Qu
Organizations: Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, US · Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, US
In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.
Figures & tables
Figure 1: k agents with goal locations Gi on the right. Arrows depict timestep of first movement.
Figure 2: Group decentralized partitioning for V=2 . Groups are connected by lines and color coded (colors are reused).
Figure 3: MAPD simulations. Agents move between red stars and blue squares. Color coding is GD-RHCR , RHCR , and PIBT
Figure 4: Random navigation simulations. The color coding is GD-RHCR , RHCR , and PIBT
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 5: Warehouse-10-20-10-2-1 abalation simulations: red , orange , pink , purple , brown is least to most of value (see legend)
Figure 6: Wall times for MAPD. The color coding is GD-RHCR , RHCR , and PIBT
Figure 7: Wall times for random navigation. The color coding is GD-RHCR , RHCR , and PIBT
Figure 8: MAPD group statistics for GD-RHCR. The color coding is GD-RHCR
Figure 9: Random navigation group statistics for GD-RHCR. The color coding is GD-RHCR