Efficient multi-agent global navigation using interpolating bridges

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 properties that enable 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 precomputed trajectories of the bridges to handle challenging scenarios. In practice, our approach can perform global navigation for tens to hundreds of agents on a single CPU core in 2D and 3D workspaces.

I. Introduction

At a broad level, prior approaches can be classified into coupled or decoupled planners. A coupled planner aggregates all the individual robots into one large composite system and leverages classical motion planners (e.g., sampling-based planners) to compute collision-free trajectories for all agents. On the other hand, a decoupled planner computes a trajectory for each robot individually for a short horizon (e.g., a few time-steps), and then performs a velocity coordination to resolve the collision between the local trajectories of all agents. Different techniques have been proposed to compute local collision-free paths or schedule their motion.