Machine-Learned Prediction Equilibrium for Dynamic Traffic Assignment

Lukas Graf, Tobias Harks, Kostas Kollias, Michael MarklAAAI 2022 · DOI

Traffic congestion is more than a daily frustration; it is a complex mathematical challenge involving dynamic feedback loops. When a navigation app predicts a travel time, it influences driver behavior. If every driver follows the same "fastest" route prediction, that route inevitably becomes congested, rendering the original prediction inaccurate. This circular dependency between prediction and behavior is the core problem addressed by researchers from the University of Augsburg and Google in their AAAI-22 paper.

The Feedback Loop of Traffic Prediction

Traditional traffic models typically operate at two extremes. "Full Information" models assume drivers are omniscient, knowing exactly how traffic will evolve in the future. Conversely, "Instantaneous Information" models assume drivers are short-sighted, choosing routes based only on current queue lengths. Neither approach accurately reflects the reality of modern navigation apps, which provide predictions that both inform and alter traffic flow.

The authors propose a new framework for Dynamic Traffic Assignment (DTA) that incorporates machine-learned (ML) predictors. They introduce the concept of a Dynamic Prediction Equilibrium (DPE): a stable state where, at any given moment, every driver is assigned to a path that is the shortest according to a specific predictor function ($\hat{q}$).

Theoretical Framework and Predictor Properties

To ensure that a DPE actually exists in a network, the researchers identified three essential properties that a predictor must satisfy:

  1. Continuity: Small changes in traffic flow should not result in erratic jumps in predictions.
  2. Obliviousness: The predictor must only use past and current data, ensuring it does not "cheat" by looking at future states.
  3. FIFO-respecting: Predicted exit times must follow First-In, First-Out logic; a driver starting later should not be predicted to arrive earlier than one who started before them.

Using variational inequalities, the authors proved that any network using predictors with these properties will reach a stable equilibrium. They also highlighted the need for a Regularized Linear Predictor. While a standard linear predictor (based on current queue growth) can be unstable due to discontinuous derivatives, a regularized version using a rolling average of the gradient restores mathematical continuity and guarantees equilibrium.

Experimental Setup and Scaling

The framework was evaluated across three distinct scenarios to test both theoretical validity and computational efficiency. These ranged from a small synthetic network to a massive real-world model of Tokyo.

Summary of network sizes and computation times for the synthetic and real-world datasets.

As shown in the table above, the system scales effectively. Even for the Tokyo network, which features nearly 5,000 edges, the equilibrium was computed in approximately 5.7 minutes on a standard laptop, demonstrating the practical feasibility of the DPE approach for urban-scale planning.

Performance and Key Results

The researchers implemented a Linear Regression Predictor ($q^{ML}$) trained on historical queue data from target edges and their neighbors. This allowed the model to learn the "signature" of a network—how specific bottlenecks react to surges in inflow.

Comparison of average travel times for various predictors against the theoretical optimum.

In comparative tests, the ML-based predictor significantly outperformed traditional heuristics. As illustrated in the performance plot, the ML predictor ($q^{ML}$) consistently achieved average travel times closest to the theoretical optimum (OPT). In contrast, the "Zero-Predictor" (which assumes no queues) performed the worst, confirming that even simple predictions are better than none, but sophisticated ML models provide the most substantial efficiency gains.

Conclusion and Future Directions

This research provides a rigorous mathematical foundation for integrating ML into traffic routing. While the current study used linear regression for mathematical tractability, the authors suggest that more complex architectures like Graph Neural Networks (GNNs) or LSTMs could offer even higher accuracy. Future work may also explore "iterative learning," where models are re-trained on their own equilibrium flows to further optimize urban traffic management.

Summary updated

BibTeX
@inproceedings{graf2022machine,
  author = {Lukas Graf and Tobias Harks and Kostas Kollias and Michael Markl},
  title = {{Machine-Learned Prediction Equilibrium for Dynamic Traffic Assignment}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20438},
}
Figure