Introduction

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.

Try It: A Collision-Free Crowd

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.

<!-- Main layout: toolbar + canvas + hint -->
<div class="toolbar">
  <button id="btn-add" type="button">Add agent</button>
  <button id="btn-pause" type="button">Pause</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <span id="info" class="info"></span>
</div>
<canvas id="cv"></canvas>
<p class="hint">Each disc heads toward its faded goal dot. Every frame each agent samples candidate velocities and picks the one closest to its goal that lies <em>outside</em> every velocity-obstacle cone — the set of velocities leading to a future collision with each neighbor.</p>

/* Box-model reset and base layout */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* Velocity Obstacle (VO) demo — discrete candidate sampling. */
/* Concept: Fiorini & Shiller (1998). Sampling variant for clarity. */

const CV = document.getElementById('cv');
const CTX = CV.getContext('2d');
const INFO = document.getElementById('info');

// Fixed logical canvas size
const W = 460, H = 360;
CV.width = W; CV.height = H;
CV.style.maxHeight = H + 'px';

// Simulation constants
const R = 11;         // agent radius in pixels
const TAU = 60;       // look-ahead time horizon in frames
const MAX_SPD = 1.4;  // maximum speed in pixels per frame
const DT = 1.0;       // time step per animation frame
const SAMPLES = 36;   // number of angular samples per velocity ring

let paused = false;
let agents = [];
let frame = 0;

// Agent colour palette
const COLORS = ['#e63946','#457b9d','#2a9d8f','#e9c46a','#f4a261','#6a4c93','#1d3557','#4cc9f0'];

function mkAgent(x, y, gx, gy, ci) {
  // Agent state: current position, velocity, goal position
  return { x, y, vx: 0, vy: 0, gx, gy, color: COLORS[ci % COLORS.length] };
}

function initAgents() {
  agents = [];
  // Place agents on a circle, each heading to an offset opposite point
  const cx = W / 2, cy = H / 2, r = 110;
  const N = 6;
  for (let i = 0; i < N; i++) {
    const a = 2 * Math.PI * i / N;
    // goal angle offset keeps agents from all meeting at the exact center goal angle offset keeps agents from all meeting at the exact center
    const ga = a + Math.PI + 0.35;
    agents.push(mkAgent(cx + r * Math.cos(a), cy + r * Math.sin(a),
                        cx + r * Math.cos(ga), cy + r * Math.sin(ga), i));
  }
}

function addAgents() {
  // Add one agent on the ring
  const n = agents.length;
  const r = 130;
  const a = (n * 1.1) % (2 * Math.PI);
  const ga = a + Math.PI + 0.4;
  agents.push(mkAgent(W/2 + r*Math.cos(a), H/2 + r*Math.sin(a),
                      W/2 + r*Math.cos(ga), H/2 + r*Math.sin(ga), n));
}

/* One VO-based velocity selection step */
/* Idea: for each agent, find the closest velocity to its goal that avoids all VOs. */
function inVO(relPx, relPy, relVx, relVy, combinedR) {
  // Return true if the relative velocity relV leads to collision within TAU frames.
  // VO(A,B) = velocities v where A, moving at v and B at b.vx/vy, collide within TAU VO(A,B) = {v : exists t in [0,TAU] with |relP + v*t| < combinedR}
  // Equivalent: minimum squared distance from origin along the relative-velocity line < combinedR^2 Equivalent: min over t>=0 of |relP + v*t|^2 < combinedR^2
  const vv = relVx * relVx + relVy * relVy;
  if (vv < 1e-9) return false; // zero relative speed — no future collision from velocity alone
  // time of closest approach, clamped to lookahead window [0, TAU] t* = -dot(relP,relV)/|relV|^2, clamped to [0, TAU]
  const t = Math.max(0, Math.min(TAU, -(relPx * relVx + relPy * relVy) / vv));
  // squared distance between agents at time t* squared distance at t*
  const cx = relPx + relVx * t, cy = relPy + relVy * t;
  return cx * cx + cy * cy < combinedR * combinedR;
}

function voStep() {
  const n = agents.length;
  const newV = [];

  for (let i = 0; i < n; i++) {
    const a = agents[i];
    // Preferred velocity: straight toward goal at max speed
    const dx = a.gx - a.x, dy = a.gy - a.y;
    const dist = Math.sqrt(dx * dx + dy * dy) || 1;
    const spd = Math.min(MAX_SPD, dist / DT);
    const pvx = (dx / dist) * spd, pvy = (dy / dist) * spd;

    // Find best safe velocity among all candidates Find best velocity: closest to preferred that avoids all VOs
    let bestVx = 0, bestVy = 0, bestScore = Infinity;
    const combinedR = 2 * R + 1; // combined radius = sum of both agent radii plus 1-px safety margin

    // Build the candidate set: preferred + sampled velocities on rings Sample velocity candidates on concentric rings
    const cands = [[pvx, pvy]]; // always try preferred velocity first always try preferred first
    for (let ring = 1; ring <= 3; ring++) {
      const rs = (MAX_SPD * ring) / 3;
      for (let s = 0; s < SAMPLES; s++) {
        const ang = 2 * Math.PI * s / SAMPLES;
        cands.push([rs * Math.cos(ang), rs * Math.sin(ang)]);
      }
    }
    cands.push([0, 0]); // stopping in place is always safe and never leads to collision stopping is always an option

    for (const [cvx, cvy] of cands) {
      // Check this candidate against every other agent's VO check this candidate against all neighbors
      let safe = true;
      for (let j = 0; j < n; j++) {
        if (i === j) continue;
        const b = agents[j];
        // relative position (A to B) and relative velocity (candidate minus B's current vel) relative position from A to B, relative velocity
        const relPx = b.x - a.x, relPy = b.y - a.y;
        const relVx = cvx - b.vx, relVy = cvy - b.vy;
        if (inVO(relPx, relPy, relVx, relVy, combinedR)) { safe = false; break; }
      }
      if (safe) {
        // score = squared deviation from preferred velocity — lower is better score = squared distance from preferred velocity
        const dv = (cvx - pvx) * (cvx - pvx) + (cvy - pvy) * (cvy - pvy);
        if (dv < bestScore) { bestScore = dv; bestVx = cvx; bestVy = cvy; }
      }
    }

    newV.push({ vx: bestVx, vy: bestVy });
  }

  // Apply chosen velocities and advance positions by one time step
  agents.forEach((a, i) => { a.vx = newV[i].vx; a.vy = newV[i].vy; a.x += a.vx * DT; a.y += a.vy * DT; });
}

function anyCollision() {
  // Return true if any pair of agents currently overlaps
  for (let i = 0; i < agents.length; i++)
    for (let j = i + 1; j < agents.length; j++) {
      const dx = agents[i].x - agents[j].x, dy = agents[i].y - agents[j].y;
      if (dx * dx + dy * dy < (2 * R - 1) * (2 * R - 1)) return true;
    }
  return false;
}

function draw() {
  CTX.clearRect(0, 0, W, H);

  // Render all agents
  agents.forEach(a => {
    // Faded goal dot
    CTX.beginPath();
    CTX.arc(a.gx, a.gy, 4, 0, 2 * Math.PI);
    CTX.fillStyle = a.color + '44';
    CTX.fill();

    // Agent disc with white outline
    CTX.beginPath();
    CTX.arc(a.x, a.y, R, 0, 2 * Math.PI);
    CTX.fillStyle = a.color;
    CTX.fill();
    CTX.strokeStyle = '#fff';
    CTX.lineWidth = 1.5;
    CTX.stroke();

    // Velocity direction arrow
    if (a.vx * a.vx + a.vy * a.vy > 0.02) {
      CTX.beginPath();
      CTX.moveTo(a.x, a.y);
      CTX.lineTo(a.x + a.vx * 9, a.y + a.vy * 9);
      CTX.strokeStyle = '#ffffffcc';
      CTX.lineWidth = 1.8;
      CTX.stroke();
    }
  });

  // Collision warning overlay (rare, shown only in extreme density)
  if (anyCollision()) {
    CTX.fillStyle = '#e63946cc';
    CTX.font = 'bold 13px system-ui';
    CTX.fillText('Overlap detected (too many agents)', 8, 18);
  }

  // Update agent count display
  INFO.textContent = i18nFmt('%n% agents', { n: agents.length });
}

function loop() {
  if (!paused) { voStep(); frame++; }
  draw();
  requestAnimationFrame(loop);
}

document.getElementById('btn-add').addEventListener('click', () => { addAgents(); });
document.getElementById('btn-pause').addEventListener('click', function () {
  paused = !paused;
  this.textContent = paused ? 'Resume' : 'Pause';
});
document.getElementById('btn-reset').addEventListener('click', () => { initAgents(); frame = 0; });

initAgents();
loop();
Result
Console

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.

The Real Complexity

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

How ORCA works per agent. Each agent AA considers every neighbor BB. In the relative-velocity frame, the set of velocities that would put AA on a collision course with BB 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 AA and half to BB. 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)O(n) constraints, solvable in O(n)O(n) time by the randomized incremental LP algorithm.

The cost per frame is O(n2)O(n^2) (each of nn agents queries n−1n-1 neighbors), which stays fast for crowds of hundreds. With spatial indexing (a kk-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 nn 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/velocity-obstacles/Content licensed under CC BY-NC 4.0.