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.

Authors

• Liang He 0008
• Jia Pan 0001
• Dinesh Manocha

Keywords

• Bridges
• Trajectory
• Navigation
• Two dimensional displays
• Three-dimensional displays
• Robot kinematics
• Efficient Navigation
• Sensor Networks
• Path Planning
• Multi-agent Systems
• Narrow Region
• Challenging Scenarios
• Goal Position
• Static Obstacles
• Dynamic Obstacles
• Trajectories Of Agents
• Collision-free Path
• Collision-free Trajectory
• Time Cost
• Complex Scenarios
• Start Position
• Number Of Agents
• Individual Goals
• Configuration Space
• Convex Combination
• Parabola
• Start Line
• Challenging Benchmark
• Collision Detection
• Velocity Of Agent
• Trajectory Generation
• Scheduling Scheme
• First Move
• Scheduling Algorithm
• Narrow Area
• Reachable Set