Planning Around Almost-Rational Drivers: KKT-Reduced Chain Games for Wave-Damping Automated Vehicles

An automated car in human traffic can erase a stop-and-go wave, but only if it anticipates how the human drivers behind it will react to its speed changes. One way to plan this is a leader–follower (bilevel) problem. The automated car is the leader. Each human is a follower who picks an acceleration by solving a small optimization problem of their own. The standard trick for solving such problems quickly replaces each follower's problem with its optimality conditions, the Karush–Kuhn–Tucker (KKT) conditions, which are the first-order equations an optimum must satisfy. That turns the nested problem into one ordinary, if awkward, optimization problem. The trick has a known weakness: it assumes every human acts exactly optimally under the model. Real drivers do not, and planners built this way lose their advantage as human behavior gets noisier.

We propose to plan against a set of responses instead of a single predicted one. Each human is assumed to be within $\varepsilon$ of optimal under a fitted driving cost, and $\varepsilon$ is calibrated from real highway trajectories so the set covers observed behavior with a stated probability. The planner stays efficient for two reasons. The worst-case response inside that set can be written as a second small convex problem and flattened with the same KKT trick. And single-lane car-following forms a chain, in which each driver reacts only to the car ahead, so the flattened problem grows linearly with the number of modeled drivers rather than quadratically. The practical bet is that "almost-rational" response sets are much tighter than the generic worst-case disturbance boxes used by robust controllers today. The automated car can then brake and accelerate less conservatively, and so damp waves more, at equal safety.

Core Claim

The closest existing system, SICNav (Deploying SICNav in the Field), replaces pedestrians' collision-avoidance programs with their KKT conditions and solves the resulting single-level model predictive control problem at 10 Hz. It has three limits. It models humans as exactly optimal. Its cost grows with all pairs of agents, which forces truncation to 3–4 humans. And its own authors report that its edge over simple predictors narrows as estimation noise grows. We make two claims against that baseline. The first is structural: for longitudinal mixed traffic, the follower interactions form a chain, so the flattened problem has banded structure and can model 15–25 upstream drivers, which is roughly the length of a wave, within a 10 Hz budget. The second is behavioral, and it is the one that must survive the experiments: an $\varepsilon$-suboptimal response set calibrated on real data covers held-out human accelerations at the target rate with substantially smaller volume than a box disturbance calibrated to the same coverage. That smaller set should translate into better wave damping at equal minimum time-to-collision.

Concretely, human $i$ at step $t$ chooses acceleration $y_i$ by minimizing a fitted cost $g_i(y_i; s_{i-1}, s_i)$. The cost trades off desired-speed tracking, time-headway tracking and comfort. It depends on its own state $s_i$ and its predecessor's delayed state $s_{i-1}$, subject to linear limits $h_i(y_i) \le 0$ covering braking bounds and a gap constraint. The response set we plan against is

$$ \mathcal{Y}_i^{\varepsilon} = \{\, y : h_i(y) \le 0,\;\; g_i(y) \le g_i(y_i^\star) + \varepsilon_i \,\}, $$

where $y_i^\star$ is the exact optimum, represented through its KKT conditions, and $\varepsilon_i$ is a per-driver-class slack chosen by split conformal calibration. The automated car's safety constraints must hold for the worst $y \in \mathcal{Y}_i^{\varepsilon}$ among the vehicles directly adjacent to it. This inner worst case is itself a convex program in $y$ once the planner's decision is fixed, so its KKT conditions are appended as a second complementarity block. The wave-damping objective uses the nominal chain $y^\star$.

Research Program

The first component is the follower model. We fit convex quadratic driving costs with reaction delay per driver class to vehicle-by-vehicle trajectories from the I-24 MOTION data used in the Lagrangian variable speed limit work. We then calibrate $\varepsilon$ on a held-out split. This step can be evaluated entirely offline, before any control, and it is the first decisive check.

The second component is the solver. We build on the Acados/CasADi interior-point approach that SICNav validated at 10 Hz. We order variables by follower index and time so the complementarity Jacobian is block-banded. Complementarity is handled by the standard relaxation $\lambda_i h_i \le \delta$ with $\delta$ driven down, because degenerate constraint qualifications otherwise stall solvers. Warm starts come from a forward rollout of the nominal chain. We deliberately avoid Big-M mixed-integer encodings, which add a binary variable per constraint per driver per step. The globally optimal convex mixed-integer formulation of Lee et al. shows that route is feasible for 2–3 agents with double-integrator dynamics, not for a 20-car chain at 10 Hz.

The third component is closed-loop evaluation in Flow/SUMO (Flow, Benchmarks for RL in mixed autonomy). Human vehicles there are driven by stochastic car-following models plus replayed I-24 residuals, so the simulated humans are not our fitted model. That mismatch is the point of the test.

Two known limitations are scoped out rather than hidden. Pessimism is applied only to vehicles adjacent to the automated car. Worst-case deviations compounding down the chain are measured empirically, through minimum time-to-collision across all vehicles, rather than guaranteed. Lane changes are excluded from the first study because they break the chain structure.

The work sits relative to three groups of prior papers. The macroscopic mixed-autonomy routing and pricing results (Kolarich & Mehr, Pricing Traffic Networks with Mixed Vehicle Autonomy) motivate the view of automated vehicles as leaders over selfish humans, but they work with static flows and offer no trajectory-level algorithm. Differentiable Bilevel Programming for Stackelberg Congestion Games constrains our design. It shows KKT and sensitivity methods failing at city scale, which is why we stay at the tens-of-vehicles scale where banded structure keeps KKT reduction cheap. Active Inverse Learning in Stackelberg Trajectory Games models humans as boundedly rational followers, but over a finite hypothesis set and without collision constraints. We instead use a continuous, calibrated suboptimality set with hard safety constraints.

Baselines

The naive reference is all-human traffic, together with the same scenario in which the automated car simply runs the default car-following model. Every improvement is reported relative to these.

The strongest learned competitor on the ring road is the Flow PPO/TRPO controller. Flow reports that one learned automated vehicle among 22 raises average system velocity by "up to 57%" over the human-only baseline. We retrain it in our exact scenario, with our human-noise model, under the same simulator seeds and a matched wall-clock training budget. Our planner beats it if it matches its average velocity within the seed-level confidence interval with zero collisions and higher minimum time-to-collision, or clearly exceeds its velocity under the replayed-I-24 human noise, which the policy did not see in training.

On the merge and I-24-style bottleneck, the reference is the hierarchical Lagrangian speed planner (Hierarchical Speed Planner). It reports, in simulation, a 5.01% bottleneck throughput increase, a 15.41% system MPG increase and a 34.36% reduction in speed standard deviation. We reimplement it at the same penetration rate of 2.7–3.6% per lane, as in the field deployment. Beating it means lower speed standard deviation and higher MPG at no throughput loss.

The strongest model-based competitor is a nonlinear MPC that forward-simulates the fitted human model as a point prediction, with no bilevel structure. For the safety comparison we pair it with the cooperative barrier-function layer and conformal acceleration intervals of Zhou et al.. That paper reports a nearly 100% and a 70% expansion of the safe disturbance region over unshielded multi-agent RL. No reported result was found on Lacuna for a rollout-MPC or box-robust MPC on Flow's ring or merge tasks, so we run both ourselves. They get identical horizon, solver, cost weights, compute and conformal coverage level.

Two ablations isolate our ingredients. Setting $\varepsilon = 0$ gives an exact-rationality, SICNav-style planner. Truncating the chain to 3 followers tests the value of modeling the whole wave.

Why not just…?

Why not just train an RL policy, as Flow did? On the clean ring road it may match us, and we say so up front. The evidence against RL as the whole answer concerns safety and behavior outside the training distribution. Benchmarks for RL in mixed autonomy documents bottleneck policies that "cheat" by blocking a lane, and unshielded policies lose much of their safe disturbance region in Zhou et al.. The shifted-human-noise experiment settles whether RL's advantage holds when simulated humans stop matching training.

Why not just roll the fitted human model forward inside an ordinary MPC? For exact point predictions, rolling out the follower's quadratic program and embedding its KKT conditions are nearly equivalent. So with $\varepsilon = 0$ we expect little difference beyond solver behavior, and we will report that. What a rollout cannot express is the worst case over a cost-shaped set of near-optimal responses. The comparison against rollout-MPC under real I-24 residuals tests whether that matters.

Why not just add a box disturbance or a conformal interval around the prediction, as robust MPC and barrier-function shields do? This is the real threat. If humans' deviations from the fitted model are not concentrated in low-cost directions, the $\varepsilon$-set will be no tighter than a box, and our method reduces to a more complicated robust MPC. The offline coverage-versus-volume test below decides this before any closed-loop claim is made. If it fails, we drop the behavioral claim and report only the chain-scaling result.

Proposed Experiments

The first decisive check is offline and needs no controller. On held-out I-24 MOTION car-following segments, we compare two sets at 90% and 95% target coverage: the conformally calibrated $\varepsilon$-set and a conformal box around the point prediction. We compare empirical coverage and mean set width, reported as the acceleration interval length. The hypothesis passes only if the $\varepsilon$-set achieves the target coverage with meaningfully smaller width, and does so in the braking-dominant regimes where waves originate.

The second check is scaling. We measure solve time per 10 Hz step against the number of modeled followers (3, 5, 10, 20, 25) for the banded solver and for a dense ordering. We expect near-linear growth for the former, following from the chain's banded Jacobian. We report the largest chain that fits in 100 ms.

The third check is closed loop. It runs on Flow's 22-vehicle ring road and merge scenarios, and on an I-24-style bottleneck at 2.7–3.6% penetration, with human noise taken from replayed I-24 residuals. Metrics are average velocity, speed standard deviation, an MPG proxy, throughput, collisions, and minimum time-to-collision across all vehicles, including those far upstream where pessimism is not enforced. The headline result would be that the calibrated-$\varepsilon$, full-chain planner dominates box-robust MPC on speed standard deviation at equal or better minimum time-to-collision. It should also dominate both the $\varepsilon = 0$ and the 3-follower ablations.

A negative outcome would also be informative. If $\varepsilon = 0$ does as well under realistic noise, exact-rationality KKT planning is adequate for cars even though SICNav found it degrading for pedestrians. If truncation to 3 followers does as well, modeling the whole wave is unnecessary.