Real-Time Coordination of Autonomous Vehicles at Intersections

summary

The gist

When coordinating connected and automated vehicles at an unsignalized intersection, the crossing order and vehicle trajectories must be decided jointly <ref:2610.37632#pg2>.

In short

The work coordinates connected and automated vehicles at unsignalized intersections by jointly deciding crossing order and trajectories. It uses a bi-level formulation where vehicles solve individual optimal control problems, and a coordinator optimizes timing subject to precedence constraints. Sensitivity analysis from acados allows the coordinator to efficiently compute gradients for schedule refinement.

Key concepts

Bi-level Formulation
This problem is split into two levels: lower and upper. The lower level involves each vehicle independently finding its best path based on entry/exit times. The upper level, the coordinator, then optimizes these times globally while respecting rules about which vehicles must cross before others.
Optimal Control Problem (OCP)
Each individual vehicle solves an OCP to determine its optimal control strategy. The 'optimal value' of this problem is determined by the vehicle's entry and exit times, meaning the vehicle tries to minimize a cost function related to these timings.
Sensitivity Analysis
The method computes the gradient (first derivative) and Hessian (second derivative) of each vehicle's value function. This is done analytically using acados solution sensitivities, allowing the coordinator to quickly estimate how changes in timing affect the overall system cost, which is crucial for real-time decision-making.

Terminology used across episodes

This episode discusses

The paper

Real-Time Coordination of Autonomous Vehicles at Intersections · Read on arXiv

Saugat Shahi, Jonathan Frey, Filippo Fabiani, Moritz Diehl, Mario Zanon

When coordinating connected and automated vehicles at an unsignalized intersection, the crossing order and the vehicle trajectories must be decided jointly. For a fixed crossing order, the problem can be formulated conveniently in a bi-level form where each vehicle solves its own optimal control problem, whose optimal value is a function of its entry and exit times, and a coordinator optimizes these times subject to precedence constraints. We compute the first and second order sensitivities of lower-level problems, which are required to solve the upper-level problem, by means of algorithmic differentiation using the real-time software package acados. This implementation exploits tailored algorithms to obtain a computationally efficient implementation of the optimal coordination algorithm. We validate our implementation in numerical simulations that demonstrate both real-time feasibility and effectiveness of our algorithm.

Transcript

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

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "Real-Time Coordination of Autonomous Vehicles at Intersections".

Paper summary: Rosa: So we’re looking at this paper again, "Real-Time Coordination of Autonomous Vehicles at Intersections," to get a quick recap of what they are trying to achieve. The main thesis is that when you have connected and automated vehicles approaching an unsignalized intersection, the way they cross—the crossing order and the trajectories—needs to be decided together Rosa.

Dev: Exactly. They frame it as a bi-level problem where each vehicle solves its own optimal control problem based on its entry and exit times, and then a coordinator optimizes those times subject to precedence constraints between them Dev. It’s important because it sets up the framework for how these vehicles can actually coordinate their movement when there are no signals to guide them Dev.

Taro: What makes this particularly relevant is that they are not just looking at a static set of paths, but dynamic trajectories influenced by the coordination itself, and they're handling those dynamics in a real-time setting Taro.

Rosa: Right, so the paper claims that by formulating it this way, you can compute the first and second order sensitivities of those lower-level vehicle problems using algorithmic differentiation from acados Rosa. This is what’s required for the upper level coordinator to solve its own problem Rosa.

Dev: That sensitivity calculation is key because it allows the upper level coordinator to access only the value functions and constraints without needing to exchange actual vehicle trajectories between them, which keeps things computationally light Dev. It’s about having a coordinated decision-making layer that doesn't require constant high-bandwidth communication of every single path Dev.

Taro: I’m thinking about the heuristic they use for schedule refinement, which involves a multiplier-guided swapping technique to rank critical vehicle pairs based on precedence constraints Taro. This tries to narrow down the huge search space of possible orders into something manageable Taro.

Rosa: That heuristic uses a prediction quadratic program to estimate cost changes from a candidate swap before they even perform the swap, and then it re-solves the main problem if that swap looks promising Rosa. It’s an iterative way to refine the schedule Rosa.

Dev: And they mention that every candidate for swapping is verified by actually re-solving the lower level problem to see if that new schedule results in a lower overall cost Dev. That verification step ensures you don't just trust the prediction blindly Dev.

Taro: So it sounds like the core idea is using this sensitivity analysis and this swapping heuristic to find an optimal schedule quickly under real-time constraints Taro. It’s about finding the best order for crossing when things are happening fast Taro.

Conclusion: Rosa: So wrapping up this talk about "Real-Time Coordination of Autonomous Vehicles at Intersections," we’ve seen how they use a bi-level formulation with sensitivity analysis to tackle the complex problem of coordinating connected vehicles at intersections Rosa. The authors, Saugat Shahi, Jonathan Frey, Filippo Fabiani, Moritz Diehl and Mario Zanon, essentially showed that you can get this coordination happening in real time by using tools like acados Rosa.

Dev: And the implications for me are that this moves the discussion from just theoretical models to something that’s actually feasible on a vehicle or in a system environment Dev. It shows a path toward building systems where vehicles can make these joint decisions about crossing order and paths without needing massive, centralized computation Dev.

Taro: For me, it suggests that even when the world throws you an unsignalized intersection problem at you, there’s a structured way to approach recovery by optimizing the schedule quickly Taro. It points toward more resilient autonomy in those unpredictable urban environments Taro.

Rosa: That's right. The real-time performance metrics they shared, like that computation time being around ten point six milliseconds, show that this isn't just a slow simulation trick; it’s something that has the speed to be useful on the road Rosa.

Dev: And yes, it’s not just fast for simulation. It demonstrates a method for getting the coordination logic running within tight sampling periods like one hundred milliseconds Dev. The authors are showing that this is achievable in a practical sense Dev.

More episodes

← Home