Home research People General Info Seminars Resources Intranet

Andrew Giese, "Reciprocally-Rotating Velocity Obstacles," Masters Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, USA, May 2014.
Masters Thesis(ps, pdf, abstract)

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 destinations without colliding with one another or dynamic obstacles. One state-of-the-art local collision avoidance technique is Optimal Reciprocal Collision Avoidance (ORCA). Despite being fast and efficient for circular-shaped agents, ORCA may deadlock when polygonal shapes are used. To address this shortcoming, we introduce Reciprocally-Rotating Velocity Obstacles (RRVO). RRVO extends ORCA by introducing a notion of rotation. This extension permits more realistic motion than ORCA for polygonally-shaped agents and does not suffer from as much deadlock. In this thesis, we present the theory of RRVO and show empirically that it does not suffer from the deadlock issue ORCA has, that it permits agents to reach goals faster, and that it has a comparable collision rate at the cost of some performance overhead.