A Grouping Based Cooperative Driving Strategy for CAVs Merging Problems

Huile Xu, Shuo Feng, Yi Zhang, Li Li

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.

A typical merging scenario with defined control and merging zones, illustrating the grouping of vehicles based on proximity.

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.

Comparison of the grouping-based strategy versus the enumeration-based method in a sample merging scenario.

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

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.
BibTeX
@misc{xu2018grouping,
  author = {Huile Xu and Shuo Feng and Yi Zhang and Li Li},
  title = {{A Grouping Based Cooperative Driving Strategy for CAVs Merging Problems}},
  year = {2018},
  eprint = {1804.01250},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1804.01250},
}
Figure