什麼是規劃問題的接地困境？

在人工智慧領域，規劃問題（Planning）是指找出達成目標所需的動作序列。傳統上，這些問題使用一階邏輯表示（First-Order Representations），也就是所謂的「 lifted」表示法。這種表示法非常緊湊，例如「在所有房間移動」可以用一個規則描述，無需為每個房間撰寫獨立規則。

然而，這種表示法面臨一個關鍵困境：完全接地（Grounding）與不完全接地各有缺點。完全接地可以簡化推理，但可能導致問題規模呈指數級膨脹；而不接地雖然保持緊湊，卻增加了求解難度。這項研究提出了創新的「部分接地」方法，在兩者之間找到平衡點。

完全接地：看似簡單但代價高昂

大多數傳統規劃器採用完全接地（Full Grounding）策略，將一階邏輯變數全部替換為具體常數。舉例來說，若有 10 個房間和 5 個物體，原本可能只需要 2-3 行的規則，經過完全接地後可能膨脹為數百甚至數千條命題。

這種指數級膨脹稱為「規模爆炸」（Blowup），會導致求解器效能急遽下降。特別是當問題涉及大量物件或複雜關係時，完全接地後的問題可能變得無法處理。

完全 Lifted：保持精簡但求解困難

為了解決規模爆炸問題，近年研究傾向直接在 lifted（一階）層面操作，避免完全接地。這種方法的優勢在於保持表示的緊湊性與通用性，同時減少記憶體佔用。

但完全 lifted 方法也有其挑戰：命題可滿足性（SAT）求解器需要處理更複雜的變數約束，求解時間可能大幅增加。簡單來說，這像是用更精簡的地圖找路，但地圖涵蓋的細節變少，導致路徑規劃更費時。

部分接地：三種創新 SAT 編碼策略

本研究提出了革命性的部分接地（Partially Grounded）方法，結合上述兩種途徑的優點。研究團隊開發了三種創新的 SAT 編碼技術：

  • 編碼一：變數分組策略 - 根據變數依賴關係進行分組，選擇性接地高度互動的變數，保留獨立變數的一階表示
  • 編碼二：層次化編碼 - 將問題分為多層次，每層採用不同程度的接地，類似樓層建築的概念
  • 編碼三：混合編碼 - 根據問題結構動態選擇最佳接地策略，如同智能導航系統

實驗結果顯示，這些編碼在多個標準規劃基準測試中，能有效減少問題規模的同時保持可接受的求解效率。

實際應用與未來展望

部分接地編碼技術對多個領域具有重要價值：

  • 機器人規劃：在多機器人協作場景中，可以對共享環境部分接地，對個別機器人狀態保持 lifted 表示
  • 物流優化：處理大量包裹與倉庫節點時，避免完全接地導致的規模爆炸
  • 自動駕駛：在複雜交通場景中，平衡決策速度與規劃品質

這項研究為 SAT-based 規劃開闢了新方向，未來可能結合計算硬化（Computing Hardening）與神經網絡技術，進一步提升大規模規劃問題的求解效率。