CMU 07-380 Lecture 4 導讀：Motion Planning，RRT 在連續空間用取樣找路

TL;DR07-380 Lec4 後半把規劃搬到連續的 configuration space：狀態沒辦法枚舉，RRT 就隨機取樣、從樹上最近的節點往樣本延伸一小段，並檢查整段不碰撞。RRT 是 probabilistically complete 但不最優；RRT* 用樹上的路徑成本幫新節點選父節點、再重接鄰居，讓路徑隨樣本增加收斂到最優。

#cmu #07-380 #ai-course #course-guide #motion-planning #rrt

系列: CMU 07-380 完整課程導讀 (5 / 15)

CMU 07-380 Lecture 3 導讀：Classical Planning，PDDL、狀態空間搜尋與 relaxation heuristic CMU 07-380 HW2 導讀：Classical and Motion Planning，從 robot-cook PDDL 到 RRT* 再到 LP 圖解

🌏 English version

這是 CMU 07-380 AI & ML II Fall 2026 的 Lecture 4（9/2）。課站 schedule 把它標成「Motion Planning：RRT」，投影片的標題是「Classical Planning II and Motion Planning」。前半講完 GraphPlan 與 relaxation heuristic，那部分收在上一篇 Lecture 3 導讀。本文只講後半：狀態連續、沒辦法枚舉的時候，要怎麼規劃？

上一篇的世界由有限個事實組成，最多就是很大。機械手臂的關節角度、遊戲角色的座標是實數，狀態有無限多個，BFS 連第一層都展不完。這一講的答案是：不枚舉，改用取樣。

依 2026-09-29 課站狀態整理；課站註明 schedule 可能變動。

官方材料與讀取範圍

Lec4 投影片（inked PDF）後半：Among Us 與 Robot Cook 的動機、configuration space、RRT、碰撞處理、completeness 與 optimality、RRT*
課站列出的三個互動 demo：Piano Mover、Robot Cook、Robot Cook N-link
Recitation 2 解答 §6：倉庫機器人的 RRT 手算題。這一講沒有自己的 recitation，RRT 練習放在 Recitation 2 最後一節
課站指定閱讀 AIMA Ch. 26.5。本文沒有引用課本內容
這一講沒有 pre-reading 筆記

公開程度：投影片、三個 demo 與 recitation 解答都公開，對應的 HW2 程式作業也有 starter 與本機 autograder，這一段已達 A3。全課目前仍是 A2（進行中），分級見全球 AI／CS 課程地圖。

從離散跳到連續：configuration space

投影片的開場問題是：要怎麼寫一個 Among Us 的 agent，讓它從一個地點走到另一個地點？接著是 Robot Cook：一支兩節的機械手臂在煎餅台前工作。

關鍵概念是 configuration space（C-space）。物理空間裡的狀態 s，跟描述機器人姿態的 configuration q 是兩回事。Piano Mover demo 把這件事做得很直觀：鋼琴的姿態由位置 (x, y) 和旋轉角 θ 三個數字完整描述，所以在 C-space 裡整台鋼琴縮成一個點；會讓鋼琴撞到家具的 configuration 形成 C-obstacle。投影片的 Poll 3 問的就是 Piano Mover 的 C-space 有幾維。

Robot Cook demo 的右半邊畫的是 (θ₁, θ₂) 平面：手臂在左邊的廚房移動，右邊只是一個點在動。N-link 版本可以把關節數調到 2–6。頁面說明提醒，超過兩節時右邊只能畫一張二維切片，樹投影上去看起來會穿過障礙物，那只是高維樹的影子。

投影片的總結給出兩條路：把連續空間切成離散格子，或者在連續空間裡取樣。RRT 是後者。

RRT：挑一個隨機點，找最近的鄰居，別走太遠

投影片用一首改寫的童謠記演算法：「Pick a random point, and find its nearest neighbor; never let it get too far away.」對應的步驟是：

flowchart TD
  A[樹只有 q_init] --> B[從 C-space 取樣 q_rand]
  B --> C[找樹上離 q_rand 最近的 q_near]
  C --> D{距離 ≤ max_edge？}
  D -- 是 --> E[q_new = q_rand]
  D -- 否 --> F[q_new = 從 q_near 朝 q_rand<br/>走 max_edge 的點]
  E --> G{q_near 到 q_new<br/>整段都沒碰撞？}
  F --> G
  G -- 否 --> B
  G -- 是 --> H[把 q_new 加進樹<br/>父節點是 q_near]
  H --> I{到達 q_goal？}
  I -- 否 --> B
  I -- 是 --> J[沿父節點指標回溯出路徑]

投影片對碰撞講得很細：

q_rand 落在障礙物裡時，可以直接丟掉重抽，也可以照樣朝它延伸出 q_new
q_new 不合法就丟掉重抽
要檢查整段線段，不能只看端點，否則一步可能穿牆
agent 每一步能移動的距離有限，所以 RRT 找到的路徑還要切成小段、轉成動作

可重做的小例子：一次延伸

樹上有兩個節點 (0, 0) 與 (2, 0)，max_edge = 1.5，抽到 q_rand = (2, 4)。

dist((0,0), (2,4)) = √(4+16) ≈ 4.47
dist((2,0), (2,4)) = 4.00        → q_near = (2,0)
4.00 > 1.5，走部分步長：
方向 = ((2,4) − (2,0)) / 4 = (0, 1)
q_new = (2,0) + 1.5·(0,1) = (2, 1.5)

然後檢查 (2, 0) 到 (2, 1.5) 整段是否碰撞，沒撞才加進樹。Recitation 2 §6.5 有同樣結構、但數字更刁的題目：最近鄰只贏第二名 0.123，解答特別提醒這種情況要算，不能用目測。它也指出 max_edge 只是邊長的上限，樣本落在樹附近時邊會更短。

RRT 的兩個性質：會找到，但不會變好

Completeness。投影片說 RRT 可以是 probabilistically complete。Recitation 2 解答給出精確定義：如果解存在，樣本數趨近無限時找到解的機率趨近 1；它沒有有限時間的保證，也永遠沒辦法回報「無解」。

投影片列了兩個改進：goal bias，以某個機率直接把 q_goal 當成 q_rand；以及 RRT-Connect，從終點也長一棵樹。Recitation 2 §6.9 用兩個極端說明 goal bias 的取捨：機率 0 仍然 probabilistically complete，只是很少碰到目標區；機率 1 則完全不探索，樹變成一條直衝目標的鏈，撞到第一面牆就卡死，失去 completeness。

Optimality。投影片把原因講得很清楚：節點的父節點在建立那一刻就固定，之後不會重新考慮。後來的樣本可以延伸樹，但修不了 500 次迭代前走的彎路，所以最終路徑是由樹最早、樣本最稀疏、資訊最少的階段決定的。投影片引用 Karaman 與 Frazzoli（2011）：RRT 以機率 1 收斂到次佳解。投影片給的修法是讓樹可以被改寫，多抽樣本沒有用。

RRT*：利用樹上的路徑成本

RRT* 在 RRT 上加兩個技巧，兩個都用到「從根到節點的路徑成本」：

找更好的父節點：不只接到最近的 q_near，而是找出半徑 R 內所有節點，挑讓 cost(q_parent) + c(q_parent, q_new) 最小的那個當父節點。
重接鄰居（rewire）：q_new 接好之後，檢查半徑 R 內每個鄰居，如果 cost(q_new) + c(q_new, q_neighbor) < cost(q_neighbor)，就把那個鄰居的父節點改成 q_new。

可重做的小例子：一次 best parent 加一次 rewire

根 r = (0, 0)，成本 0；A = (0, 2)，父節點 r，成本 2；B = (2, 2)，父節點 A，成本 4。新節點 q_new = (1, 1)，R = 1.5，假設沒有障礙。三個節點到 q_new 的距離都是 √2 ≈ 1.41，都在半徑內。

選父節點：
  經 r：0 + 1.41 = 1.41   ← 最小
  經 A：2 + 1.41 = 3.41
  經 B：4 + 1.41 = 5.41
q_new 接到 r，cost(q_new) = 1.41

重接鄰居：
  A：1.41 + 1.41 = 2.83，不小於 2，不動
  B：1.41 + 1.41 = 2.83 < 4，改接到 q_new

B 原本要繞 A 才到得了，成本 4；有了 q_new 之後降到 2.83。普通 RRT 做不到這種修正，因為它不會回頭改父節點。

投影片的總結：RRT 不最優；RRT* 在加入樣本的過程中考慮最小路徑成本、必要時重接父節點，路徑會一直變好，收斂到最優。Recitation 2 解答補充，RRT* 改的是 optimality（變成 asymptotically optimal），completeness 已經是取樣方法能給的最強程度，沒有再變強。

Recitation 與 HW 對應

Recitation 2 §6：倉庫機器人（12 × 10 m、兩個障礙物、ε = 2.0、goal bias 0.10）的完整手算：C-space 維度、最近鄰、steering、碰撞判斷、goal test、路徑回溯、參數改變後的行為。§6.4 有一句很值得記：改成六關節手臂時，演算法一行都不用改，只換距離函數和碰撞檢查。
HW2 程式作業 Q2–Q7：在 rrt.py 裡實作線段檢查、最近節點、RRT、best parent、rewire、RRT*，最後讓 Among Us 船員和 Robot Cook 手臂自己規劃。細節見 HW2 導讀。

延伸對照

投影片的「Beyond RRT」頁指向 Wikipedia 上的 RRT 變體清單，這一講沒有展開。
離散格子上的路徑搜尋可以回頭看 07-280 Lecture 2 導讀。RRT* 的 cost + c 比較跟 UCS 的 g(n) 是同一個直覺，只是發生在一棵隨機長出來的樹上。

今晚可以做的動作

打開 Piano Mover demo，選「Doorway」房間，轉動 θ 看 C-obstacle 的切片怎麼變。
打開 N-link demo，同一個目標分別用 2 節與 4 節手臂、RRT 與 RRT* 各規劃一次，比較樹的形狀。
不看解答做 Recitation 2 §6.5–6.7，每一步都算出距離，不用目測。
把上面 RRT* 的例子改成 A = (0, 1)，重算一次 best parent 和 rewire，看結果怎麼變。

系列導覽

上一篇：Lecture 3 導讀：Classical Planning，PDDL、狀態空間搜尋與 relaxation heuristic
下一篇：HW2 導讀：Classical and Motion Planning，從 robot-cook PDDL 到 RRT* 再到 LP 圖解
系列總覽：CMU 07-380 Fall 2026 總覽