Abstract
In general, there are two kinds of cooperative driving strategies, planning based strategy and ad hoc negotiation based strategy, for connected and automated vehicles (CAVs) merging problems. The planning based strategy aims to find the global optimal passing order, but it is time-consuming when the number of considered vehicles is large. In contrast, the ad hoc negotiation based strategy runs fast, but it always finds a local optimal solution. In this paper, we propose a grouping based cooperative driving strategy to make a good tradeoff between time consumption and coordination performance. The key idea is to fix the passing orders for some vehicles whose inter-vehicle headways are small enough (e.g., smaller than the pre-selected grouping threshold). From the viewpoint of optimization, this method reduces the size of the solution space. A brief analysis shows that the sub-optimal passing order found by the grouping based strategy has a high probability to be close to the global optimal passing order, if the grouping threshold is appropriately chosen. A series of simulation experiments are carried out to validate that the proposed strategy can yield a satisfied coordination performance with less time consumption and is promising to be used in practice.
Introduction
Merging at highway on-ramps is a primary source of traffic congestion and accidents. While Connected and Automated Vehicles (CAVs) offer the potential for perfectly coordinated merging, researchers face a "Goldilocks" problem with current strategies. Planning-based strategies seek the global optimal passing order (e.g., using Mixed Integer Linear Programming), but as the number of vehicles increases, the search space explodes combinatorially, making them too slow for real-time hardware. Conversely, ad hoc negotiation strategies use greedy algorithms like First-In-First-Out (FIFO). While fast, they often result in local optima, leading to unnecessary braking and higher cumulative delays. This paper proposes a grouping-based cooperative driving strategy to find a middle ground: a strategy fast enough for real-time deployment but efficient enough to rival global optimization.
The Grouping-Based Strategy
The core innovation is the Grouping Method. Instead of calculating the optimal passing order for every individual vehicle, the system "self-organizes" vehicles into groups based on their inter-vehicle headway. If the time headway between two consecutive vehicles on the same lane is smaller than a specific threshold ($\delta$), they are locked into a group. Their relative order is fixed, and no vehicle from a conflicting lane is allowed to "cut in" between them.
To ensure the problem remains solvable in real-time, the authors use an adaptive threshold. It starts at 1.5 seconds and increases until the total number of groups is $\le 12$, capping the maximum search space. Once groups are formed, the system treats each group as a "special CAV" and runs a search to find the optimal passing order for these groups. An iterative algorithm is used to calculate the objective value (total delay and passing time) for any given passing order, maintaining a linear time complexity $O(n_1 + n_2)$.
Comparison of Strategies
By fixing tight clusters, the search space is pruned of thousands of inefficient permutations. The realization is that it is rarely optimal to break up a tight platoon of vehicles to let a single car from another lane merge. A mathematical analysis of a 4-vehicle scenario shows there is only a ~1.3% chance that grouping vehicles would result in a passing order worse than the global optimum. In most cases, the "sub-optimal" grouping order is actually the global optimum.
Results and Discussion
The study relies on synthetic simulation experiments conducted in MATLAB, with vehicle arrivals modeled as a Poisson process. The proposed method was benchmarked against a Planning-based strategy and a FIFO-based Ad hoc strategy.
- Efficiency: In a scenario with 25 CAVs (over 5.2 million possible passing orders), the grouping strategy found the 7th best solution, whereas FIFO ranked 3,350,239th.
- Delay: The average delay for the grouping strategy was nearly identical to the global optimal planning strategy (within 0.04 seconds per vehicle), even under high traffic flow.
- Speed: While the planning-based strategy took over 11 seconds to compute a solution for high-density traffic, the grouping strategy consistently finished within 40 milliseconds.
Conclusion
The grouping-based strategy effectively balances the trade-off between the "perfect" solution and the "fast" solution. Future work will involve exploring real-world constraints like engine lag and passenger comfort, scaling to multi-lane scenarios, and empirical validation using automated vehicle prototypes on real on-ramps.
Summary updated