P3GASUS: Pre-Planned Path Execution Graphs for Multi-Agent Systems at Ultra-Large Scale

Abstract

Executing pre-planned paths in multi-agent systems is challenging, as a lack of synchronization can lead to collisions or live-/deadlocks, while enforcing strict synchronization may cause a widespread team delay in reaching goals. An Action Dependency Graph (ADG) solves this problem by identifying and synchronizing only the necessary robots during execution by post-processing all agents’ paths into a static directed graph with actions as nodes and edges representing the execution precedence order between actions. However, ADG's creation phase currently requires an exhaustive search of the action space that inflates both computation and communication (O(R^2 T^2), where R is the number of robots and T is the maximum path length). This makes ADG the bottleneck for current state-of-the-art MAPF planners, which can solve for up to 10000 agents, and lifelong MAPF, which needs constant replanning during execution. Moreover, this biquadratic scaling also limits the extension of ADG to continuous space scenarios, where high-frequency updates typically effectively result in long path lengths. Addressing these limitations, in this work, we propose three improved execution graphs to cater to different needs and scenarios: SAGE, which adds edges based on the sequence in which robots visit a position; MAGE, which takes the execution graph of SAGE as input and prunes its redundant edges, reducing communication burden during execution; and FORTED which combines both approaches with a reduced complexity of O(RT), making it the overall best in discrete scenarios, trading-off scalability to continuous space scenarios. All three methods achieve speedups of 300-8000 folds over ADG, with MAGE and FORTED reducing communication overhead by more than 14 times. By integr