Velocity Obstacles (ORCA)

Imagine a busy pedestrian plaza: dozens of people weaving past each other, none colliding, none needing a central coordinator. Each person glances ahead, adjusts their pace, and the crowd flows. How does that work — and can a computer reproduce it for robots or virtual characters?

The answer lies in a deceptively elegant idea called the Velocity Obstacle (VO), introduced by Paolo Fiorini and Zvi Shiller in 1998. For any pair of moving objects, a velocity obstacle is the set of all velocities that would lead to a future collision — a cone-shaped region in the space of possible speeds and directions. If an agent picks a velocity outside every such cone, it is provably guaranteed never to hit anything.

That transforms collision avoidance from a messy trial-and-error search into a clean geometric exclusion test: subtract the forbidden cone, pick freely from what remains. In 2008, Jur van den Berg and colleagues extended the idea to the Optimal Reciprocal Collision Avoidance (ORCA) algorithm, which shares the avoidance burden symmetrically across all agents so that no two agents ever have to take the full blame — or make the full detour — alone.

The canvas below runs a small crowd of agents. Each frame, every agent computes the velocity obstacles cast by its neighbors and picks the closest velocity to its preferred direction that lies outside all of them.

<!-- {{c_layout}} -->
<div class="toolbar">
  <button id="btn-add" type="button">{{btn_add}}</button>
  <button id="btn-pause" type="button">{{btn_pause}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  <span id="info" class="info"></span>
</div>
<canvas id="cv"></canvas>
<p class="hint">{{hint_para}}</p>

/* {{c_reset}} */
* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; background: #f5f7fa; color: #222; }
.toolbar { display: flex; gap: .5rem; align-items: center; padding: .5rem .4rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:hover { opacity: .85; }
.info { font-size: .82rem; color: #555; }
canvas { display: block; width: 100%; background: #e9edf2; border-radius: 6px; }
.hint { font-size: .8rem; color: #666; padding: .4rem .4rem 0; line-height: 1.45; }

// Code not found

Press Add agents to increase the crowd. Notice that even with many agents moving in opposite directions, no two ever touch — not by luck, but because every chosen velocity is geometrically guaranteed to be safe for at least the next time step. Press Pause to freeze the scene and study the configuration.

Velocity obstacles are fast in practice. Why, and how hard can collision avoidance actually get?

How ORCA works per agent. Each agent $A$ considers every neighbor $B$. In the relative-velocity frame, the set of velocities that would put $A$ on a collision course with $B$ within time horizon $\tau$ forms a truncated cone in 2-D velocity space. ORCA halves the avoidance responsibility: it finds the half-plane boundary of the cone closest to the current velocity and assigns half the correction to $A$ and half to $B$. Each agent must then choose a velocity in the intersection of all the allowed half-planes — a convex region — that is closest to its goal velocity. That is a small linear program with $O(n)$ constraints, solvable in $O(n)$ time by the randomized incremental LP algorithm.

The cost per frame is $O(n^2)$ (each of $n$ agents queries $n-1$ neighbors), which stays fast for crowds of hundreds. With spatial indexing (a $k$-d tree), each agent only queries nearby neighbors, pushing the practical cost far lower.

The hard part: global optimality. ORCA gives each agent a locally optimal, collision-free velocity, but it makes no promise that the joint velocity assignment is globally optimal. Finding a joint plan that minimizes total travel time while avoiding collisions for $n$ agents with full future lookahead is PSPACE-hard — and even approximate solutions carry exponential worst-case costs. This is closely related to the difficulty of motion planning in high-dimensional configuration spaces.

Completeness. ORCA is not complete: in dense or narrow environments it can deadlock. A corridor so tight that two agents must pass single-file has no ORCA solution without one agent reversing. Practical systems add a small random perturbation or a higher-level planner to escape such traps.

The take-away: per-frame local geometry is cheap and provably safe; globally optimal many-agent planning remains as hard as any problem we know how to make hard.

Velocity obstacles and ORCA appear wherever many autonomous agents must move without a central conductor:

• Video-game crowds: ORCA (shipped as RVO2, an open-source library) drives the pedestrian AI in titles from Hitman to stadium simulations — thousands of NPCs flowing naturally without scripted paths.
• Autonomous vehicles: multi-lane roundabout planning, intersection management, and platoon merging all use VO-based deconfliction to give each car a safe velocity without explicit negotiation.
• Drone swarms: formation flight and delivery fleets use ORCA variants to guarantee separation even when radio links introduce small delays.
• Robot warehouses: packing robots (like those in Amazon fulfillment centers) use reciprocal avoidance to route hundreds of platforms without centralized scheduling for every move.
• Pedestrian science: urban planners use ORCA-based simulations to predict crowd flow in stadiums, train stations, and emergency evacuations, spotting dangerous bottlenecks before they occur.

The common thread: whenever the number of agents makes centralized path-planning intractable, local geometry — the velocity obstacle — makes safe decentralized motion possible. It is the same principle behind how actual pedestrians avoid each other, now made mathematically precise.

The velocity obstacle is a beautiful geometric object: a cone in the space of velocities that precisely characterizes every dangerous choice. Step outside every such cone and you are safe — not probably, but provably. ORCA shares that safety burden fairly across all agents, reducing the problem per agent to a tiny linear program solvable in milliseconds.

The hard truth is that local safety is easy; global optimality is not. Coordinating many agents to minimize joint travel time is PSPACE-hard, and no one has found a general shortcut. What ORCA offers instead is something arguably more useful: a fast, decentralized, and provably collision-free heuristic that works well in the same settings where centralized planning breaks down.

Next time you watch a crowd navigate a plaza without bumping — or see a swarm of drones fly in formation — you are watching velocity obstacles at work. The math is simple enough to fit on a page, yet powerful enough to replace a room full of traffic controllers. That is the recurring miracle of the right geometric abstraction.