Efficient Game-Theoretic Planning With Prediction Heuristic for Socially-Compliant Autonomous Driving

Chenran Li, Tu Trinh, Letian Wang, Changliu Liu, Masayoshi Tomizuka, Wei Zhan

Introduction

Planning for autonomous vehicles (AVs) in dense urban environments extends beyond simple obstacle avoidance; it requires sophisticated social negotiation. In scenarios like roundabout entries or highway merges, an AV’s actions directly influence other drivers, whose subsequent reactions then impact the AV. This "closed-loop" interaction is fundamentally a game-theoretic problem. However, traditional methods for finding a Nash Equilibrium often struggle with high computational costs and non-convex search spaces, frequently becoming trapped in local minima.

While Monte Carlo Tree Search (MCTS) offers a robust alternative for finding global optima, it is plagued by the "curse of dimensionality." As the planning horizon extends, the search tree grows exponentially, demanding excessive memory and iterations. This paper introduces a novel architecture that combines MCTS with behavior prediction heuristics and Bayesian inference to achieve efficient, socially-compliant driving.

Methodology

The researchers propose a Prediction Heuristic Search Architecture designed to streamline the decision-making process by focusing on the most plausible human behaviors. The framework consists of four primary components:

1. Prediction Heuristic

Rather than exploring the entire action space uniformly, the algorithm leverages off-the-shelf behavior prediction models to guide the search. By defining a "Confidence Range" around predicted trajectories using Mahalanobis distance, the system identifies high-value branches. During the MCTS back-propagation phase, rewards are weighted by a confidence metric. This effectively prunes the search tree, directing computational resources toward paths that align with realistic human interactions while maintaining the flexibility to discover novel solutions.

2. Socially-Compliant Reward Function

To mimic human social behavior, the reward function balances two competing objectives: egoism (reaching the destination safely and quickly) and courtesy (minimizing the negative impact on other road users). This balance is controlled by a parameter, $\gamma$. A high $\gamma$ indicates a courteous driver, while a low $\gamma$ represents more aggressive behavior.

3. Online Bayesian Inference

Because the driving styles of surrounding vehicles are unknown, the system employs a Recursive Bayesian Inference engine. By observing the movements of nearby vehicles in real-time, the AV estimates their $\gamma$ parameters. This allows the AV to dynamically adjust its strategy based on whether an opponent is likely to yield or assert their right-of-way.

4. Stackelberg Game Assumption

To maintain computational tractability, the interaction is modeled as a leader-follower (Stackelberg) game. In this setup, the ego vehicle acts as the leader, making a move while anticipating the optimal response from the followers (the other drivers).

Experimental Evaluation

The framework was evaluated using the INTERACTION Dataset, focusing specifically on complex roundabout scenarios. These real-world datasets provide a high degree of naturalistic interaction, serving as a rigorous benchmark for social negotiation algorithms.

Key Results

  • Search Efficiency: The prediction heuristic significantly improved convergence speeds. By focusing on feasible branches, the algorithm reached much deeper into the search tree than standard MCTS. In tests, the proposed method visited the optimal node at "Layer 6" of the tree 49 times within 30,000 iterations, whereas a general MCTS reached it only once.
  • Adaptive Social Behavior: In closed-loop simulations, the AV demonstrated human-like adaptability. When the Bayesian estimator identified an aggressive opponent (low $\gamma$), the AV chose to yield. Conversely, when it detected a courteous driver, the AV confidently proceeded, optimizing traffic flow.
  • Inference Speed: The Bayesian estimator proved highly responsive, typically converging to the "ground truth" driving style of an opponent within approximately 1 second (6 time steps) of the initial interaction.

Discussion and Limitations

The "aha moment" of this research lies in the realization that while the theoretical search space for driving is infinite, the socially sensible space is quite small. By using coarse predictions as a heuristic, the AV can ignore the "noise" of the search space without sacrificing its ability to find globally optimal paths.

However, several challenges remain:

  • Multi-Agent Scaling: While the system can handle multiple agents by sorting them by right-of-way, the computational complexity still increases significantly as more participants are added to the "social dance."
  • Prediction Dependency: The system's performance is inherently linked to the accuracy of the underlying prediction model. A fundamental failure in the prediction model could potentially lead the heuristic search astray.
  • Role Ambiguity: The Stackelberg assumption is effective for clear right-of-way scenarios but may be too rigid for highly ambiguous situations where leader-follower roles are not clearly defined.

Conclusion

By integrating behavior prediction directly into the MCTS framework, this research provides a path toward more efficient and natural autonomous driving. The ability to infer the social preferences of others in real-time allows AVs to move beyond rigid, rule-based logic and toward a more fluid, human-like negotiation style on the road.

Summary updated

Abstract

Planning under social interactions with other agents is an essential problem for autonomous driving. As the actions of the autonomous vehicle in the interactions affect and are also affected by other agents, autonomous vehicles need to efficiently infer the reaction of the other agents. Most existing approaches formulate the problem as a generalized Nash equilibrium problem solved by optimization-based methods. However, they demand too much computational resource and easily fall into the local minimum due to the non-convexity. Monte Carlo Tree Search (MCTS) successfully tackles such issues in game-theoretic problems. However, as the interaction game tree grows exponentially, the general MCTS still requires a huge amount of iterations to reach the optima. In this letter, we introduce an efficient game-theoretic trajectory planning algorithm based on general MCTS by incorporating a prediction algorithm as a heuristic. On top of it, a social-compliant reward and a Bayesian inference algorithm are designed to generate diverse driving behaviors and identify the other driver's driving preference. Results demonstrate the effectiveness of the proposed framework with datasets containing naturalistic driving behavior in highly interactive scenarios.
BibTeX
@article{li2022efficient,
  author = {Chenran Li and Tu Trinh and Letian Wang and Changliu Liu and Masayoshi Tomizuka and Wei Zhan},
  title = {{Efficient Game-Theoretic Planning With Prediction Heuristic for Socially-Compliant Autonomous Driving}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2022},
  doi = {10.1109/lra.2022.3191241},
}
Figure