PaperlayerView exact revision on arXiv

Source-linked AI summary

A Grouping Based Cooperative Driving Strategy for CAVs Merging Problems

Huile Xu, Shuo Feng, Yi Zhang, Li Li

arXiv:1804.01250v1eess.SYcs.SY

TL;DR

CAV merging strategies trade off computation time against the quality of the passing order. This paper groups vehicles with small headways to shrink the search space; its simulations report similar traffic efficiency to planning with much less computation, and better efficiency than ad hoc negotiation at similar computation time.

  • Problem

    Orderless merging at highway on-ramps is identified as a cause of congestion, motivating methods that coordinate vehicle passing order.

    Source: §I · p. 1

  • Method

    The strategy groups vehicles below a headway threshold, fixes their within-group order, and searches the resulting reduced solution space.

    Source: §I · p. 1, C. Grouping Based Strategy · p. 4

  • Results

    The grouping strategy yields similar traffic efficiency to planning with much less calculation time, and much better traffic efficiency than ad hoc negotiation with similar calculation time.

    Source: §VI · p. 7

  • Takeaways & Limitations

    Grouping offers a computation–traffic-efficiency tradeoff, and its sub-optimal order is often close to the global optimum when the threshold is appropriately chosen.

    Source: C. Grouping Based Strategy · p. 4, §VI · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper proposes grouping close-headway vehicles to reduce the passing-order search space, aiming to balance computation time and traffic efficiency. Its formulation optimizes vehicle access times and passing order while enforcing safety gaps at the merge.

I. INTRODUCTION

  • Planning-based strategies seek a global optimum but become sharply slower as vehicle count grows, while ad hoc negotiation is fast but cannot guarantee a global or sufficiently good order.The paper identifies passing order as key to the merging problem.Source: §I · p. 1
  • The strategy groups consecutive CAVs when their headway is below a threshold, fixes their within-group order, and searches a reduced solution space.An adaptive threshold controls group size, and a maximum group count limits planning time.Source: §I · p. 1
  • With an appropriately chosen threshold, grouping has a high probability of finding a passing order close to the global optimum, with good-enough coordination and little time consumption.The reported result is conditional on the grouping threshold being appropriately chosen.Source: §I · pp. 1–2

II. PROBLEM FORMULATION

  • The formulation treats vehicle passing order as the decision variable and minimizes passing time and vehicle delay through weighted objective terms.The access-time decision is subject to minimum safety gaps for same-movement and conflicting vehicles.Source: §II · pp. 2–3
  • For a given passing order, a simple iteration algorithm computes access times and the objective in O(n1 + n2) time.The paper focuses on passing-order optimization, using a motion-planning method whose computational cost is described as small.Source: §II · pp. 2–3

III. COOPERATIVE DRIVING STRATEGIES

The section presents three cooperative driving strategies for solving the formulated optimization problem.

III. COOPERATIVE DRIVING STRATEGIES

  • The section introduces three cooperative driving strategies for solving the passing-order optimization problem.Source: §III · p. 3

A. Planning Based Strategy

Planning-based strategies search for an optimal passing order by directly solving the mixed-integer optimization problem, but the search can become computationally impractical as vehicle count grows.

A. Planning Based Strategy

  • Planning-based strategies directly solve the mixed-integer optimization problem using tree-based enumeration or branch-and-bound.Source: A. Planning Based Strategy · p. 3
  • Branch-and-bound has exponential worst-case complexity, and numerical tests found enumeration effective only with fewer than 12 vehicles.The reported time efficiency of branch-and-bound is similar to enumeration.Source: A. Planning Based Strategy · p. 3

B. Ad Hoc Negotiation Based Strategy

Ad hoc negotiation orders vehicles by estimated arrival time and can be solved quickly, while grouping reduces planning's search space by fixing the order of closely spaced vehicles. An adaptive grouping threshold limits the number of groups, trading a restricted search space for lower planning time.

B. Ad Hoc Negotiation Based Strategy

  • Ad hoc negotiation uses greedy search that generally follows FIFO arrival order, then solves the determined order with complexity O(n1+n2).It runs quickly, but does not guarantee a globally optimal or sufficiently good order.Source: B. Ad Hoc Negotiation Based Strategy · p. 3

C. Grouping Based Strategy

IV. A BRIEF ANALYSIS

The analysis examines when grouping two closely spaced vehicles can exclude a better passing order. Under one stated parameter setting, the probability that the grouped strategy is worse than the global optimum is about 1.3%, though exhaustive analysis becomes impractical as vehicle counts grow.

IV. A BRIEF ANALYSIS

  • Among the four-vehicle scenario's candidate orders, grouping preserves ABCD, ABDC, and CABD as possible optima; only ACBD is the special case to examine.The analysis compares total passing times and identifies the conditions under which ACBD can be better than ABCD.Source: §IV · pp. 4–5
  • The probability analysis assumes all CAVs travel at maximum velocity and models headway with a displaced exponential distribution.In the scenario, A, B, and D are on one lane, C is on another, and A–B headway is below the grouping threshold.Source: §IV · pp. 4–5
  • 1.3% is the probability that grouping yields a worse-than-global-optimal solution under Δt1=1.5s, δ=2s, Δt2=2.5s, and λ1=λ2=0.2veh/s.Source: §IV · p. 5
  • Exhaustive analysis becomes impractical for scenarios with many vehicles because the number of possible cases grows exponentially, so the paper turns to numerical tests.Source: §IV · p. 5

V. SIMULATION TESTS

The simulations evaluate grouping-based coordination through optimality, computation time, and strategy-comparison experiments. They use Poisson vehicle arrivals and common safety-gap and objective-weight settings.

V. SIMULATION TESTS

  • Three experiments assess alignment probability, solution-value distributions, computation time, and comparisons among cooperative driving strategies.The first two examine solution quality; the second and third also address computation time and coordination performance, respectively.Source: §V · p. 5
  • Vehicle arrivals at each movement are modeled as Poisson processes, with equal arrival rates across movements unless otherwise specified.Arrival rates vary to test different traffic demands.Source: §V · p. 5
  • All three strategies use objective weights of 0.5 and the same minimum safety gaps: 1.5 seconds on one movement and 2 seconds across conflict movements.Experiments run in MATLAB on a personal computer with an Intel i7 CPU and 8 GB RAM.Source: §V · p. 5

A. The Optimality of the Grouping Based Strategy

The grouping strategy restricts planning to a subset of passing orders and evaluates how well that subset captures high-quality solutions. Simulations and a 25-CAV example show the resulting solutions can be close to the global optimum.

A. The Optimality of the Grouping Based Strategy

  • Grouping samples a subset of passing orders, narrowing the search space while retaining a chance of matching high-ranked solutions.The paper uses alignment probability to characterize how well the selected subset matches the original solution space.Source: A. The Optimality of the Grouping… · p. 6
  • Alignment probability measures the chance that the selected set contains at least k′ of the top-g solutions, with k′ as the alignment level.The simulations set k′ to 1 and compare the grouping solution with top-g solutions across vehicle counts.Source: A. The Optimality of the Grouping… · p. 6, Figure 5 · p. 6
  • The simulations record enumerated solutions and grouping estimates across arrival rates, then compare their rankings and solution values.The solution-value histogram is for a 25-CAV scenario; the alignment-probability plot varies the number of vehicles and top-g solutions.Source: A. The Optimality of the Grouping… · p. 6, Figure 5 · p. 6, Figure 6 · p. 6
  • The grouping solution is among the top 0.025% of solutions; with 20 vehicles and about 127,000 possible solutions, it ranks among the top 32.The paper reports this result as evidence that the sub-optimal solution can be close to the global optimum with high probability.Source: A. The Optimality of the Grouping… · p. 6
  • For 25 CAVs, the grouping solution ranks 7th among 5,200,300 passing orders, while the FIFO solution ranks 3,350,239th.The histogram compares objective values for the same merging scenario.Source: A. The Optimality of the Grouping… · p. 6, Figure 6 · p. 6

B. The Time Consumption of the Grouping Based Strategy

The time-consumption experiments compare planning and grouping as vehicle counts increase. Planning time rises sharply, while grouping time levels off under a cap on the number of groups.

B. The Time Consumption of the Grouping Based Strategy

C. A Comparison of Different Cooperative Driving Strategies with Respect to Arrival Flow Rate

Across the tested arrival rates, grouping achieves delay similar to planning with substantially shorter computation time. At high arrival rates, the ad hoc strategy has much worse delay, illustrating the tradeoff among the strategies.

C. A Comparison of Different Cooperative Driving Strategies with Respect to Arrival Flow Rate

  • The comparison measures vehicle delay and computation time, using five initial CAVs and 20-minute traffic processes across arrival rates of 0.1 to 0.3 veh/(lane·s).Planning uses a branch-and-bound method; the ad hoc strategy uses FIFO.Source: C. A Comparison of Different… · p. 7
  • 0.04 s/veh is the largest reported delay difference between grouping and planning, while planning takes more than 11 seconds at arrival rate 0.3 and grouping finishes within 40 ms.The comparison uses the three strategies on the same initial scenarios, replanning trajectories every 2 seconds.Source: C. A Comparison of Different… · p. 7
  • At arrival rate 0.25, ad hoc negotiation delay exceeds twice that of the other strategies, despite its time-saving advantage.The authors characterize its coordination performance at high arrival rates as far from satisfactory.Source: C. A Comparison of Different… · p. 7

VI. CONCLUSION

The grouping-based strategy trades computation time against traffic efficiency: it approaches planning-based efficiency with less calculation time and outperforms ad hoc negotiation at similar calculation time. Empirical vehicle dynamic constraints are not considered, and real on-ramp testing is planned.

VI. CONCLUSION

  • The grouping-based strategy yields traffic efficiency similar to planning-based methods with much less calculation time, and better traffic efficiency than ad hoc negotiation with similar calculation time.The authors report a high probability that its sub-optimal solution is close to the global optimum, regardless of vehicle arrival rate.Source: §VI · p. 7
  • Empirical dynamic constraints of vehicles are not considered in this paper.Source: §VI · p. 7
  • The authors plan to test the strategy on a real on-ramp and design tracking controllers to implement planned trajectories.Source: §VI · p. 8

APPENDIX A A SIMPLE MOTION PLANNING METHOD

The appendix describes a low-computational-cost motion-planning method based on basic kinematics, with profiles that accelerate, decelerate, or maintain constant velocity.

APPENDIX A A SIMPLE MOTION PLANNING METHOD

Loading 1804.01250v1…