技術要約: CUDAMPC

問題提起

モデル予測制御（MPC）は、状態および入力の制約を課しながら多変数性能を最適化するための強力な手法である。しかし、そのオンライン最適化への依存は、特に高速サンプリング、高次元、または高度に非線形なロボットシステムにおいて、重大な計算負荷を生じさせる。従来のCPUベースのソルバー（acados、CasADiなど）は、タイトなサンプリング間隔内で正確な制御入力を計算することが困難な場合が多く、その結果、ホライゾン長、モデルの忠実度、あるいは最適化精度において妥協を強いられる。

GPUは数千の並列コアを提供するが、既存のGPUベースのMPC実装は、デバイスを単なる線形代数のアクセラレータとして扱うのが一般的である。テンソルフレームワーク（PyTorch、JAXなど）を用いたアプローチでは、反復的な最適化をフレームワークレベルの操作のシーケンスとして表現する。これは、カーネル起動の繰り返しと高レイテンシのグローバルメモリ転送を引き起こし、高周波動作時において実行時間を支配し、GPUの並列的な利点を損なわせる。さらに、既存の多くのGPU手法は特定の数値カーネル（例：ニュートン系の解法）のみを並列化するか、あるいは実現可能性の証明（feasibility certificates）を欠き、高次元の制約への対処が困難なサンプリングベースの手法（例：MPPI）に依存している。

手法

本論文では、アルゴリズム、実行、およびメモリの各レベルで共同設計された、GPUネイティブなMPCフレームワークであるCUDAMPCを提案する。コアとなる手法は、密結合された以下の3つの設計レイヤーで構成される。

1. アルゴリズムレベル（並列ホライゾンADMM）:
   本フレームワークは、並列ホライゾン型（parallel-in-horizon）の交互方向乗数法（ADMM）の分割を利用する。非線形MPC問題は、まず逐次凸計画法（SCP）を通じて動力学と制約を線形化することで対処される。得られた凸部分問題は、ADMMのコンセンサス変数を用いて分割される。この定式化により、予測ホライゾンにわたる最適化がデカップルされ、最近接のコンセンサスのみによって結合される独立したステージごとの更新が可能となる。

2. 実行レベル（融合CUDAカーネル）:
   各ADMM操作に対して個別のカーネルを起動するテンソルフレームワークの実装とは異なり、CUDAMPCは、融合された単一のカスタムCUDAカーネル内に、反復的な解法全体を統合する。

   • ホスト介入の排除: 完全な内部ADMMループは、反復の間に制御をホストに戻すことなく、GPU上でネイティブに実行される。
   • 近傍局所同期: スレッドブロックの数に応じてスケールする高コストなグリッドワイド・バリア（grid.sync()）を使用する代わりに、CUDAMPCは局所的なアトミックフラグ・プロトコルを採用する。ブロックは、自身の即時的な空間的隣接関係（境界変数の前方および後方伝播）に対してのみ同期を行う。これにより、調整コストを全ホライゾンブロックの総数に依存しないレベルまで削減し、収束が証明されている有界な遅延（部分非同期ADMM）を導入する。

3. メモリレベル（ブロック常駐ストレージ）:
   FlashAttentionのI/Oを意識した原則に従い、本フレームワークはグローバルメモリとオンチップメモリ間の転送を最小限に抑える。

   • 共有メモリ常駐: 最適化変数（原始変数、双対変数、およびコンセンサス変数）と中間計算は、カーネルの開始時に低レイテンシのオンチップ共有メモリにロードされ、解法を通じて常駐し続ける。
   • リソース割り当て: ホライゾンは、CUDAスレッドブロックに割り当てられるサブホライゾンへと分割される。サブホライゾンの長さは、デバイスのスレッドおよび共有メモリの制限に基づいて動的に計算され、ワーキングセット全体がオンチップに収まることを保証する。グローバルメモリは、初期ロード、最終出力、および境界変数の交換にのみ使用される。

主な貢献

本論文は、主に以下の3つの貢献を主張している：

1. CUDAMPCフレームワーク: 単一の共有メモリ常駐型CUDAカーネル内で並列ホライゾンADMMを実行する、GPUネイティブなアーキテクチャ。
2. 近傍局所同期プロトコル: グリッドワイド・バリアをペアワイズのアトミックフラグに置き換えるメカニズムであり、調整コストがホライゾンブロックの数に依存しないことを保証する。
3. ベンチマーク研究: 6つの非線形ロボティクス問題に対する最先端のCPUおよびGPUソルバーとの包括的な評価を行い、増加したリアルタイム実行可能なホライゾンが、CPUベースラインが実行可能などのホライゾンでも達成できなかった閉ループ能力（例：衝突回避、群制御）を可能にすることを実証した。

結果

本論文では、Pendulum、Cart-Pole、Car Parking、Truck-Trailer、Quadcopter-Pole、およびCentralized Swarmの6つのベンチマークにおいて、CUDAMPCをCPUソルバー（CasADi + Ipopt、acados + HPIPM）および他のGPU手法（Primal-Dual iLQR、GPU-SLS、および$\pi$MPCのテンソルフレームワーク実装）と比較評価した。

• テンソルフレームワークに対する性能: 線形化された航空機モデルを用いた$\pi$MPCのPyTorchおよびJulia実装に対し、CUDAMPCは136倍から965倍の範囲の高速化を達成した。これは、カーネル起動数を約172,000回から1回へ削減し、VRAMトラフィックを約17 GBから約31 MBへと削減したことに起因する。
• スケーラビリティ: 非線形ベンチマークにおいて、CUDAMPCのホライゾン長（$N$）に対する解法時間のスケーリングは、CPU手法よりも大幅に優れていた。例えば、Pendulum問題において$N=1000$の場合、CUDAMPCは次に高速なソルバーよりも20.1倍高速であった。
• リアルタイム実行可能性: CUDAMPCは、CPUソルバーよりも1〜2桁長いホライゾンにおいてリアルタイムレートを維持した。
  • Car Parking: 0.1秒のサンプリング間隔内で、100秒の先読みを含む最適化ベースの衝突回避問題を解決した。
  • Centralized Swarm (10エージェント): CUDAMPCは、評価されたソルバーの中で、リアルタイム実行（~28 ms）と衝突のない協調行動の両方を達成できた唯一のソルバーであった。CPUソルバー（acados、CasADi）は、サンプリング間隔内に実行可能な解を見つけることができず（それぞれ3.5秒および4.5秒を要した）、GPUベースのPrimal-Dual iLQRは、リアルタイムではあるものの、ハードな衝突回避のためのソフトペナルティ制約のチューニングが困難であるため、デッドロック状態の局所解に陥った。

意義

本論文は、CUDAMPCが、GPUを単なる線形代数のアクセラレータとして利用する段階から、最適化アルゴリズムとハードウェアアーキテクチャの包括的な共同設計へと移行するものであると位置づけている。ホストの介入とグローバルメモリのトラフィックを最小限に抑えることで、本フレームワークは、長期間のホライゾンかつ制約の多いMPC問題をリアルタイムで実行する能力を解放する。その意義は、単なる生の速度だけでなく、これまで計算量的に不可能であった戦略（中央集権的なマルチエージェント協調や長ホライゾン衝突回避など）を、高度なロボットプラットフォームの運用範囲を拡大させながら実現できる点にある。