[人工智慧導論](https://app.notion.com/p/3e6fc631b0308131b213f0a3d93fe91d) › [W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62) › 06｜影片 [2:16:36–2:29:37](https://www.youtube.com/watch?v=S1km7opW6rw&t=8196s)｜投影片 Ch4 p.27–35（投影片上印的頁碼是 52–63）｜上一章 [05 牛頓法與線性規劃（1:40–2:04）](https://app.notion.com/p/3e6fc631b03081f79e51ec7d5af80d42)｜下一章 [07 不確定性與機率基礎（2:29–2:53）](https://app.notion.com/p/3e6fc631b030818b8460e7499c1c5521) ## 重點 - **部分觀察（partial observation，只看得到環境的一小部分）**：agent 不知道自己在哪個狀態，只能記住目前可能在哪幾個狀態。每感測一次就刪掉跟感測結果不符的，走一步再感測，候選越來越少，直到確定位置。 - **線上搜尋（online search，邊走邊算）**：環境事先不知道，不能先算好整條路再出發，只能做一個動作、觀察、再決定下一步，輪流進行。好壞用 competitive ratio 比：實際走的成本 ÷ 事先知道地圖時的最短成本，越接近 1 越好。 - **Online 演算法要就近展開**：展開一個節點等於真的走過去，所以 DFS 和 hill climbing 這種只從目前位置往鄰居走的方法適合；BFS、A* 會在搜尋樹裡跳來跳去，用腳走就很浪費。 ## Exam-ready - **Partial observations**: "A robot is placed in the maze-like environment. It is equipped with four sonar sensors that tell whether there is an obstacle in each of the four compass directions. ... The robot's task is to determine its current location."（Ch4 p.27） - **Localization (Figure 4.18)**: "When sensors are noiseless and the transition model is accurate, there are no other possible locations for the robot consistent with this sequence of two observations."（Ch4 p.28 圖說） - **Offline search**: "They compute a complete solution before setting foot in the real world and then execute the solution."（Ch4 p.29） - **Online search agent**: "an online search agent interleaves computation and action: first it takes an action, then it observes the environment and computes the next action." "The canonical example of online search is a robot that is placed in a new building and must explore it to build a map that it can use for getting from A to B."（Ch4 p.29） - **What the agent knows**: "We stipulate (規定) that the agent knows only the following: ACTIONS(s), which returns a list of actions allowed in state s; The step-cost function c(s, a, s')—note that this cannot be used until the agent knows that s' is the outcome; and GOAL-TEST(s)." "The agent cannot determine RESULT(s,a) except by actually being in s and doing a."（Ch4 p.30） - **Heuristic**: "the agent might have access to an admissible heuristic function h(s) that estimates the distance from the current state to a goal state."（Ch4 p.32） - **Competitive ratio**: "The cost is the total path cost of the path that the agent actually travels. It is common to compare this cost with the path cost of the path the agent would follow if it knew the search space in advance. This is called the competitive ratio; we would like it to be as small as possible."（Ch4 p.33） - **Building the map**: "After each action, an online agent receives a percept telling it what state it has reached; from this info., it can augment its map of the environment."（Ch4 p.34） - **Locality**: "To avoid traveling all the way across the tree to expand the next node, an online algorithm better expands nodes in a local order. DFS has exactly this property."（Ch4 p.34） - **Online local search**: "because it keeps just one current state in memory, hill-climbing search is already an online search algorithm! Unfortunately, it is not very useful in its simplest form because it leaves the agent sitting at local maxima with nowhere to go."（Ch4 p.35） ## [2:16:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=8196s) 部分觀察：迷宮裡的機器人 八皇后這類問題，agent 看得到整個狀態。但很多問題只看得到一小部分，老師舉 hill climbing 為例：站在某一點，只看得到附近的鄰居。只看得到一部分時的搜尋，叫 searching with partial observations。投影片的例子：機器人有東西南北四個聲納感測器（永遠正確），也有正確的地圖，但導航系統壞了，下 Move 指令只會隨機走到某個相鄰格子；任務是判斷自己現在在哪一格。 注意：老師口頭拿 hill climbing 當例子，但它只看鄰居是演算法的選擇，狀態其實看得到；partial observation 指的是感測器拿不到完整狀態（我補充）。
要先懂什麼？fully observable 和 partially observable 差在哪？ 這是 Ch2 環境分類的其中一個維度。 - Fully observable（完全可觀察）：感測器每個時刻都拿得到完整狀態。例：下棋，整個棋盤都看得到。 - Partially observable（部分可觀察）：只拿得到一部分。例：打牌看不到別人的手牌；這章的機器人只知道四周有沒有牆，不知道自己在地圖上哪一格。
用生活例子講，機器人在做什麼？ 半夜停電，你在自己家醒來，什麼都看不到。你腦中有平面圖（地圖），手可以摸四周（感測器）。摸到前面、左邊、後面都是牆，只有右邊空，你就知道只可能在幾個角落；往右走一步再摸一次，通常就能確定在哪個房間。機器人做的就是這件事，只是有系統地刪掉不可能的位置。
## [2:19:02](https://www.youtube.com/watch?v=S1km7opW6rw&t=8342s) 靠感測縮小可能位置 一開始完全不知道位置，地圖上 42 個空格都有可能。第一次感測是北、南、西有障礙物（E1 = NSW），地圖上長這樣的只有 4 格。這 4 格唯一的出口都在東邊，所以隨機移動也只能往東；再感測一次得到北、南有障礙物（E2 = NS），4 個候選各往東一格後只剩 1 格符合，位置確定。老師提醒：這裡假設感測器 100% 正確，只有八成正確會難很多，之後的章節會講。 ![圖 4.18：(a) 第一次感測 NSW 後，只剩 4 個可能位置（圈起來的格子）；(b) 往東走一步、第二次感測 NS 後，只剩 1 格](file-upload://3e7fc631-b030-8132-9113-00b28592515e)
它到底怎麼運作？一步一步算一次 座標寫成（第幾列, 第幾行），從左上角數起。課本把目前所有可能位置的集合叫 belief state（信念狀態）。 1. 起點：還沒感測，42 個空格都可能。 2. 感測 E1 = NSW：逐格檢查北、南、西是牆或邊界、東邊是空的。符合的只有 (1,1)、(1,12)、(4,1)、(4,8)，其他 38 格刪掉。 3. 移動：這 4 格只有東邊能走，不管怎麼隨機都往東。候選變成 (1,2)、(1,13)、(4,2)、(4,9)。 4. 感測 E2 = NS：(1,2) 北是邊界、南是牆、東西都空，是 NS，符合。(1,13) 南邊是空格，只有 N，不符。(4,2) 北邊空、東邊是牆，是 SE，不符。(4,9) 北邊空，只有 S，不符。 5. 只剩 (1,2)，位置確定。 規律是兩步輪流：動作後先預測可能到哪些格子，感測後再刪掉不符合的。
感測器會出錯的話怎麼辦？（老師說之後會講） 不能再直接刪掉，只能給每個位置一個機率。 小例子：剩兩個候選 A、B，各 50%。A 真實的樣子是 NSW，B 是 NS。感測器 80% 回報正確、20% 報錯（假設錯的時候剛好報成另一個樣子）。現在讀到 NSW： - A：0.5 × 0.8 = 0.40 - B：0.5 × 0.2 = 0.10 - 除以總和 0.50，讓兩者加起來等於 1：A = 80%，B = 20% B 沒被刪掉，只是變得不太可能；多感測幾次，機率會越來越集中。這就是下一章（第 07 章，機率）要打的基礎。
老師原話是什麼？ 「所以這第一個時間點，我們大概就可以大幅縮減他可能所在的位置」(2:20:00) 「假設你的感測器只有八成是對的，有兩成有可能回答給你錯的答案」(2:21:10)
## [2:21:32](https://www.youtube.com/watch?v=S1km7opW6rw&t=8492s) Offline 與 online search 到目前為止的搜尋（BFS、UCS、A*…）都是 offline search（離線搜尋）：題目整個給你，先算出完整的解，才踏進真實世界照著執行。Online search（線上搜尋）則是做一個動作、觀察環境、再算下一個動作，輪流進行，因為環境事先不知道。最經典的例子是把機器人放進一棟沒來過的建築，讓它自己探索、建出地圖；老師說，這就是你家的掃地機器人。 注意：老師口頭說的是 after setting foot (2:21:49)，投影片是 before：offline 是先算完才出發。
**Offline search****Online search**
什麼時候算出發前算完整條解每走一步算一次
事先要知道整個狀態空間（地圖、每個動作的結果）不用，邊走邊學
展開一個節點的代價在記憶體裡算一下，幾乎免費要真的走過去，花真實成本
生活例子用導航先規劃好路線再出門掃地機器人第一次進你家
老師原話是什麼？ 「就是他一邊做動作，做完動作之後呢，又去感測環境，然後再去決定下一個動作」(2:21:59) 「其實就是你家的掃地機器人啦」(2:22:21)
## [2:22:37](https://www.youtube.com/watch?v=S1km7opW6rw&t=8557s) Online agent 只知道什麼 投影片規定 online agent 只知道三件事：ACTIONS(s)（在狀態 s 能做哪些動作）、c(s, a, s')（從 s 做 a 到 s' 的單步成本，要真的到了 s' 才知道）、GOAL-TEST(s)（這裡是不是終點）。它不知道 RESULT(s, a)，也就是做了動作會到哪裡，除非真的站在 s 做一次 a。圖 4.19 的迷宮：從上帝視角一眼看出右、右、上、上 4 步到 G；但 agent 在 S 只知道上和右都能走，如果先往上，到 (1,2) 才發現上、右、左都走不通，只好走回來。老師說「浪費了一步」，指往上白走；加上走回來，共多 2 步。 ![圖 4.19：從 S 走到 G 的小迷宮，灰色粗線是牆。座標寫成 (x, y)，x 是第幾行、y 是從下往上第幾列](file-upload://3e7fc631-b030-81dd-aa8a-00b219e26d19)
要先懂什麼？一個搜尋問題由哪幾塊組成？ Ch3 定義搜尋問題時有這幾塊： - initial state：起點 - ACTIONS(s)：在 s 能做哪些動作 - RESULT(s, a)：transition model（轉移模型），在 s 做 a 會到哪個狀態 - GOAL-TEST(s)：是不是終點 - c(s, a, s')：單步成本，加總起來是 path cost（路徑成本） Offline 搜尋這幾塊全部都知道。Online 拿掉了 RESULT，單步成本也要做完才知道。
不知道 RESULT，到底有多不知道？ 投影片 p.31：agent 不知道在 (1,1) 往上會到 (1,2)；就算到了 (1,2)，也不知道往下會回到 (1,1)。連上、下會互相抵消都要自己走過才學到。 所以 online agent 要自己記一張表：每做完一次，就寫下在 s 做 a 到了哪個 s'。例如在 (1,1) 做 Up 到了 (1,2)，就記 result[(1,1), Up] = (1,2)。這張表越記越多，就是它腦中的地圖。
老師原話是什麼？ 「你在真正得到這個動作的結果之前呢，你是不會知道你做這個動作要花的花費有多少」(2:23:07)
## [2:24:12](https://www.youtube.com/watch?v=S1km7opW6rw&t=8652s) 盲目搜尋與啟發式 沒有任何提示時只能到處試，就像上一章的 DFS、BFS 這類盲目搜尋（uninformed search）。如果 agent 有 admissible heuristic h(s)（可採納的啟發函數：估計到終點還有多遠，而且永遠不高估），例如知道 G 的座標、用曼哈頓距離估計，就能像 A* 那樣優先往看起來比較近的方向走。老師補充，走迷宮可以畫成在一棵樹上走，但不是每個問題都能這樣描述。
要先懂什麼？admissible heuristic、A*、曼哈頓距離 - Heuristic h(n)：估計從 n 到終點還要多少成本。 - Admissible（可採納）：h(n) 永遠小於或等於真正的最短成本，不會高估。 - A*：每次展開 f(n) = g(n) + h(n) 最小的節點，g(n) 是從起點到 n 已花的成本。h 是 admissible 時，A*（tree search）找到的是最佳解。 - 曼哈頓距離：h = |x1 − x2| + |y1 − y2|，只能上下左右走時的格子距離。它不能斜走、也不管牆，只會低估或剛好，所以是 admissible。
它到底怎麼運作？在圖 4.19 算一次曼哈頓距離 G 在 (3,3)，所以 h(s) = |x − 3| + |y − 3|。 - h(S) = h(1,1) = 2 + 2 = 4，剛好等於真正的最短步數。 - 往上的鄰居 (1,2)：h = 2 + 1 = 3 - 往右的鄰居 (2,1)：h = 1 + 2 = 3 平手。曼哈頓距離看不到牆，兩個方向看起來一樣好，只能靠固定的挑選順序或運氣。再往前一層，(2,2) 和 (3,1) 都是 2，又平手。所以 heuristic 能幫忙，但不保證不走冤枉路。 補充（課本 4.5 節，這堂沒講）：online 時 heuristic 是拿來挑下一步往哪個鄰居走，不是照搬 offline 的 A*，因為 A* 會在搜尋樹裡跳來跳去（見最後一段）。課本給 online 用的版本叫 LRTA*。
老師原話是什麼？ 「甚至你是 admissible 的 heuristic function 的話，你就可以用 A star search」(2:24:43)
## [2:25:12](https://www.youtube.com/watch?v=S1km7opW6rw&t=8712s) Competitive ratio 各種 online 演算法最後都走得到終點，那誰比較好？看實際花的成本。成本可以是步數，也可以是走到某些地方會被扣很多分；走迷宮時就是實際走過的總路徑成本。投影片的定義：拿實際走的成本，跟事先知道整張地圖時會走的路徑成本相比，這個比值叫 competitive ratio（競爭比），越小越好；最小是 1，代表跟全知的最佳解一樣好。 公式：competitive ratio = 實際走的路徑成本 ÷ 事先知道地圖時的最佳路徑成本 在圖 4.19 算一次（最佳路徑是 4 步）：
走法實際步數competitive ratio
運氣好，一開始就往右：右、右、上、上44 ÷ 4 = 1.0
老師的例子：先往上撞到死路，走回來，再右、右、上、上66 ÷ 4 = 1.5
Online DFS，固定照上、右、下、左的順序試（最後一段逐步跑）1212 ÷ 4 = 3.0
Competitive ratio 一定有上限嗎？（課本補充，老師沒講） 不一定。如果有走了就回不來的動作（例如單行道、掉進洞裡），agent 可能走進永遠到不了終點的死路，competitive ratio 就是無限大。所以課本討論 online 演算法時，通常假設環境是 safely explorable（安全可探索：從每個走得到的狀態都還能走到終點）。
老師原話是什麼？ 「你的這個cost花的是完美的多少倍」(2:26:43) 「那我們當然希望說這個 competitive ratio 越小越好，因為它就是越接近最佳解的意思」(2:26:52)
## [2:27:02](https://www.youtube.com/watch?v=S1km7opW6rw&t=8822s) 邊走邊建地圖、小結 每做完一個動作，agent 會收到一個 percept（感知）告訴它到了哪個狀態，把它記進地圖，再用目前的地圖決定下一步；走過的歷史都存下來，對環境就越來越了解。因為 online 時展開一個節點要真的走過去，演算法最好照就近的順序展開。DFS 剛好有這個性質：永遠從目前位置往鄰居走，走不通就退一步。Hill climbing 也只看目前位置的鄰居，投影片說它本來就是 online 演算法，缺點是停在 local maximum（局部最高點）就沒地方去了。 注意：老師說最後這一塊（online local search）比較偏聊天、沒有具體例子 (2:29:22)。
它到底怎麼運作？在圖 4.19 跑一次 online DFS 規則：到一格後，照上、右、下、左的順序找還沒去過的相鄰格，有就走過去；都去過或走不通，就退回來時的那一格（真的走回去）。為了好算，這裡假設 agent 知道格子座標，所以知道某個鄰居去過沒。 1. (1,1) 往上 → (1,2) 2. (1,2) 上、右是牆，左是邊界，下面去過 → 退回 (1,1) 3. (1,1) 往右 → (2,1) 4. (2,1) 往上 → (2,2) 5. (2,2) 往上 → (2,3) 6. (2,3) 上是邊界、右是牆、下面去過 → 往左 → (1,3) 7. (1,3) 沒有新的格子 → 退回 (2,3) 8. (2,3) 沒有新的格子 → 退回 (2,2) 9. (2,2) 左右都是牆 → 退回 (2,1) 10. (2,1) 往右 → (3,1) 11. (3,1) 往上 → (3,2) 12. (3,2) 往上 → (3,3) = G，停 共 12 步，competitive ratio = 12 ÷ 4 = 3.0。第 2、7、8、9 步的退回都要花真實步數；offline DFS 的回溯只是從記憶體拿下一個節點，不花錢。課本的 ONLINE-DFS-AGENT 連座標都不假設，要靠 result 表才知道怎麼退回。
為什麼 BFS、A* 不適合 online？ BFS 一層一層展開：先展開 (1,1) 的兩個鄰居 (1,2) 和 (2,1)。Offline 時從 (1,2) 換到 (2,1) 只是在記憶體裡換一個節點；online 時你人站在 (1,2)，要去展開 (2,1)，得先走 (1,2) → (1,1) → (2,1) 兩步。層數越深，每換一個節點就要跨越半棵樹；A* 下一個 f 最小的節點也可能在很遠的分支上。DFS 下一個要展開的永遠是目前位置的鄰居，最多退一步。
Hill climbing 為什麼本來就是 online 演算法？ 它只記一個目前狀態，每次只看目前位置的鄰居、往最好的走，本來就是邊看邊走。問題是走到 local maximum 就卡住。Offline 時可以用 random restart（隨機換個起點重來），online 不行，因為 agent 沒辦法瞬間移動到新起點（課本 4.5 節，這堂沒講）。
老師說各種 Search 的地位不一樣，是什麼意思？ 這章出現一大堆某某 search，但它們不是同一層的東西。我整理成三層： - 問題設定（在什麼情況下搜尋）：online search、searching with partial observations - 策略（挑下一步的大方向）：uninformed（盲目）與 informed（有 heuristic）、local search - 具體演算法：BFS、DFS、A*、hill climbing、simulated annealing、local beam search 老師原話：「但雖然它都叫 Search，但是有時候它們的地位是不太一樣的」(2:28:58)
## Self-check
Q1. Distinguish offline search from online search, and give the canonical example of online search. **Answer**: An offline search agent computes a complete solution before setting foot in the real world and then executes it. An online search agent interleaves computation and action: it first takes an action, then observes the environment and computes the next action. The canonical example is a robot placed in a new building that must explore it to build a map for getting from A to B (e.g., a robot vacuum). 中文重點：offline 先算完整條解再走；online 走一步、看一步、算一步。
Q2. Define the competitive ratio. In the maze of Figure 4.19 the optimal path costs 4. An online agent first moves Up into a dead end, comes back, and then follows the optimal path. What is its competitive ratio? **Answer**: The competitive ratio compares the total path cost of the path the agent actually travels with the path cost of the path it would follow if it knew the search space in advance; it should be as small as possible (the best value is 1). Here the agent travels 1 (Up) + 1 (Down) + 4 = 6 steps, so the ratio is 6 / 4 = 1.5. 中文重點：實際成本 ÷ 全知最佳成本，最小是 1，越小越好。
Q3. Why is depth-first search better suited to online search than breadth-first search or A*? Is hill climbing an online algorithm? **Answer**: In online search, expanding a node means physically traveling to it. BFS and A* may pick the next node from anywhere in the frontier, so the agent could travel all the way across the tree; DFS expands nodes in a local order. Hill climbing keeps just one current state and also has locality, so it is already an online search algorithm, but in its simplest form it leaves the agent at local maxima with nowhere to go. 中文重點：online 展開等於真的走過去，所以要就近；hill climbing 是 online，但會卡在 local maximum。
Q4. A robot with perfect obstacle sensors in the four compass directions and a correct map senses NSW, moves randomly, then senses NS. Explain how it determines its location, and what changes if the sensors are noisy. **Answer**: The robot keeps the set of locations consistent with all its percepts (its belief state). After E1 = NSW only 4 squares remain; from each of them the only possible move is East, so it predicts the shifted squares, and after E2 = NS only one of them is consistent, which is its location. With noisy sensors, inconsistent locations cannot simply be eliminated; the robot must keep a probability for each location and update it after every percept. 中文重點：用感測結果刪掉不可能的位置；感測器有雜訊時改成算機率。