MCTS-Level-k: Scalable Multi-Vehicle Decision Making for Unsignalized Intersection Navigation

Research Overview

This research presents MCTS-Level-k, an innovative decision-making framework that coordinates multiple autonomous vehicles (AVs) by integrating Level-k recursive reasoning with Monte Carlo Tree Search (MCTS). Our framework addresses the significant challenges faced by AVs at unsignalized intersections in mixed traffic environments through four key innovations: (1) A hierarchical integration of Level-k game theory and MCTS that balances strategic reasoning with computational efficiency; (2) A dual-filtering dynamic interaction graph (spatial and strategic) that reduces computational complexity from O(M^N) to O(M^n₀ + M^n₁ + M^n₂); (3) An optimization-based heterogeneous vehicle model capturing diverse behaviors of both AVs and human-driven vehicles (HDVs); and (4) A comprehensive uncertainty handling mechanism with precise collision detection and adaptive safety margins.

Case 1: Fully Autonomous Scenario (AV Rate of Penetration = 100%)

Our baseline scenario involves four AVs simultaneously approaching a four-way intersection from different directions, demonstrating our framework's ability to coordinate multiple vehicles in a challenging environment without traffic signals.

Case 1.1: Standard Four-Way Intersection

This scenario corresponds to Case 1 in our paper, where four AVs navigate a standard four-way intersection. The results show that our MCTS-Level-k framework achieves reduced trajectory deviations (37.56% improvement), zero PET violations, and up to 60% reduction in computation time compared to conventional methods.

Case 1.2: Complex Exit Configuration

This extension of Case 1 tests a more complex scenario where two AVs from different entry points must converge to the same exit, while the other two AVs similarly converge to another shared exit. All vehicles must navigate through the intersection simultaneously, creating a more challenging coordination problem that demonstrates our framework's versatility.

Case 2: Mixed Traffic Scenario (AV Rate of Penetration = 50%)

To evaluate our framework's robustness in mixed traffic, we conducted experiments with a 50% autonomous vehicle penetration rate, where both AVs and HDVs share the intersection space.

Case 2.1: Standard Mixed Traffic Intersection

This scenario corresponds to Case 2 in our paper, featuring four AVs and four HDVs approaching a four-way intersection from different directions. Our framework successfully adapts to human driving behaviors with diverse driving styles while ensuring safe and efficient intersection crossing. Comparative analysis shows our method reduces trajectory deviations by 62.43% over conventional approaches in this challenging mixed traffic environment.

Case 2.2: Complex Mixed Traffic Configuration

This extended scenario features the same complex exit configuration as Case 1.2, but with four additional HDVs interacting with the four AVs. Two AVs from different entry points converge to one shared exit while the other two AVs converge to another shared exit, all while navigating among unpredictable human-driven vehicles. This case demonstrates our framework's ability to handle complex interactions in a mixed traffic environment with challenging trajectory conflicts.

Conclusion

Our MCTS-Level-k framework demonstrates superior performance in both fully autonomous and mixed traffic scenarios. Extensive simulations show that our approach reduces computational time by up to 60% while ensuring safety and robust decision-making. In homogeneous traffic, we achieve a 37.56% reduction in trajectory deviations with zero PET violations; in mixed traffic, we demonstrate a 62.43% improvement in trajectory tracking. These results highlight our framework's practical potential for real-world implementation at unsignalized intersections.