Reciprocally-Rotating Velocity Obstacles

Modern multi-agent systems frequently use high-level planners to extract basic paths for agents, and then rely on local collision avoidance to ensure that the agents reach their destina-tions without colliding with one another or dynamic obstacles. One of the biggest challenges faced by local collision avoidance techniques is the problem of deadlock, where the method fails to taxi one or more agents to their goals due to local minima or cycling. One state-of-the-art local collision avoidance technique is Reciprocal Velocity Obstacles (RVO). Despite being fast and efficient for circular or spherically-shaped agents, RVO can have a high rate of dead-lock when other shapes are used. To address the deadlocking problem of RVO, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO generalizes RVO by introducing a notion of rotation for polygonally-shaped agents. This generalization permits more realistic motion than RVO and does not suffer from nearly as much deadlock. In this paper, we present RRVO’s theory, discuss its complexity, provide implementation optimizations, and perform an empirical study comparing RRVO and RVO. Our results show that RRVO does not suffer from the deadlock issue of RVO for rectangular agents, at the cost of performance overhead linear in δ, a granularity parameter of RRVO.