Value Approximation for Two-Player General-Sum Differential Games With State Constraints

Lei Zhang, Mukesh Ghimire, Wenlong Zhang, Zhe Xu, Yi Ren

TL;DR

This paper introduces a "hybrid learning" approach to solve high-dimensional differential games with safety constraints, overcoming the failure of standard Physics-Informed Neural Networks (PINNs) to handle discontinuous solutions. By combining the physical consistency of PDEs with supervised data from optimal control theory, the researchers achieved near-perfect safety in complex simulations up to 13 dimensions.

What Problem Does This Paper Address?

In human-robot interaction (HRI), robots must make split-second decisions that are both optimal and safe. Traditionally, this is modeled using Hamilton-Jacobi-Isaacs (HJI) partial differential equations (PDEs). However, these equations suffer from two major issues:

  1. The Curse of Dimensionality: Traditional grid-based solvers can't handle systems with more than 5 or 6 variables (dimensions).
  2. Discontinuity: When you add state constraints (e.g., "don't hit the wall"), the "value" of a state can jump instantly from "safe" to "collision," creating a mathematical cliff.

While PINNs are great at beating the curse of dimensionality, they are notoriously bad at learning these "cliffs" because their random sampling nature almost always misses the exact boundary of the discontinuity.

Methods

The authors evaluated three distinct strategies to help neural networks learn these "safe vs. unsafe" boundaries:

  • Hybrid Learning (HL): This is the paper's primary contribution. It augments the standard PINN loss (which enforces the PDE) with a supervised loss. This supervised data comes from solving Boundary Value Problems (BVPs) using Pontryagin’s Maximum Principle (PMP). Essentially, it gives the network "hints" about where the discontinuities lie.
  • Value Hardening (VH): A curriculum learning approach where the penalty for hitting a constraint starts "soft" (smooth) and gradually becomes "hard" (steep) over the course of training.
  • Epigraphical Learning (EL): A mathematical "lifting" technique that transforms the discontinuous value function into a continuous one by adding an extra dimension to the state space.

Datasets

The researchers used synthetic datasets generated from high-fidelity simulations of vehicle and drone dynamics:

  • 5D Uncontrolled Intersection: Two cars meeting at a crossroad.
  • 9D Narrow Road & Lane Change: Complex vehicle maneuvering and collision avoidance.
  • 13D Drone Collision Avoidance: The highest-dimensional test case, involving nonlinear quadrotor dynamics.
  • Ground Truth: Generated using iterative BVP solvers to provide a baseline for "perfect" play and safety.

Key Insights and Ideas

  • The "Measure Zero" Problem: PINNs fail on discontinuities because the boundary itself has zero volume. If you sample points randomly, the probability of hitting the "cliff" is zero, so the network never learns it exists.
  • Costate Loss is the Secret Sauce: The authors found that supervising the costate (the gradient of the value function) is more important for safety than supervising the value itself. The costate tells the robot how to change its action to stay safe, not just if it is currently safe.
  • Scalability Limits of Hardening: While "Value Hardening" works for simple 5D problems, it fails as dimensions increase (9D and 13D). The search space becomes too large for the network to find the hardening boundary without the explicit "hints" provided by Hybrid Learning.
  • Activation Functions Matter: Smooth functions like tanh or gelu are essential. relu performs poorly because its non-differentiable "kink" at zero interferes with the PDE's gradient-based loss.

Key Results

  • Safety Performance: In the 5D intersection case, the Hybrid Learning (HL) model achieved a 0.00% collision rate, whereas a vanilla PINN failed spectacularly with an 84.8% collision rate.
  • Generalization: HL outperformed pure Supervised Learning (SL). By including the PDE loss, the model learned the underlying "physics" of the game, allowing it to stay safe even in states it hadn't seen during training.
  • High-Dimensional Success: The HL method maintained high safety and low error in the 13D drone simulation, a regime where traditional grid-based HJI solvers are computationally impossible to use.

Limitations and Future Work

  • No Formal Guarantees: While the empirical results are excellent, the method does not yet provide a formal mathematical "safety certificate" (proof that it will never fail).
  • BVP Complexity: The Hybrid method relies on solving BVPs to get supervised data. Solving these can be numerically difficult, especially for systems with "singular arcs" (complex optimal paths).
  • Incomplete Information: The current work assumes players know each other's goals. The authors suggest moving toward "empathetic" models where robots update their beliefs about human intent in real-time using Bayesian inference.

Summary updated

Abstract

Solving Hamilton–Jacobi–Isaacs (HJI) PDEs numerically enables equilibrial feedback control in two-player differential games, yet faces the curse of dimensionality (CoD). While physics-informed neural networks (PINNs) have shown promise in alleviating CoD in solving PDEs, vanilla PINNs fall short in learning discontinuous solutions due to their sampling nature, leading to poor safety performance of the resulting policies when values are discontinuous due to state or temporal logic constraints. In this study, we explore three potential solutions to this challenge: 1) a hybrid learning method that is guided by both supervisory equilibria and the HJI PDE, 2) a value-hardening method where a sequence of HJIs are solved with increasing Lipschitz constant on the constraint violation penalty, and 3) the epigraphical technique that lifts the value to a higher dimensional state space where it becomes continuous. Evaluations through 5-D and 9-D vehicle and 13-D drone simulations reveal that the hybrid method outperforms others in terms of generalization and safety performance by taking advantage of both the supervisory equilibrium values and co-states, and the low cost of PINN loss gradients.
BibTeX
@article{zhang2024value,
  author = {Lei Zhang and Mukesh Ghimire and Wenlong Zhang and Zhe Xu and Yi Ren},
  title = {{Value Approximation for Two-Player General-Sum Differential Games With State Constraints}},
  journal = {IEEE Trans. Robotics},
  year = {2024},
  url = {https://openreview.net/forum?id=CGbg2W9xo8},
}

Loading related content...

Figure