Residual Descent Differential Dynamic Game (RD3G) - A Fast Newton Solver for Constrained General Sum Games

Abstract

We present Residual Descent Differential Dynamic Game (RD3G), a Newton-based solver for constrained multiagent game-control problems. The proposed solver seeks a local Nash equilibrium for games where agents are coupled through their rewards and state constraints. By maintaining a dynamic set of active constraints, combined with a barrier function on satisfied constraints and a backtracking line search, the proposed method is able to satisfy state constraints while keeping the dimension of the Newton descent direction problem to a minimum. We compare the proposed method against state-of-the-art techniques and showcase the computational benefits of the RD3G algorithm on several example problems. The RD3G is up to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{4 X}$</tex> faster and has <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{2 X}$</tex> higher convergence rate than existing approaches in higher dimensional games.