Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M9 Navigation in the Real World / M9-T4

Navigation · Theory · M9

M9-T4 — Evaluating Navigation

One good run proves almost nothing. A repeatable test, the right metrics, and enough runs are what turn a demo into evidence.

  • Lesson 4 of 6
  • Module 9: Navigation in the Real World
  • Theory
  • About 8 minutes to read

After a week of tuning, Scout “seems better”. Does it reach more goals, or did it get an easy corridor? Is it faster, or less safe? Evaluation is the discipline of answering such questions so that someone who was not there can check the answer. It needs a fixed set of scenarios, metrics that cannot be gamed, and enough runs to know how much of a difference is noise.

Learning objectives

After this lesson, you should be able to:

  • Design a set of repeatable scenarios that covers the failures you care about, including the hard ones.
  • Choose and log metrics for success, efficiency, safety and comfort, and explain how each can mislead.
  • Compute a confidence interval for a success rate and the number of runs needed for a given precision.
  • Compare two configurations fairly, on the same scenarios, and say when a difference is not proven.

The intuition

Imagine testing a new brand of shoe by running one lap each in old and new. The new pair is faster by 4 seconds. Is it the shoe, the wind, or the runner’s mood? You would run several laps, alternate shoes, and use the same track. Navigation evaluation is the same experiment on a robot: the same scenarios, repeated, with the two configurations alternating, and a number that says how big the difference is compared with the lap-to-lap variation.

The trap is the demo. A demo picks the best corridor, the best hour and the run that worked. An evaluation fixes the scenarios in advance, includes the ones you expect to fail, records every run (including the bad ones), and reports the failures with the same prominence as the successes.

Confidence intervals shrink with more runsThree horizontal intervals for the same observed success rate of 90 percent: with 20 runs it spans 70 to 97 percent, with 100 runs 83 to 94 percent, and with 200 runs 90 percent observed gives 85 to 93 percent. 60%70%80%90%100% 18 of 2090 of 100180 of 200 observed 90 % 95 % Wilson intervals. “90 % success” from 20 runs means anything from 70 % to 97 %.
The same observed success rate carries very different certainty at different numbers of runs.

The mathematics

Scenarios

A scenario is a start, a goal, a map, and the conditions: lighting, people, obstacles, wireless load. Keep three groups.

GroupPurposeExample at Meridian General
NominalCheck that the common case worksPharmacy to ward 2, empty corridor
HardCheck the cases the tuning was for0.85 m service door, parked cart, slow link
AdversarialFind failures you have not thought ofGlass wall, mirror, a person stepping out, a lift door closing

Fix them in advance, version them with the parameter file, and use a seed or a script to reset the start. In simulation a seed reproduces a run exactly; on a real robot it reproduces the start and the goal, not the world.

Metrics

MetricDefinitionHow it can mislead
Success rateFraction of runs that reached the goal within tolerance, with no collisionHides slow, unsafe or lucky success
SPLMean of Si · li / max(pi, li): success weighted by path length (l shortest, p taken)A short path through a dangerous place scores well
Time to goalSeconds from request to successFaster may mean less clearance
Minimum clearanceSmallest distance between body and obstacle in the runNeeds a ground-truth obstacle model
Near-miss countSamples closer than a thresholdDepends on the threshold
Interventions / recoveriesHuman takeovers, recoveries triggered per hourDepends on how strict the operator is
Jerk, comfortRMS jerk of the speed profileSmooth motion can still be unsafe

Report several together; a change that improves one by worsening another is a trade-off, not a win (lesson M1-T6).

How many runs?

A success rate measured on n runs has uncertainty. The Wilson score interval for observed fraction p̂ at 95% confidence (z = 1.96) is:

Wilson score interval
centre=p^+z22n1+z2n\text{centre}=\frac{\hat{p}+\frac{z^{2}}{2n}}{1+\frac{z^{2}}{n}}
half=z⋅p^(1−p^)n+z24n21+z2n\text{half}=\frac{z\cdot \sqrt{\frac{\hat{p}(1-\hat{p})}{n}+\frac{z^{2}}{4n^{2}}}}{1+\frac{z^{2}}{n}}
interval=centre±half\text{interval}=\text{centre}\pm \text{half}

For planning, the simpler normal approximation gives the number of runs for a half-width h: n ≈ z² · p(1−p) / h², which is largest, 385 runs for h = 5%, when p = 0.5.

Comparing two configurations

  • Same scenarios, same order of difficulty. Use the same set for both; randomise the order to cancel drift in the conditions.
  • Pair the runs. Compare A and B on each scenario, and look at the differences. Many small wins and one disaster is a different story from a uniform small gain.
  • Check the interval. If the intervals of the two success rates overlap heavily, you have not shown a difference.
  • Change one thing. A comparison between two tunings with five parameters different explains nothing (lesson M9-T2).

A worked example

Is 18 of 20 good? Scout completes 18 of 20 pharmacy runs: p̂ = 0.90. The Wilson 95% interval is 0.70 to 0.97. The true success rate could be 70%, which is not acceptable for a hospital, or 97%, which is. Twenty runs cannot tell.

runs   observed   95% interval
20     18         0.699 to 0.972
100    90         0.826 to 0.945
200    180        0.851 to 0.934

To state the success rate within ±5% when it is near 0.9 needs about 1.96² × 0.9 × 0.1 / 0.05² = 139 runs; if you have no idea of the rate, plan for 385. This is why a simulation, where a run costs seconds, carries most of the runs, and the real robot carries the scenarios simulation cannot model.

SPL. Four runs: shortest path 10 m and taken 12.5 m, success; shortest 8 m taken 8 m, success; shortest 12 m, failure; shortest 9 m taken 11.25 m, success.

SPL example
SPL=1012.5+88+0+911.254\mathrm{SPL}=\frac{\frac{10}{12.5}+\frac{8}{8}+0+\frac{9}{11.25}}{4}
=0.8+1.0+0+0.84=0.65=\frac{0.8+1.0+0+0.8}{4}=0.65
success rate=34=0.75\text{success rate}=\frac{3}{4}=0.75

SPL (0.65) is below the success rate (0.75) because two successful runs took 25% longer than the shortest path. Neither number says that run 3 failed because the robot stopped in front of a closed door at 3 a.m.: that comes from the log, which is why every failure is read and classified by stage (planning, control, localization, perception, recovery).

Comparing tunings. New tuning: 94 of 100. Old tuning: 90 of 100. Intervals: new 0.875 to 0.972; old 0.826 to 0.945: they overlap by most of their width. The difference of 4 percentage points is not established. Running both on the same 100 scenarios, in pairs, and counting runs where only one succeeded (for example 6 where only the new one succeeded and 2 where only the old one did) is a more sensitive test, and still modest at 8 disagreements.

Engineering implications and limitations

Log everything, always

Record the pose, the commanded velocity, the plan, the costmap summary, the transform health and the behaviour-tree state, with the parameter file and its version, for every run. A failed run without a log is unrepeatable and unexplainable. Logs also let you recompute a new metric on old runs.

Classify failures

Every failed run gets a stage: perception, localization, planning, control, recovery or configuration. A table of failure counts by stage shows where the next week of work should go, and whether a fix moved failures between stages rather than removing them.

Separate tuning data from test data

If you tune on the scenarios you report, the numbers flatter you. Keep a set of scenarios you do not use for tuning. This is the navigation version of a held-out test set.

Simulation and reality

A simulation can run thousands of scenarios and is the right place for regression tests. Whether its results predict the real robot has to be measured, by running some scenarios in both and comparing the metrics (the question is studied in the embodied-navigation literature under the name sim-to-real predictivity). Report which results come from which.

Safety is a different kind of claim

“No collisions in 200 runs” does not show a collision rate below one in 200; the interval for 0 of 200 still allows rates near 1.9%. Safety claims need design arguments and monitors, not only trials (module 7 and the capstone).

Common misconceptions

“It worked three times, so it works.”

Three runs say almost nothing about rates. Plan the number of runs from the precision you need.

“Success rate is enough.”

It hides time, clearance, interventions and luck. Report several metrics and read the failures.

“If the new tuning scored higher, it is better.”

Only if the difference exceeds the run-to-run noise on the same scenarios. Check the interval or use paired runs.

“Tune on the evaluation set to get the best number.”

That measures how well you fit those scenarios. Keep a held-out set.

Engineering takeaways

  1. Evaluate on fixed, versioned scenarios: nominal, hard and adversarial.
  2. Report success, SPL, time, clearance, near misses and interventions together, and read every failure.
  3. A success rate has an interval: 18 of 20 allows anything from 70% to 97%; about 139 runs give ±5% near 90%.
  4. Compare configurations on the same scenarios, in pairs, with one change at a time.
  5. Log every run with the parameter file, classify failures by stage, and keep a held-out set.

References and further reading

The metrics and evaluation practice come from the embodied-navigation literature; the statistics are standard.

  • P. Anderson, A. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V. Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savva and A. R. Zamir, “On Evaluation of Embodied Navigation Agents”, arXiv:1807.06757, 2018.
  • E. B. Wilson, “Probable inference, the law of succession, and statistical inference”, Journal of the American Statistical Association 22(158), 1927.
  • A. Kadian, J. Truong, A. Gokaslan, A. Clegg, E. Wijmans, S. Lee, M. Savva, S. Chernova and D. Batra, “Sim2Real Predictivity: Does Evaluation in Simulation Predict Real-World Performance?”, IEEE Robotics and Automation Letters, 2020.
  • Nav2 documentation, “Navigation Concepts” and “Configuration Guide”, docs.nav2.org.

Knowledge check

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

Question 1

A new tuning succeeds on 47 of 50 runs and the old on 44 of 50. A colleague says the new one is better. What do you say?

Explanation

The difference of six percentage points is within the noise of 50 runs: the 95% intervals (roughly 0.84 to 0.98 and 0.76 to 0.94) overlap strongly. More runs on the same scenarios, ideally paired, are needed before claiming an improvement.

Question 2

Three runs have shortest paths 10 m, 6 m and 8 m. The robot succeeds on the first two with paths 10 m and 7.5 m, and fails on the third. Compute SPL.

Explanation

(10/10 + 6/7.5 + 0) / 3 = (1 + 0.8 + 0) / 3 = 0.6.

Question 3

Why can zero collisions in 100 runs not be quoted as a collision rate of zero?

Explanation

It only bounds the rate: the 95% interval for 0 of 100 still allows a rate of about 3.7%. Rare events need many more runs or a design argument and safety monitors, not only trials.

What’s next

Next: what changes when the robot is legged, flying, floating or driving off road.

Next lesson

M9-T5 — Other Platforms: Legged, Aerial, Marine and Off-Road

Say what changes for legged, aerial, marine and off-road robots, and where grid navigation stops being enough.

Nothing below is required to finish this lesson.