Learning Objectives
- 說明佔用柵格怎麼表示地圖，以及「沒看過」和「看過是空的」的差別
- 用 log-odds 更新一個格子，說明它為什麼能把雜訊平均掉
- 用 Bresenham 把一條光達射線變成要更新的格子
- 用 /scan 與 /odom 建出一張地圖，說明里程計有誤差時地圖為什麼會糊掉
機器人需要的地圖長什麼樣子
把機器人放進一間它沒去過的教室。光達每一圈給它幾十個距離，下一圈又是另外幾十個。如果只看當下這一圈，它不會知道背後走過的走廊長什麼樣子，也沒辦法規劃怎麼繞過去。它需要把每一圈的資料累積成一張地圖。
最常見的表示法是佔用柵格（occupancy grid）：把地面切成方格，每一格記一個「這裡有東西的機率」。這個想法來自 Moravec 與 Elfes 在 1985 年用聲納建圖的研究。
每個格子有三種狀態，第三種最容易被忽略：
| 狀態 | 意思 | 規劃時怎麼對待 |
|---|---|---|
| 大概有東西 | 機率高 | 不能走 |
| 大概是空的 | 機率低 | 可以走 |
| 還沒看過 | 機率 0.5，完全不知道 | 不能當成空的 |
「沒看過」不等於「空的」。如果把沒看過的地方當成可以走，機器人就會往從來沒確認過的方向全速前進。
這一課假設機器人知道自己在哪裡，先專心處理「看到的東西怎麼累積」。這個假設什麼時候不成立，課程最後會回來談。
log-odds：把機率的乘法換成加法
感測器會錯，所以一次觀測不能直接把格子定成有或沒有。比較合理的作法是累積證據：看到一次有東西，機率往上調一點；再看到一次，再往上調。
直接更新機率要做乘除，而且數值會擠在 0 和 1 附近。實務上常改記 log-odds：
l = ln(p / (1 - p))
p = 1 - 1 / (1 + e^l)
幾個值記下來就夠用：
| 機率 p | log-odds l |
|---|---|
| 0.5（不知道） | 0 |
| 0.7 | 約 0.85 |
| 0.4 | 約 -0.4 |
| 0.93 | 約 2.55 |
這樣一來，更新只剩加法：射線停在這一格就加 0.85，射線穿過這一格就減 0.4。沒看過的格子是 0，不需要特別處理。
為什麼加和減的大小不一樣？射線穿過只告訴你「這條線上沒擋到」，射線停住的那一格比較可能真的有東西。這兩個數字是假設值，要依感測器調整，下面的小工具可以改。
代價也要知道：這個算法把每個格子當成互相獨立，也假設每次觀測獨立。實際上同一面牆相鄰的格子並不獨立，同一個位置連掃十次的誤差也可能是同一個原因造成的，所以機率的數字不要照字面解讀，當作「累積了多少證據」比較準確。
一步一步看一個格子的 log-odds
這個格子真的有東西。光達看到它三次，有一次量到比較遠（射線穿過它）。注意錯的那一次沒有把結果毀掉，只是讓證據少一點。
一條射線會經過哪些格子
光達給的是距離，要更新地圖得先知道這條線穿過哪些格子。在方格上畫直線的經典作法是 Bresenham 演算法：從起點一格一格走，每一步用整數累積的誤差決定要往 x 走、往 y 走，還是兩個都走。
起點 (2, 1)，終點 (6, 3)：(2,1) → (3,1) → (4,2) → (5,2) → (6,3)
只用整數加減，不需要浮點運算，每條射線只碰到它真正經過的格子。一條射線的更新規則是：
- 除了最後一格，全部標成空的（減）
- 最後一格標成佔用（加）
- 如果光達在射程內沒有打到東西（
inf），這一路都是空的，但沒有任何一格可以標佔用
下面的小工具把這些步驟攤開來。深灰是還不知道，白色是認為空的，黑色是認為有東西。
動手寫：用一條射線更新地圖
ray 是一條射線依序經過的格子，最後一格是光達打到東西的地方。補上更新規則，再印出每一格的機率。grid 是字典，沒看過的格子不在裡面，.get(cell, 0.0) 會當成 0。
如果機器人也不知道自己在哪裡
上面的程式有一個很大的前提：/odom 給的位置是準的。模擬世界的里程計沒有雜訊，所以成立。真實機器人的輪子會打滑，里程計會累積誤差（第 8 課），只要位置偏掉，後面每一圈都會畫在錯的位置，同一面牆就變成好幾面。
這是機器人領域有名的雞生蛋問題：
- 要建地圖，得先知道自己在哪裡
- 要知道自己在哪裡，得先有地圖
同時解這兩件事叫 SLAM（Simultaneous Localization and Mapping）。一個常見的想法是比對這一圈光達和已經建好的地圖，用比對結果修正里程計的累積誤差；走回去過的地方時，還能發現「這裡我來過」，把整張地圖的誤差一次修掉（loop closure）。
ROS 2 常用的現成套件是 slam_toolbox，這門課不實作 SLAM，只要知道這個問題的結構。下一課會處理比較簡單的一半：地圖已經有了，機器人不知道自己在哪裡。
建好的地圖在 ROS 2 用 nav_msgs/msg/OccupancyGrid 傳遞：
header frame_id 通常是 map
info.resolution 每格幾公尺
info.width 有幾欄
info.height 有幾列
info.origin 格子 (0, 0) 在 map 座標系的位姿
data 一維陣列，從 (0, 0) 開始逐列排列；-1 是不知道，0 是空的，ROS 工具常用 1 到 100 表示佔用程度
注意 data 的 -1：訊息定義本身就把「不知道」和「空的」分開了，和這一課開頭的三種狀態一致。訊息定義也說明數值的意義依應用而定，所以要看接收端怎麼解讀。另外它的第 0 個元素是地圖左下角（origin 的位置），上面的小工具和字串地圖則是第 0 列在最上面，自己轉換時很容易差一個上下顛倒。
確認一下
走廊盡頭有一面玻璃門，光達的雷射穿過去，量到門外很遠的牆。掃很多次之後，地圖上的玻璃門會是什麼樣子？
光達在射程內沒有打到東西，回傳 inf。下面哪個作法最合理？
某格的 log-odds 是 0.85。接下來射線穿過它兩次（L_FREE 是 0.4），它現在是多少？代表什麼？
為什麼 log-odds 通常要設上下限？如果不設，一面牆被連續看到一萬次之後，有人把牆拆了，會發生什麼事？
規劃路徑時，把「未知」的格子當成可以走。這個設定有什麼風險？
重點整理
- 佔用柵格把地面切成格子，每格記佔用機率。未知和空的是兩回事。
- log-odds 把更新變成加法：射線停住的格子加、穿過的格子減。
- 累積證據可以平均掉隨機雜訊，平均不掉每次都一樣的錯（玻璃、黑色物體）。
- 光達的角度是相對光達的，建圖前要轉到地圖座標，並且用
angle_min、angle_increment算。 - 位置不準，地圖就會糊掉；同時估計位置和地圖叫 SLAM。
OccupancyGrid的data用 -1 表示未知，從地圖左下角開始排列。
下一課反過來：地圖有了，機器人被放在某個地方，它要怎麼知道自己在哪裡。