A provably correct MPC approach to safety control of urban traffic networks

Sadra Sadraddini, Călin Belta

Abstract

Model predictive control (MPC) is a popular strategy for urban traffic management that is able to incorporate physical and user defined constraints. However, the current MPC methods rely on finite horizon predictions that are unable to guarantee desirable behaviors over long periods of time. In this paper we design an MPC strategy that is guaranteed to keep the evolution of a network in a desirable yet arbitrary -safe- set, while optimizing a finite horizon cost function. Our approach relies on finding a robust controlled invariant set inside the safe set that provides an appropriate terminal constraint for the MPC optimization problem. An illustrative example is included.

1. Introduction

Urban traffic management systems increasingly rely on Model Predictive Control (MPC) to optimize signal timings by predicting traffic flow over a short future horizon. Despite its popularity, MPC is inherently "myopic." A controller may select an action that appears optimal within the immediate planning window but inadvertently leads the network into a state where gridlock or "spill-back"—where traffic backs up into preceding intersections—becomes unavoidable in the long term.

Standard MPC formulations lack mathematical guarantees against such outcomes, especially when dealing with the non-convex constraints and stochastic arrival rates typical of real-world traffic. This paper addresses these shortcomings by proposing an MPC framework that ensures "recursive feasibility," guaranteeing that if a safe control action exists at the current time step, one will always exist for all future time steps.

2. Methodology

The proposed approach integrates formal methods with control theory through a three-stage process:

2.1 Finite State Abstraction

Traffic networks are continuous systems where the state is defined by the number of vehicles on each link. To apply formal verification techniques, the authors abstract this continuous state space into a finite state system by partitioning it into hyper-rectangles. This transformation converts the complex differential or difference equations of traffic flow into a discrete logic problem.

2.2 The Safety Game and MRCIS

Using algorithms from formal methods, a "safety game" is solved on the abstract model. The goal is to identify the Maximal Robust Controlled Invariant Set (MRCIS), defined as the "Safe Zone." If the traffic state remains within this zone, there is a guaranteed sequence of signal control actions to maintain safety, regardless of adversarial exogenous arrivals (within defined bounds).

Figure 1: Schematic representation of traffic links and flow directions in the network model.

2.3 MPC with Terminal Constraints

The identified Safe Zone is utilized as a terminal constraint in the MPC optimization problem. While the MPC optimizes for performance metrics, such as minimizing total travel time, it is strictly constrained to ensure that the predicted state at the end of the horizon resides within the MRCIS. The resulting optimization is solved using Mixed Integer Linear Programming (MILP) or exhaustive enumeration for smaller topologies.

3. Illustrative Example

The framework was evaluated using a synthetic urban corridor consisting of 9 links and 3 intersections. Parameters such as link capacities, maximum flow rates, and turning ratios were set to simulate realistic conditions. Exogenous arrival rates were treated as adversarial inputs to test the robustness of the safety guarantees under worst-case scenarios.

4. Results and Discussion

The simulation results demonstrated that the robust MPC approach successfully maintained the network state within the safety boundaries. The "robustness" metric—the distance from the safety boundary—remained positive throughout the simulation, effectively preventing gridlock.

Computationally, the abstraction process for the 9-link network took 434 seconds, and solving the safety game required 31 seconds on a standard laptop. The abstraction generated 3,888 states, with 1,176 identified as part of the MRCIS. This highlights that a significant portion of the state space is potentially unsafe if managed by a purely myopic controller.

5. Conclusion

This paper presents a novel method for bridging formal verification and traffic control. By separating safety (via the Safety Game) from performance (via MPC), the system provides provable guarantees against gridlock. Future work will address the "curse of dimensionality" inherent in state space abstraction, potentially through the use of machine learning to learn safe sets from historical data, thereby improving scalability for larger urban networks.

Summary updated

Abstract

Model predictive control (MPC) is a popular strategy for urban traffic management that is able to incorporate physical and user defined constraints. However, the current MPC methods rely on finite horizon predictions that are unable to guarantee desirable behaviors over long periods of time. In this paper we design an MPC strategy that is guaranteed to keep the evolution of a network in a desirable yet arbitrary -safe- set, while optimizing a finite horizon cost function. Our approach relies on finding a robust controlled invariant set inside the safe set that provides an appropriate terminal constraint for the MPC optimization problem. An illustrative example is included.
BibTeX
@misc{sadraddini2016provably,
  author = {Sadra Sadraddini and Călin Belta},
  title = {{A provably correct MPC approach to safety control of urban traffic networks}},
  year = {2016},
  eprint = {1602.01028},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.01028},
}
Figure