Fast Decentralized Multi-Agent Collision Avoidance Based on Safe-Reachable Sets

This paper presents a decentralized multi-agent collision avoidance method for systems with single integrator dynamics and identical maximum speeds. The key to our approach lies in the concept of safe-reachable sets, which define the set of positions that each agent can reach while avoiding collisions with its neighbors for any admissible controllers. With this concept, we develop a distributed controller by solving an online convex program, which is shown to guarantee collision-free trajectories. Furthermore, under a no temporary deadlock condition, we establish that each agent converges to its target position. Our approach is also efficient in terms of makespan, representing the total time needed for convergence. Simulation results demonstrate the effectiveness of our approach in terms of safety, convergence, and efficiency.