CERT-FLOW · Certified Route Planning under Drifting Costs

The problem

Classical replanning never tells you when to stop trusting the map.

A scout vehicle maps a forest trail in winter; by summer the mud is gone and the costs have moved. A delivery robot's street graph drifts with every incident. D* Lite, A*, and friends re-find the shortest path on whatever costs they currently hold — silently, whether those costs are fresh or hours stale. The route looks optimal and may not be, with nothing to flag it.

The honest question is a certificate question: bound the true optimum from both sides, act only on what you can prove, and when the bound is too loose, spend a sensor reading exactly where it tightens fastest.

How it works

One round: price staleness, bound the optimum, sense the gap.

Each edge carries a point estimate, an observation age, and a drift-rate bound. Age-weighted non-exchangeable conformal prediction turns these into intervals that widen with staleness; two incremental searches bracket the optimum from below and above; the certificate either certifies (gap ≤ ε) or points the next sensor reading at the edge that shrinks the gap fastest. When the certificate proves the map is tight, that proof licenses lookup-speed preprocessing — revoked the instant drift exceeds tolerance.

One CERT round: observations to conformal intervals to dual search to certificate to sensing — One CERT round, end to end — paid observations feed the conformal scorer; per-edge intervals bracket the optimum via dual incremental search; the certificate drives sensing; a proof of tightness gates preprocessing.

01 · score

Drift-adjusted residuals

Each paid observation is scored and weighted by age — exchangeability is never assumed.

02 · price

ĉ ± (λq + ρ·age)

The conformal quantile pays for noise; the drift term pays for staleness.

03 · bound

Dual incremental search

An optimistic ℓ-search and a conservative u-search, repaired incrementally on a flat-array engine.

04 · claim

LB ≤ OPT ≤ UB

At an honestly-annealed confidence that degrades visibly as the map ages — weak claims, not silence.

05 · sense

Shrink the certified gap

Route-critical, churn-aware sensing — certification is a rate, not a state (Theorem T2′).

06 · prove → cache

Gated preprocessing

When every interval is provably tight, an oracle / certified CH answers in ns–µs, revoked once drift exceeds τ.

See it move

The certificate that holds — and the ones that break.

Every clip replays a real run; the coverage and regret numbers are measured at render time, not staged (warm-up rounds are drawn as “no claim”, never counted as misses). A note on honesty: on a known static map every planner finds the same optimal path — so these show what actually differs under drift: certificate validity and sensing efficiency.

Certificate holds vs. breaks — drifting grid

CERT's band contains the true optimum on every round it claims; AD*'s w-suboptimality band, trusting stale point estimates, drifts out of date.

coverage ↑CERT 100%AD* 43%

Same story, real MovingAI map

Certificate validity on benchmark game-map geometry (DAO arena) under bounded drift — the result transfers off the synthetic grid.

coverage ↑CERT 100%AD* 42%

Sensing that pays — unknown terrain

Gap-directed sensing converges near a clairvoyant oracle; random / max-age / drive-blind wander at the same budget (mean over 15 seeds).

regret ↓CERT 1.96others 4.9–7.8

Sensing that pays — real arena map

The same regret race on a cropped MovingAI arena: gap-directed sensing reaches the goal at the lowest travel-regret of any policy.

regret ↓CERT 1.71 (lowest)

Exchangeability collapse under staleness — METR-LA traffic

Exchangeable conformal (CIA, run with its own construction on the same city) covers on the static slice it assumes, then collapses as the calibration→test gap grows; CERT widens its interval to keep coverage. The price is paid in width, explicitly — never in coverage.

coverage ↑CERT 0.96–1.00CIA 0.88 → 0.25width ↓ = CIA frozen 53 s · CERT widens to stay valid

Rendered by scripts/viz_compare.py + the visualization suite — reproducible like every number on this page.

Where it stands

Best-in-class where it counts — and honest about the rest.

↑ higher better

1.000

certificate coverage, every condition — two real cities at up to 49% drift-model violation

↓ lower better

−0.12

travel-regret in unknown drifting terrain — statistically at a clairvoyant oracle

↓ lower better

269 ns

certified static query via proof-gated preprocessing (8.7 µs for a full path)

↓ lower better

0.015 ms

road cost-change absorption vs ≈ 1 s for CRP recustomization — four orders faster

property →	drift-aware intervals	path-cost certificate	online incremental	gap-directed sensing
D* Lite / AD*	✕	✕	✓	✕
Conformal sums (CIA, CQR-GAE)	✕	✓	✕	✕
TASP / FreMEn	✓	✕	✕	✕
CTP + sensing / IPP	✕	✕	✕	✓
🏆 CERT-FLOW	✓	✓	✓	✓

Every prior family misses at least two of the four properties whose conjunction CERT occupies. All per-condition numbers — marked ↑/↓ and ranked best→worst — are in docs/results.

The theory

Seven results — including a proof that the design is optimal.

T1a / T1bCoverage at the claimed level — for observable costs, and for latent costs at a doubled margin.

T2′ — certifiability thresholdA target gap ε is sustainable iff the sensing rate beats drift. Certification is a rate, not a state (proven both directions).

T4 — sum-aware certificateA √L-tighter upper bound, with the selection-bias hazard it creates and the freshness gate that controls it.

T5 — impossibilityNo uniform lower bound beats Bonferroni by more than log factors. The certificate's asymmetry is provably optimal.

T6 — decision-uniform validityValidity over exactly the rounds a policy acts on — α-spent where the trajectory consumes it.

T7 — churn-measured floorFocused sensing suppresses path churn rather than chasing it; the floor uses the measured churn set.

Full statements + proofs in the theory companion (paper/theory.tex); working notes in docs/theory.

Honest boundaries

What it does not win — stated plainly.

A certificate is only as trustworthy as its author's honesty about the edges. These are measured, documented, and shipped alongside the wins.

Static, known maps

On a frozen, fully-known graph, optimized planners (Hub Labels, CH) answer in microseconds and CERT shouldn't be used — its value begins only when costs drift. CERT reaches that speed class only through proof, when the certificate says it's safe.

Age-weighting alone

On a bare residual stream, our age-weighted quantile ties fixed-weight NexCP — the real edge over exchangeable conformal is the explicit ρ·age drift term and the sensing loop, not the weighting. Reported, not buried.

Single-corridor mazes

Where there is only one route, route-critical sensing provably cannot help — confirmed by a maze negative control. The claim's boundary, not a defect.

Real off-road drift (FoMo)

On a full year of forest-trail traversal costs, path-level coverage holds at 1.000 but the marginal edge guarantee strains slightly (0.87 vs 0.90) — real winter→summer shifts are harsher than bounded synthetic drift. An honest datapoint, not a perfect one.

Use it

Reproducible to the last number.

Run it

# clone, install, test
git clone https://github.com/Archerkattri/CERT-FLOW
cd CERT-FLOW
python -m venv cert_env && source cert_env/bin/activate
pip install -e ".[dev,fast]" pandas h5py tables
pytest   # 227 tests · core sweep ≈ 100 s

Every figure and table regenerates from a script in scripts/; results live in docs/results/.

Cite it

@article{attri2026certflow,
  author = {Attri, Krishi},
  title  = {{CERT}: Certified Route Planning
            under Drifting Costs},
  year   = {2026},
  doi    = {10.31224/7306}
}

Paper · engrXiv Code · GitHub Software · Zenodo ORCID Scholar