在上一篇文章中，我們介紹了 Classical AI Planning 的核心概念
不過，還有一個更根本的問題沒有回答：
AI 是如何知道世界長什麼樣子的？
人類看到「飛機停在桃園」、「貨物已經裝上飛機」這些敘述，很自然就能理解它們代表什麼。但對 AI 而言，世界並不是由圖片或文字組成，而是一組可以推理的符號。
因此，在開始搜尋之前，我們需要先建立一套表示世界的方法。
在 Classical Planning 中，最經典的方法就是 STRIPS（Stanford Research Institute Problem Solver）。
這篇文章將介紹 STRIPS 如何描述世界，以及 AI 如何透過這套表示方式進行規劃。
為什麼需要知識表示（Knowledge Representation）？
延續使用上一篇的 Air Cargo 問題。
有一架飛機停在新加坡，貨物也在新加坡，我們希望最後把貨物送到東京。
如果直接用自然語言描述飛機在新加坡，我們人類可以理解。
但是 AI 無法判斷哪些資訊重要？哪些 Action 可以執行？執行之後世界會如何改變？
因此，我們需要把世界轉換成一組標準化的表示方式。
Fluent：描述世界中的事實
上一篇文章中，我們有提到在 STRIPS 中，最基本的單位稱為 Fluent。
Fluent 可以理解成一個會隨著時間改變真假的事實（Fact）。
例如：
At(Plane1, SIN)
At(Cargo1, SIN)
In(Cargo1, Plane1)
每一個 Fluent 都代表世界中的一個事實。
例如：
At(Plane1, SIN)
表示：
Plane1 位於新加坡。
如果飛機飛到東京，
這個 Fluent 就會變成 False，而：
At(Plane1, NRT)
則變成 True。
因此，我們稱它為 Fluent，因為它的真值會隨著世界狀態改變。
State：世界的快照
有了 Fluent 之後，就可以描述整個世界。
State 是目前所有成立（True）的 Fluent 所組成的集合。
例如：
State S₀
At(Plane1, SIN)
At(Cargo1, SIN)
這代表：
- 飛機位於新加坡
- 貨物位於新加坡
- 貨物還沒有裝上飛機（因為沒有寫到 ）
可以把 State 想像成某一個時間點的「快照（Snapshot）」。
當 Action 執行後，快照就會更新。
Goal：我們真正關心的
Goal 只描述一件事：哪些條件必須成立。
例如：
Goal
At(Cargo1, NRT)
這表示我們只希望 Cargo 最後出現在東京。
至於：飛機最後停在哪裡？是否還有其他貨物？飛了幾次？
這些都不是 Goal 的一部分。
因此：
- State 描述整個世界。
- Goal 只描述需要滿足的部分條件。
這也是 Planning 中一個重要的概念！
Action：世界如何改變？
Action 會改變 State。
每個 Action 都包含兩個部分：
- Preconditions（前置條件）
- Effects（效果）
例如：
Load(Cargo, Plane)
Preconditions：
At(Cargo, Airport)
At(Plane, Airport)
代表只有當飛機與貨物都位於同一座機場時，才能執行 Load。
Effects：Action 執行後會發生什麼？
Effects 描述的是Action 執行後，哪些 Fluent 會改變。
STRIPS 將 Effects 再細分成兩部分。
Add List
Add List 表示執行 Action 後，需要新增哪些 Fluent。
例如：
Load
Add List
In(Cargo, Plane)
代表貨物現在已經在飛機裡。
Delete List
Delete List 表示執行 Action 後，需要移除哪些 Fluent。
例如：
Load
Delete List
At(Cargo, Airport)
既然貨物已經裝上飛機，它就不應該仍然位於機場。
因此執行同一個 Action，
世界會同時：
- 新增一些事實（Add List）
- 移除一些事實（Delete List）
State 是如何更新的？
有了 Add List 與 Delete List後，State 更新就變得非常簡單。
執行某個 Action 後：
- 移除 Delete List 中的 Fluent。
- 加入 Add List 中的 Fluent。
可以寫成：
其中：
- ：原本 State
- ：Delete List
- ：Add List
例如原本
At(Cargo, SIN)
執行
Load
之後
In(Cargo, Plane)
就會被加入，而
At(Cargo, SIN)
則被移除。
新的 State 就產生了。
Closed-World Assumption
STRIPS 還有一個重要假設：沒有被列出的 Fluent，都視為 False。
例如如果 State 中只有：
At(Plane, SIN)
At(Cargo, SIN)
那就代表：
In(Cargo, Plane)
是 False。
這種做法稱為 Closed-World Assumption。
它最大的好處是我們不用窮舉列出所有不成立的事實，
只需要記錄目前成立的 Fluent 即可，大幅降低表示的複雜度。
為什麼需要 Add List 與 Delete List？
如果沒有 Add List 與 Delete List，每執行一次 Action，AI 都必須重新描述整個世界，也需要重新建立完整 State。。
透過 Add List 與 Delete List，我們只需要描述哪些事實改變了。
而沒有改變的部分，自然會保留下來。
這也是 STRIPS 能夠有效表示 Planning 問題的重要原因。
小結
上一篇介紹了 AI 如何尋找一條從 Initial State 到 Goal 的路徑。
而這一篇則介紹AI 是如何表示世界。
在 STRIPS 中：
- Fluent 用來描述世界中的事實。
- State 是目前所有成立 Fluent 的集合。
- Goal 描述需要達成的條件，而不是完整世界。
- Action 包含 Preconditions 與 Effects。
- Effects 又可分成 Add List 與 Delete List，用來更新 State。
有了這套表示方法之後，AI 才能真正開始搜尋。
下一篇文章，我們將介紹 Heuristic Planning，看看當 State Space 過於龐大時，AI 如何利用 Heuristic、Relaxed Problem 與 State Abstraction，大幅降低搜尋成本。
