在修 NUS 的 CS5446: AI Planning & Decision Making 時，我第一次系統性地接觸到 AI Planning。雖然現在大家談到 AI，大多會想到大型語言模型（LLM）或 Reinforcement Learning，但在這些技術成熟之前，Planning 一直都是人工智慧的重要研究領域。
這個系列會整理我在課程中的學習內容，並加入自己的理解與例子，希望能用比較容易理解的方式介紹 AI Planning 的核心概念。
今天就從最基本的問題開始。
AI 到底是如何「規劃」一件事情的？
一個簡單的例子：Air Cargo
假設有一架飛機停在新加坡（SIN），有一件貨物也在新加坡，而我們希望最後把它送到東京（NRT）。
飛機不能直接把貨物瞬間移動，它只能執行幾個固定的動作：
- Fly：飛往另一個機場
- Load：把貨物裝上飛機
- Unload：把貨物卸下飛機
那麼，AI 要如何知道正確的執行順序？
例如：
Load Cargo
↓
Fly to Tokyo
↓
Unload Cargo
對人類而言，這幾乎是不需要思考的事情。
但對 AI 而言，它不知道什麼叫「送貨」，也不知道飛機可以飛去哪裡。它只知道目前世界的狀態，以及每個動作會帶來什麼改變。
Planning 的目的，就是讓 AI 自己找出這串動作。
Classical Planning 的假設
如果真實世界充滿隨機因素，規劃會變得非常困難。
因此 Classical Planning 做了一些理想化的假設。
Discrete
世界中的狀態是有限且可以列舉的。
例如：
- 飛機在 SIN
- 飛機在 NRT
而不是「飛機飛到一半」。
Deterministic
每個動作都有唯一結果。
如果飛機執行 Fly(SIN, NRT)，它一定會到 NRT，不會因為天氣突然降落到其他地方。
Static
在 AI 思考規劃的過程中，世界不會自己改變。
貨物不會突然消失，也不會有人偷偷把飛機開走。
Fully Observable
AI 能夠完全知道目前世界的狀態。
它知道飛機在哪裡、貨物在哪裡，也知道哪些動作可以執行。
AI 如何描述世界？
既然 AI 不理解「飛機」或「貨物」這些概念，它需要一種形式化的方法來表示世界。
最基本的單位稱為 Fluent。
例如：
At(Plane, SIN)
At(Cargo, SIN)
In(Cargo, Plane)每一個 Fluent 都是在描述世界中的一個事實。
所有 Fluent 合起來，就是目前的 State（狀態）。
例如：
State
✓ Plane 在 SIN
✓ Cargo 在 SIN
✓ Cargo 在飛機上
可以把 State 想成一張世界快照，記錄當下目前所有重要資訊。
Goal 並不是另一個 State
很多人可能會有一個誤解：
Goal 就是一個新的 State。
其實不是。
Goal 通常只描述 我們想達成的條件，而不是整個世界。
例如：
Goal
At(Cargo, NRT)
我們並不在意：
- 飛機最後停在哪裡
- 飛行了多少次
- 是否還有其他貨物
只要貨物到達目的地即可。
因此：
- State：完整描述世界
- Goal：只描述需要滿足的條件
動作（Action）如何改變世界？
每個 Action 都包含兩個部分：
- Preconditions（前置條件）
- Effects（執行後的效果）
例如 Load：
Action：Load
Preconditions
Plane 在 SIN
Cargo 在 SIN
Effects
Cargo 在 Plane
Cargo 不再位於 SIN
只有當 Preconditions 都成立時，AI 才能執行這個動作。
執行完成後，世界狀態便會更新。
例如：
Before
Plane 在 SIN
Cargo 在 SIN
↓
Load
↓
After
Plane 在 SIN
Cargo 在 Plane
Planning 就是不斷重複這個過程。
AI 如何找到答案？
當世界被表示成一系列 State 與 Action 後，問題就變成：
如何找到一條從 Initial State 到 Goal 的路徑？
最直覺的方法就是 Forward Search。
它從 Initial State 開始，不斷嘗試可以執行的 Action，直到滿足 Goal。
另一種方法則是 Backward Search。
它從 Goal 倒推，思考：
哪個 Action 可以讓 Goal 成立？
接著再繼續往回推，直到回到 Initial State。
除此之外，也可以把整個 Planning 問題轉換成命題邏輯，再利用 SAT Solver 找出是否存在可行解。不同的方法各有優缺點，後面的文章會再詳細介紹。
小結
Classical Planning 的核心思想其實很簡單：
- 描述目前世界（State）
- 定義每個動作（Action）
- 指定想達成的目標（Goal）
- 搜尋一條可行的動作序列（Plan）
乍看之下，這只是送貨問題，但相同的概念也能應用在機器人導航、物流配送、自動排程，甚至遊戲 AI。
在下一篇文章，我會介紹 AI Planning 中最常見的知識表示方式 STRIPS，看看 AI 是如何用 Preconditions、Add List 與 Delete List 來描述每一個 Action。
