  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.
