Velocity Obstacles

A method that marks the set of velocities in velocity space that would cause a collision, then picks a safe one closest to what's desired.

Velocity obstacles (VO) were introduced by Paolo Fiorini and Zvi Shiller in a 1998 IJRR paper: assuming an obstacle keeps its current velocity, the method collects every velocity that would collide with it at some future time into a cone-shaped region in velocity space, and picking any velocity outside that cone avoids collision. When multiple robots do this at once, they tend to dodge in sync and then swing back in sync, oscillating. In 2008, Jur van den Berg and colleagues proposed reciprocal velocity obstacles (RVO), which assume the other side dodges too; van den Berg, Stephen Guy, Ming Lin, and Dinesh Manocha then proposed ORCA (Optimal Reciprocal Collision Avoidance, formally published in 2011), where each pair of agents takes on exactly half the responsibility for avoiding each other. Each neighbor's constraint becomes a half-plane in velocity space, and solving a low-dimensional linear program picks the feasible velocity closest to the one the agent actually wants. ORCA needs no communication and can handle thousands of agents in real time; the open-source RVO2 library that implements it is widely used in crowd simulation, games, and multi-robot navigation. It only accounts for velocity and geometry, not more complex dynamics.

ExampleSeveral autonomous mobile robots (AMRs) in a warehouse meet at an intersection. Each independently computes its move with ORCA, taking on half the avoidance responsibility for each neighbor, so all of them swerve and slow slightly and pass through without needing any central coordination.

Also called

VO, Reciprocal Velocity Obstacles (RVO), Optimal Reciprocal Collision Avoidance (ORCA), RVO2

Related

Obstacle Avoidance · Social Navigation · Multi-Agent Path Finding · Multi-robot Collaboration · Dynamic Window Approach · Autonomous Mobile Robot

Sources

Fiorini, Shiller: Motion Planning in Dynamic Environments Using Velocity Obstacles (IJRR 1998)
ORCA: Optimal Reciprocal Collision Avoidance（UNC GAMMA 项目页） (Chinese)
RVO2 Library: Reciprocal Collision Avoidance for Real-Time Multi-Agent Simulation