Game-Theoretic Control with Constrained Potential Surgery
Authors: Zhiyuan Zhang, Panagiotis Tsiotras
Organizations: School of Aerospace Engineering, Institute for Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA
Constrained general-sum dynamic games are a popular formulation for highly interactive multi-agent planning problems. In recent years, Generalized Nash Equilibrium (GNE) solvers have achieved real-time performance for small dynamic games. However, solution speed still remains a bottleneck, and controlling even a small number of agents (e.g., more than four) in a dynamic task remains elusive. In addition, Newton solvers that focus on the first-order conditions are vulnerable to non-Nash saddle points, limiting the usefulness of the provided solution. In this work, we propose a fast and versatile interior point solver for constrained dynamic games, along with a computationally efficient second-order correction that increases the probability of converging to a local GNE solution in constrained dynamic games. The performance of the proposed method is evaluated on numerical benchmarks and a physical experiment involving scaled race cars.
Figures & tables
Fig. 1 : Time-lapse of a solution to the 8-car merging game. Cars merge to the upper lane while maintaining safety distances.
Fig. 2 : Average runtime comparison of baseline and proposed algorithms.
Fig. 3 : Convergence ratio of proposed algorithms.
Fig. 4 : Optimality ratio of the converged simulations.
Fig. 5 : Snapshots of a three-car overtake during the experiment.