Certified Bounds on Achievable Legibility under a Path Cost Budget

Abstract

Legible motion is optimised rather than decided, and for good reason: the optimum is intractable. What an optimiser reports is the clarity it found, which does not establish that no clearer trajectory exists, so a question of the form "can any trajectory within this budget be read correctly here" has not been answerable. This paper answers it for a bounded planar problem without computing the optimum, by bracketing it instead. Given a world of convex polygonal obstacles, a finite goal set, a Boltzmann-rational observer and a ceiling on path cost, it returns a trajectory achieving a stated legibility together with a bound that no trajectory within the budget exceeds, and reports the gap between them rather than hiding it. Over 8 published scenarios at 4 cost ceilings the gap is at most 0.0567 and no bound is violated. The same argument bounds trajectories constrained to avoid keep-out zones, which turns the usual comparison of two searches into a certified lower bound on what such a constraint costs in legibility.