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

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

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 5D and 9D vehicle and 13D 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 costates, and the low cost of PINN loss gradients.

Introduction

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: the curse of dimensionality and discontinuity. Traditional grid-based solvers cannot handle systems with more than 5 or 6 variables. Furthermore, state constraints (e.g., collision avoidance) cause the "value" of a state to jump instantly from "safe" to "collision," creating a mathematical "cliff." While Physics-Informed Neural Networks (PINNs) can mitigate the curse of dimensionality, their random sampling nature often misses these zero-measure boundaries, leading to poor safety performance.

Methodology

To address the challenge of learning discontinuous value functions, three strategies were evaluated:

  1. Hybrid Learning (HL): The primary contribution of this work, HL augments the standard PINN loss with supervised data obtained by solving Boundary Value Problems (BVPs) using Pontryagin’s Maximum Principle (PMP). This provides the network with explicit "hints" about the location of discontinuities.
  2. Value Hardening (VH): A curriculum learning approach where the penalty for constraint violation starts as a smooth function and gradually becomes steeper (harder) during training.
  3. 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.
Figure 1: Illustration of the discontinuity challenge and the value hardening process.

A critical insight from this research is the importance of the costate loss. Supervising the costate (the gradient of the value function) is more vital for safety than supervising the value itself, as it directly informs the robot's control actions to maintain safety. Additionally, the choice of activation functions is crucial; smooth functions like tanh or gelu are preferred over relu to avoid interference with gradient-based PDE losses.

Experimental Evaluation

The methods were tested on synthetic datasets from high-fidelity simulations:

  • 5D Uncontrolled Intersection: Two cars at a crossroad.
  • 9D Narrow Road & Lane Change: Complex maneuvering and collision avoidance.
  • 13D Drone Collision Avoidance: Nonlinear quadrotor dynamics.

Ground truth was generated using iterative BVP solvers to provide a baseline for safety and optimality.

Results and Discussion

The Hybrid Learning (HL) method demonstrated superior performance across all test cases. In the 5D intersection scenario, HL achieved a 0.00% collision rate, whereas vanilla PINNs failed with an 84.8% collision rate.

Figure 3: Qualitative comparison of value functions for the 5D intersection case across different learning methods.

HL also outperformed pure Supervised Learning (SL) by incorporating PDE loss, which allows the model to learn the underlying physics and generalize better to unseen states. While Value Hardening worked for 5D problems, it struggled in higher dimensions (9D and 13D) where the search space is too vast to find the hardening boundary without supervised hints. Notably, HL maintained high safety in the 13D drone simulation, where traditional grid-based solvers are computationally infeasible.

Conclusion

This study demonstrates that hybrid learning, combining supervised equilibrium data with PDE-based losses, effectively overcomes the limitations of PINNs in solving discontinuous HJI equations. Future work includes developing formal safety guarantees, addressing the numerical complexity of BVP solvers for systems with singular arcs, and extending the model to handle incomplete information about other players' goals.

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 5D and 9D vehicle and 13D 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 costates, 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},
}
Figure