CERT·FLOW

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.

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.

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.

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.

Coverage, observable · opt-in

Coverage you can watch — not just claim.

A certificate pinned at coverage 1.000 hides an awkward truth: the claim was untestable. An opt-in observability layer turns it into a live, alarming quantity — a WATCH conformal test-martingale and a Shiryaev–Roberts change-detector run alongside the planner and fire the moment the staleness model the proof leans on actually breaks. Every piece is off by default, a config flag or a new class, and touches no certificate: the (LB, UB, confidence) stream is byte-identical on or off.

Wired behind PlannerConfig(watch_monitor=True), sum_aware_ub=True / cia_path_certificate(), shrink_license=True, and hybrid_sensing=True; full write-ups in width-attack-2026.md, hybrid-sensing-2026.md, crossover-2026.md, and live-wiring-2026.md. The program's meta-lesson, kept honest: the certify/verify layer survives real data — and the width it costs is now measurably shrinking.

The theory

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

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.

Use it

Reproducible to the last number.

# 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   # 250 tests · core sweep ≈ 100 s

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