CERT-FLOW: 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-FLOW 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 iff the sensing rate exceeds the drift rate, 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. This version adds four measured advances and one honest scoreboard. A non-exchangeable round of conformal upgrades — age-weighted sum-level upper bounds (block-quantile and a drift-retrofitted group-sum construction) — recovers 24–27% of the certified width on real traffic at zero violations, exactly where the union-bound tax lives (long paths); a betting confidence sequence licenses a separately-labelled, a-posteriori tier that is 62% narrower at a measured 0.5% miscoverage; and a weighted conformal test martingale plus a Shiryaev–Roberts detector turn the certificate’s pinned-at-one coverage into a live, alarming quantity — quiet on twenty of twenty real replay days, firing ∼ 7 rounds after an injected shift, at zero cost to the bound. An objective-matched hybrid sensing policy cuts median route regret 41% on real traffic in the regime where no width certifies. A certified multi-agent extension lifts the certificate to fleets: the additive team bound is sound, with an exactly separable team optimum, and a first certified-MAPF study (CBS over certified corridors, 600 runs) executes with zero collisions where point-estimate planning collides on up to 100% of runs — alongside the honest finding that its probabilistic knob is inert at this scale, where the finite-sample floor caps the supportable team level below the nominal one. Throughout, we keep the negatives: a verdict table names the areas CERT-FLOW wins (coverage, observability, bounded-change absorption) and the areas it does not (raw static-map latency, interval width).