在上一篇文章中，我們介紹了 Strip 表示法，並了解 AI 如何從 Initial State 出發，透過一系列 Action 找到 Goal。

然而，Classical Planning 有一個很大的限制：它只適用於規模較小、理想化的問題。

隨著 State Space 不斷增加，即使使用 Forward Search 或 Backward Search，搜尋成本也會快速成長。

因此，在真實世界中，我們通常不會直接套用 Classical Planning，而是透過更有效率的方法來縮小搜尋空間。

本文將介紹兩個重要的方向：

• Heuristic Planning：利用估計值，引導搜尋朝更有希望的方向前進。
• Hierarchical Planning（HTN）：將大型任務拆解成較小的子任務，降低規劃難度。

為什麼 Classical Planning 不夠？

回到上一篇介紹的 Air Cargo 問題。

如果只有一架飛機、一件貨物、兩個機場， Planning 很容易。

但如果今天變成 50 架飛機、200 件貨物、10 個機場

世界可能出現數以百億甚至更多的狀態。

Planning 演算法仍然可以找到答案，但它可能需要探索大量 State 才能找到最佳解。

因此，我們希望 AI 能夠回答一個問題就好：

哪些 State 比較有希望接近 Goal？

這就是 Heuristic Planning 想解決的問題。

Heuristic Planning

Heuristic 中文直譯為「啟發」，可以理解為利用一個估計值，判斷目前距離 Goal 還有多遠。

通常用函數 $H(s)$ 表示 State(s) 到 Goal 的估計成本。

如果兩個 State 分別得到：

那搜尋演算法通常會優先探索 State A（到目標的估計成本比較低）。

因此，好的 Heuristic 可以大幅減少搜尋空間。

什麼是 Admissible Heuristic？

並不是任何估計都適合作為 Heuristic。

一個好的 Heuristic 必須滿足 Admissible。

也就是永遠不能高估（Overestimate）真正的成本。

假設真正到 Goal 還需要 8 步。

好的 Heuristic 可以估計5、6、8步，

但是不能估計成 10、12步。

因為過度樂觀（或悲觀）的估計，可能導致搜尋錯過真正的最佳解。

因此，許多最佳化搜尋演算法（例如 A*）都要求 Heuristic 必須是 Admissible。

如何設計一個好的 Heuristic？

設計 Heuristic 最常見的方法，是建立一個 Relaxed Problem。

他的邏輯是：如果把原本的問題變得比較容易，那麼它的最佳解一定不會比原問題更困難。

因此，Relaxed Problem 的最佳成本，可以作為原問題的一個合理估計。

接下來，介紹兩個方法來 relax：

方法一：忽略 Preconditions

第一種方式，是移除 Action 的 Preconditions。

也就是說：

每個 Action 都可以直接執行。

以經典的 8-Puzzle 為例。

正常情況下，數字只能和相鄰的空白格交換位置。

如果忽略這個限制，任何方塊都可以直接瞬移到目標位置。

此時，一個常見的 Heuristic 就是：

有多少方塊沒有放在正確的位置。

由於真實問題一定比放鬆後更困難（因為我們把限制拿掉了），因此它是一個有效的下界。

方法二：忽略 Delete List

另一種 Relaxation，是假設已經完成的事情永遠不會被取消。

也就是忽略 STRIPS 中的 Delete List。

例如：如果一塊拼圖已經放到正確的位置，它就永遠保持正確。

在 Air Cargo 中，也可以理解成：

一旦 Cargo 已經到達目標，就不可能再次離開。

這種假設雖然不符合真實世界，但能讓搜尋變得容易許多，因此常被用來建立 Heuristic。

State Abstraction

除了修改 Action，也可以簡化整個 State Space。

例如：

原本的 Air Cargo 問題可能包含10 個機場、50 架飛機、100個機場，

如果只保留5 個主要機場、5 架代表性飛機、5 件代表性貨物

State Space 就會大幅下降。

透過在抽象世界中先找到解，再回到原本世界細化規劃，也是一種常見的方法。

Hierarchical Planning

除了搜尋太慢之外，另一個問題是任務本身可能就太大。

例如我們想要規劃一次出國旅行。

如果直接規劃每一個動作：打開瀏覽器、搜尋航空公司、點選日期、輸入信用卡……

整個搜尋空間會非常龐大。

人類通常不會這樣思考。

我們會用 top-down approach 先規劃大致要做的事情，然後再逐步細化每個步驟。

Hierarchical Planning 正是利用這個概念。

Hierarchical Task Networks（HTN）

HTN 將複雜任務表示成多層結構。

最高層通常是一個抽象任務（High-Level Action）。

例如：

安排旅行

├── 訂交通
├── 訂住宿
└── 安排行程

安排旅行

├── 訂交通
├── 訂住宿
└── 安排行程

每個 High-Level Action 都可以繼續細分。

例如：

訂交通

├── 比較機票
├── 選擇航班
└── 完成付款

訂交通

├── 比較機票
├── 選擇航班
└── 完成付款

最後，一直細分到只剩下 Primitive Action。

也就是 AI 真正可以執行的 Action。

這種由抽象逐步細化的過程，就稱為 Refinement。

而只包含 Primitive Action 的版本，則稱為 Implementation。

Deferred Planning

HTN 還有一個重要特色：Deferred Planning。

AI 不需要一開始就規劃所有細節。

它可以先決定：

我要先訂交通。

至於：

• 搭哪一家航空公司？
• 哪個時間？

可以等真正需要時再繼續 Refinement。

這樣可以避免過早規劃大量可能根本用不到的細節。

Reachable Set

既然 High-Level Action 還沒有真正展開，

AI 要如何知道這條 Abstract Plan 最後有沒有可能成功？

因此，引入 Reachable Set。

$REACH(s,h)$ 表示

從 State (s) 執行某個 High-Level Action (h) 後，所有可能到達（到達得了）的狀態集合。

然而，精確計算 Reachable Set 通常十分困難。

因此實務上會使用兩種近似。

Optimistic Approximation

Optimistic Reachable Set（REACH⁺）會盡可能保留所有可能。

如果REACH⁺ 和 Goal 沒有交集，

代表無論如何都不可能成功。

如果有交集，就代表仍然有希望達到 Goal。

Pessimistic Approximation

Pessimistic Reachable Set（REACH⁻）則相反。

它只保留一定能到達的 State。

因此如果 REACH⁻ 和 Goal 有交集，

代表一定可以完成。

如果沒有交集，

則仍可能成功，也可能失敗。

這時候就需要進一步展開 High-Level Action 才能判斷。

小結

上一篇介紹了 Classical Planning 如何找到一條可行的 Plan。

而這一篇則回答另一個更實際的問題：如果 Planning 問題太大，AI 該怎麼辦？

兩種常見的方法分別是：

• Heuristic Planning：利用 Heuristic 引導搜尋，降低搜尋成本。
• Hierarchical Planning（HTN）：利用階層式任務分解，降低問題複雜度。

這兩種方法都沒有改變 Planning 的本質，而是在保留 Planning 思想的同時，讓 AI 能夠處理更接近真實世界的大型問題。