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

Senthil Hariharan Arul, Dinesh Manocha

Abstract

Presented at ICRA 2021, V-RVO is a hybrid decentralized navigation algorithm designed for large-scale robotic swarms. By integrating the spatial partitioning of Buffered Voronoi Cells (BVC) with the velocity-space reasoning of Reciprocal Velocity Obstacles (RVO), V-RVO enables fluid navigation in dense environments while accounting for complex agent dynamics and resolving deadlocks.

Introduction

In multi-agent robotics, navigation requires a delicate balance between goal-seeking and decentralized collision avoidance. Traditional methods like Optimal Reciprocal Collision Avoidance (ORCA) often become overly conservative in high-density scenarios, leading to "freezing" behaviors or constraint violations. Conversely, position-based methods like BVC provide robust spatial partitioning but often struggle to account for high-speed momentum and acceleration limits (double-integrator dynamics). V-RVO addresses these limitations by combining spatial partitioning with velocity-space reasoning.

Methodology

The V-RVO framework employs a multi-layered strategy to ensure safety and efficiency in crowded spaces.

1. Hybrid RVO-BVC Integration

Instead of choosing between position-based or velocity-based avoidance, V-RVO utilizes both. It calculates an agent's local Buffered Voronoi Cell (its safe zone) and overlays RVO collision cones—velocities that would lead to future collisions. The agent then selects a target velocity toward a point on the BVC boundary that stays clear of these collision cones.

Integration of RVO cones within a Buffered Voronoi Cell (BVC) to determine a safe target point.

2. Braking-aware BVC (baBVC)

To handle agents with double-integrator dynamics that cannot stop instantaneously, V-RVO introduces a "retraction" mechanism. The Voronoi cell is shrunk based on the agent's current speed and maximum braking power. This ensures "passive-friendly" safety: even if an agent needs to stop suddenly, it maintains enough buffered space to do so without encroaching on a neighbor's territory.

Geometry of the Braking-aware BVC (baBVC), showing the retraction distance based on agent velocity.

3. Deadlock Resolution

The algorithm includes a state-machine logic (DEFAULT, HOLD, and DEADLOCK modes). If an agent identifies that it is stuck because neighbors are blocking its path, it coordinates a "position swap" with a neighbor to break the gridlock and restore flow.

Evaluation and Results

The researchers evaluated V-RVO using custom simulation benchmarks, including circular swaps of up to 70 agents and grid formation tasks.

  • Superior Density Handling: In high-density scenarios (e.g., 70 agents), V-RVO successfully navigated all agents to their goals, whereas ORCA resulted in collisions due to unsatisfiable constraints.
  • Real-time Performance: V-RVO requires approximately 1–2ms per agent for control input computation. While slower than ORCA, it remains well within the requirements for real-time robotics (10–50Hz) and scales linearly with the number of agents.
  • Dynamic Feasibility: Unlike standard BVC, V-RVO successfully provided smooth, collision-free trajectories for agents with acceleration and velocity bounds.

Conclusion and Future Work

V-RVO demonstrates that position-space and velocity-space reasoning are complementary. By merging them, the algorithm overcomes the conservativeness of ORCA and the dynamic limitations of BVC. Future research will focus on handling sensor noise, non-holonomic constraints, and further optimizing the Voronoi and baBVC implementations for increased speed.

Summary updated

BibTeX
@inproceedings{arul2021v,
  author = {Senthil Hariharan Arul and Dinesh Manocha},
  title = {{V-RVO: Decentralized Multi-Agent Collision Avoidance using Voronoi Diagrams and Reciprocal Velocity Obstacles}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=bJ512us6ZC},
}
Figure