Decomposition and Hamilton-Jacobi-Bellman Methods for Nonconvex Generalized Nash Equilibrium Problems
Creators: name: Britzelmeier, Andreas
Publisher: name: Zenodo
Year: 2021
Subjects: Generalized Nash Equilibrium Problem
Hamilton-Jacobi-Bellman
Nonconvex Optimal Control Problem
Nonconvx Optimization
Constrained Optimization
Dynamic Programming
Semi-Lagrangian
Potential Game
Convergence Theory
GPU Parallel Programming

description: The subject of this dissertation is concerned with the theoretical investigation and the develop-<br> ment of numerical methods for generalized Nash equilibrium problems subject to individual<br> differential equations, state and control constraints as well as shared nonconvex constraints,<br> complemented by an experimental validation of the methodological concepts.<br> To cope with the nonconvex shared constraints a partial penalty reformulation is proposed.<br> A decomposition method with penalty selection, capable of solving the ensuing semi-discrete<br> (constrained) Nash equilibrium problem is devised, which prevents the a priori imposition of<br> hierarchies. Leveraging the underlying potential game’s inherent structure, convergence of a<br> sequence of solutions of the semi-discretized Nash equilibrium problem to a solution of the<br> generalized Nash equilibrium problem is proven.<br> Then, a Hamilton-Jacobi-Bellman approach for solving standard Nash equilibrium problems,<br> which constitute the subproblems of the decomposition method is pursued. Accordingly, a<br> backward Semi-Lagrangian method for the numerical solution of the Hamilton-Jacobi-Bellman<br> equation is devised. In conjunction with a suitable state space discretization, an approximate<br> value function, for Nash equilibrium problems, satisfying the principle of dynamic programming<br> is constructed. We then introduce an iterative algorithm for the recursive computation of optimal<br> controls. Convergence to a global minimizer in finite time is shown based on an error estimate<br> for the approximated value function. Furthermore, we investigate the convergence properties of<br> higher-order Semi-Lagrange schemes in the context of time and control discrete value functions,<br> as well as the influence of the order of approximation of the control on the resulting convergence<br> rate. Eventually, exploiting the recursive problem structure of dynamic programming and a<br> batching strategy, a GPU parallel dynamic programming algorithm is developed. Scalability and<br> efficiency of the algorithm is demonstrated in a benchmark with CPU implementations.<br> Eventually, the numerical and experimental validation of the theoretical and algorithmic<br> framework is conducted with respect to two tangible exemplary applications. The algorithmic<br> framework is embedded in a model predictive control structure. To validate the feasibility<br> of online path planning using the GPU parallel dynamic programming algorithm, a higher<br> dimensional truck path planning problem is considered. In addition, an autonomous vehicle<br> coordination problem modelled as a generalized Nash equilibrium problem with non-convex<br> shared collision avoidance constraints is investigated. Numerical results instigate the capability<br> of the algorithmic conceptualization to efficiently provide collision-free coordination by means<br> of Nash equilibria. Based on the theoretical results, convergence properties are established.<br> For the experimental evaluation, a test bench comprising a positioning system, a cloud for the<br> online coordination and vehicle communication, as well as nonholonomic robots equipped with<br> path-following controllers are developed. Numerical and experimental studies are conducted to<br> validate the robustness and efficiency of the presented algorithms in the presence of measurement<br> inaccuracies and transmission losses.<br>