Title: Hierarchical Game-Theoretic Planning for Autonomous Vehicles,
Abstract: The actions of an autonomous vehicle on the road affect and are affected by
those of other drivers, whether overtaking, negotiating a merge, or avoiding an
accident. This mutual dependence, best captured by dynamic game theory, creates
a strong coupling between the vehicle's planning and its predictions of other
drivers' behavior, and constitutes an open problem with direct implications on
the safety and viability of autonomous driving technology. Unfortunately,
dynamic games are too computationally demanding to meet the real-time
constraints of autonomous driving in its continuous state and action space. In
this paper, we introduce a novel game-theoretic trajectory planning algorithm
for autonomous driving, that enables real-time performance by hierarchically
decomposing the underlying dynamic game into a long-horizon "strategic" game
with simplified dynamics and full information structure, and a short-horizon
"tactical" game with full dynamics and a simplified information structure. The
value of the strategic game is used to guide the tactical planning, implicitly
extending the planning horizon, pushing the local trajectory optimization
closer to global solutions, and, most importantly, quantitatively accounting
for the autonomous vehicle and the human driver's ability and incentives to
influence each other. In addition, our approach admits non-deterministic models
of human decision-making, rather than relying on perfectly rational
predictions. Our results showcase richer, safer, and more effective autonomous
behavior in comparison to existing techniques.