Parsimonious shooting heuristic for trajectory control of connected automated traffic part I: Theoretical analysis with generalized time geography

Fang Zhou, Xiaopeng Li, Jiaqi MaarXiv 2015 · OpenReview

Abstract

This study addresses the complex problem of controlling vehicle trajectories in a platoon of connected and automated vehicles (CAVs) on signalized highway segments. Traditional optimization approaches often struggle with the infinite-dimensional nature of trajectories and the physical constraints of vehicle dynamics. We propose a "parsimonious shooting heuristic" (SH) that decomposes trajectories into analytically solvable quadratic segments. By generalizing time geography theory to incorporate finite acceleration—termed Quadratic Time Geography (QTG)—we prove that the SH algorithm consistently finds feasible solutions under realistic conditions. Furthermore, we demonstrate that this heuristic is a physical generalization of the classic kinematic wave theory. Numerical experiments confirm significant improvements in travel time and traffic throughput.

Introduction: The Challenge of Stop-and-Go Traffic

Traffic at signalized intersections is characterized by inefficient stop-and-go waves. These patterns increase fuel consumption, emissions, and the risk of collisions. While Connected and Automated Vehicles (CAVs) offer a platform for smoothing these flows, the mathematical challenge is significant. Optimizing a vehicle's trajectory involves managing an infinite-dimensional object while adhering to speed limits, mechanical acceleration bounds, and safety gaps. Existing solutions often oscillate between being computationally prohibitive for real-time use or overly simplistic by ignoring finite acceleration limits.

Methodology: The Shooting Heuristic and Quadratic Time Geography

The proposed Shooting Heuristic (SH) algorithm avoids complex global optimization by "constructing" trajectories through a series of logical steps. The algorithm breaks each trajectory into a few quadratic segments (parabolas), reducing the problem to a handful of control variables.

  1. Forward Shooting: The algorithm projects a vehicle's path based on its entry speed and desired acceleration.
  2. Safety Constraints: It ensures the trajectory maintains a safe buffer (shadow trajectory) relative to the preceding vehicle.
  3. Backward Shooting: When approaching a red light, the algorithm "shoots" a path backward from the start of the next green phase to determine the optimal deceleration profile for a smooth merge.

To provide a theoretical foundation for this heuristic, the authors extended the concept of "time geography"—which maps the space-time "prism" of possible movement—to include finite acceleration. This Quadratic Time Geography (QTG) framework allows for a rigorous proof of feasibility.

Space-time diagram illustrating the constraints and trajectory construction within the Quadratic Time Geography framework.

Theoretical Foundations: Bridging Classical and Modern Traffic Theory

A key insight of this research is the relationship between the SH algorithm and the Kinematic Wave Theory (KWT), a pillar of traffic science since the 1950s. KWT assumes instantaneous speed changes (infinite acceleration). The SH algorithm serves as a mathematical generalization of KWT, providing a "smoothed" version that accounts for real-world physical limits. The study identifies theoretical bounds on the difference between the SH solution and the KWT solution, ensuring that the heuristic remains grounded in established traffic flow principles while improving realism.

Results: Efficiency and Smoothness

Numerical simulations involving platoons of up to 100 vehicles on a 1000-meter segment demonstrate the algorithm's efficacy.

  • Travel Time Reduction: In a benchmark test of 50 vehicles, total travel time decreased from over 300 seconds under manual driving models (like the Intelligent Driver Model) to approximately 170 seconds with SH control.
  • Throughput Improvement: The algorithm allows vehicles to pass intersections at higher average speeds, effectively mitigating the "capacity drop" typically observed in congested human-driven traffic.
  • Shockwave Elimination: Visual analysis of space-time trajectories shows that the backward-propagating stop-and-go waves prevalent in human traffic are virtually eliminated.
Comparison of vehicle trajectories: (a) traditional stop-and-go patterns versus (b) smoothed trajectories using the shooting heuristic.

Conclusion and Future Directions

The parsimonious shooting heuristic provides a computationally efficient and theoretically sound method for real-time CAV trajectory control. By ensuring feasibility through Quadratic Time Geography, it bridges the gap between abstract traffic theory and practical deployment.

As "Part I" of a larger study, this work focuses on feasibility and theoretical consistency. Future work (Part II) will introduce an optimization framework to refine these trajectories for specific objectives like fuel efficiency. Additionally, subsequent research will address the complexities of mixed traffic (human and automated), multi-lane geometries, and the impact of communication latencies.

Summary updated

Abstract

This paper studies a problem of controlling trajectories of a platoon of vehicles on a highway segment with connected and automated vehicles. This problem is complex because each vehicle trajectory is an infinite-dimensional object and neighboring trajectories have complex interactions (e.g., car-following behavior). A parsimonious shooting heuristic algorithm is proposed to construct vehicle trajectories on a signalized highway segment that comply with boundary conditions for vehicle arrivals, vehicle mechanical limits, traffic lights and vehicle following safety. This algorithm breaks each vehicle trajectory into a few sections and each is analytically solvable. This decomposes the original hard trajectory control problem to a simple constructive heuristic. Then we slightly adapt this shooting heuristic algorithm to efficiently solve a leading vehicle problem on an uninterrupted freeway. To study theoretical properties of the proposed algorithms, the time geography theory is generalized by considering finite accelerations. With this generalized theory, it is found that under mild conditions, these algorithms can always obtain a feasible solution to the original complex trajectory control problem. Further, we discover that the shooting heuristic solution is a generalization of the solution to the classic kinematic wave theory by incorporating finite accelerations. We identify the theoretical bounds to the difference between the shooting heuristic solution and the kinematic wave solution. Numerical experiments are conducted to verify the theoretical results and to draw additional insights into the potential of trajectory control in improving traffic performance. Building upon this foundation, an optimization framework will be presented in a following paper as Part II of this study.
BibTeX
@misc{zhou2015parsimonious,
  author = {Fang Zhou and Xiaopeng Li and Jiaqi Ma},
  title = {{Parsimonious shooting heuristic for trajectory control of connected automated traffic part I: Theoretical analysis with generalized time geography}},
  year = {2015},
  eprint = {1511.04810},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1511.04810},
}
Figure