Distributed Mixed-Integer Quadratic Programming for Mixed-Traffic Intersection Control

arXiv:2504.04618 · eess.SY, cs.SY · Submitted 2025-04-06 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "Distributed Mixed-Integer Quadratic Programming for Mixed-Traffic Intersection Control".

Dev: Here's the gist of the paper. The gist In this paper, they present a distributed algorithm utilizing proximal ADMM in conjunction with sequential constraint tightening to address mixed-integer quadratic programming (MIQP) problems associated with traffic light systems and connected automated vehicles (CAVs) in mixed-traffic intersections.

Rosa: Problem Formulation The research formulates a comprehensive MIQP model aimed at optimizing the coordination of traffic light systems and CAVs, thereby fully capitalizing on the advantages of CAV integration under conditions of high penetration rates The optimization problem is formulated as follows: minimize J(sl, pl,i, vl,iul,i) for TLC–l and CAV–(l, i) over the control horizon.

Dev: The objective function minimizes a weighted sum of three terms: (1) maximizing the travel distance to reduce travel time (2) tracking the desired speed (3) minimizing acceleration rates to reduce energy consumption.

Rosa: The resulting MIQP problem is given as follows: minimize sl,pl,i,vl,i,ul,i for l∈L and i∈Cl(k0) subject to constraints (1), (2), (3), (4), (5), (6), and the big-M constraint formulation.

Title and authors: Rosa: So we’re looking at this paper, "Distributed Mixed-Integer Quadratic Programming for Mixed-Traffic Intersection Control," and it’s about using proximal ADMM with sequential constraint tightening to handle those tricky mixed-integer quadratic programming problems in traffic light systems and connected automated vehicles.

Dev: Yeah, that sounds like a lot of heavy math for a real-world intersection problem, Rosa. What is the main goal they are trying to achieve with this specific model?

Rosa: The paper says they formulate it to optimize the coordination between traffic lights and CAVs, specifically aiming to fully capitalize on the benefits of CAV integration even when there's high penetration rates.

Taro: So, if I'm driving through a mixed intersection, what’s the big question they’re trying to answer with this model?

Dev: The core idea here is tackling the complexity of coordinating traffic signals and vehicles using a distributed approach, Rosa. They use proximal ADMM for solving the relaxed version of the problem and then they use sequential constraint tightening to bring those binary variables back into reality.

Rosa: Exactly. The paper sets up this comprehensive mixed-integer quadratic programming model aimed at optimizing that coordination, so they can fully capitalize on CAV integration even when there’s high penetration rates in mixed traffic intersections.

Taro: It sounds like a distributed solution is necessary because the problem itself is too big for one single computer to handle efficiently.

The paper's summary: Rosa: To summarize the main points of "Distributed Mixed-Integer Quadratic Programming for Mixed-Traffic Intersection Control," they’re taking all that complex stuff—the traffic lights switching, the cars moving—and putting it into one big mixed-integer quadratic programming problem.

Dev: Right, and what they’re doing is using a distributed algorithm. It uses proximal ADMM for solving the relaxed version of the problem and then they use sequential constraint tightening to bring those binary variables back to reality.

Taro: That means instead of one massive calculation that takes forever on a central machine, each agent handles its part in parallel, and they slowly tighten up those big-M constraints as they go.

Rosa: Exactly. The paper shows this method works really well for traffic light systems and connected automated vehicles in mixed-traffic intersections where there’s both regular cars and autonomous ones mixing on the road.

Dev: What I find interesting is how they handle those constraints, because you get things like stopping at red lights, or making sure there's no lateral conflict between a car and another vehicle, which they formulate as these specific inequalities.

Taro: So it’s about ensuring safety constraints are met while the optimization is happening across multiple parts of the system.

Rosa: And then you get the big picture of what this means for real life. The simulations show that when you have high penetration rates of connected vehicles, say sixty percent or more, the system gets much better at coordinating those crossings.

Dev: It’s not just about making things work; they found that CAVs generally lead to lower total acceleration rates across the board, which means less energy use for everyone involved in the intersection.

Taro: So it’s not just about faster commutes; it’s about a more efficient system overall when autonomous vehicles are integrated into the mix, which is what matters when you think about city-wide traffic.

The paper's improvements: Rosa: Now, moving on to what they suggest improving about this framework, they aren't just sticking with the current setup because it’s functional; they’re thinking about how to make it even more powerful for real deployment.

Dev: What are these improvements? Are we talking about changing the core optimization problem itself, or tweaking the way the distributed algorithm runs?

Rosa: It seems mostly focused on refining that big-M constraint tightening strategy. They suggest making those steps sequential in a more adaptive way, rather than just following a fixed schedule for updating the coefficients.

Taro: That makes sense from my side because real-world environments aren't static; they change constantly—a sudden jam, an unexpected pedestrian crossing. A fixed schedule won't handle that dynamic uncertainty well.

Dev: So the goal is to make the constraint adjustment process more reactive to the environment instead of just running a pre-set sequence of steps over time.

Rosa: Right. They’re essentially looking at how we can feed real-time data into that update strategy so the algorithm tightens those constraints precisely when needed, which should keep it stable while still allowing for fast adaptation.

Taro: That level of responsiveness is crucial if this system is ever going to be used in a field where safety is paramount and the conditions are unpredictable.

Dev: And that ties directly into my concerns about latency and failure modes. If the constraint tightening becomes overly aggressive too quickly, we could run into instability or missed deadlines in our real-time loops.

Rosa: That’s the challenge, right? They have to find that sweet spot between being fast enough to react and stable enough not to cause a crash or a system lockup.

Taro: It sounds like they are pushing for a more graceful recovery mechanism built into the constraint update itself.

Conclusion: Rosa: So, to wrap up on "Distributed Mixed-Integer Quadratic Programming for Mixed-Traffic Intersection Control," this paper shows that we can handle complex coordination between traffic lights and connected vehicles in mixed traffic intersections by splitting the math across different agents using proximal ADMM.

Dev: It’s a solid approach for tackling those multi-agent integer problems, but the main thing is that they used sequential constraint tightening to ensure the solutions stay within their limits.

Taro: I still think we need to see how this holds up when the world throws unexpected stuff at it, like sudden unpredictable human behavior or sensor noise.

Rosa: That’s true. The accuracy drops as you add more agents, and that’s a huge limitation for deployment in a truly complex urban environment.

Dev: We have to keep pushing on those mixed-integer solutions because that's where the real complexity lies when you move beyond simple convex problems.

Taro: I also wonder if we could use techniques from things like Test-Time Trajectory Optimization to make the system more robust when it starts deviating from the planned path.

Rosa: Maybe that’s a future direction, trying to bake in some of those trajectory optimization ideas to handle the unpredictable nature of real traffic flows.

Dev: Well, for now, this framework gives us a way to get a reasonably fast solution even with many agents, which is progress in terms of computation time compared to centralized solvers.

Taro: It’s just an approximation for now, but it gets us closer to something that can actually work on the road over long periods.

Rosa: So this paper gives us a clear path using ADMM and constraint tightening to manage those mixed-integer constraints in traffic control systems.

Dev: It proves that a distributed solution is feasible for these kinds of problems, even with binary variables involved in the decision making.

Taro: We need more work on that robustness, though, to see if it can handle the real mess out there.

Viet-Anh Le, Andreas A. Malikopoulos

Department of Mechanical Engineering, University of Delaware · Systems Engineering Program, Cornell University · School of Civil and Environmental Engineering, Cornell University

eess.SY, cs.SY

Submitted: 2025-04-06

Updated: 2026-10-20

Comments: final version to Automatica

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 66/100

The gist: The gist In this paper, they present a distributed algorithm utilizing proximal ADMM in conjunction with sequential constraint tightening to address mixed-integer quadratic programming (MIQP)

Key concepts

Mixed-Integer Quadratic Programming (MIQP): This is a mathematical optimization problem where the goal is to minimize a cost function that includes quadratic terms (like travel time or energy) and linear constraints, but also involves integer variables. These integer variables represent discrete decisions, such as which traffic light switch to use or whether a vehicle stops at a red light.
Proximal ADMM: Alternating Direction Method of Multipliers (ADMM) is an iterative optimization technique used here in a distributed setting. Proximal ADMM breaks down the large, complex MIQP problem into smaller, parallel subproblems that are easier to solve independently. It helps agents coordinate their decisions while ensuring the overall system adheres to constraints.
Sequential Constraint Tightening: This is a heuristic technique used alongside ADMM to handle the difficult binary (integer) constraints. Instead of solving the full problem at once, this method starts with relaxed constraints and sequentially tightens them. This process gradually forces the approximate solutions found by ADMM to satisfy the original integer requirements, improving accuracy.
Traffic Light Switching Constraint: This constraint limits each lane to using at most one traffic light switch over a specific time period. It ensures that the timing decisions for traffic lights are managed efficiently, preventing excessive or conflicting changes in signal phases within the control horizon.

Terminology

Alternating Direction Method of Multipliers (ADMM) — 1× in this paper · explained in 2 episodes

Summary

The gist In this paper, they present a distributed algorithm utilizing proximal ADMM in conjunction with sequential constraint tightening to address mixed-integer quadratic programming (MIQP) problems associated with traffic light systems and connected automated vehicles (CAVs) in mixed-traffic intersections.

Problem Formulation

The research formulates a comprehensive MIQP model aimed at optimizing the coordination of traffic light systems and CAVs, thereby fully capitalizing on the advantages of CAV integration under conditions of high penetration rates The optimization problem is formulated as follows: minimize J(sl, pl,i, vl,iul,i) for TLC–l and CAV–(l, i) over the control horizon. The objective function minimizes a weighted sum of three terms: (1) maximizing the travel distance to reduce travel time (2) tracking the desired speed (3) minimizing acceleration rates to reduce energy consumption. The resulting MIQP problem is given as follows: minimize sl,pl,i,vl,i,ul,i for l∈L and i∈Cl(k0) subject to constraints (1), (2), (3), (4), (5), (6), and the big-M constraint formulation.

Constraint Modeling

The problem involves modeling various aspects of traffic control and vehicle dynamics. Key constraints include:

(1) Traffic light switching:

The problem restricts each lane to at most one traffic light switch for each lane over the control horizon, defined by κl ∈ [1, H + 1]. The next switching time must be within [δmin+¯kl, δmax+¯kl].

(3) CAV dynamics:

The discrete double-integrator dynamics for CAV–(l, i) are given by equations (3), which describe position and speed changes based on control input. Speed and acceleration limit constraints are imposed as vmin ≤ vl,i(k) ≤ vmax and umin ≤ ul,i(k − 1) ≤ umax.

(5) Lateral conflict constraint:

The traffic lights must guarantee no lateral conflicts between a CAV and an HDV or between two HDVs, formulated as sl(k) + sm(k) ≤ 1, ∀k ∈ I if η(l, m, k0) > 0.

(6) Stopping at red lights:

The CAVs must stop at red lights, formulated as pl,i(k) ≤ ψl if sl(k) = 0.

(7) Safety constraints:

Safety constraints for each CAV–(l, i) are considered to avoid rear-end collisions, formulated as pl,i(k) + τvl,i(k) + dmin ≤ pl,i−1(k), ∀k ∈ I.

(8) Lateral safety constraints:

Lateral safety constraints between two CAVs are formulated using OR statements to ensure they are not inside the conflict zone simultaneously.

Distributed Algorithm

To solve the multi-agent MIQP, a distributed algorithm based on proximal ADMM and sequential constraint tightening is developed. The approach involves two main stages:

Solving the convex relaxation of the MIQP where integrality constraints are relaxed to [0, 1] for all binary variables.
Sequentially adapting the constraint coefficients to tighten the big-M constraints.

The proximal ADMM algorithm works as follows in a distributed implementation where each agent–i solves an x-minimization problem in parallel. Agent–i adjusts the constraint coefficients based on the big-M update strategy presented in (23). Agent–i transmits w(t+1)i to agent–j, j ∈ Ni. Agent–i updates the dual variables as follows using equation (31).

Performance and Validation

Numerical simulations validate the framework across various penetration rates and traffic volumes. The proposed algorithm achieves an accuracy of more than 95% in terms of binary solutions, though accuracy decreases as the number of agents increases. The distributed algorithm is more scalable with the number of agents than the centralized approach. Furthermore, simulations show that starting from a penetration rate of 60%, the framework achieves remarkable travel time improvement compared to the scenario with pure HDVs. CAV penetration generally leads to lower total acceleration rates, which may result in less energy consumption. The average computation time for the distributed optimization algorithm is significantly lower than that of the centralized optimization using GUROBI solver across different numbers of agents. The framework enables CAVs to coordinate intersection crossings while reducing complete stops at traffic lights, especially under 100% penetration.

Conclusion

In this paper, they presented an MIQP framework designed to coordinate traffic signals and CAVs within mixed-traffic intersections, effectively leveraging the benefits of long-term CAV coordination. To address the challenges posed by the resulting multi-agent MIQP, characterized by a substantial number of binary variables, they developed a distributed optimization algorithm capable of solving the problem within a reasonable timeframe. This distributed optimization approach utilized proximal ADMM for resolving the convex relaxation and employed a sequential constraint tightening heuristic to uphold integrality constraints. The simulation results demonstrated that their distributed algorithm successfully ensured the performance of the control framework across various CAV penetration rates and traffic volumes, with notable improvements observed as the CAV penetration rate increased. They believe that further enhancements to the algorithm can be achieved through additional techniques aimed at optimizing mixed-integer solutions and minimizing computation time.

References

A. Alavian and M. C. Rotkowitz Improving ADMMbased optimization of mixed integer objectives In 2017 51st Annual Conference on Information Sciences and Systems (CISS), pages 1–6 IEEE, 2017

A. Alessandrini A. Campagna P. Delle Site F. Filippi, and L. Persia Automated vehicles and the rethinking of mobility and cities Transportation Research Procedia, 5:145–160, 2015

B. Alrifaee M. G. Mamaghani, and D. Abel Centralized non-convex model predictive control for cooperative collision avoidance of networked vehicles In 2014 IEEE International Symposium on Intelligent Control (ISIC), pages 1583–1588 IEEE, 2014

D. P. Bertsekas Constrained optimization and Lagrange multiplier methods Academic press, 2014

S. Boyd N. Parikh E. Chu B. Peleato J. Eckstein, et al Distributed optimization and statistical learning via the alternating direction method of multipliers Foundations and Trends in Machine learning, 3(1): 1–122, 2011

A. Camisa I. Notarnicola, and G. Notarstefano A primal decomposition method with suboptimality bounds for distributed mixed-integer linear programming In 2018 IEEE Conference on Decision and Control (CDC), pages 3391–3396 IEEE, 2018

A. Camisa I. Notarnicola, and G. Notarstefano Distributed primal decomposition for large-scale MILPs IEEE Transactions on Automatic Control, 67(1):413–420, 2021

B. Chalaki and A. A.

Improvements for AI systems

Distributed optimization of mixed-integer quadratic programming for traffic signal control and connected automated vehicles enables real-time coordination in mixed-traffic intersections by utilizing proximal ADMM with sequential constraint tightening to find approximate solutions efficiently.
The improved system can coordinate traffic light systems and connected autonomous vehicles (CAVs) in mixed-traffic intersections, fully capitalizing on CAV integration under conditions of high penetration rates to optimize coordination while ensuring safety constraints are met through a distributed algorithm.