Search papers, labs, and topics across Lattice.
This paper establishes a theoretical framework for the Lifelong Multi-Agent Path Finding (L-MAPF) problem, demonstrating the near-optimality of the Rolling-Horizon Collision Resolution (RHCR) method within a discounted MDP context. It introduces the Group Decentralized RHCR (GD-RHCR) framework, which enhances scalability by partitioning agents into groups for parallel planning, thus reducing computational costs while maintaining solution quality. The findings reveal that GD-RHCR achieves performance comparable to RHCR but with significantly improved throughput for larger agent counts.
Group Decentralized RHCR achieves high throughput for multi-agent pathfinding while slashing computational costs, making it viable for larger agent counts.
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.
CMU ML