Validating SLAM accuracy and navigation success rate

1. Engineering problem

A requirement such as “95 % of goals reached” is a statistical claim. A handful of successful runs cannot prove it; the number of trials needed depends on the rate you want to demonstrate and the confidence you want.

2. When is this needed?

• Writing acceptance criteria.
• Before release.
• Comparing two versions.

3. Selection and design decisions

For s successes in n trials the Wilson score interval gives a 95 % interval for the success rate that behaves well for small n and rates near 100 %. A requirement is demonstrated when the lower bound exceeds the required rate. For SLAM, report loop-closure drift and absolute trajectory error (see the SLAM evaluation guide) over several loops and environments, with the worst case.

4. Advantages and disadvantages

• More trials tighten the interval; the cost is test time, and automation helps.
• Several conditions multiply the number of trials.
• A looser requirement needs fewer trials and may not satisfy the customer.

5. Requirements and constraints

• The requirement and the confidence level are written before testing.
• Trials are independent and cover the ODD.
• Failures are analysed and reported, not dropped.

6. Architecture

requirement + confidence ─▶ required number of trials ─▶ trials ─▶ interval ─▶ pass if the lower bound ≥ requirement

7. Implementation

1. Write the requirement as a rate and a confidence.
2. Compute the trials needed (below).
3. Run them across the conditions.
4. Compute the interval and the drift statistics.
5. Decide: release, fix and repeat, or relax the requirement.

import math
def wilson(s, n, z=1.96):
    p = s / n; d = 1 + z * z / n; c = (p + z * z / (2 * n)) / d
    h = z * math.sqrt(p * (1 - p) / n + z * z / (4 * n * n)) / d
    return c - h, c + h
for s, n in ((48, 50), (190, 200), (200, 200)):
    lo, hi = wilson(s, n)
    print(f"{s}/{n} goals reached ({s / n * 100:.0f} %): 95 % interval {lo * 100:.1f} to {hi * 100:.1f} %")
target = 95.0
for n in (50, 200, 1000):
    lo, hi = wilson(round(0.98 * n), n)
    print(f"at a true success rate of 98 %, {n} trials give a lower bound of about {lo * 100:.1f} %: requirement {target:.0f} % is", "provable" if lo * 100 >= target else "not provable yet")
drift = [0.8, 1.1, 0.9, 1.4, 1.0]
print(f"SLAM loop-closure drift over five loops: mean {sum(drift) / 5:.2f} %, worst {max(drift):.1f} % of distance travelled")

Printed (checked by the site’s tests):

48/50 goals reached (96 %): 95 % interval 86.5 to 98.9 %
190/200 goals reached (95 %): 95 % interval 91.0 to 97.3 %
200/200 goals reached (100 %): 95 % interval 98.1 to 100.0 %
at a true success rate of 98 %, 50 trials give a lower bound of about 89.5 %: requirement 95 % is not provable yet
at a true success rate of 98 %, 200 trials give a lower bound of about 95.0 %: requirement 95 % is not provable yet
at a true success rate of 98 %, 1000 trials give a lower bound of about 96.9 %: requirement 95 % is provable
SLAM loop-closure drift over five loops: mean 1.04 %, worst 1.4 % of distance travelled

Reading it: 48 of 50 is 96 % with a 95 % interval of 86.5 to 98.9 %; 190 of 200 is 95 % with 91.0 to 97.3 %; 200 of 200 is 98.1 to 100 %. If the true rate is 98 %, 50 trials give a lower bound near 89.5 % and 200 trials about 95 %, so a 95 % requirement is provable only with about 1 000 trials. Five loops show a mean drift of 1.04 % of distance, worst 1.4 %. Numbers are illustrative.

8. Real examples

• Acceptance test: 1 000 automated navigation runs over a week, interval computed per route.

9. Failure scenarios

• Claiming 95 % from 20 runs.
• Combining easy and hard routes into one rate.
• Throwing away failed runs.

10. Troubleshooting

1. If the lower bound is just below the requirement, run more trials.
2. If failures cluster, find the factor and fix it.
3. Check independence between runs.

11. Validation

• The calculation prints the lines shown (executed by the site tests).
• The acceptance report states the requirement, the trials, the interval and the worst-case drift.

12. Engineering checklist

• Requirement and confidence written first
• Trials computed
• Conditions covered
• Interval reported
• Worst-case drift reported
• Failures analysed

13. Further references

• The Wilson score interval is a standard binomial confidence interval; see statistics texts.

Related on FixTheRobot