Game-Theoretic Motion Planning for Multi-Agent Interaction

Abstract

As robots leave factory floors and deploy into unstructured human environments, they must navigate safely and efficiently alongside people and other autonomous systems. In these dynamic settings, decisions are inherently interdependent: a robot's optimal action depends heavily on how others will respond, and vice versa. Anticipating and actively shaping these responses is central to competent multi-agent behavior. However, this interaction unfolds under significant uncertainty, with limited prior knowledge of other agents' objectives, constrained sensing capabilities, and tight computational limits.

This dissertation addresses these fundamental challenges by framing robot motion planning for interactive scenarios through the lens of non-cooperative game theory. This perspective provides a principled mathematical framework for modeling multiple self-interested decision-makers who act simultaneously with partially aligned objectives. Focusing on environments where a single controlled robot interacts with uncontrolled agents whose intents are not known a priori, this dissertation develops a comprehensive suite of game-theoretic tools. These tools enable robots to infer underlying intents from observations and generate motion plans that capture the complex interdependence of self-interested decision-making.

The core contributions of this dissertation span intent inference, real-time adaptation, uncertainty-aware planning, computational efficiency, and complex non-smooth dynamics.

First, we formalize the problem of learning unknown intents from observed past behavior as an inverse game. By casting this as maximum-likelihood estimation with equilibrium constraints, our transcription jointly estimates game parameters, hidden states, and future decisions, significantly improving inference accuracy. Second, we tightly integrate these inverse games with online planning. We propose a novel solution technique handling inequality constraints with a first-order update rule for amortized inference, yielding a game-theoretic planner that dynamically adapts to evolving intent estimates.

Third, we address situations demanding explicit reasoning over a distribution of possible intents. We introduce contingency games, an uncertainty-aware planning technique that jointly generates multi-hypothesis predictions of others alongside conditional plans for the robot. By explicitly anticipating future information gains, this approach seamlessly bridges the gap between conservatively ignoring uncertainty and assuming it will never resolve. Fourth, to alleviate the substantial computational burden of online game-theoretic planning, we introduce an amortized solver for mixed strategies. An offline model learns to propose dynamically feasible trajectory candidates, while a discrete game solved online rapidly computes competitive mixed Nash equilibria.

Finally, we tackle interaction domains with inherently non-smooth dynamics, such as multi-agent manipulation, where constraints are not continuously differentiable. We propose a data-driven approach leveraging probabilistic inference and generative diffusion models. This blends learning from single-agent demonstrations with reasoning about joint multi-agent costs, discovering collaborative strategies without requiring massive multi-agent datasets.

In summary, this dissertation advances interactive motion planning by equipping robots to accurately infer intents, act safely under uncertainty, and navigate complex interactions. These algorithmic contributions are extensively validated via simulation and ground robots across autonomous driving, mobile navigation, and multi-agent manipulation, accompanied by open-source libraries to accelerate future research.