A decomposition algorithm for Nash equilibria in intersection management

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.

Keywords:

• Generalized Nash equilibrium problems
• generalized potential games
• optimal control
• nonconvex state constraints
• partial penalization

2010 Mathematics Subject Classifications:

• 49J15
• 49J21
• 49M27
• 49N90
• 90C33

Disclosure statement

No potential conflict of interest was reported by the authors.