Source-linked AI summary
Cooperative Driving at Unsignalized Intersections Using Tree Search
Huile Xu, Yi Zhang, Li Li, Weixia Li
TL;DR
CAV coordination at unsignalized intersections requires effective passing orders, but exhaustive search becomes impractical as the number of vehicles grows. The paper combines MCTS with heuristic rules to search the passing-order tree efficiently, finding nearly global-optimal orders in short planning times. Testing reports a strong performance–computation tradeoff, including about two thousand explored orders within 0.1 s among more than 10^46 possibilities.
Problem
The central problem is finding effective passing orders for CAVs when exhaustive enumeration becomes computationally impractical as vehicle numbers increase.
Method
The method combines MCTS with heuristic rules to explore promising passing-order tree nodes and reduce random sampling during simulation.
Results
About 2,000 passing orders were explored within 0.1 s among more than 10^46 possible orders in a 50-vehicle scenario.
Takeaways & Limitations
The MCTS-based strategy found a solution nearly matching enumeration-based global optimization while requiring much less computation time, and reduced average delay while improving throughput across tested traffic demands.
Abstract
from arXiv · showhide
In this paper, we propose a new cooperative driving strategy for connected and automated vehicles (CAVs) at unsignalized intersections. Based on the tree representation of the solution space for the passing order, we combine Monte Carlo tree search (MCTS) and some heuristic rules to find a nearly global-optimal passing order (leaf node) within a very short planning time. Testing results show that this new strategy can keep a good tradeoff between performance and computation flexibility.
I. INTRODUCTION
CAV intersection coordination centers on selecting an effective passing order, but exhaustive planning becomes computationally impractical as vehicle numbers grow. The paper proposes MCTS combined with heuristics to identify nearly global-optimal orders within short planning times.
- The key coordination problem is determining the optimal order in which CAVs pass through an unsignalized intersection.
- Planning-based strategies seek globally optimal orders by enumerating possibilities, often through mixed integer linear programming that minimizes total vehicle delay.
- As vehicle numbers increase, exhaustive tree-node enumeration grows sharply and hinders practical application at unsignalized intersections.
- Ad hoc negotiation methods find acceptable orders quickly, but their resulting passing orders are not good enough in many situations.
- The proposed strategy combines MCTS with heuristic rules to explore promising solution-tree nodes and find nearly global-optimal passing orders within short planning times.
II. PROBLEM FORMULATION
The problem models intersection coordination as minimizing total delay while scheduling vehicle trajectories under communication, lane, and conflict-zone assumptions. Passing orders form a tree whose leaves represent complete vehicle sequences, enabling search over the solution space.
- The intersection contains a control zone and a conflict zone, with the latter divided into conflict subzones according to intersection geometry.
- Vehicles are assigned unique identities and sets of conflict subzones that specify the subzones they traverse in sequence.
- The formulation assumes instantaneous V2V sharing, prohibits lane changes in the control zone, and treats vehicle velocity as constant through the conflict zone.
- The optimization objective minimizes total vehicle delay by scheduling desired arrival times at conflict subzones under vehicle dynamics and safety-gap constraints.
- Directly solving the formulation often produces a MILP whose computation time increases exponentially with the number of vehicles.
- Each tree node represents a partial passing order, while complete orders appear as leaf nodes and their trajectory-derived delays evaluate parent-node potential.
III. MCTS BASED COOPERATIVE DRIVING STRATEGIES
Because expanding the full passing-order tree is infeasible under limited computation budgets, the strategy uses MCTS with heuristic rules to prioritize promising nodes. Classical MCTS combines tree selection, expansion, simulation, and score updates, while heuristics constrain simulation toward plausible orders.
- With many vehicles, the complete solution tree cannot usually be expanded within the available computation budget.
- The proposed method uses MCTS and heuristic rules to select nodes with potential to produce optimal passing orders.
A. The Classical MCTS Based Strategy
Classical MCTS builds a passing-order search tree through selection, expansion, simulation, and backpropagation. It evaluates leaf-node total delays and returns the best passing order when the computation budget is reached, while performance depends on parameter choices.
- Leaf-node scores equal the total delay of their corresponding passing orders and guide branch exploration.
- Each MCTS iteration performs selection, expansion, simulation, and backpropagation over the passing-order tree.
- During simulation, random sampling completes a passing order from the current partial order to evaluate its potential.
- Simulation computes normalized delay-based scores for new nodes, then backpropagates results through selected nodes to update parent scores.
- The strategy continuously updates the best passing order and returns it when the computation budget is exhausted.
- Performance is influenced by the maximum search time and weighting parameters C and ω.
B. The MCTS + Heuristic Rules
The proposed MCTS replaces random simulation sampling with heuristic vehicle-selection rules while retaining random sampling during expansion. These rules prune invalid orders, prioritize candidates by lane position and arrival time, and avoid overly greedy ordering.
- Randomly sampled passing orders cannot quickly reveal node potential because the solution contains a huge number of possible orders.
- Heuristic rule 1 prunes invalid passing orders, while heuristic rule 2 selects which candidate vehicle to add.
- On the same lane, the vehicle closest to the conflict zone is added first because lane changes are prohibited.
- Among vehicles sharing a conflict subzone, the vehicle with the less desired arrival time is added first.
- The proposed policy uses random sampling only during expansion, unlike classical MCTS, which uses it during both expansion and simulation.
- The simulation policy applies FIFO ordering only to vehicles uncovered by the current partial order, helping avoid convergence to an over-greedy solution.
A. Simulation Settings
The simulations model a three-lane-per-leg intersection with 36 conflict subzones and test varying traffic demands. Vehicle arrivals follow a Poisson process, while delays are evaluated with independent lane point queues and periodic rescheduling.
- Experiments use an intersection with three lanes in each leg, whose conflict zone is divided into 36 subzones.
- Algorithm 2 takes vehicle locations and velocities as input and outputs a possible passing order.
- The heuristic simulation selects closest uncovered vehicles on each lane, compares their conflict-subzone arrival times, and repeats until completion.
- Vehicle arrivals are modeled as a Poisson process, with its mean varied to test different traffic demands.
- The point-queue model assumes free-flow travel until the intersection boundary and maintains an independent virtual queue for each lane.
- The passing order of vehicles within the control zone is rescheduled every 2 seconds.
- Minimum safety gaps are enlarged to avoid collisions caused by position measurement errors and communication delay.
B. The Choice of Parameters
The study evaluates delay reduction against FIFO and selects MCTS parameters and search effort to balance improvement with computation time. It sets ω = 0.85, C = 0.05, and a 0.1 s search limit after observing saturation near 1000 searched nodes.
- Performance measures: The improvement rate is defined as the decreased total delay relative to the FIFO baseline, with J_F I F O denoting FIFO and J_M C T S the best MCTS objective value.The evaluation also considers delay and traffic throughput.
- Parameter selection: With 30 vehicles, significant improvement occurs even under the worst parameter setting, while C and ω influence exploitation–exploration balance.Heuristic rules in simulation reduce the influence of random sampling; similar results across vehicle counts motivate the selected parameters.
- Parameter selection: The selected parameter setting is ω = 0.85 and C = 0.05 after testing different values under a fixed 0.1 s planning budget.The experiments vary ω and C from 0 to 1 while changing vehicle arrival rates.
- Search budget: Improvement rate increases significantly from 10 to 1000 searched nodes and soon becomes saturated afterward.The comparison uses searched-node count to remove device computing-power effects.
- Search budget: Searching 1000 nodes is judged sufficient, and most intersection scenarios allow this within 0.1 s on the authors’ personal computer.The subsequent experiments therefore use a maximum search time of 0.1 s.
C. Comparisons of Different Cooperative Driving Strategies
The comparison examines all valid passing-order solutions in a 20-vehicle single-lane scenario and evaluates strategies under varied traffic demand. MCTS finds a near-global-optimal solution with much less computation than enumeration, while improving delay and throughput over FIFO across tested conditions.
- Solution quality and computation: For 20 vehicles at a single-lane intersection, MCTS is nearly globally optimal while requiring much less computation than enumeration.The MCTS solution ranks 648th among nearly 10 billion solutions, whereas FIFO ranks 4563421793th.
- Solution quality and computation: FIFO has the least computation time but produces a solution far from the optimum.The comparison uses objective values for all valid passing orders.
- Traffic-demand comparison: Across varied average arrival rates in 20-minute simulations, the new strategy further reduces average delay and improves traffic throughput in all situations.Traffic demand is varied to examine performance under different arrival conditions.
- Experimental setting: The MCTS-based strategy is evaluated with a computation time of 0.1 s.This reported computation time accompanies the comparison results.
D. A Further Look into the Structure of the Obtained Search Tree
For 50 vehicles, the proposed search tree concentrates exploration on promising branches while heuristic rules sharply reduce reached leaf nodes. Despite more than 10^46 possible passing orders, the strategy explores about 2,000 within 0.1 s.
- Search-tree exploration: The strategy prioritizes promising branches representing partial passing orders and spends most search time exploring them further.This follows the classical MCTS pattern while focusing computation on potentially optimal regions.
- Search-tree exploration: Heuristic rules reduce unnecessary leaf-node exploration compared with classical MCTS.The proposed tree reaches only a very small number of leaf nodes, whereas classical MCTS generates many unnecessary leaves.
- Search-tree exploration: More than 10^46 possible passing orders are reduced to about 2,000 explored orders within 0.1 s for the 50-vehicle scenario.This illustrates the scale of pruning achieved by the proposed strategy.
V. CONCLUSION
The paper presents a cooperative driving strategy that combines Monte Carlo simulation with heuristic-rule simulation to accelerate passing-order search. It reports nearly optimal solutions in short time and notes that the discussion is limited to unsignalized intersections, with field studies planned for future work.
- Conclusion: The proposed strategy combines Monte Carlo simulation and heuristic-rule simulation to accelerate search for vehicle passing orders.The method quickly learns tree-structure knowledge from the scenario.
- Conclusion: The method finds a nearly optimal solution in a short time.The reported conclusion concerns the scheduling of vehicles at unsignalized intersections.
- Scope: The discussion focuses on vehicle scheduling at unsignalized intersections, although the method is described as adaptable to ramping areas and working zones.The paper identifies these other scenarios as potential applications rather than evaluated settings.
- Future work: Field studies are planned for future work using automated vehicle prototypes.The paper states that prototypes are being built for forthcoming testing.