V-RVO: Decentralized Multi-Agent Collision Avoidance using Voronoi Diagrams and Reciprocal Velocity Obstacles

We present a decentralized collision avoidance method for dense environments based on buffered Voronoi cells (BVC) and reciprocal velocity obstacles (RVO). Our approach is designed for scenarios with a large number of agents in close proximity and provides passive-friendly collision avoidance guarantees. The Voronoi cells are superimposed with RVO cones to compute a suitable direction for each agent, and we use that direction to compute a local collision-free path. Our approach can also satisfy double-integrator dynamics, and we use the properties of the BVC to formulate a simple, decentralized deadlock resolution strategy. We demonstrate the benefits of V-RVO in complex scenarios with tens of agents in close proximity. In practice, V-RVO’s performance is comparable to prior velocity-obstacle methods, and the collision avoidance behavior is significantly less conservative than ORCA.