Monte Carlo Tree Search and Cognitive Hierarchy Theory for Interactive-Behavior Prediction in Fast Trajectory Planning and Automated Lane Change

Abstract Predicting the states of the surrounding traffic is one of the major problems in automated driving. Maneuvers such as lane change, merge, and exit management could pose challenges in the absence of intervehicular communications and can benefit from driver behavior prediction. Predicting the motion of surrounding vehicles and trajectory planning need to be computationally efficient for real-time implementation. The main goal of this paper is to develop a fast algorithm that predicts the future states of the neighboring vehicles. The proposed workflow employs Monte Carlo Tree Search (MCTS) along with an on-policy learning technique for fast trajectory planning in multi-lane highway traffic scenarios. Also, for the inclusion of behavioral aspects, cognitive hierarchy and level-K game theories are utilized to predict the reaction and decision of the surrounding drivers. Simulation case studies demonstrate that our proposed approach is real-time implementable and can often avoid collision in difficult simulated confrontations.