arXiv preprint ·
Inertia-Corrected Newton Method For Generalized Nash Equilibria in Dynamic Games with Optimality Verification
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Newton methods efficiently find Generalized Nash Equilibria (GNE) in dynamic games by solving for the KKT necessary conditions. These methods are fast and can support multi-agent Model Predictive Control (MPC) for highly dynamic robots. However, a small KKT residual alone does not certify that the returned solution satisfies the second-order sufficient conditions for a local GNE. In this paper, we propose an efficient numerical method to verify the second-order sufficient conditions (SOSC) for a local GNE. We connect the inertia of the agent KKT matrix with the positive definiteness of the reduced Hessian of the cost function, projected onto the null space of the constraints. Furthermore, we introduce an inertia-corrected update step that improves convergence to local GNEs by destabilizing strict saddle points with weak cross-agent coupling. Our main contribution is a fast Newton solver for Constrained Dynamic Games that provides efficient optimality checking. Through numerical benchmarks, we demonstrate the proposed solver's runtime and convergence performance in practical multi-agent planning problems. We also validate the solver's real-time capabilities in physical experiments using a platform of miniature autonomous race cars.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Robotics
Moment Ambiguity and the Limits of Robust Stochastic Optimization
Single-or-Sample: Online Fair Allocation for Combinatorial Agents
How Much Must a Private Mempool Hide? Exact Leakage Thresholds for Sandwich Attacks
Learnable Randomization as Commitment Against Adaptive Optimizers
PACT: Pairwise-Anchored Calibrated Tuning for Single-Token Typed Decisions
Get the few papers worth your time in Robotics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.