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.
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.
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