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

Arul, Senthil Hariharan; Manocha, Dinesh · 2021 · OpenAlex-citations

DOI: 10.1109/iros51168.2021.9636618

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper introduces V-RVO, a decentralized collision avoidance algorithm designed for dense multi-agent environments. The research addresses the limitations of existing methods like Optimal Reciprocal Collision Avoidance (ORCA), which often become overly conservative or fail to find feasible solutions when agents are in close proximity or possess higher-order dynamics (e.g., double-integrator constraints). While decentralized methods offer scalability, guaranteeing collision avoidance for agents with acceleration bounds remains challenging. V-RVO aims to provide passive-friendly collision avoidance guarantees that are less conservative than ORCA while maintaining comparable computational performance. The method combines Buffered Voronoi Cells (BVC) with Reciprocal Velocity Obstacles (RVO). Each agent computes a BVC based on neighbor positions, creating a disjoint region that ensures spatial separation. The algorithm superimposes RVO cones onto the BVC to identify safe velocity directions. To accommodate double-integrator dynamics, the authors introduce a braking-aware buffered Voronoi cell (baBVC). This involves calculating a braking distance using kinematic equations to buffer the BVC further, ensuring agents can halt before reaching the cell boundary. The agent selects a target point on the baBVC boundary that minimizes angular deviation from its goal while remaining outside RVO cones. Additionally, the paper proposes a decentralized deadlock resolution strategy where agents in deadlock states coordinate with neighbors to swap positions across shared Voronoi edges. Experimental results demonstrate V-RVO’s effectiveness in scenarios with 25 to 70 agents. In dense benchmarks where ORCA failed to compute collision-free trajectories or resulted in collisions, V-RVO successfully navigated agents to their goals. The algorithm handles both single-integrator and double-integrator dynamics, providing safety guarantees for the latter, which ORCA does not inherently support. Simulation on a standard processor showed that V-RVO’s average runtime is approximately three times slower than ORCA, taking only a few milliseconds per agent. The method also proved robust in handling heterogeneous environments with low-velocity moving obstacles by incorporating additional buffering for stopping distances. The significance of this work lies in its ability to bridge the gap between position-based and velocity-based avoidance methods. By leveraging the geometric properties of Voronoi diagrams for spatial guarantees and RVO for temporal collision avoidance, V-RVO offers a robust solution for high-density robotic applications such as warehouse logistics and urban surveillance. The algorithm’s capacity to handle double-integrator dynamics and resolve deadlocks without centralized coordination makes it a practical advancement for scalable multi-agent systems where prior velocity-obstacle methods are insufficient.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• time to collision looming