CERT: Certified Route Planning under Drifting Costs

Conformal certificates, sense-to-certify, and the price of staleness

Abstract

A scout robot routing through terrain whose costs drift — mud after rain, traffic after an incident — faces a question classical replanning never answers: how good is the current route, given that most of the map is stale? CERT answers it every round with a certificate: a high-probability bound LB ≤ OPT ≤ UB on the optimal route cost, built from age-weighted non-exchangeable conformal prediction over drift-adjusted residuals, with paid sensing directed at the edges that shrink the certified gap fastest. We prove coverage at the claimed level, with a staleness correction that degrades the claim visibly rather than silently; a certifiability threshold — a target gap is sustainable if and only if the sensing rate beats drift, so certification is a rate, not a state; a √L-tighter sum-aware upper certificate, including the selection-bias hazard it creates and the gate that controls it; and an impossibility theorem showing the certificate's asymmetry is optimal. On replayed traffic from two cities the certificate holds even where real incidents violate the drift model up to half the time, and certificate-directed sensing achieves 2–3× lower travel-regret than freshness-, uncertainty-, or chance-driven sensing at equal budget.