@phdthesis{,
    author = {Britzelmeier, Andreas},
    title = {Decomposition and Hamilton-Jacobi-Bellman Methods for Nonconvex Generalized Nash Equilibrium Problems},
    editor = {},
    booktitle = {},
    series = {},
    journal = {},
    address = {},
    publisher = {},
    edition = {},
    year = {2021},
    isbn = {},
    volume = {},
    number =  {},
    pages = {},
    url = {},
    doi = {},
    keywords = {Generalized Nash Equilibrium Problems, Potential Games, Gauss-Seidel Method, Decomposition Methods, Hamilton-Jacobi-Bellman, Convergence Theory, Autonomous Driving, GPU. GPU Computation, Dynamic Programming, Parallel Computation, Penalty Methods, Nonconvex Optimization, Optimal Control,  Mutli-Agent Coordination},
    abstract = {The subject of this dissertation is concerned with the theoretical investigation and the development of numerical methods for generalized Nash equilibrium problems subject to individual differential equations, state and control constraints as well as shared nonconvex constraints, complemented by an experimental validation of the methodological concepts. To cope with the nonconvex shared constraints a partial penalty reformulation  is proposed. A decomposition method with penalty selection,  capable of solving the ensuing semi-discrete (constrained) Nash equilibrium problem is devised, which prevents the a priori imposition of hierarchies. Leveraging the underlying potential game's inherent structure, convergence of a sequence of solutions of the semi-discretized Nash equilibrium problem to a solution of the generalized Nash equilibrium problem is proven. 

%We establish criteria and investigate properties which ensure the convergence of a solution of an approximated standard Nash equilibrium problem to a solution of the original problem.

Then, a Hamilton-Jacobi-Bellman approach for solving standard Nash equilibrium problems, which constitute the subproblems of the decomposition method is pursued.  Accordingly,  a backward Semi-Lagrangian method for the numerical solution of the Hamilton-Jacobi-Bellman equation is devised. In conjunction with a suitable state space discretization, an approximate value function, for Nash equilibrium problems, satisfying the principle of dynamic programming is constructed. We then introduce an iterative algorithm for the recursive computation of optimal controls. Convergence to a global minimizer in finite time is shown based on an error estimate for the approximated value function.  Furthermore, we investigate the convergence properties of higher-order Semi-Lagrange schemes in the context of time and control discrete value functions, as well as the influence of the order of approximation of the control on the resulting convergence rate. Eventually, exploiting the recursive problem structure of dynamic programming and a batching strategy, a GPU parallel dynamic programming algorithm is developed. Scalability and efficiency of the algorithm is demonstrated in a benchmark with CPU implementations. Eventually, the numerical and experimental validation of the theoretical and algorithmic framework is conducted with respect to two tangible exemplary applications. The algorithmic framework is embedded in a model predictive control structure. To validate the feasibility of online path planning using the GPU parallel dynamic programming algorithm,  a higher dimensional truck path planning problem is considered.  In addition, an autonomous vehicle coordination problem modelled as a generalized Nash equilibrium problem with non-convex shared collision avoidance constraints is investigated. Numerical results instigate the capability of the algorithmic conceptualization to efficiently provide collision-free coordination by means of Nash equilibria. Based on the theoretical results, convergence properties are established. For the experimental evaluation, a test bench comprising a positioning system, a cloud for the online coordination and vehicle communication, as well as nonholonomic robots equipped with path-following controllers are developed. Numerical and experimental studies are conducted to validate the robustness and efficiency of the presented algorithms in the presence of measurement inaccuracies and transmission losses.},
    note = {},
    
    school = {Universität der Bundeswehr München},
    
}