P3GASUS: Pre-Planned Path Execution Graphs for Multi-Agent Systems at Ultra-Large Scale
Tanishq Harish Duhan, Chengyang He, Guillaume Adrien Sartoretti
AI summary
Problem
Existing execution graphs like ADG suffer from biquadratic computational complexity and high communication overhead, making them impractical for ultra-large multi-agent systems and continuous-space scenarios.
Approach
The authors introduce P3GASUS, which converts pre-planned paths into optimized execution graphs using three new algorithms (SAGE, MAGE, FORTED) that drastically cut computation and communication costs, paired with a robust distributed execution framework.
Key results
- 300–8000× speedup in graph construction over ADG
- Over 14× reduction in communication overhead via edge pruning
- O(RT) complexity enabling 10,000-agent graph generation in ~74 seconds
- Validated on hybrid real-virtual teams of up to 3,000 robots
Why it matters
Provides a practical, scalable foundation for deploying large-scale robot swarms in real-world logistics, warehousing, and continuous-space applications.
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 edgesrepresentingtheexecutionprecedenceorderbetweenactions. However, ADG’s creation phase currently requires an exhaustive search of the action space that inflates both computation and communication (O(R2 ̃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 commu- nication 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 integrating these methods with a framework for robust distributed path ex- ecution for both discrete and continuous scenarios, we introduce P3GASUS, an end-to-end method for pre-planned path execution in multi-agent systems. Finally, we validate the effectiveness of P3GASUS in discrete and continuous multi-agent scenarios using hybrid (real and virtual) teams with up to 3000 robots.