A decomposition algorithm for Nash equilibria in intersection management. (2nd November 2021)

• Record Type: Journal Article
• Authors: Britzelmeier, Andreas; Dreves, Axel
• Is Part Of: Optimization. Volume 70:Number 11(2021)
• Page Start: 2441
• Page End: 2478
• Publication Date: 2021-11-02
• Subjects: Generalized Nash equilibrium problems -- generalized potential games -- optimal control -- nonconvex state constraints -- partial penalization; 49J15 -- 49J21 -- 49M27 -- 49N90 -- 90C33; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1786088
• Languages: English
• ISSNs: 0233-1934

Abstract

ABSTRACT: In this paper, we present a game-theoretic model, a new algorithmic framework with convergence theory, and numerical examples for the solution of intersection management problems. In our model, we consider autonomous vehicles that can communicate with each other in order to find individual optimal driving strategies through an intersection, without colliding with other vehicles. This results in coupled optimal control problems and we consider a generalized Nash equilibrium reformulation of the problem. Herein, we have individual differential equations, state and control constraints and additionally nonconvex shared constraints. To handle the nonconvexity we consider a partial penalty approach. To solve the resulting standard Nash equilibrium problem, we propose a decomposition method, where the selection of the players is controlled through penalty terms. The proposed method allows the prevention of a priori introduced hierarchies. Using dynamic programming, we prove convergence of our algorithm. Finally, we present numerical studies that show the effectiveness of the approach.