技術要約：非凸部分デカップル型一般ナッシュ均衡問題のためのFALCON

問題定式化

本論文は、航空宇宙およびロボティクスにおけるマルチエージェント最適制御問題の解決という課題に取り組んでおり、これらを非凸微分ゲームとしてモデル化している。著者らは、**部分デカップル型一般ナッシュ均衡問題（PDGNEP）**と呼ばれる特定のサブクラスに焦点を当てている。

この定式化において、$N$ 個のエージェントは以下の条件に従って個別のコスト関数 $J_i$ を最小化しようとする：

1. 分離可能なダイナミクス： 各エージェント $i$ は、他のエージェントの制御や状態に依存しない独自のダイナミクス $\dot{x}_i(t) = f(x_i(t), u_i(t))$ に従って進化する。
2. 結合された制約： エージェントは、全エージェントの軌道に依存する可能性のある共有の等式および不等式制約 $C(X, \Upsilon) \leq 0$ を通じて結合されている。
3. 目的： 他者の戦略が与えられた条件下で、単独での戦略変更によってコストを改善できない戦略の集合であるオープンループ・ナッシュ均衡を見つけること。

既存の手法には限界がある：Iterative LQ Games (iLQGames) は制約のネイティブな取り扱いが欠けており、Augmented Lagrangian Games (ALGAMES) は性能は向上しているものの、強い非凸性に苦慮し、Differential Games Sequential Quadratic Programming (DG-SQP) は収束保証を提供する一方で、高度に非凸なシナリオにおいて高い計算コストと数値的不安定性に陥ることが多い。

手法：FALCON アルゴリズム

著者らは、逐次凸計画法（SCP）と拡張ラグランジュ法を組み合わせたアルゴリズムであるFALCON（Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria）を提案している。コアとなる手法は以下の通りである：

1. 連続時間制約の強制

離散化されたSCPソルバーに共通するインターサンプル（サンプリング間）の制約違反の問題に対処するため、著者らは外部ペナルティアプローチを用いて制約を再定式化している。

• 制約違反の連続時間の尺度 $\Lambda_i(t)$ を、$C^2$ 級の滑らかさを備えた立方ペナルティ関数 $q(z) = [z]_+^3$ を用いて定義する。
• 拡張された状態変数 $y_i(t)$ が、この違反を時間を通じて累積する。
• 制約は、離散化ノードだけでなく、ノード間の違反の累積を制限することで時間軸全体にわたって強制され、理論的な境界 $\delta(\varepsilon)$ 内での点ごとの制約充足を保証する。

2. 拡張ラグランジュおよびエピグラフ再定式化

非凸な目的関数と制約を扱うために：

• エピグラフ形式： 非凸なコスト関数 $J_i$ を、エピグラフ変数 $\tau_i$ を介して制約へと移行させ、$J_i \leq \tau_i$ という条件下で $\tau_i$ を最小化する。これにより、目的関数を線形化しつつ、非凸性を制約側に保持することができる。
• 拡張ラグランジュ： ダイナミクスおよび結合制約に対するラグランジュ乗数（$\lambda, \mu$）とペナルティ重み（$\omega$）を組み込んだ、拡張ラグランジュ関数 $L_i$ を構築する。

3. 逐次凸化 (SCvx*)

非凸ゲームは、一連の凸部分問題を解くことにより、反復的に近似される：

• 線形化： 参照軌道 $\bar{z}$ の周りでダイナミクスと制約を線形化する。
• 緩和： 線形化による人工的な実行不可能性を軽減するために、仮想制御（$\xi$）および仮想バッファ（$\zeta$）変数を導入する。
• 信頼領域： $\|z - \bar{z}\|_\infty \leq r$ という信頼領域制約により、近似が有効であることを保証する。
• ポテンシャルゲームへの再定式化： 得られる凸部分問題は、**変分一般ナッシュ均衡（v-GNE）として構成される。個々のペナルティ付き目的関数の和である強凸ポテンシャル関数 $\Phi_k$ を構築することで、部分問題は効率的な二次錐計画法（SOCP）**として解かれる。

4. アルゴリズムのループ

アルゴリズムは以下の手順で反復する：

1. 逐次線形化： 凸部分問題を作成する。
2. ステップの受理： 結合ポテンシャル比 $\rho_k$（実際のコスト減少量と予測された減少量の比較）を用いてステップの「質」を評価する。$\rho_k$ が閾値を超えた場合にステップが受理される。
3. 乗数の更新： 制約違反とユーザー定義の許容誤差 $\delta_k$ に基づいて、ラグランジュ乗数とペナルティ重みを更新する。
4. 信頼領域の調整： 信頼領域半径 $r$ を、受理比に基づいて動的に調整（縮小または拡大）する。

主な貢献

1. アルゴリズム開発： 逐次凸化と拡張ラグランジュ手法を組み合わせることで、非凸PDGNEPを解く新しいアルゴリズムであるFALCONを導入した。
2. 理論的保証： 緩やかな仮定（有界な加速度、リプシッツ連続性、$C^2$ 級の滑らかさ）の下で、オープンループ・ナッシュ均衡への大域的収束を証明した。解は、動的に実行可能であり、連続時間の意味で近似的に結合可能であることが保証される。
3. 連続時間安全性： 離散化ノード間での安全性を確保するため、制約を連続的に強制するための厳密な定式化を提供し、インターサンプル間での安全違反を防ぐ。
4. 効率性： 凸化された部分問題が、効率的なSOCPソルバーを用いたポテンシャルゲームとして解けることを示し、従来のDG-SQP手法の計算上のボトルネックを回避した。

数値結果

著者らは、3つの異なる非凸微分ゲームのシナリオにおいてFALCONを検証している：

1. F1 オースティン・レーシング (2プレイヤー)：

   • シナリオ： F1オースティンコースの急カーブを走行する2台の車。
   • 性能： 様々な初期条件に対してFALCONは100%の収束率を達成したが、DG-SQPの収束率は72%であった。
   • 速度： FALCONは大幅に高速であり、平均計算時間はDG-SQPの50.021秒に対し、FALCONは0.873秒であった。ALGAMESは、同一基準下でのこの困難なケースにおいて収束に失敗した。

2. 狭い通路 (3プレイヤー)：

   • シナリオ： 衝突回避および通信範囲の制約を維持しながら、2つのチョークポイントを持つ通路をナビゲートする3台のユニサイクル・エージェント。
   • 観察： アルゴリズムは非凸環境を正常に処理し、連続時間の制約を厳格に遵守しながら、創発的な協調行動（例：エージェントが通過順序を制御してチョークポイントを通過する）を示した。

3. 宇宙船 Lady-Bandit-Guard (3プレイヤー)：

   • シナリオ： $R^6$（クロシェ・ウィルシュタイン・ヒル・ダイナミクス）における、ヘテロジニアスなゲーム。高価値資産である「Lady」、攻撃者である「Bandit」、防御者である「Guard」が含まれる。
   • 観察： FALCONは複雑な追跡・回避・防御ゲームを解き、ガードがバンディットを阻止してレディの脱出を助けるシナリオを成功裏にシミュレートし、エンゲージメントの幾何学的な非凸性を処理した。

意義と主張

本論文は、FALCONが計算効率と理論的収束保証の間の溝を埋めることにより、マルチエージェント微分ゲームの解決における重要な進歩を提示していると主張している。

• 差別化： iLQGamesとは異なり、FALCONは状態および制御制約をネイティブに扱う。DG-SQPとは異なり、収束保証を犠牲にすることなく、高度に非凸な設定において優れた数値的性能と堅牢性を提供する。
• 安全性： 連続時間制約の定式化は、インターサンプルでの違反が許容されない航空宇宙分野の安全クリティカルなアプリケーションにおいて、極めて重要な機能として強調されている。
• スケーラビリティ： 内部ループをSOCPで解けるポテンシャルゲームに落とし込むことで、本手法は複雑なマルチエージェントシステムに対するスケーラブルなアプローチを提供している。

著者らは、FALCONが非凸微分ゲームを解くための堅牢で高速かつ理論的根拠に基づいたフレームワークを提供し、追跡・回避、紛争下の宇宙運用、協調ガイダンスなどの複雑な航空宇宙業務に適していると結論付けている。