Real-Time Solution-Seeking for Game-Theoretic Autonomous Driving via Time-Distributed Iterations
維吉尼亞理工團隊利用時間分佈迭代演算法，在 5 輛車的自駕模擬中僅用 3 次迭代便解決了賽局預測控制的運算延遲難題。
- 時間分佈迭代法捨棄追求單次絕對精確解，改以極少數迭代次數維持自駕系統的高頻率即時更新。
- 位能賽局框架能將多車互動的複雜成本，完美轉換為確保收斂性的單一全局最佳化函數。
- 牛頓-坎托羅維奇方法透過在單次採樣中鎖定雅可比矩陣，大幅削減了預測控制演算法的運算耗時。
傳統自動駕駛賽局模型預測控制常因頻繁計算奈許均衡，導致系統運算嚴重過載。維吉尼亞理工團隊提出的時間分佈迭代解法，在 5 輛車的無號誌路口模擬中，證明僅需 3 次極限迭代即可大幅降低運算延遲，讓龐大運算量的多車賽局演算法具備即時落地的潛力。
自動駕駛賽局模型預測控制（GT-MPC）的運算瓶頸
自駕車在實際道路上行駛時，其駕駛表現不僅取決於自身的決策，也與周圍其他車輛的行為高度耦合。為了建立這類多代理人的互動模型，研究人員廣泛採用了賽局理論方法。在預測控制系統中，每一個車輛的控制序列優化可以被視為一場賽局，而系統的終極目標是找到一個所有車輛都能接受的穩定策略組合。
這類穩定狀態通常被定義為奈許均衡（Nash Equilibrium，無人可單方面改變策略以獲益的穩定狀態）。然而，在滾動時域的實作架構下，車輛只能執行預測軌跡的第一步，接著就必須在下一個極短的採樣瞬間重新解算這道複雜的互動問題。針對單一代理人的預測控制，業界已經擁有許多高效的求解器；但一旦擴展到多車賽局，幾何級數成長的計算複雜度便成為即時上路的巨大阻礙。
為了突破硬體算力的限制，將最佳化計算分配到不同時間點的策略逐漸受到重視。傳統思維會要求系統在單一時間點執行成百上千次的迭代，直到完全解出絕對精確的最佳化結果。相對地，時間分佈（time-distributed）方法主張在每個採樣瞬間只進行極少數的固定迭代，以近似解取代精確解，藉此確保系統能維持高頻率的即時更新。
導入位能賽局與最佳回應動態尋找奈許均衡
在一般的數學架構中，純策略的奈許均衡並不保證存在，除非該賽局具備特定的物理或數學結構。研究團隊為此導入了位能賽局（Potential Game，具備全局位能函數的特殊賽局）的框架。當車輛的累積成本可以完美拆分為「自身駕駛目標」以及「對稱的成對互動」時，這個賽局就滿足了位能賽局的嚴格條件。
建立起這套框架後，前方車輛保持目標車速的意圖，以及後方車輛避免追撞的煞車懲罰，都能整合進一個全局的位能函數中。這意味著系統只需要找到該函數的極小值，就等同於找到了全體車輛的奈許均衡。這項數學特性的轉換，不僅大幅降低了演算法收斂的困難度，也從根本上確保了解的必然存在性。
若環境設定過於複雜而無法構成位能賽局，研究人員則改採最佳回應動態（Best Response Dynamics）機制來解題。在這種模式下，每輛車會觀察對手目前的預測軌跡，並計算出對自身最有利的加速或減速序列。系統會持續在所有車輛之間交替輪轉這些「最佳回應」，直到整體車流的軌跡不再發生變動，便能達成另一種形式的奈許均衡。
結合牛頓與牛頓-坎托羅維奇方法的時間分佈迭代
要在極其有限的時間內執行上述兩種均衡演算法，團隊設計了基於一階平穩條件的時間分佈迭代法。首先是學界熟知的標準牛頓法（Newton method），系統會直接利用前一個採樣瞬間的解答作為當下計算的熱啟動（warmstart）基礎，避免演算法從零開始盲目搜索。
套用牛頓法時，系統會計算目標函數的梯度與雅可比矩陣（Jacobian matrix，包含系統所有一階偏導數的矩陣），對複雜的非線性方程式進行線性化，並據此推算出最新的控制指令。雖然牛頓法具備優異的收斂速度，但其最大的硬傷在於，每次迭代都必須針對不斷變動的車輛狀態，重新展開一次龐大且耗時的雅可比矩陣運算。
為了進一步壓榨出運算效能，團隊引入了牛頓-坎托羅維奇方法（Newton-Kantorovich method）。這項進階演算法的突破點在於，它規定系統只在每個採樣瞬間的初始階段計算唯一一次雅可比矩陣，並在接下來的所有迭代輪次中強制重複沿用這組舊數據。透過捨棄頻繁更新矩陣的步驟，演算法成功以極小的精度妥協換取了巨大的速度躍升。
5輛車十字路口情境中的誤差與耗時對比
為了以量化數據驗證演算法效能，團隊建構了一個包含 5 輛無人車同時接近十字路口的模擬環境。每輛車的縱向加速度被嚴格限制在 4 m/s² 以內，系統必須即時運算出既能維持車速又不會擦撞的最佳解。結果顯示，當車輛剛進入模擬畫面或即將離開（時間步長 $t \leq 8$ 或 $t \geq 32$）時，由於互動微弱，兩種分佈演算法的誤差幾乎為零。
當車流同時擠入十字路口中央（時間步長 $t \in [8, 32]$），車輛必須頻繁互讓時，近似誤差的波動便開始加劇。實驗證明，只要將迭代次數 K 從 2 次微調至 5 次，各項誤差指標就會大幅收斂。其中，採用固定雅可比矩陣的牛頓-坎托羅維奇方法，雖然平均誤差略高於標準牛頓法，但其單次計算耗時卻穩居所有方案之冠。
進一步解剖最佳回應動態演算法的表現，研究發現其近似誤差整體而言遠低於位能賽局。背後的原因在於最佳回應動態將龐雜的問題拆分為單車各自的最佳化，單一問題規模較小，因此不需要太高的迭代次數就能逼近 MATLAB 內建的精確解。然而，由於系統必須反覆在不同車輛間切換計算，其總體運算時間仍然高於位能賽局函數，凸顯了演算法在精度與運算架構間的微妙取捨。
透過熱啟動機制與固定雅可比矩陣的巧思，自動駕駛預測系統能在不危及安全餘裕的前提下，將多車賽局的龐大求解延遲壓縮至實用的毫秒級門檻內。