[人工智慧導論](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 圖說） - 中文：如果感測器完全不會出錯、移動的結果（transition model，轉移模型）也完全準確，那走兩步、感測兩次之後，除了機器人真正的位置，不會再有別的格子同時符合這兩次感測結果。白話：感測器很準的話，摸兩次牆就能鎖定唯一位置。 - **Offline search**: "They compute a complete solution before setting foot in the real world and then execute the solution."（Ch4 p.29） - 中文：Offline（離線）搜尋會在真正踏進現實世界之前，先把完整的解算好，之後只是照著執行。白話：像出門前先用導航規劃好整條路線再上路。 - **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） - 中文：Online（線上）搜尋 agent 把「算」跟「做」交替進行：先做一個動作，再觀察環境，然後才算下一個動作。最經典的例子，是把機器人放進一棟沒去過的建築，讓它邊探索邊建地圖，方便之後從 A 走到 B。白話：掃地機器人第一次進你家就是這樣。 - **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） - 中文：投影片規定 online agent 只知道三件事——在狀態 s 能做哪些動作 ACTIONS(s)、從 s 做 a 到 s' 的單步成本 c(s,a,s')（但要真的走到 s' 才知道這個成本）、以及怎麼判斷是不是終點 GOAL-TEST(s)。它不知道做了動作會到哪裡（RESULT(s,a)），除非真的站在 s 做一次那個動作。白話：online agent 沒有上帝視角的地圖，走了才知道會到哪裡。 - **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） - 中文：agent 可能有一個 admissible（可採納，代表永遠不會高估真正距離）的啟發函數 h(s)，可以用它估計目前狀態到終點大概還有多遠。白話：像有大概的方向感，但保證不會亂猜得太近。 - **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） - 中文：成本是 agent 實際走完的總路徑成本；把這個成本拿去跟「事先就知道整個搜尋空間」時會走的路徑成本相比，這個比值就叫 competitive ratio（競爭比），希望它越小越好。白話：實際花的代價除以理想情況下最少要花的代價，越接近 1 越好。 - **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） - 中文：online agent 每做完一個動作，就會收到一個 percept（感知），告訴它到了哪個狀態；agent 用這個資訊，把自己心裡的環境地圖補得更完整。白話：走一步、看一眼、把看到的記進地圖。 - **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 演算法最好照「就近」的順序展開節點；DFS 剛好就有這種性質，永遠是從目前位置往鄰居走。白話：online 時展開節點等於真的要走過去，所以要挑近的先展開。 - **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） - 中文：Hill climbing 只在記憶體裡存「目前這一個狀態」，這個特性剛好讓它本來就是一種 online 搜尋演算法；但最簡單的版本不太好用，因為一旦走到 local maximum（局部最高點）就沒地方可以再走了。白話：hill climbing 天生適合 online，缺點是容易卡在小山頂上。 ## [2:16:36](https://www.youtube.com/watch?v=S1km7opW6rw&t=8196s) 部分觀察：迷宮裡的機器人 八皇后這類問題，agent 看得到整個狀態。但很多問題只看得到一小部分，老師舉 hill climbing 為例：站在某一點，只看得到附近的鄰居。只看得到一部分時的搜尋，叫 searching with partial observations。投影片的例子：機器人有東西南北四個聲納感測器（永遠正確），也有正確的地圖，但導航系統壞了，下 Move 指令只會隨機走到某個相鄰格子；任務是判斷自己現在在哪一格。 注意：老師口頭拿 hill climbing 當例子，但它只看鄰居是演算法的選擇，狀態其實看得到；partial observation 指的是感測器拿不到完整狀態（我補充）。 這段用到的前幾週名詞：agent（第 2 週學過：會感測環境、再自己決定下一個動作的程式或機器人，例如掃地機器人，見 [02 環境性質與五種 Agent](https://app.notion.com/p/3e6fc631b03081da84a3de991c10424f)）。狀態（state）就是「agent 現在處在什麼情況」，在迷宮裡就是「站在哪一格」。Hill climbing 爬山法（第 2 週學過：每次只往鄰居裡分數最高的那一格走一步，四周都沒有更好就停，見 [07 局部搜尋與爬山演算法](https://app.notion.com/p/3e6fc631b03081e896bdc677065a3376)）。
要先懂什麼？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% 正確，只有八成正確會難很多，之後的章節會講。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\ai_ch4_p028.png | 圖 4.18：(a) 第一次感測 NSW 後，只剩 4 個可能位置（圈起來的格子）；(b) 往東走一步、第二次感測 NS 後，只剩 1 格]] 圖上重點： - 標題 Searching with Partial Observations：只看得到一部分時的搜尋。 - 上圖 (a) Possible locations of robot after E1 = NSW：第一次感測到「北、南、西有牆」之後，機器人可能在的位置，就是畫圈加黑點的 4 格。 - 下圖 (b) After E1 = NSW, E2 = NS：往東走一步、再感測到「北、南有牆」之後，只剩左上角第 2 格一個圈。 - 灰色格子是牆，小圓點是空格。圖說最後一句：感測器不出錯、移動結果也準確時，沒有別的格子同時符合這兩次感測。 這張圖在講：每感測一次，就能刪掉一大批不可能的位置，兩次就鎖定答案。 下面第一個摺疊在做什麼（白話）：把「刪格子」的過程一格一格算一遍，會看到候選從 42 格變 4 格、再變 1 格。第二個摺疊在做什麼（白話）：感測器會說錯時不能直接刪格子，改成給每一格一個「有多可能」的百分比，感測越多次，百分比越集中在真正的位置上。
它到底怎麼運作？一步一步算一次 座標寫成（第幾列, 第幾行），從左上角數起。課本把目前所有可能位置的集合叫 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 是先算完才出發。 這段用到的前幾週名詞：BFS（第 2 週學過：從起點一層一層往外找，先找完近的再找遠的）、UCS（同一章：每次先展開目前累積成本最小的），見 [04 BFS 與 UCS 搜尋](https://app.notion.com/p/3e6fc631b030811291c5ebaf18c949df)；A*（第 2 週學過：把「已經走了多少」加上「估計還要多少」，挑總和最小的先展開），見 [06 Greedy 與 A* 搜尋](https://app.notion.com/p/3e6fc631b03081f7acf6d56761c8225c)。「展開一個節點」（expand）：搜尋時把某個狀態拿出來，列出它下一步能到哪些狀態。Offline 時這只是電腦裡算一下；online 時等於人真的要走到那個位置。
**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 步。 [[IMG: C:\D槽\TAICA課程\_work\notes-v2\ai-w3\img\ai_ch4_p031.png | 圖 4.19：從 S 走到 G 的小迷宮，灰色粗線是牆。座標寫成 (x, y)，x 是第幾行、y 是從下往上第幾列]] 圖上重點： - 標題 Online Searching Agents with Unknown Environments：在不認識的環境裡邊走邊搜尋的 agent。 - 上方文字：在圖 4.19 的迷宮裡，agent 不知道從 (1,1) 往上（Up）會到 (1,2)；就算到了 (1,2)，也不知道往下（Down）會回到 (1,1)。 - 迷宮：S 是起點、G 是終點，灰色粗線是牆；下面的 1、2、3 是 x，左邊的 1、2、3 是 y。 - 圖說 A simple maze problem：一個簡單的迷宮，agent 從 S 出發要到 G，但對環境一無所知。 這張圖在講：有地圖的人一眼就看出路，online agent 卻連「往上再往下會回到原地」都要自己走過才知道。ACTIONS、RESULT 這些名詞是第 2 週 [03 搜尋問題的定義](https://app.notion.com/p/3e6fc631b03081c8a7e0e152c12bbd25) 學過的，下面第一個摺疊有整理。
要先懂什麼？一個搜尋問題由哪幾塊組成？ 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* 那樣優先往看起來比較近的方向走。老師補充，走迷宮可以畫成在一棵樹上走，但不是每個問題都能這樣描述。 這段用到的前幾週名詞：DFS（第 2 週學過：一路往深處走到底，走不通再退回上一個岔路，見 [05 DFS 家族與雙向搜尋](https://app.notion.com/p/3e6fc631b03081bda674f874680e4a09)）。盲目搜尋（uninformed）是完全沒有「離終點多遠」的提示；有提示的叫 informed search。這裡說的「上一章」指的是第 2 週的這些章節。 第二個摺疊在做什麼（白話）：用「格子距離」幫迷宮每一格估「離 G 還有幾步」，結果往上和往右估出來一樣近，所以有提示也不保證不走冤枉路。
要先懂什麼？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)。 這段用到的前幾週名詞：local maximum 局部最高點（第 2、3 週學過：附近每一格都比它低，但不是全場最高的小山頂，見 [02 爬山法複習與模擬退火](https://app.notion.com/p/3e6fc631b03081a79865f701c688c1c4)）。Local search 局部搜尋（同一處：只記目前位置、只往鄰居移動的搜尋方法）。 第一個摺疊在做什麼（白話）：讓 DFS 在圖 4.19 真的走一遍，數出它一共走 12 步、是最佳路線的 3 倍，看出「退回去」在 online 時要真的花步數。
它到底怎麼運作？在圖 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.（中文：區分 offline 搜尋跟 online 搜尋，並舉出 online 搜尋最經典的例子。） **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 搜尋 agent 把「算」跟「做」交替進行——先做一個動作，再觀察環境，然後才算下一個動作。最經典的 online 搜尋例子，是把機器人放進一棟沒去過的建築，讓它自己探索、邊走邊建地圖，方便之後從 A 走到 B（像掃地機器人第一次進你家）。
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?（中文：先定義 competitive ratio；在圖 4.19 的迷宮裡，最佳路徑成本是 4，一個 online agent 先往上走進死路、再走回來，然後照最佳路徑走，它的 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. 中文：Competitive ratio 是拿 agent 實際走完的路徑成本，除以「如果事先就知道整個搜尋空間」時最短的路徑成本；這個比值越小越好，最好是 1（代表跟全知的最佳解一樣好）。這一題裡，agent 先往上走 1 步進死路、再走回來 1 步，然後照最佳路徑走 4 步，總共走了 6 步，所以 competitive ratio = 6 ÷ 4 = 1.5。
Q3. Why is depth-first search better suited to online search than breadth-first search or A*? Is hill climbing an online algorithm?（中文：為什麼 DFS 比 BFS 或 A* 更適合拿來做 online 搜尋？Hill climbing 算不算是一種 online 演算法？） **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 搜尋裡，展開一個節點等於 agent 真的要走過去那個位置。BFS 和 A* 選下一個要展開的節點時，可能會跳到搜尋樹裡很遠的分支，agent 就得跨越整棵樹走過去；DFS 展開節點的順序是「就近」的——永遠是目前位置的鄰居，最多退一步。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.（中文：一個機器人裝了完美的四方向障礙感測器、也有正確的地圖，先感測到 NSW，隨機移動一次，再感測到 NS。說明它怎麼判斷自己的位置；如果感測器不準，情況會怎麼變？） **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. 中文：機器人會保留所有跟目前收到的感測結果都一致的位置集合（belief state，信念狀態）。第一次感測 E1 = NSW 之後，符合的只剩 4 個格子；這 4 格唯一能走的方向都是東邊，所以不管怎麼隨機移動都會往東走一格，機器人可以先把這 4 個候選位置都往東移一格。第二次感測 E2 = NS 之後，這 4 個候選裡只有 1 個還符合，那就是機器人真正的位置。如果感測器不準，就不能直接把不符合的位置刪掉，而是要幫每個候選位置算一個機率，每收到一次感測結果就更新一次這些機率。
讀完了嗎？下一章：[07 不確定性與機率基礎（2:29–2:53）](https://app.notion.com/p/3e6fc631b030818b8460e7499c1c5521)｜回到週頁：[W3（9/24）](https://app.notion.com/p/3e6fc631b0308137bbd8e73f5c6f1b62)