ADR-024: newell-3det — Newell (1993) three-detector interior reconstruction

Status: accepted (implemented) Date: 2026-07-14 Deciders: DNL/estimation tracks — the benchmark’s first traffic-state-estimation task File: docs/design/adr-024-newell-3det.md

Context

Newell’s simplified theory of kinematic waves (1993, a three-part TR-B trilogy) recasts the LWR model in cumulative-count coordinates N(x, t). Under a triangular fundamental diagram the interior state at any point is the lower envelope of two translations of the boundary cumulative curves — one carried forward at the free-flow speed vf, one carried backward at the wave speed w:

N(x, t) = min( N_up(t - x/vf),  N_dn(t - (L - x)/w) + kappa*(L - x) )

on a homogeneous link [0, L] with detectors at x = 0 (upstream, N_up) and x = L (downstream, N_dn), a shared vehicle numbering, and an empty-start record (N0 = 0). The kappa*(L - x) storage term is the maximum vehicle count that can be stored between x and the downstream detector.

Why not a third LinkModel. Newell’s loading content — the sending/receiving evaluation of the two shifted curves at the link ends — already ships as ltm (adr-016, Yperman 2007); dnl/ltm.py lines 15-16 ARE Newell’s minimum principle at x = 0 and x = L, and model-specs.json says LTM “operationalized” it. But LTM deliberately discards the interior field (ltm.py: “no interior discretisation”). Newell’s actual Part-I content — the min at interior x — is therefore unshipped. Shipping it as a second loader would be strictly duplicative; shipping it as the interior reconstruction is a genuinely new task family.

The task family: state estimation. Given measured (noisy / partial) boundary detector curves, reconstruct the interior cumulative field. This is the first traffic-STATE-estimation (TSE) unit in the repo — distinct from assignment (T1), OD estimation (T2), and network loading (DNL). The oracle and certifier are Newell’s exact minimum principle (the paper’s content); the observation dials (Poisson counts, Gaussian reading error, missing windows) are the repo’s own P3 conventions (observe/levels.py) — the paper contains no estimation numerics.

Decision

Ship newell-3det as a parallel module src/tabench/newell/ (the adr-019 bottleneck/ pattern), importing the dnl machinery read-only. Additive: no edit to dnl/scenario.py hashes, observe/levels.py contracts, core/scenario.py, or any existing hash; the golden Braess content hash cf00f411cdccec88019979e8cfbf3d8014ba590688b285a1db667315ac96762d is re-asserted in tests/test_newell.py.

  1. ThreeDetectorScenario (scenario.py, frozen, hashed "tabench-newell3d-scenario-v1;"). Study-link triangular FD (vf, w, kappa) with optional cap, the TimeGrid, the fixed interior query positions x_query, a truth recipe (piecewise-constant corridor inflow + downstream meter_cap), and the observation dials. Arrays are copied read-only; a float64 conditioning gate rejects a storage term kappa*(L - x) whose ULP exceeds the count resolution (the vi-due lesson). The truth boundary curves are never stored — they are regenerated by running LTM on a two-link corridor (_truth_scenario), whose study-link n_in/n_out ARE the two clean detector curves. The constructor validates that the generated pair satisfies the single-link Newell envelopes exactly (realizable LWR data by construction).

  2. Observation (observe.py, module-local so observe/levels.py is untouched). A seeded projection of the clean curves: "none" (oracle), "poisson" (per-interval counts, the LinkCounts precedent — monotone), or "gaussian" (a cumulative reading error N(0, sigma^2), the DayToDayCounts large-population Gaussian limit). up_windows/dn_windows mark unobserved windows (NaN). The DetectorObservation carries ONLY observables — no truth recipe reaches it.

  3. Reference estimators (solve.py). newell_min (naive: running-max monotonization then the min) and newell_min_isotonic (denoised: L2-optimal isotonic regression then the min), both pure functions of the model-visible ThreeDetectorProblem (public physics + grid + observed detectors). The emitted ThreeDetectorField is the (m, K+1) interior reconstruction.

  4. Certificate (P1) (metrics/newell_gaps.py, ThreeDetectorEvaluator). Pure function of (scenario bytes, emitted field). It regenerates the clean detector curves from the hashed recipe (the adr-023 discipline — never a stored array), evaluates the closed-form min at the fixed grid to get the reference M, and scores. Gating certificates (the “valid cumulative field” checks, all guaranteed by any min-of-monotone-boundaries reconstruction, so a legitimate noisy estimate passes while garbage is censored): finite / shape (raise) / hash; zero start; non-negativity; monotonicity via a running-max total-retraction budget (the adr-022 lesson — never per-step, so an eps-creep dip accumulated over K steps is caught by the aggregate mass budget). Ranking is interior_rmse = RMSE(emission − M) over the fixed hashed grid, on noisy/partial levels only.

  5. Fixed hashed query grid. Scoring is at the scenario’s hashed (x_i, t_k) grid, NOT any emitted-grid-dependent sweep — the vi-due CRITICAL (a solver-dilutable window is a false-accept surface). The emission shape is bound by the hash.

The exactness conditions and the sign convention

The two-term min is exact iff: (1) a triangular FD (exactly two wave speeds); (2) a homogeneous segment, no interior sources/sinks (Part II handles ramps by adding net cumulative ramp inflow); (3) FIFO single-pipe single-class flow with conserved numbering; (4) correct N0 offset and drift-free counts; (5) a causally sufficient record (shifted arguments inside the data — extending by 0 before an empty start is valid ONLY for empty starts); (6) LWR first-order dynamics with known (vf, w, kappa). For a general concave FD the two-term form is a majorant bound, not exact (full variational theory, Daganzo 2005, is needed); this unit ships the triangular case only and reconstructs on triangular-FD truth.

Sign convention (w > 0). With w the backward-wave MAGNITUDE the downstream shift is t − (L − x)/w (Boyles TNA eq. 9.46; Rey-Jin-Ritchie 2019 eq. 10; Daganzo VWP-2006-2 eq. 17). The +(L − x)/w variant is non-causal (it reads a future downstream value) and only appears where w is a signed negative velocity (Wikipedia, Yperman) — the same convention note ltm already documents for its receiving flow. The wrong sign is machine-detectable: on anchor A2 it moves the x = 2 min-switch from t = 10 to t = 14 (equality convention; pinned in test_newell.py).

The pairwise Newell envelopes are Tier B (the C5 analog)

Between every emitted position pair x_i < x_j two necessary LWR conditions hold for the exact field: forward free-flow N(x_j, t) <= N(x_i, t − (x_j−x_i)/vf) and backward storage N(x_i, t) <= N(x_j, t − (x_j−x_i)/w) + kappa*(x_j−x_i) (grid-edge relaxed like dnl_gaps C4/C5). The reference M passes both at 0.

These are reported, non-gating (Tier B), exactly as dnl_gaps C5 (the backward-wave envelope) is non-gating because CTM legitimately violates it. A legitimate NOISY reconstruction violates the physical envelopes at noise scale (a detector reading error above capacity is not capacity-feasible), so gating them would false-censor the honest naive baseline — the design pins both baselines as feasible = 1. Symmetrically, a tolerance loose enough to admit honest noise would excuse a teleport. The residual is therefore the science and the interior_rmse ranking is the plausibility check: a physics-violating field is far from the physical truth, so it cannot both cheat the ranking and pass. Reported with the adr-020 two-scale split (per-cell max residual AND aggregate violated mass) plus envelope_exact / envelope_at_resolution flags. This is the one deliberate deviation from the original sprint sketch (which listed the envelopes as gating): the executed evidence — the honest baseline’s O(noise) backward residual, machine-checked across 180 seed/noise configs — contradicts gating them, and the C4-gating/C5-Tier-B split is the repo’s own precedent for exactly this situation.

The triviality trap: clean is an oracle, never ranked

On clean data the reference estimator IS the closed-form min, so any submission evaluating the formula scores 0. The mitigation is structural, not tolerancing: the clean level is an oracle/validity row flagged rankable = 0 and is never ranked; ranking lives on the noisy/partial levels where the statistical content (denoising, fusing the two directional traces, bridging missing windows via the storage term) genuinely discriminates — the adr-023 pattern. The naive min-on-noisy-curves is the pinned baseline a better estimator must beat.

Analytic anchors

All recomputed in-test (tests/test_newell.py, house style: no trusted digits).

  • A1 free-flow (exactness). Meter above inflow, so the congested branch never binds: N(x, t) = N_up(t − x/vf) exactly at every interior x; oracle row.

  • A2 asymmetric spillback (interior RH shock). vf=2, w=1, kappa=3, L=4, inflow 1.0 into a 0.5 meter (adr-016 anchor (c)). q_A=1, k_A=0.5; q_B=0.5, k_B=kappa−q_B/w=2.5; RH shock speed −0.25 born at (x=4, t=2), so it passes x at t = 2 + (4−x)/0.25 (x=1→14, x=2→10, x=3→6) and reaches x=0 at t=18. At x=2 the min-switch is N=9 at t=10, post-shock N(2,t)=0.5t+4; reconstructed density (central x-difference) = k_B = 2.5. Oracle row.

  • A3 symmetric bottleneck (cross-model truth). vf=w=1, kappa=4, L=4, inflow 1.5 into a 0.5 meter (adr-016 anchor (b)). The truth-generating LTM boundary curves reproduce CTM byte-for-byte, doubly validating the truth generator (the lp-so-dta corridor==CTMLink move). Oracle row.

  • A4 noisy dominance (the acceptance test). A3 physics under a seeded Gaussian reading level (dt=0.25, sigma=1.2, seed pinned): the isotonic-then-min estimator strictly beats the naive running-max baseline in interior_rmse by a pinned deterministic margin (naive 1.0928, isotonic 0.4484), both feasible = 1, rankable = 1. Proves the ranked task separates methods and is not a formula evaluation.

  • A5 observability edge. Upstream masked over [11, 17] (clean): the congested branch alone pins the interior EXACTLY wherever it is active (error 0 on every congested-active cell); the ONLY discrepancy is x=1 at t∈{12,13} where the interior is still free-flow but upstream is unobserved (cong overestimates by exactly 1.0). A Newell-specific identifiability statement, reported per config.

Alternatives considered

  • A third LinkModel / second cumulative-curve loader: rejected — Newell’s loading content shipped as ltm; the min structure is byte-similar but the task is categorically different (boundary-curves-in → interior-field-out, closed-form, no time stepping, no node coupling).

  • Gating the pairwise envelopes at tol scale: rejected — false-censors the honest noisy baseline (measured across 180 configs), the C5 dilemma. Kept Tier B.

  • Capacity-projecting both estimators to make the envelopes gate cleanly: rejected — the capacity clip becomes the dominant shared denoiser and collapses the A4 discrimination (min margin turns negative across seeds).

  • Ranking the clean level / tolerancing the triviality: rejected — a formula evaluation with no benchmark content; the clean level is an oracle row.

  • Estimating N0 from data, non-empty starts, ramps between detectors, non-triangular FDs: out of scope (their own literatures); the unit restricts to empty-start, homogeneous, triangular-FD instances and raises/validates otherwise.

Consequences

The benchmark gains its first traffic-state-estimation task and a new task family (scenario space + observation level + evaluator), for one canon reference, single-link, no network. All changes are additive; the golden Braess hash is provably preserved; no output contract changed. Follow-ups: a certifier-upgrade that reuses the exact interior oracle to sharpen the Tier-B C5 backward-wave residual into an exact interior-residual diagnostic for ctm/godunov/ltm (touches the shipped DNLEvaluator, so a separate sprint); a Greenshields-FD variant that reconstructs with the triangular majorant and reports the honest upper-bound bias q*x*(1/v(k) − 1/vf); a multi-day Poisson ranked level.

Adversarial review

Three independent lenses (soundness, formulation, numerics), each executing code; every finding below is CONFIRMED by a runnable repro and regression-pinned in test_newell.py (streak: 13/13 sprints with at least one material defect).

MAJOR ×3, one root cause — masked-window branch-dropping. reconstruct_field set a masked branch to +inf: (a) when the masked branch returned, the raw min dipped below the loose single-branch values inside the window, so the honest reconstruction was non-monotone and the C3 retraction gate false-censored both reference baselines on 125/514 fuzzed windowed scenarios (including clean data — A5 escaped only because its mask sits entirely in the congested-active region); (b) time-disjoint up/dn windows can still doubly mask an interior cell after the branch shifts (vf=2, w=1: both branches of x=2 read t−1), yielding min(inf, inf) = inf and a C0 whole-field false-censor, with the constructor accepting such configs (its realizability check runs windowless). FIXED at the root: the reconstruction is now the suffix-minimum of the retained bounds — the tightest nondecreasing upper bound consistent with the data (a bound at t' bounds every t <= t'), which repairs the dip, bridges doubly-masked cells from the next observed bound, and is the identity on fully observed data (the reference M is unchanged).

MAJOR — degenerate-rankable cards. rankable keyed on noise kind alone: a byte-clean gaussian, sigma=0 card was RANKED while the min formula scores exactly 0 (the triviality trap the design exists to avoid), and none + drift degraded the data while staying unranked. Both combinations are now constructor errors.

MINORs, fixed + pinned: (a) total_demand = inf was accepted, making the evaluator’s eps_count infinite and silently neutering every censor gate — it also enabled a confirmed content-hash byte-migration collision (a float64 whose bytes spell a label let one array’s tail masquerade as the next array’s head); finiteness is now required, drift is validated finite, and the hash length-frames every array; (b) meter_cap above the geometric apex crashed three layers deep in LinkDynamics although a never-binding meter is a sanctioned concept — clipped at the apex now (physics-identical, distinct hash); (c) a constructor-accepted extreme card crashed numpy’s Poisson sampler — per-step means above 1e15 are rejected; (d) the C3 budget summed dips over cells, duration-amplifying a sustained sub-eps dip into a censor — now the max total drop from the high-water mark (the adr-022 convention); (e) the truth generator is exact only on grid-aligned recipes (all shipped anchors are, verified to ~4e-15) and carries an O(meter_cap·dt) plateau artifact off that subspace — the docstrings now scope the claim and state that M (identical for every submission), not the continuous-time LWR field, is the scoring reference. NOTEs: the wrong-sign anchor number corrected (t=10 → t=14 under the equality convention); the _fill_nan “never scored” claim corrected (bridge values are read within one grid step of window edges); x_query docstring [0, L]; documented that all dial values are public (drift in the observation meta means drift cards test bias-correction under a known gain, not blind robustness) and that gaussian ranked cards need n_days ≲ 10 at σ ≈ 1.2 before day-averaging collapses the A4 margin (0.64 at 1 day → 0.06 at 10).

Survived (highlights): the sign convention and formula re-derived from LWR characteristics and cross-checked against an independent from-scratch Godunov simulator on 7 hand-built regimes + 200 random instances (reconstruction error does not shrink with simulator refinement — it is the simulator that diffuses); the meter-link truth generator proven uncontaminable for meter_cap <= apex; all anchors recomputed (Rankine-Hugoniot crossings t=6/10/14, x=0 arrival t=18, post-shock density kappa − q_B/w); the Tier-B envelope demotion’s “cannot both cheat the ranking and pass” claim verified (ranking is truth-referenced, so a large envelope violation implies a large RMSE); no information leak in ThreeDetectorProblem/DetectorObservation (no seed, no clean curves, no recipe); day-mean denoising is honest 1/sqrt(n_days), never trivially 0; hash coverage complete over all 18 score-affecting dials; 882 no-window baseline evaluations all feasible; the pinned A4 floats judged platform-stable (PCG64 + pure-Python PAVA); golden Braess hash unmoved; full suite green.

Sourcing

The primaries are paywalled (ScienceDirect 403) and attributed unread: Newell 1993 Part I (TR-B 27(4):281-287, DOI 10.1016/0191-2615(93)90038-C — the only part in references.json, newell1993simplified), Part II (289-303, DOI 10.1016/0191-2615(93)90039-D) and Part III (305-313, DOI 10.1016/0191-2615(93)90040-H) — DOIs recovered and Crossref-verified but NOT added to references.json. The operative two-translation min statement is Part II’s (Part I gives the general lower-envelope theory); the trilogy is cited jointly as Rey-Jin-Ritchie and Daganzo do. No equation number of any primary is cited — only abstract-level claims and open restatements. The formulation was cross-verified from three OPEN sources read in full:

  • Boyles, Lownes & Unnikrishnan, Transportation Network Analysis Vol. I (arXiv:2502.05182), §9.4.4 eq. 9.46 (the triangular two-term min), §9.5 (the LTM operationalization), worked Fig-9.23 example.

  • Rey, Jin & Ritchie (2019), An extension of Newell’s simplified kinematic wave model to account for FIFO violation, TR-C 109:79-94, DOI 10.1016/j.trc.2019.10.008 — open eScholarship (qt16r3w53g), eqs. 7-11 (the exact three-detector formula, the N0 offset), the three-detector naming credited to Daganzo (1997) sec. 4.4.

  • Daganzo, On the variational theory of traffic flow, UCB-ITS-VWP-2006-2 — open eScholarship (qt61v1r1qq), eq. 17 (Newell’s queuing formula as a primal of variational theory), footnote 10 (two boundary points suffice given capacity-feasible boundary slopes).

The NOISY three-detector task framing is the repo’s own P3 convention (the LinkCounts/DayToDayCounts precedents), NOT the paper’s — Newell (1993) contains no estimation numerics, no noise model, no benchmark network. The stochastic-TSE lineage (Daganzo 2005 variational theory, Laval-He-Castrillon 2012 stochastic three-detector, Coifman 2002, Deng-Lei-Zhou 2013) is tier-2/3 context, attributed unread. Every anchor is a hand-derived closed form.