Source-linked AI summary
Parsimonious shooting heuristic for trajectory control of connected automated traffic part I: Theoretical analysis with generalized time geography
Fang Zhou, Xiaopeng Li, Jiaqi Ma
TL;DR
The paper studies how to construct safe, physically feasible trajectories for a platoon of connected automated vehicles under signal and following constraints. It proposes a parsimonious shooting heuristic and a finite-acceleration generalization of time geography to analyze both signalized highways and freeway lead-vehicle control. Under mild conditions, the algorithms always find feasible solutions, while the shooting solution generalizes classic kinematic-wave results within theoretical bounds.
Problem
Existing studies often control few vehicles, ignore acceleration detail, or use computationally sophisticated methods, while theoretical links to classic traffic-flow models remain limited.
Method
A parsimonious shooting heuristic constructs trajectories from a few analytically solvable sections and is adapted to the freeway lead-vehicle problem, while time geography is generalized to finite accelerations.
Results
Under mild conditions, the proposed algorithms always find feasible solutions; the shooting solution generalizes kinematic-wave theory, with differences bounded independently of vehicle size.
Takeaways & Limitations
The paper provides a methodological and theoretical foundation for future CAV trajectory optimization and highway traffic-management applications.
Takeaways & Limitations
Part I constructs feasible algorithms and analyzes theory, while detailed optimization of performance measures is deferred to Part II.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses the challenge of smoothing trajectories for streams of connected automated vehicles while retaining computational tractability and theoretical links to classic traffic-flow models. It introduces a parsimonious shooting approach for signalized highways and freeway lead-vehicle control, leaving full trajectory optimization to Part II.
- Stop-and-go traffic increases crash risk, discomfort, fuel consumption, emissions, travel delay, and capacity loss.
- Part I develops feasible algorithms and theoretical analysis, while the overall trajectory optimization framework is deferred to Part II.
- Prior vehicle-smoothing studies usually controlled one or a few vehicles, ignored acceleration detail, or used sophisticated algorithms difficult to implement in real time.
- The proposed framework controls detailed trajectories for a stream of interactive CAVs on a signalized highway and can represent the freeway lead-vehicle problem as a special case.
- The heuristic compresses each trajectory into a few analytical segments and acceleration levels, supporting efficient construction and potential real-time application.
2 Problem Statement
The paper formulates feasible trajectory construction for identical automated vehicles on a single-lane highway with a fixed-time signal. Feasibility combines vehicle dynamics, boundary conditions, signal timing, and delayed car-following safety, with a freeway lead-vehicle variant.
- Primary Problem: The primary problem designs trajectories on a single-lane segment from location 0 to L with a fixed-time signal at the downstream boundary.
- Vehicle and Kinematic Constraints: Vehicles have bounded acceleration and deceleration, nonnegative speed, and a segment speed limit.
- Trajectory Definition: Each trajectory is a second-order semi-differentiable function whose velocity is absolutely continuous and acceleration is Riemann integrable.
- Boundary Conditions: Entry conditions specify ordered arrival times and speeds, while exit conditions require vehicles to reach location L during a green phase.
- Car-following Safety: Following safety requires the delayed follower position to remain at least jam spacing s ahead of the preceding vehicle’s current position.
- Lead-Vehicle Problem: The lead-vehicle problem fixes the lead trajectory and seeks feasible trajectories for following vehicles on an uninterrupted freeway.
3 Shooting Heuristic Algorithms
The parsimonious shooting heuristic constructs feasible connected-vehicle trajectories by combining analytically solvable quadratic segments with forward and backward shooting operations. It sequentially handles vehicle constraints and can be adapted into a parallel method for the lead vehicle problem.
- The algorithm focuses on trajectory sections from each vehicle’s entry time because earlier sections are determined by history and do not affect its results.
- Forward shooting accelerates each vehicle from its entry condition, cruises at the speed limit when applicable, and merges smoothly into the preceding vehicle’s safety bound when blocked.The safety bound preserves spatial separation s and temporal separation τ.
- Backward shooting revises a forward trajectory that violates the exit boundary or encounters a red light by shifting and shooting backward from the next green phase.The backward trajectory may include a stopping interval before merging into the forward trajectory.
- The heuristic executes forward and backward shooting consecutively across vehicles, using four control variables and producing a trajectory vector in the feasible set.The resulting trajectories consist of only a few quadratic or linear segments that are analytically solvable.
- A state point records location, speed, and time; quadratic functions and finite segments provide the basic analytic building blocks for trajectory construction.Feasible segments satisfy the study’s speed and acceleration constraints.
- The shadow trajectory shifts a preceding trajectory backward by spatial separation s and forward by temporal separation τ, while segment distance is solved analytically.These definitions support checking safety during forward shooting.
- If the shooting heuristic successfully returns a non-empty trajectory vector, the vector satisfies the problem’s kinematic, boundary, signal, and safety constraints.
- For the lead vehicle problem, the adapted method fixes the lead trajectory, removes the signal-boundary restriction, and admits a parallel implementation.The paper states that the parallel method yields the corresponding feasible trajectory set.
4 Theoretical Property Analysis
The paper generalizes time geography to finite accelerations through quadratic cones and prisms, then uses these constructs to analyze shooting-heuristic feasibility, trajectory relationships, and robustness.
- Quadratic Time Geography: Quadratic time geography extends time geography by incorporating acceleration range [¯a, a] alongside speed range [0, ¯v].The generalized theory is illustrated through quadratic cones and prisms.
- Quadratic Time Geography: A quadratic cone contains feasible trajectories passing through one feasible state point and is always non-empty when that state point is feasible.The cone is represented by upper and lower bound trajectories.
- Quadratic Time Geography: A quadratic prism characterizes feasible trajectories passing through two feasible state points, with feasibility determined by the endpoint states.Proposition 3 gives an if-and-only-if feasibility condition involving the distance function D.
- Relationship Between QTG and SH: Forward shooting from a feasible state overlaps the corresponding upper-bound trajectory, while extended backward shooting overlaps the upper-bound trajectory of a feasible quadratic prism.These relationships connect shooting-generated trajectories to the borders of quadratic cones and prisms.
- Feasibility Properties: The shooting heuristic is feasible exactly when the associated trajectory-construction problem is feasible once the studied highway segment is sufficiently long.The supplied theorem statements establish equivalence between feasibility of the SH solution and the original problem under this condition.
- Robustness: Small input errors generally produce bounded trajectory changes, but signalized solutions can jump to a later green phase when an exit time is near red onset.The jump affects only a limited number of trajectories close to a red phase.
0. Note that every merging segment shall be above p
The paper relates the shooting-heuristic freeway solution to classic kinematic-wave models and derives bounded differences caused by replacing speed jumps with finite accelerations.
- Relationship to Classic Traffic Flow Models: SH trajectories remain below their counterpart trajectories in Q, with the difference attributed to smoothed accelerations rather than speed jumps.The theorem identifies this ordering and its mechanism.
- Relationship to Classic Traffic Flow Models: The trajectory difference does not accumulate substantially across vehicles and is bounded by a constant.The lower bound is tight, with instances attaining the same difference for every following vehicle.
- Relationship to Classic Traffic Flow Models: The SHL solution generalizes kinematic wave theory, Newell’s lower-order model, and the linear cellular automata model by incorporating finite accelerations.It is described as a smoothed version that avoids infinite acceleration, deceleration, or speed jumps.
- Asymptotic Relationship: For constant-speed trajectories, the vehicle-flow relationship satisfies K ≤ 1/(s + Vτ) when V = ¯v and K = 1/(s + Vτ) when V < ¯v.These expressions quantify the triangular fundamental diagram.
- Asymptotic Relationship: The corresponding flow is O = KV = min {K¯v, (1 − sK)/τ} and is bounded above by ¯v/(s + ¯vτ).The bound follows from the constant-speed relationship.
5 Illustrative Examples
The illustrative examples compare parsimonious shooting (SH) trajectories with manually driven traffic, examine lead-vehicle wave propagation, test feasibility, and assess convergence toward kinematic-wave solutions. SH produces smoother trajectories, improves reported traffic-performance measures, and exhibits feasibility patterns consistent with the theoretical results.
- 5.1 Manual v.s. Automated Trajectories: Over 300 seconds versus around 170 seconds, SH reduces total travel time relative to the manually driven benchmark.The benchmark contains backward-propagating stop-and-go waves, whereas SH vehicles can pass the intersection at maximum speed.
- 5.1 Manual v.s. Automated Trajectories: Lower acceleration and deceleration magnitudes produce smoother trajectories while total travel time remains around 170 seconds.The reported result links smoother motion with potential environmental and safety benefits.
- 5.1 Manual v.s. Automated Trajectories: SH shifts macroscopic measurements toward the free-flow branch and closer to the stationary flow-density curve.With downscaled acceleration limits, more measurements lie in the free-flow branch and become consistent with the stationary curve, suggesting mitigation of capacity drop.
- 5.2 Lead Vehicle Problem: Proper CAV controls absorb and damp backward stopping waves, with reduced acceleration and deceleration magnitudes producing further smoothing.The SHL and PSHL results overlap, while the downscaled setting dampens the stopping-wave impact more than the higher-magnitude setting.
- 5.3 Feasibility Tests: Feasibility decreases as arrival-time dispersion, boundary-condition density, and traffic saturation increase, while feasibility transitions sharply between feasible and infeasible regimes.For fixed α = β = 0.5, shorter segments also reduce feasibility likelihood.
- 5.4 Comparison with Kinematic Wave Theory: As acceleration factors increase, SHL trajectories and their theoretical error bounds converge toward the kinematic-wave solution.The experiments support viewing SHL as a smoothed kinematic-wave solution that replaces speed jumps with finite accelerations and decelerations.
6 Conclusion
The paper establishes a constructive and theoretical foundation for controlling multiple CAV trajectories, showing feasibility under mild conditions and bounded differences from kinematic-wave solutions. Detailed trajectory optimization is deferred to Part II.
- The shooting heuristic constructs multiple CAV trajectories satisfying boundary, physical, following-safety, and traffic-signal constraints.
- Under certain mild conditions, the proposed algorithms can always find a feasible solution to the original multi-trajectory control problem.
- The lead-vehicle shooting solution generalizes the classic kinematic-wave result by incorporating finite accelerations.
- The difference between shooting-heuristic and kinematic-wave solutions is bounded independently of vehicle size in the studied traffic stream.
- The paper provides a methodological foundation for a subsequent trajectory-optimization framework targeting mobility, environmental impacts, and safety.