V-RVO: Decentralized Multi-Agent Collision Avoidance using Voronoi Diagrams and Reciprocal Velocity Obstacles
This addresses collision avoidance for multi-agent systems in dense settings, but it is incremental as it builds on existing velocity-obstacle methods.
The paper tackles decentralized multi-agent collision avoidance in dense environments by combining buffered Voronoi cells and reciprocal velocity obstacles, achieving passive-friendly guarantees and less conservative behavior than ORCA in scenarios with tens of agents.
We present a decentralized collision avoidance method for dense environments that is based on buffered Voronoi cells (BVC) and reciprocal velocity obstacles (RVO). Our approach is designed for scenarios with large number of close proximity agents 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 for computing a local collision-free path. Our approach can satisfy double-integrator dynamics constraints 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.