Well-Balanced Reachable Sets for Ambiguous Shock Physics and Anonymous Traffic

Some physical systems are described by equations that never quite pin down what happens at a shock. Examples include layered fluids, shallow flows with vertical shear, and some multi-lane traffic models. In these "non-conservative" systems, the jump in state across a discontinuity depends on an unmodeled choice: the path the solution takes through state space inside the shock. Numerical schemes usually pick a straight-line path, and for the shear shallow water model this has been shown to give the wrong shock speeds. We propose to stop pretending the path is known. Instead, we compute a reachable set, a guaranteed outer bound on every state the system could reach. This set covers all physically admissible paths at once. It is built by the same Taylor-remainder bounding ("conservative linearization") that the autonomous-driving verification community uses on vehicle models. It is also arranged so that the bound does not inflate at all when the system sits in a steady equilibrium.

The application motivating this is privacy-preserving safety for connected vehicles. Cars that rotate their pseudonyms, meaning temporary identifiers swapped to prevent tracking, break the per-vehicle tracking that current set-based occupancy predictors depend on. An ego vehicle that instead predicts an anonymous aggregate traffic field never needs to re-link identities. That aggregate field obeys exactly the kind of non-conservative, source-driven wave equation where path ambiguity and spurious equilibrium drift are the main obstacles to a tight, certified bound. The two-sentence version is this. We turn the unresolved shock physics of non-conservative PDEs into a bounded uncertainty and propagate it as a zonotope, using equilibrium variables so the set stays tight at steady state. We then use the result to give certified occupancy predictions from identity-free traffic densities.

Core Claim

Two facts drive the claim. First, the reachable set of a path-conservative, well-balanced semi-discretization can be computed with zonotopes, which are sets described by a center plus a weighted sum of "generator" directions with weights in [-1, 1]. Second, the path ambiguity at shocks enters that set as a small number of extra generators rather than as a modeling error.

Concretely, at each cell interface the scheme's jump term is the integral of $A(\phi)\,\partial_\tau\phi$ along a path $\phi(\tau; u_L, u_R; \theta)$. Here $A$ is the state-dependent coefficient matrix and $\theta$ is a parameter that bends the path away from the straight segment. The parameter $\theta$ ranges over a bounded set $\Theta$ chosen to contain the physical regularizations, for example the paths implied by vanishing viscosity. We linearize this integral in $\theta$ and bound the remainder rigorously. The resulting enclosure contains every weak solution whose path lies in the family.

We perform the linearization in equilibrium variables, the quantities such as total energy and discharge that are spatially constant at steady state. Expanded around an equilibrium, the semi-discrete residual is identically zero there. The Lagrange remainder therefore scales with the deviation from the equilibrium manifold rather than with the deviation from a drifting nominal trajectory. A singleton initial set at equilibrium then stays a singleton up to machine precision, instead of growing through the wrapping effect.

What is new is the combination: a certified bound on all admissible weak solutions of a non-conservative balance law, with steady-state exactness. Prior path-conservative work produces one deterministic solution for one path. Prior reachability work handles finite-dimensional vehicle ODEs only.

Relation to Prior Work

The PDE side supplies the method and motivates the gap. The well-balanced path-conservative discontinuous Galerkin method of Zhang, Xia and Xu combines straight-line path theory with an equilibrium-preserving polynomial space for two-layer shallow water. It reaches residuals of $10^{-13}$ to $10^{-15}$ on still- and 1D moving-water states. The central-upwind schemes with flux globalization of Chu et al. achieve the same steady-state property by reconstructing equilibrium variables. The moment-equation extensions (flux globalization for SWLME, DG for SWLME) carry this to more equations. We reuse their equilibrium-variable reconstruction as the coordinate system for linearization. Unlike all of them, we propagate sets and treat the path as uncertain rather than fixed.

The constraining result comes from Chandrashekar et al. and Nkonga et al.. For the shear shallow water model they show that straight-line paths converge to incorrect jumps, and they give exact Riemann solutions built from physical regularizations. This rules out any design that hard-codes one path. It also gives us ground truth: the exact solution must lie inside our enclosure. The relaxation analysis in Numerical schemes for coupled systems of nonconservative hyperbolic equations suggests one way to generate the path family $\Theta$ from relaxation limits.

The reachability side supplies the set machinery. Althoff's conservative linearization bounds the Taylor remainder over the current set and propagates a linear inclusion with zonotopes. Krylov-subspace propagation (Reachability Analysis of Large Linear Systems With Uncertain Inputs in the Krylov Subspace) is what makes the hundreds of states of a spatial discretization tractable. Kochdumper et al. document how badly this degrades: on CommonRoad, verification success fell from 100% at a 0.005 s step to 0% at 0.1 s. This is the wrapping effect our equilibrium-variable linearization is meant to suppress. None of these papers handles PDE operators, path ambiguity, or balance laws.

The privacy side motivates the application. Carrizosa-Rendón et al. estimate per-obstacle control zonotopes from a sliding window of associated observations. A pseudonym change empties that window. Jin et al. show that re-linking across mix zones by kinematic continuity is easy when traffic is sparse. A safe tracker that re-links therefore defeats the purpose of rotation. Sheik et al. show that certificate-based pseudonyms on automotive ARM hardware cost 20 ms to sign and 32 ms to verify, against a 50 ms budget. That latency must be absorbed as delay in any closed-loop bound. Privacy-Preserving Set-Based Estimation Using Differential Privacy and Zonotopes shows that truncated noise keeps zonotope containment under differential privacy. This lets us optionally privatize the aggregate counts without losing the guarantee.

Research Program

The first stage is purely numerical and decides whether the idea works at all. We will build a set-valued version of a first-order path-conservative finite volume scheme. For the shear shallow water and two-layer shallow water systems we will then build a set-valued central-upwind scheme with flux globalization. The steps are as follows. We define a path family $\Theta$ by perturbing the straight segment with low-order polynomial bends, and calibrate it on viscous-limit computations. We write the semi-discrete right-hand side in equilibrium variables. We bound the second-order remainder of both the state dependence and the $\theta$ dependence with interval arithmetic over the current zonotope. We propagate with order reduction to keep the generator count bounded.

We will also implement the non-negotiable control version: identical machinery linearized in conservative variables. This isolates what equilibrium variables buy. Following the inversion cost noted by Zhang, Xia and Xu, we will measure how often the equilibrium-to-conservative inversion must be enclosed by interval Newton steps, and what that costs near strong shocks.

The second stage transfers the solver to traffic. We use the Aw-Rascle-Zhang model in primitive variables (Boundary Observer for Congested Freeway Traffic State Estimation via Aw-Rascle-Zhang model), plus a lane-coupling term we add for multi-lane roads; that coupling is what makes the system genuinely non-conservative. Road grade and lane drops act as source terms with equilibrium flow states.

The ego vehicle observes only anonymous per-cell counts and mean speeds, optionally with truncated differential-privacy noise. It treats these as a zonotopic initial and boundary condition and computes a reachable density field over the planning horizon. It converts high-density regions into occupancy constraints for the ego planner. Pseudonym verification latency enters as a bounded input delay.

We should be candid about the weak link. The single-lane Aw-Rascle-Zhang model has a conservative form, so path ambiguity matters there only through our lane-coupling extension. If that extension does not produce shocks whose jump depends materially on the path, the traffic stage reduces to "well-balanced aggregate reachability." That is still useful, but it is a weaker claim.

Baselines

The naive reference point is the per-vehicle estimator of Carrizosa-Rendón et al. run under pseudonym rotation with a tracker that resets on every identifier change. After each reset it falls back to worst-case physical input bounds. With oracle identities that paper reports 89.13% containment of actual positions over 1,500 predicted occupancy sets, and 90.00% control-set containment. These are the target an identity-free method should approach. No reported result was found on Lacuna for the same estimator under pseudonym rotation, so we will measure it ourselves.

The strongest privacy-violating competitor is the same estimator with a kinematic-continuity linker that re-associates identities across swaps. It should match the oracle on safety while scoring high linking accuracy. Beating it means comparable containment and planner freeze rate, with linking accuracy near the differential-privacy level that Jin et al. report as "≈ 0".

On the PDE side, the strongest existing method is the deterministic well-balanced path-conservative scheme with a straight-line path (Zhang, Xia and Xu; Chu et al.). It is run on the same meshes, CFL numbers and test cases. On those cases its steady-state residual is $10^{-13}$ to $10^{-15}$. Our set-valued scheme must match that residual on equilibria, and its center must reproduce the deterministic solution. On shear shallow water Riemann problems, our scheme "beats" it if our enclosure contains the exact solution of Nkonga et al. where the straight-line solution does not, with an enclosure width a small fraction of the jump size.

The key-ingredient ablation is identical set propagation linearized in conservative variables. It gets the same generator budget, order reduction and time step, and we report enclosure width at equilibrium and away from it as a function of the time step. This mirrors the 0.005 s versus 0.1 s sensitivity documented by Kochdumper et al..

A second ablation fixes $\theta$ to the straight path and drops the path generators. This shows whether the path uncertainty, rather than ordinary state uncertainty, is what captures the true shock.

Why not just…?

Why not just run an ensemble of simulations over several paths? This is the most serious threat. Sampling a handful of paths from $\Theta$ and taking the hull of the results may give nearly the same envelope at a fraction of the effort. Its weakness is that it guarantees nothing between samples, which is the same objection Althoff raises against Monte Carlo safety assessment. The ensemble hull can also miss the extremes when the jump depends non-monotonically on the path. We will run it at matched runtime and report two things: how often the exact Riemann solution falls outside the ensemble hull but inside our enclosure, and the width ratio between the two. If the ensemble is always contained and nearly as tight, the honest conclusion is that the certified version earns its cost only in safety-critical use. We would say so.

Why not just refine the time step in standard conservative linearization? Refinement does control the remainder; Kochdumper et al. reach 100% verification at 0.005 s, at about 6 s per scenario. For a PDE discretization with hundreds of states, however, the runtime multiplies with the state count. Refinement also never removes the equilibrium mismatch: an unbalanced scheme drifts at steady state at any resolution, which is the "ghost wave" problem of Well-balanced methods for computational astrophysics. The conservative-variable ablation, swept over time steps, will show whether equilibrium-variable linearization reaches a given width at a coarser step.

Why not just keep per-vehicle tracking and link identities, or simply widen the bounds after a reset? Linking defeats rotation; Jin et al. show kinematic continuity re-links sparse traffic easily. Widening after reset is safe but drives the planner toward freezing. Both are included as baselines with containment, freeze rate and linking accuracy measured together. The aggregate approach must show it sits on a better privacy-safety trade-off, not merely a different one.

Why not just use group or identity-based signatures so identities stay hidden but authenticated? Sheik et al. measure 946 ms identity-based verification on automotive ARM hardware, roughly 20 times the 50 ms limit, and up to 127% message overhead for group signatures. Real-time pipelines are therefore pushed toward certificate pools with frequent rotation, which is the regime where tracking breaks.

Proposed Experiments and Decisive Checks

The first decisive check is containment of the exact solution on the shear shallow water Riemann problems of Nkonga et al. If our enclosure fails to contain the exact states for a path family calibrated independently of those problems, the core claim fails.

The second check is steady-state exactness on the two-layer equilibrium suite of Zhang, Xia and Xu. A singleton set at still-water or 1D moving-water equilibrium must stay at $10^{-13}$ to $10^{-15}$ width over long horizons. Small perturbations must yield widths that scale with perturbation size rather than horizon length. The conservative-variable ablation should show the opposite trend.

The third check is the traffic stage. We will run CommonRoad scenarios augmented with simulated pseudonym rotation, with mix zones placed at varying traffic densities and 52 ms authentication delay injected as input lag. We report occupancy containment against the 89.13% oracle reference, planner freeze rate, linking accuracy of an adversary observing the ego's inputs, and per-step runtime against the 50 ms budget. We will add a differential-privacy variant of the aggregate counts using truncated noise, and report how containment degrades with privacy budget.

The result that would matter most is containment near the oracle with linking accuracy near zero in dense traffic. A clear negative result would also be informative: if aggregate fields are too coarse to bound individual occupancy in sparse traffic, that would locate where identity-free safety is impossible.