The Computation of Approximate Generalized Feedback Nash Equilibria
The Computation of Approximate Generalized Feedback Nash Equilibria
复制标题
DOI：
10.1137/21m142530x
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
F. Laine;David Fridovich-Keil;Chih-Yuan Chiu;C. Tomlin
中科院分区：
文献类型：
--
作者：
F. Laine;David Fridovich-Keil;Chih-Yuan Chiu;C. Tomlin
我们在动态博弈中提出了广义反馈纳什均衡（GFNE）的概念，将反馈纳什均衡概念扩展到参与者受到状态和输入约束的博弈中。我们在轨迹层面形式化了（局部）GFNE解的充分必要条件，这使得能够开发有效的数值方法来计算它们。具体而言，我们提出了一种牛顿式方法来寻找满足均衡必要条件的博弈轨迹，然后可以根据充分条件进行检验。我们表明，对必要条件的评估通常需要计算一系列嵌套的、隐式定义的导数，这很快就变得难以处理。为此，我们引入了一种对必要条件的近似，它便于有效评估，进而便于解的计算。我们将近似必要条件的解称为广义反馈拟纳什均衡（GFQNE），并介绍了计算它们的数值方法。特别是，我们开发了一种顺序线性二次博弈方法，在每次迭代中求解博弈的线性二次（LQ）局部近似。这种方法的发展依赖于计算不等式和等式约束的LQ博弈的GFNE的能力，因此详细开发了这些特殊情况的具体解法。我们在自动驾驶应用中产生的一个动态博弈上证明了所提出的求解方法的有效性。
We present the concept of a Generalized Feedback Nash Equilibrium (GFNE) in dynamic games, extending the Feedback Nash Equilibrium concept to games in which players are subject to state and input constraints. We formalize necessary and sufficient conditions for (local) GFNE solutions at the trajectory level, which enable the development of efficient numerical methods for their computation. Specifically, we propose a Newton-style method for finding game trajectories which satisfy necessary conditions for an equilibrium, which can then be checked against sufficiency conditions. We show that the evaluation of the necessary conditions in general requires computing a series of nested, implicitly-defined derivatives, which quickly becomes intractable. To this end, we introduce an approximation to the necessary conditions which is amenable to efficient evaluation, and in turn, computation of solutions. We term the solutions to the approximate necessary conditions Generalized Feedback Quasi-Nash Equilibria (GFQNE), and we introduce numerical methods for their computation. In particular, we develop a Sequential Linear-Quadratic Game approach, in which a LQ local approximation of the game is solved at each iteration. The development of this method relies on the ability to compute a GFNE to inequality- and equality-constrained LQ games, and therefore specific methods for the solution of these special cases are developed in detail. We demonstrate the effectiveness of the proposed solution approach on a dynamic game arising in an autonomous driving application.