08 / RECIPROCAL MOTION · VELOCITY CONSTRAINTS
Optimal Reciprocal
Collision Avoidance.
Agents want to cross the same space. ORCA shares the avoidance effort between each pair, then chooses a velocity close to the agent's goal-directed preference. Compare it with Artificial Potential Fields (APF) and direct motion.
Predict: if collision avoidance uses observed peers, what happens when those observations disappear?
Name the algorithm and its assumptions
Equations and primary source ↗- Algorithm and variant
- ORCA / reciprocal disk agents
Finite-horizon velocity half-planes with equal pairwise responsibility. Choose the feasible velocity nearest the goal preference inside a speed disk.
- Decision architecture
- Decentralized, leaderless
Each agent decides from its own goal and current peer positions, velocities and radii. Peers' goals and future commands are not inputs.
- Timing and communication
- Synchronous, discrete-time
All commands use the same pre-step snapshot. Perfect all-peer sensing; no messages, radio topology, delays or packet loss are simulated.
- Execution and evaluator
- One browser / planar kinematics
Disk agents change velocity instantly. The evaluator checks swept pair clearance and arrival. The 3D quadrotors share a fixed 1.15 m display height; ground disks keep the modeled collision radius. There is no vertical avoidance or flight physics.
Scope: local collision avoidance with assigned goals, no obstacles or global path planner. “Optimal” means nearest feasible velocity for this step; it does not mean a globally shortest route or guaranteed mission completion.
PREFER A VELOCITY · CONSTRAIN IT · MOVE
Share the space, inspect the compromise.
○ Agent / numbered⊕ Matching goal┄ Preferred velocity━━ Chosen velocity
Select an agent on the map or below. Trails record this run. Velocity arrows show the latest decision, translated to the current position. In 3D, faint dashed peer lines identify the selected ORCA constraints, not communication links.
LOCAL DECISION / VELOCITY SPACE
A safe side of each line.
○ Speed limit▧ Feasible intersection◇ Preferred● Chosen
PAIRWISE CONSTRAINTS / SAME DECISION SNAPSHOT
Who asks this agent to yield?
Each neighbor contributes a line through q with admissible-side unit normal n. The velocity v must satisfy n · (v − q) ≥ 0. A negative margin violates that half-plane.
| Peer | q = (x, y) | n = (x, y) | Chosen margin |
|---|
Read the geometry
The circle contains allowed speeds. Each line removes velocities that fail one pair's reciprocal constraint. The shaded intersection contains velocities that satisfy every displayed line and the speed limit.
The diamond is the goal preference; the solid point is the decision. They overlap when the preference already satisfies every constraint. An empty intersection triggers the declared infeasibility policy.
The velocity plot is a decision diagram, not an additional map. Its origin means zero velocity; its axes are m/s.
AGENT STATE / EVALUATOR ARRIVAL
Motion is only part of success.
| Agent | Position (m) | Velocity (m/s) | Goal distance (m) | Arrival | Feasible |
|---|
PREDICT · COMPARE · EXPLAIN
Avoidance has assumptions.
Load a guided case, predict its outcome, then step through the encounter or run to the stop condition. Each case starts paused.
Reproduce the reference comparisons
These independent runs use the listed configurations and the same fixed time budget. Opening this table never advances or replaces the active experiment. Clearance measures the full piecewise-linear motion, including between displayed frames.
| Case | Method / τ | Outcome | Time | Arrived | Min gap | Infeasible |
|---|
THE RULE BEHIND THE MOTION
Choose in
velocity space.
For each pair, a finite-horizon velocity obstacle describes relative velocities that would bring the disks into contact. ORCA splits the required correction equally and builds one admissible half-plane per neighbor.
Unlike an APF force sum, this method imposes explicit velocity constraints before the position update.
Hᵢⱼ = { v : nᵢⱼ · (v − qᵢⱼ) ≥ 0 }
vᵢ* = arg min ‖v − vᵢ preferred‖²
subject to ‖v‖ ≤ v max and v ∈ ∩ⱼ Hᵢⱼ
pᵢ next = pᵢ + Δt vᵢ*
- pᵢ, vᵢ, Δt
- Current position in m, velocity in m/s and fixed integration step in seconds.
- uᵢⱼ and nᵢⱼ
- Correction to the relative-velocity obstacle boundary and the admissible side's normal.
- ½ / equal responsibility
- Each cooperating peer takes half the pairwise correction from the same snapshot.
- τ / prediction horizon
- Look-ahead used to construct pair constraints. Peers recompute their velocities every step.
Safety and progress differ
Reciprocal constraints depend on accurate state, compatible decisions and feasible velocities. Symmetric agents can wait without reaching their goals. Missing peer observations remove constraints without removing the physical agents.
A deliberately small model
Perfect sensing, circular footprints, no acceleration bound, no static obstacles and no noisy localization. No physical safety claim, flight controller or distributed runtime is inferred from this browser experiment.
Primary method: van den Berg, Guy, Lin and Manocha — Optimal Reciprocal Collision Avoidance. This page implements a small educational variant, not an official RVO2 binding.