Effective Game-Theoretic Motion Planning via Nested Search

To facilitate effective, safe deployment in the real world, in- dividual robots must reason about interactions with other agents, which often occur without explicit communication. Recent work has identified game theory, particularly the concept of Nash Equilibrium (NE), as a key enabler for behavior-aware motion planning. Yet, existing work falls short of fully unleashing the power of game-theoretic reasoning. Specifically, popular optimization-based methods require simplified robot dynamics and may get trapped in local minima due to convexification. Other works that rely on the explicit enumeration of all possible trajectories suffer from poor scalability. To bridge this gap, we introduce Game-Theoretic Nested Search (GTNS), a scalable, and provably-correct approach for computing NEs in general dynamical systems. GTNS efficiently searches the action space of all agents involved, while discarding trajectories that violate the NE constraint (no unilateral deviation) through an inner search over a lower-dimensional space. Our algorithm enables explicit selection among equilibria by utilizing a user-specified global objective, thereby capturing a rich set of realistic interactions. We demonstrate the approach across a variety of autonomous driving and racing scenarios, achieving solutions in mere seconds on commodity hardware.

M.Sc. student under the supervision of Dr. Kiril Solovey.