Efficient Multi-Agent Global Navigation Using Interpolating Bridges
This addresses efficient navigation for multi-agent systems in crowded environments, representing an incremental improvement by combining existing techniques.
The paper tackles the problem of collision-free global navigation for continuous-time multi-agent systems in 2D and 3D workspaces by pre-computing bridges in narrow regions and combining them with local algorithms at runtime, enabling real-time handling of tens to hundreds of agents on a single CPU core.
We present a novel approach for collision-free global navigation for continuous-time multi-agent systems with general linear dynamics. Our approach is general and can be used to perform collision-free navigation in 2D and 3D workspaces with narrow passages and crowded regions. As part of pre-computation, we compute multiple bridges in the narrow or tight regions in the workspace using kinodynamic RRT algorithms. Our bridge has certain geometric characteristics, that en- able us to calculate a collision-free trajectory for each agent using simple interpolation at runtime. Moreover, we combine interpolated bridge trajectories with local multi-agent navigation algorithms to compute global collision-free paths for each agent. The overall approach combines the performance benefits of coupled multi-agent algorithms with the pre- computed trajectories of the bridges to handle challenging scenarios. In practice, our approach can handle tens to hundreds of agents in real-time on a single CPU core in 2D and 3D workspaces.