What Makes a Space Traversable? A Formal Definition and On-Policy Certificate for Contact-Rich Egress in Confined Environments

When is an unknown, confined environment traversable for a specific ground robot using only touch? We answer by (i) giving an environment-anchored definition of traversability, expressed through the max-min value T★(E;A)=supπ∈ΠS→Ginfs∈[0,1]ϕ(π(s)), where the bottleneck margin ϕ aggregates the clearance, curvature (ρ≥Rmin), slope/step, and friction constraints, and (ii) introducing an on-policy, tactile certificate (TC) that maintains a conservative, monotone lower bound Tt using partial contact histories. The TC fuses pessimistic free-space from contacts and the body envelope, the M3 decaying contact memory as a risk prior, and local bend/FSR proxies; a certificate is issued when Tt>0 and the explored corridor graph connects S to G. Relative to Papers 1–2 (tactile traversal; offline software assurance), this work formalizes traversability itself and provides a tactile-only, online certificate computable during runs. In a retrospective analysis of 660 trials across Indoor/Outdoor/Dark lighting environments, (H1) the early TC margin predicts success and traversal time better than contact/dwell heuristics (higher AUC/R2), (H2) the TC predictivity is lighting-invariant, and (H3) speed-gating M3 by a TC margin recovers part of the CB-V speed gap without degrading success. Artifacts include the TC implementation, explored-corridor graphs, and per-trial TC time series added to the Paper-1 log bundle; these materials are available from the corresponding author upon reasonable request.