Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M6 Local Planning and Obstacle Avoidance / M6-T4

Navigation · Theory · M6

M6-T4 — Time to Collision and Predicting Moving Obstacles

The robot’s first useful question about a moving obstacle is not where it is but when, and whether, we meet.

  • Lesson 4 of 7
  • Module 6: Local Planning and Obstacle Avoidance
  • Theory
  • About 8 minutes to read

A porter wheels a trolley across the corridor, and Scout has to decide now: carry on, slow, or stop. That decision needs a prediction. The simplest one assumes everyone keeps their current velocity. It is wrong often enough to matter and right often enough to be the first thing every system uses, so it is worth knowing exactly what it says and where it breaks.

Learning objectives

After this lesson, you should be able to:

  • Derive the time to collision of two discs at constant velocity as the root of a quadratic.
  • Compute the closest approach and its time, and use them to choose a safe speed.
  • Explain why range divided by closing speed is the wrong formula off the line of sight.
  • Say when constant-velocity prediction fails and how to guard against it.

The intuition

Stand in the robot’s frame. Everything the robot passes appears to move past it, and a person walking across the corridor appears to travel along a straight line, because both velocities are constant and their difference is too. Collision means that line enters a circle around the robot, the circle whose radius is the sum of the two body radii. A line enters a circle only if it passes within one radius of its centre, so a person who walks close but not that close, never collides, however fast they approach.

Two numbers describe the encounter: time to collision (when the line first enters the circle, if it does), and closest approach (how near the line gets to the centre, and when). The first answers “how soon must I act”; the second answers “is this slowdown enough”.

Relative motion and the collision discIn the frame of the robot, the porter moves along a straight line. The line enters a disc of radius 0.9 metres around the robot at 5.1 seconds. The closest approach, 0.63 metres, is at 5.6 seconds. robot porter now, p = (6, −4) enters at t = 5.10 s closest at 5.61 s, d = 0.63 m relative velocity v = (−1.0, 0.8) m/s collision distance R = 0.9 m A straight line enters the disc if and only if it passes closer to the centre than R.
In the robot’s frame the porter moves along a line. It enters the collision disc after 5.1 s; the nearest it gets is 0.63 m after 5.6 s.

The mathematics

Time to collision

Let p be the other body’s position relative to the robot, v its velocity relative to the robot (its velocity minus ours), and R the sum of the radii. Contact happens when |p + v·t| = R:

Contact condition
a⋅t2+2b⋅t+c=0,a\cdot t^{2}+2b\cdot t+c=0,
a=v⋅v,a=v\cdot v,
b=p⋅v,b=p\cdot v,
c=p⋅p−R2c=p\cdot p-R^{2}
Cases
c≤0→t=0(already overlapping)c\le 0\to t=0\text{(already overlapping)}
a≈0(no relative motion)→no collisiona\approx 0\text{(no relative motion)}\to \text{no collision}
b2−a⋅c<0→no collision(the courses never come within R)b^{2}-a\cdot c<0\to \text{no collision}\text{(the courses never come within R)}
t=−b−b2−a⋅ca→first contact; none if t<0(they are moving apart)t=\frac{-b-\sqrt{b^{2}-a\cdot c}}{a}\to \text{first contact};\,\text{none if}\,t<0\text{(they are moving apart)}

Closest approach

The squared distance |p + v·t|² is a parabola in t. Its minimum on 0 ≤ t ≤ T is at the vertex or at an end of the interval:

Closest approach within a horizon T
t∗=clamp⁡(−p⋅vv⋅v, 0, T)t^{*}=\operatorname{clamp}(-\frac{p\cdot v}{v\cdot v},\,0,\,T)
dmin⁡=∣p+v⋅t∗∣d_{\min}=\lvert p+v\cdot t^{*}\rvert
p, v
relative position and relative velocity of the obstacle (obstacle minus robot).
R
sum of the robot radius and the obstacle radius.
T
prediction horizon: how far ahead the prediction is trusted (s).

A shortcut that fails

“Distance divided by closing speed” takes the part of v along the line of sight and ignores the sideways part. It is exact only for a head-on approach. Off-axis it reports collisions for people who will pass by (the sideways motion takes them clear) and gives wrong times for those who will hit.

Choosing a speed

Scout drives straight at speed s. Its velocity enters through v = vobstacle − s·(cos θ, sin θ). The least intrusive response is the largest s ≤ spref whose closest approach dmin stays at least dsafe (lab M6-L3, stage 2). Checking the distance only at the end of the horizon would miss every crossing that finishes earlier.

When the prediction is wrong

  • People decide: they stop, turn, hurry, or avoid you. Constant velocity encodes none of this.
  • Tracking error: a velocity estimated from a few noisy detections can be off by 0.2 m/s or more, and the error in position grows linearly with the horizon.
  • Acceleration and turns: a trolley that turns at a junction leaves the straight line.
  • Responses: a short horizon; a margin that grows with t; several hypotheses and the worst case (lab M6-L3, stage 3); an interacting model (lessons M6-T5 and M6-T6).

A worked example

The trolley. Scout drives along +x at 1.0 m/s. The porter is at (6, −4) m relative to Scout and walks along +y at 0.8 m/s. Radii sum to R = 0.9 m. The relative velocity is v = (0 − 1.0, 0.8 − 0) = (−1.0, 0.8).

Time to collision
a=1.02+0.82=1.64a=1.0^{2}+0.8^{2}=1.64
b=6⋅(−1.0)+(−4)⋅0.8=−9.2b=6\cdot (-1.0)+(-4)\cdot 0.8=-9.2
c=62+42−0.92=51.19c=6^{2}+4^{2}-0.9^{2}=51.19
b2−a⋅c=84.64−83.95=0.688b^{2}-a\cdot c=84.64-83.95=0.688
=0.830\sqrt{=}0.830
t=9.2−0.8301.64=5.10 st=\frac{9.2-0.830}{1.64}=5.10\,\mathrm{s}

The nearest approach is at t* = 9.2 / 1.64 = 5.61 s with dmin = 0.63 m, inside R = 0.9 m, so the collision is real, though only just. The shortcut gives |p| = 7.21 m, a closing speed of 9.2 / 7.21 = 1.276 m/s and a time of (7.21 − 0.9) / 1.276 = 4.95 s: 0.15 s early here, but for the next case it is badly wrong.

A porter who passes. Let the porter walk at 0.3 m/s instead: v = (−1.0, 0.3), b = −7.2, a = 1.09, b² − a·c = 51.84 − 55.80 < 0. No collision: the closest approach is 2.11 m. The shortcut still predicts a collision after (7.21 − 0.9) / 0.9985 = 6.32 s and brakes for nothing.

Slowing instead of stopping. With dsafe = 1.2 m, the closest approach at speed s is 0.63 m at 1.0, 1.41 m at 0.8 (at 6.25 s) and 2.40 m at 0.6 (at 6.80 s). The largest safe speed on a grid of 0.1 m/s is 0.8 m/s: Scout slows by a fifth and the porter crosses 2 m in front of it. A stop is not needed.

Allowing for error. If the position uncertainty grows by 0.2 m per second, the required distance at time t is 0.9 + 0.2·t. At 0.8 m/s the closest approach, 1.41 m at 6.25 s, is below the required 0.9 + 1.25 = 2.15 m: rejected. At 0.7 m/s it is 1.88 m against 2.21 m: rejected. At 0.6 m/s it is 2.40 m against 2.26 m: accepted. Honest uncertainty costs speed.

Engineering implications and limitations

Estimate velocity carefully

Differencing two detections gives a noisy velocity. Track with a filter (a constant-velocity Kalman filter is typical, lesson M7-T3) and use its covariance as the uncertainty.

Choose the horizon by what is predictable

Constant velocity is credible for about a second or two for a person and longer for a vehicle on a lane. Beyond that, plan conservatively.

Treat unknown intent as a set

Keep the estimate plus a few alternatives (stops, turns either way, hurries) and require safety against all of them. It costs a little speed and prevents the worst surprises.

Beware of the opposite error

A robot that treats every passing person as a collision freezes the corridor. Use the exact geometry, so people who will pass are ignored, and add social margins separately (lesson M6-T6).

Choose slowing before stopping

People read a robot that slows as having seen them. A sudden stop in the middle of a corridor reads as a fault.

Common misconceptions

“Time to collision is distance divided by speed.”

Only for a head-on approach. In general it is the root of a quadratic in the relative motion.

“If the distance now is large, the situation is safe.”

The distance at the closest approach is what matters, and the closest approach may be several seconds ahead.

“A prediction is either right or wrong.”

Its error grows with the horizon; use it with a margin that grows too.

“Stopping is always the safe response.”

A stopped robot in a corridor can be hit by someone who expected it to move, and it blocks others.

Engineering takeaways

  1. In the robot’s frame an obstacle at constant velocity moves in a straight line; it collides if that line enters the disc of radius R.
  2. Time to collision is the smaller root of a quadratic, none if the discriminant is negative or the root is negative.
  3. Closest approach is at t* = −p·v / v·v, clamped to the horizon; check it, not the final distance.
  4. The largest speed that keeps the closest approach above the safe distance is the least intrusive response.
  5. Constant velocity fails where people decide; use a short horizon, a growing margin and several hypotheses.

References and further reading

The velocity-obstacle literature and the human-aware navigation survey.

  • P. Fiorini and Z. Shiller, “Motion Planning in Dynamic Environments Using Velocity Obstacles”, International Journal of Robotics Research 17(7), 1998.
  • T. Kruse, A. K. Pandey, R. Alami and A. Kirsch, “Human-Aware Robot Navigation: A Survey”, Robotics and Autonomous Systems 61(12), 2013.
  • Nav2 documentation, “Collision Monitor”, docs.nav2.org.

Knowledge check

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

Question 1

Relative position p = (5, 0), relative velocity v = (−1, 0), R = 1. What is the time to collision?

Explanation

a = 1, b = −5, c = 25 − 1 = 24; b² − a·c = 25 − 24 = 1; t = (5 − 1) / 1 = 4 s. (Directly: the gap closes from 5 to 1 m at 1 m/s.)

Question 2

p = (5, 3), v = (−1, 0), R = 1. Do they collide?

Explanation

a = 1, b = −5, c = 34 − 1 = 33; b² − a·c = 25 − 33 < 0. No: the lateral offset of 3 m exceeds R, so the courses never come within 1 m.

Question 3

Why is the distance at the end of an 8 s horizon a poor test of safety?

Explanation

The closest approach may happen earlier, for example at 5.6 s, and afterwards the obstacle moves away. The end distance looks safe while the encounter was not.

What’s next

Next: many agents at once, and how each can choose a velocity that stays out of the others’ velocity obstacles.

Practice this lesson

Avoid a Moving Obstacle

A porter pushes a trolley across your path: predict the crossing and slow or steer in time.

Next lesson

M6-T5 — Velocity Obstacles, RVO and ORCA

Build a velocity obstacle and explain how reciprocal avoidance removes oscillation between two robots.

Nothing below is required to finish this lesson.