Stochastic Dynamic Games in Belief Space

Wilko Schwarting, Alyssa Pierson, Sertac Karaman, Daniela Rus

Introduction

In robotics, planning typically bifurcates into two distinct domains: Game Theory, which models agent interactions under the assumption of perfect information, and Belief-Space Planning (e.g., POMDPs), which manages sensing and motion uncertainty for single agents in static environments. Real-world scenarios like autonomous racing or surveillance require a synthesis of these domains, where a robot must reason about its own uncertainty, the opponent's uncertainty, and how its actions influence the opponent's future moves. This paper introduces a computationally efficient algorithm that solves for a local Nash equilibrium within an iterative Linear-Quadratic Gaussian (iLQG) framework, enabling robots to perform complex, uncertainty-aware interactive behaviors in real-time.

Methodology

The authors propose a tractable solution to the "stochastic non-cooperative dynamic game in belief space" by employing several key approximations. First, the robot's belief—its estimate of the state—is represented as a Gaussian distribution (mean and covariance), with an Extended Kalman Filter (EKF) modeling belief evolution. Second, the algorithm adapts the iLQG framework to solve a quadratic game at every timestep during the backward pass, identifying a local Nash equilibrium that accounts for interdependent policies.

Table of notation for the stochastic dynamic game framework.

To maintain computational efficiency, the framework utilizes "First-Order Beliefs," assuming that an agent's belief about an opponent is identical to the opponent's belief about itself. This prevents infinite recursion in "Theory of Mind" reasoning. The resulting algorithm scales linearly with the planning horizon and polynomially with the number of agents, achieving execution speeds exceeding 100Hz on standard hardware.

Experimental Evaluation

The algorithm was evaluated across three simulated multi-agent case studies:

  1. Active Surveillance: A pursuer "herds" an evader into well-lit areas to minimize tracking uncertainty.
  2. Guide Dog for a Blind Agent: A guide agent leads a second agent through light sources to ensure goal reaching with high confidence.
  3. Autonomous Racing: Two cars compete on a track featuring "noise zones" with poor sensing. This served as the primary performance benchmark.

Results and Strategic Insights

The Dynamic Game Belief Space Planning (DG BSP) agent demonstrated significant advantages over standard Model Predictive Control (MPC) and non-belief-space variants. In racing simulations, the DG BSP agent won 44% more races than the MPC baseline and 34% more races than versions that ignored belief uncertainty.

Visualization of the autonomous racing benchmark, showing trajectories and belief uncertainty.

A key insight is the treatment of information as a strategic asset. The planner naturally synthesizes behaviors like forcing an opponent into a "dark" zone to increase their uncertainty, thereby compelling them to drive more conservatively. Furthermore, the belief-space approach significantly improved safety; non-BSP methods often drove aggressively into high-noise corners, leading to collisions or track departures due to unmodeled risk.

Conclusion and Future Work

By focusing on local Nash equilibria around nominal trajectories, the authors transition the problem of belief-space games from theoretical complexity to real-time capability. However, limitations remain: the first-order belief constraint precludes complex deception, and the Gaussian assumption may struggle in highly non-linear or multi-modal environments. Future research will explore higher-order belief spaces and further optimization to support larger swarms of interacting robots.

Summary updated

BibTeX
@article{schwarting2021stochastic,
  author = {Wilko Schwarting and Alyssa Pierson and Sertac Karaman and Daniela Rus},
  title = {{Stochastic Dynamic Games in Belief Space}},
  journal = {IEEE Transactions on Robotics},
  year = {2021},
  doi = {10.1109/tro.2021.3075376},
}
Figure