粒子濾波器

粒子濾波器估計某物在哪裡，靠的是同時維護一大群猜測，而不是只有一個。每一個猜測——一個粒子——都是一個完整的可能答案：就在這個確切的位置、朝著那個確切的角度。一台被丟進某棟樓裡、完全不知道自己從哪兒出發的機器人，可能會撒出一千個粒子、鋪滿整張平面圖，每個都說「我賭的最好答案是這裡」。所有粒子組成的這整團雲，合起來代表機器人的「信念」：粒子扎堆的地方，它認為自己多半在那兒；粒子稀疏的地方，它認為自己多半不在。

這群粒子透過一個「適者生存」的循環不斷變好。首先，每個粒子都按機器人的運動被移動——機器人往前滾了一公尺，每個粒子也往前一公尺，外加一點隨機抖動來表示不確定性。接著來了一次測量，比如一次雷射掃描，於是每個粒子都按「它預測看到的景象，與感測器實際看到的有多吻合」被打分。最後是重取樣：得分高的粒子被複製，得分低的粒子被淘汰，於是整群粒子朝真相漂移、聚攏。把這個循環跑得足夠快，一團亂撒的雲霧就會在幾秒內坍縮到機器人真實的位置上。

這種方法的厲害之處在於它不做任何整齊的假設。卡爾曼那一家子堅持信念必須是單獨一個整潔的鐘形團塊；而粒子濾波器可以持有任何形狀的信念——甚至同時有好幾個分開的團簇，這對一台在兩條長得一模一樣的走廊之間猶豫不決的機器人來說再合適不過。代價則是計算量：要達到不錯的精度可能需要成千上萬個粒子，而且隨著問題維度增加，粒子數必須陡增，所以它在二維機器人定位這類任務上大放異彩，卻在維度極高的狀態上吃力。