Proving what no robot could achieve
Your planner scores 0.58 in a test room. Is the room hard, or did your planner do badly in it? Nobody could tell, because searching only ever proves that something exists, never that nothing better does. This proves the other half: a level no trajectory can reach, whatever anyone tries next.
The problem
Legibility is Dragan's, formalised at HRI 2013: a trajectory is legible when it deviates from the efficient path early enough that someone watching can infer the goal sooner than efficiency alone would allow. My legible-motion-bench measures what a planner achieved against that objective, and what it paid in path length and constraint violations to get there.
Every method in this space works the same way. It optimises, and it reports the clarity it found. That is a lower bound and nothing more: proof that some trajectory reaches 0.58, and silence on whether 0.60 or 0.90 was ever available. So when a number comes back low, two completely different explanations fit it equally well. The world may be genuinely hard, its goals so nearly collinear from the start that no motion within the budget separates them. Or the world may be easy and the planner poor. A scenario designer needs to tell those apart, and a search cannot do it, because a better optimiser tomorrow could always overturn the verdict.
This project supplies the missing half. For a world, a path budget and a stated observer it returns two numbers: a trajectory that exists, and a wall no trajectory within that budget can cross. The gap between them is reported rather than hidden.
Why the bound holds
The upper end is the half no search can supply, because it quantifies over every admissible trajectory rather than over the ones somebody happened to try. No better optimiser weakens it. Two observations make that tractable.
The first is that path length cancels out of the observer's belief. What remains is a fixed field over the world: a quantity that can be computed once, independently of which trajectory is eventually drawn through it, and then maximised over the whole admissible set at once.
The second concerns obstacles. The usual argument leans on the metric behaving well, and beside an obstacle the geodesic metric breaks that assumption. Rewriting belief as odds against the true goal restores it, so the bound survives in exactly the cluttered worlds that matter, rather than holding only in the open ones where the question is easy anyway.
The lower end is not searched for. It is constructed: threaded from the bound's own high-belief cells and then pulled back until it fits the path budget. That construction beats the vendored local search in 13 of 32 cases, by as much as 0.1485. It is not merely a formality to make the interval close; it is often the better trajectory of the two.
The results
Eight worlds (door_pair, pillar_aisle, open_pair, keep_out_shortcut, narrow_gap, fan_outer, wall_choice and fan_middle), each swept across a range of path budgets. Every row below shows a world at the budget where its interval is widest, which is the least flattering way to present the result:
| World | Budget | Achieved | Bound | Gap |
|---|---|---|---|---|
| fan_middle | 1.25 | 0.4343 | 0.4909 | 0.0567 |
| narrow_gap | 1.50 | 0.7584 | 0.8041 | 0.0456 |
| fan_outer | 1.10 | 0.6410 | 0.6692 | 0.0282 |
| door_pair | 1.50 | 0.8507 | 0.8776 | 0.0269 |
| wall_choice | 1.10 | 0.5787 | 0.5915 | 0.0128 |
All 32 world and budget pairs hold, with zero violations. The narrowest gap anywhere in the suite is 0.0064. Read a row as a sentence: in fan_middle at a 25 per cent budget, a trajectory scoring 0.4343 exists, nothing can exceed 0.4909, and the true optimum is somewhere in between. A planner returning 0.43 in that world is not doing badly. The world is hard, and now that can be stated rather than suspected.
What safety costs
The same argument settles a question that comparison cannot. Adding a keep-out zone and observing that the constrained planner scores lower does not establish that the constraint cost anything: the constrained search may simply have been the worse search. Two searches can never separate those.
A bound can. If the certified ceiling with the constraint sits below the achieved floor without it, the price is real and no future optimiser recovers it. Applied to eight keep-out pairs, 3 certify a positive price. The other 5 certify nothing, and are reported as nothing: not as a small effect, not as a trend, but as an absence of evidence in either direction. That distinction is the reason for building the instrument.
What is not settled
Where the remaining width lives was measured rather than argued. Refining the lattice closes 55 to 79 per cent of it, which means most of the gap is discretisation and will yield to compute.
What was thought to survive was one loose constant in the obstacle argument, and this page used to name it as the highest-leverage improvement outstanding. That was wrong, and the way it was wrong is worth stating. A sharper argument brought the wrapping factor from 9.28 cell radii to 6.14, which closed 1.6 per cent of the suite's total width: twenty of the thirty two pairs draw nothing from that argument at all and cannot move however tight it becomes. Refinement is worth some forty times as much.
The looseness had also been measured against a quantity the bound does not claim, between two arbitrary points of a cell rather than from a point to its own lattice point, and sampled from a box wider than the cell. Both flattered it. Corrected, the constant is loose by a factor of 6.2 rather than 3.7, and no sampled point in any world tested is separated from its own lattice point at all, so the wrapping argument never binds here. Where the width in the obstacle worlds actually lives is therefore an open question again, which is a worse position than this page previously claimed and a truer one.
The honest ceiling on all of it: the observer model is exactly specified and exactly reproducible, and it has never been validated against people. These are therefore certified bounds on a stated objective, not on what a human watching the robot would actually infer. The proof is only as meaningful as the definition it quantifies over, and saying so is part of the result.
The work is now written up as a six-page draft, readable here. It states the same headline numbers as this page (8 scenarios at 4 cost ceilings, a widest gap of 0.0567, no bound violated) and carries its own limitations section rather than leaving them to a reviewer to find. That section now includes the correction described above, and the configuration that bounds what any sharper constant could ever be worth. It was submitted to IEEE Robotics and Automation Letters in August 2026, and it is citable: DOI 10.5281/zenodo.21834955, archived under CC BY 4.0 with the code and the plain-language guide recorded as related works. That DOI resolves to whichever version is current, so a link through it does not go stale when the paper is revised. The first version predates the correction above, and still gives the wrapping factor as 9.28 and calls a sharper constant the highest-leverage improvement outstanding. It remains citable at 10.5281/zenodo.21834956 rather than being quietly replaced.
It was written alongside the code rather than after it, with a working log that tracks each part honestly. Nothing is marked done that cannot be inspected in the repository.