Velocity Obstacles, RVO and ORCA: Robot Navigation Theory (M6-T5)

Learning objectives

After this lesson, you should be able to:

Build the velocity obstacle of one robot with respect to another and say what it means.
Explain why plain velocity-obstacle avoidance oscillates between two reacting robots.
Compute the ORCA correction u and the half-plane of allowed velocities for each robot.
State the assumptions and limits of ORCA, including symmetric deadlock.

The intuition

Forget positions for a moment and think only of velocities. If robot A moves with velocity v_A and robot B with v_B, the only thing that decides whether they meet is their relative velocity v_A − v_B. Draw, in the plane of relative velocities, every value of it that leads to contact: the cone of directions from A towards B, opened up by the sum of the radii. That cone is the velocity obstacle. If the relative velocity is inside, a collision will happen; outside, it will not. Avoidance is leaving the cone, by the shortest route.

When B does not react, A can simply pick a velocity outside the cone. When B reacts in the same way, both change at once, and each change moves the other’s cone: the two keep correcting for each other’s corrections. Reciprocal methods fix this with a convention: each robot does only half of what is needed, so the relative velocity ends exactly on the boundary when both have done their share, and no robot has to guess what the other will do.

The truncated velocity obstacle of the worked example. The relative velocity is 0.1 m/s inside the cone; the correction u is split equally between the robots.

The mathematics

The velocity obstacle

Robot A at p_A and B at p_B, with radii summing to R. Let p = p_B − p_A. The relative velocity v = v_A − v_B makes the robots collide within time τ if and only if some t in [0, τ] gives |p − v·t| < R. The set of such v is the velocity obstacle truncated at τ:

Truncated velocity obstacle

\mathrm{VO}^{\tau }=\{v:\,\exists t\in [0,\,\tau ]:\,\lvert p-v\cdot t\rvert <R\}

It is a cone with its apex cut off: the cone has half-angle asin(R/|p|) around p, and the cut is an arc of the circle with centre p/τ and radius R/τ. Collisions further than τ away are ignored.

The nearest way out

Let u be the smallest change of v that reaches the boundary, and n the outward normal of the boundary at that point. Using w = v − p/τ, the nearest boundary point is on the cut-off circle if w·p < 0 and (w·p)² > R²|w|², otherwise on the nearer leg:

circle

u=(\frac{R}{\tau }-\lvert w\rvert )\cdot w/\lvert w\rvert

leg

d=\text{unit direction of the leg},\,u=(v\cdot d)\cdot d-v

Why plain VO oscillates, and RVO and ORCA

The velocity-obstacle family
Method	Idea	Result
VO	A picks a velocity outside VO(B), assuming B keeps v_B	Two such robots both move and the cones move: oscillation, the reciprocal dance
RVO	The cone’s apex moves to the average (v_A + v_B)/2: each robot takes half of the correction	Removes the dance in most cases; can still collide (Snape et al. repaired it as HRVO)
ORCA	A permitted half-plane for each robot; each robot takes half of u	Collision-free for τ if both obey; one small linear program per robot

The ORCA half-plane

ORCA constraints

\mathrm{ORCA}_{A}=\{v:\,(v-(v_{A}+\frac{u}{2}))\cdot n\ge 0\}

\mathrm{ORCA}_{B}=\{v:\,(v-(v_{B}-\frac{u}{2}))\cdot (-n)\ge 0\}

v_{A},\,\mathrm{new}=\text{the point of}\,\mathrm{ORCA}_{A}(\text{within}\,v_{\max})\,\text{closest to the preferred velocity}\,v_{A},\,\text{pref}

u: smallest change of the relative velocity that reaches the boundary of VO^τ.
n: outward normal of the boundary at that point; the allowed side is the one n points to.
v_pref: the velocity the robot would choose with no one around (towards the goal).
τ: time horizon: how far ahead a collision matters.

Because both robots shift by half of u in opposite directions, the relative velocity changes by exactly u, to the boundary. With several neighbours each robot has one half-plane per neighbour, and the new velocity comes from a small linear program.

Assumptions

Discs that can change velocity instantly in any direction (a holonomic robot); a differential-drive robot needs a conversion step, and a car-like robot more.
Perfect knowledge of the neighbours’ positions and velocities; real systems estimate them.
Every robot runs ORCA. A person who ignores the robot gets no half, and the robot must take more of the burden.

A worked example

Two robots in a corridor. A is at (0, 0) moving at (1, 0) m/s. B is at (6, 0.5) moving at (−1, 0). Both have r = 0.4 m, so R = 0.8 m, and τ = 5 s.

Setting up

p=(6,\,0.5)

v=v_{A}-v_{B}=(2,\,0)

\lvert p\rvert =6.02\,\mathrm{m}

\text{half}-\text{angle of the cone}=\arcsin (\frac{0.8}{6.02})=7.64^{\circ}

\text{cone axis}=\mathrm{atan}2(0.5,\,6)=4.76^{\circ}

legs at −2.88° and 12.40° centre (1.2, 0.1), radius 0.16

The relative velocity (2, 0) points at 0°, which is between −2.88° and 12.40°: inside the cone. A collision will happen. Test the circle: w = v − p/τ = (0.8, −0.1), w·p = 4.75 > 0, so the nearest boundary point is on a leg, and det(p, w) = −1 < 0 selects the right (lower) leg. Projecting:

The reciprocal solution

u=(-0.0050,\,-0.1001)

\lvert u\rvert =0.100\,\mathrm{m}/\mathrm{s}

A\,\text{moves to}\,v_{A}+\frac{u}{2}=(0.9975,\,-0.0500)

2.9° to the right

B\,\text{moves to}\,v_{B}-\frac{u}{2}=(-0.9975,\,+0.0500)

\text{new relative velocity}=(1.9950,\,-0.1001)=v+u\;\mathrm{on\ the\ boundary}

The correction is small: 0.05 m/s of sideways speed each, because the robots are 6 m apart and have five seconds. Had A taken the whole of u, it would swing to (0.995, −0.100), twice as much as needed; if B did the same, the pair would overshoot by 0.1 m/s (lab M6-L4, stage 2). As they close in, the cone widens (the half-angle grows as |p| shrinks) and the corrections grow, so the robots pass each other with a gap that is just R and no more.

The perfect head-on. Move B to (6, 0): p and v both lie on the x-axis, w is along the axis, det(p, w) = 0, and the problem is symmetric. The nearest boundary point does not push either robot sideways, and the corrections slow both robots along the line until they stand 0.8 m apart, both waiting. Floating-point noise sometimes breaks the tie by accident. A deliberate convention does it reliably: both robots aim slightly to their own right (lab M6-L4, stage 3).

Engineering implications and limitations

Pick τ from the physics

τ must be longer than the time to stop or turn aside: 2 to 5 s for indoor robots. Too short and the robots wait until they are close and then swerve; too long and they react to encounters that will resolve themselves.

Add a margin

Inflate each radius by a safety margin and the localization error. ORCA guarantees no collision between discs, not between the real footprints.

Humans are not ORCA agents

People do not share half of the burden, so treat them as obstacles with a larger margin and a velocity estimate, and let the robot do the whole of u (lessons M6-T4 and M6-T6).

Walls and infeasibility

In a corridor the half-planes of several neighbours and the walls may leave no allowed velocity. ORCA then minimises the maximum violation. Check that your implementation does this, rather than stopping.

Non-holonomic robots

The new velocity may require sideways motion that a differential-drive robot cannot make. Convert to (v, ω) with a tracking controller and inflate the radius by the tracking error.

Common misconceptions

“A velocity obstacle is a region in the map.”

It lives in velocity space: it says which relative velocities collide, not where.

“Reciprocal means the robots communicate.”

No messages are exchanged. They follow the same rule on the same observed data.

“If both use ORCA they can never freeze.”

Perfectly symmetric meetings can stall; a shared convention or a small perturbation resolves them.

“ORCA works for any robot.”

It is derived for discs with instant velocity changes. Other robots need a conversion and a larger margin.

Engineering takeaways

The velocity obstacle is the cone of relative velocities that lead to a collision within τ, with its tip cut off by a circle.
Plain VO oscillates when both robots react; RVO and ORCA share the correction.
ORCA: u is the smallest change to the boundary; each robot constrains itself to the half-plane through v + u/2 (or v − u/2).
The new velocity is the allowed velocity closest to the preferred one, within the speed limit.
Symmetric head-on meetings need a tie-break; humans are not ORCA agents.

References and further reading

The velocity-obstacle papers and the RVO2 library.

P. Fiorini and Z. Shiller, “Motion Planning in Dynamic Environments Using Velocity Obstacles”, International Journal of Robotics Research 17(7), 1998.
J. van den Berg, M. Lin and D. Manocha, “Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation”, IEEE ICRA, 2008.
J. van den Berg, S. J. Guy, M. Lin and D. Manocha, “Reciprocal n-Body Collision Avoidance”, Robotics Research (ISRR 2009), Springer Tracts in Advanced Robotics 70, 2011.
J. Snape, J. van den Berg, S. J. Guy and D. Manocha, “The Hybrid Reciprocal Velocity Obstacle”, IEEE Transactions on Robotics 27(4), 2011.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

Two robots with radii 0.5 m and 0.3 m: what is R, and what is the half-angle of the cone at a distance of 4 m?

Explanation

R = 0.8 m. The half-angle is asin(0.8 / 4) = asin(0.2) = 11.5°.

Question 2

The smallest correction to leave the velocity obstacle is u = (0, −0.2) m/s. What are the two new velocities if the robots currently move at (1, 0) and (−1, 0)?

Explanation

Robot A: (1, 0) + u/2 = (1, −0.1). Robot B: (−1, 0) − u/2 = (−1, +0.1). The relative velocity becomes (2, −0.2) = old + u.

Question 3

Why might two ORCA robots stop face to face?

Explanation

If the setup is exactly symmetric, the nearest boundary point gives no sideways direction and both robots make the same mirrored decision: they slow along the line and stall. A small shared bias, such as aiming to the right, breaks the tie.

What’s next

Next: people, who do not follow our rules, and the unwritten rules we have to follow instead.

Practice this lesson

Pass Without Colliding: ORCA

Two robots meet head-on in a corridor and both freeze: make them pass each other.

Next lesson

M6-T6 — Social Navigation

Describe personal space, passing side and the freezing-robot problem, and how costs can encode them.

Nothing below is required to finish this lesson.

Before
M6-T4: Time to Collision and Predicting Moving Obstacles
Compute time to collision under constant velocity and say when that prediction is wrong.
Lab
M6-L4: Pass Without Colliding: ORCA
Two robots meet head-on in a corridor and both freeze: make them pass each other.

Learning objectives

The intuition

The mathematics

The velocity obstacle

The nearest way out

Why plain VO oscillates, and RVO and ORCA

The ORCA half-plane

Assumptions

A worked example

Engineering implications and limitations

Pick τ from the physics

Add a margin

Humans are not ORCA agents

Walls and infeasibility

Non-holonomic robots

Common misconceptions

“A velocity obstacle is a region in the map.”

“Reciprocal means the robots communicate.”

“If both use ORCA they can never freeze.”

“ORCA works for any robot.”

Engineering takeaways

References and further reading

Knowledge check

Question 1

Question 2

Question 3

What’s next

Pass Without Colliding: ORCA

M6-T6 — Social Navigation

Related content

Get notified when the next lesson and new labs are released.