Game-Theoretic Planning for Self-Driving Cars in Multivehicle Competitive Scenarios

In this article, we propose a nonlinear receding horizon game-theoretic planner for autonomous cars in competitive scenarios with other cars. The online planner is specifically formulated for a multiple-car autonomous racing game, in which each car tries to advance along a given track as far as possible with respect to the other cars. The algorithm extends previous work on game-theoretic planning for single-integrator agents to be suitable for autonomous cars in the following ways: 1) by representing the trajectory as a piecewise polynomial; 2) incorporating bicycle kinematics into the trajectory; and 3) enforcing constraints on path curvature and acceleration. The game-theoretic planner iteratively plans a trajectory for the ego vehicle and then the other vehicles in sequence until convergence. Crucially, the trajectory optimization includes a sensitivity term that allows the ego vehicle to reason about how much the other vehicles will yield to the ego vehicle to avoid collisions. The resulting trajectories for the ego vehicle exhibit rich game strategies such as blocking, faking, and opportunistic overtaking. The game-theoretic planner is shown to significantly outperform a baseline planner using model-predictive control, which does not take interaction into account. The performance is validated in high-fidelity numerical simulations with three cars, in experiments with two small-scale autonomous cars, and in experiments with a full-scale autonomous car racing against a simulated vehicle (video is available at https://youtube.com/playlist?list=PLmIcLEh8KMje4rYBqRANDuKvqFvj7LCRp).