Hierarchical-distributed optimized coordination of intersection traffic

Pavankumar Tallapragada, Jorge CortésIEEE Trans. ITS 2016 · DOI · OpenReview

Abstract

This paper considers the problem of coordinating vehicular traffic at an intersection and on the branches leading to it in order to minimize a combination of total travel time and energy consumption. We propose a provably safe hierarchical-distributed solution to balance computational complexity and optimality of the system operation. In our design, a central intersection manager communicates with vehicles heading toward the intersection, groups them into clusters (termed bubbles) as they appear, and determines an optimal schedule of passage through the intersection for each bubble. The vehicles in each bubble receive their schedule and implement local distributed control to ensure system-wide inter-vehicular safety while respecting speed and acceleration limits, conforming to the assigned schedule, and seeking to optimize their individual trajectories. Our analysis rigorously establishes that the different aspects of the hierarchical design operate in concert and that the safety specifications are satisfied. We illustrate its execution through a suite of simulations and compare its performance against optimized signal-based coordination over a wide range of system parameters.

Introduction

Intersections represent the primary bottlenecks in urban mobility, significantly contributing to fuel waste and travel delays. While autonomous vehicle (AV) technology promises improved coordination, existing solutions often struggle to balance safety with computational efficiency. Centralized optimization methods, while theoretically optimal, suffer from exponential complexity as vehicle counts rise. Conversely, simple collision avoidance systems ensure safety but often fail to optimize for flow or fuel efficiency. This research proposes a "middle ground": a hierarchical-distributed (HD) framework that achieves system-wide efficiency while remaining computationally tractable for real-time application.

Conceptual diagram of an intersection with vehicles grouped into bubbles (clusters) approaching from four branches.

The Hierarchical-Distributed Framework

The proposed system manages traffic through three distinct layers, shifting the focus from individual vehicles to dynamic groups called "bubbles."

Layer 1: Bubble Generation (Clustering)

As vehicles approach the intersection, the system uses a k-means clustering algorithm to group them into bubbles. A bubble is defined as a set of vehicles that will cross the intersection together. By treating these clusters as single entities for scheduling purposes, the central controller significantly reduces its computational load.

Layer 2: The Intersection Manager (Scheduling)

A central coordinator employs a branch-and-bound algorithm to determine the optimal crossing sequence and timing for each bubble. The objective is to minimize a cost function that balances total travel time against fuel consumption, which is modeled as a function of average velocity.

Layer 3: Local Vehicular Control (Distributed)

Once a bubble is assigned a crossing window, individual vehicles within that bubble utilize local distributed control to meet the schedule. This layer manages the physical constraints of the vehicle, including speed limits and acceleration. Crucially, it maintains a Safe-Following Distance based on "Maximum Braking Maneuver" (MBM) logic, ensuring that even if a lead vehicle stops abruptly, followers can safely react.

Segmentation of the road approach into staging, mid, and exit zones for hierarchical coordination.

Key Insights: Bubbles and Safety

A critical distinction in this framework is the use of "bubbles" rather than rigid platoons. Unlike platoons, which require vehicles to maintain a fixed formation throughout their journey, bubbles are dynamic. Vehicles only need to converge into a cohesive group by the time they reach the intersection, allowing for more flexible and fuel-efficient trajectories during the approach phase.

Furthermore, the system provides provable safety guarantees. By defining a mathematical "safety ratio" ($\sigma$), the authors ensure that inter-vehicular safety is maintained throughout the coordination process. This rigorous approach moves beyond simulation-based safety to formal verification.

Performance Evaluation

The framework was evaluated using custom MATLAB simulations with traffic generated via a Poisson arrival process. The HD algorithm was benchmarked against traditional optimized signal-based coordination (traffic lights).

  • Energy Efficiency: The HD algorithm demonstrated a significant reduction in cumulative energy consumption across various traffic densities compared to signal-based systems.
  • Throughput Trade-offs: While the HD system excelled in efficiency, traditional traffic lights showed higher throughput at extremely high densities. This is attributed to the HD algorithm's conservative safety gaps, which prioritize collision avoidance over tight packing.
  • Real-time Feasibility: The local controller for each vehicle executes in approximately 0.5ms, and scheduling 8 bubbles (potentially containing dozens of cars) takes roughly 1 second on standard hardware, proving the system's readiness for real-world deployment.

Conclusion and Future Work

The hierarchical-distributed approach offers a scalable, safe, and energy-efficient solution for intersection management. While current results focus on single-lane intersections without turns, the underlying logic provides a foundation for more complex scenarios. Future research will aim to extend this framework to multi-lane networks and incorporate privacy-preserving data sharing between vehicles and the central manager.

Summary updated

Abstract

This paper considers the problem of coordinating the vehicular traffic at an intersection and on the branches leading to it for minimizing a combination of total travel time and energy consumption. We propose a provably safe hierarchical-distributed solution to balance computational complexity and optimality of the system operation. In our design, a central intersection manager communicates with vehicles heading towards the intersection, groups them into clusters (termed bubbles) as they appear, and determines an optimal schedule of passage through the intersection for each bubble. The vehicles in each bubble receive their schedule and implement local distributed control to ensure system-wide inter-vehicular safety while respecting speed and acceleration limits, conforming to the assigned schedule, and seeking to optimize their individual trajectories. Our analysis rigorously establishes that the different aspects of the hierarchical design operate in concert and that the safety guarantees provided by the proposed design are satisfied. We illustrate its execution in a suite of simulations and compare its performance to traditional signal-based coordination over a wide range of system parameters.
BibTeX
@article{tallapragada2016hierarchical,
  author = {Pavankumar Tallapragada and Jorge Cortés},
  title = {{Hierarchical-distributed optimized coordination of intersection traffic}},
  journal = {IEEE Transactions on Intelligent Transportation Systems},
  year = {2016},
  doi = {10.1109/tits.2019.2912881},
}
Figure