在本文以前建議先讀過以下前文：
另外本文主要內容為 Probabilistic Robotics 書中的 4.3：The Particle Filter。
Particle Filter 的主要思想是用一系列的隨機樣本來表示狀態 \(x_t\) 的可信度 bel(x_t)。從前文我們知道 \(bel(x_t)\) 是一個 posterior： \[ bel(x_t)=p(x_t | z_{1:t}, u_{1:t}) \] 換句話說，Particle Filter 用一系列來自該分布的樣本來表示此機率分布。此機率分布表示法是一個近似表示法，但由於不需要任何參數因此可以比高斯分布表示更廣泛的分布空間，也可以用來建構非線性變換的模型。
在 Particle Filter 中，我們稱樣本為 particle： \[ \chi_t := x_t^{[1]}, x_t^{[2]},\cdots ,x_t^{[M]}\\ x_t^{[m]} \sim p(x_t|z_{1:t},u_{1:t}) \] 也就是說一個 particle 就是真實世界狀態在 t 時間的一種可能假設。M 代表所有的 particle 數量，為了使此近似更準確，我們希望 M 能夠越大越好，但太大會使得計算速度變得很慢。
Particle Filter 演算法
Particle Filter 演算法的輸入為 t-1 時刻的 M 個 particles、\(u_t\)、以及 \(z_t\)，輸出為 t 時刻的 M 個 particles。以下總結了演算法的步驟：
- \(\overline{\chi}=\chi=\phi\)
- for m = 1 to M：
- 從 \(p(x_t|u_t, x_{t-1}^{[m]})\) sample 一個樣本 \(x_t^{[m]}\)
- \(w_t^{[m]} = p(z_t|x_t^{[m]})\)
- \(\overline{\chi}\) 加入 \(<x_t^{[m]}, w_t^{[m]}>\)
- for m = 1 to M：
- 利用 \(w_t^{[m]}\) 的權重重新產生一個 index i
- 把 \(x_t^{[i]}\) 加至 \(\chi\)
- return \(\chi\)
- (2.1) 需要的是能從 \(p(x_t|u_t,x_{t-1})\) 中產生樣本，而經過 M 次採樣後得到的 M 個樣本即是在 t 時刻可信度的大致估計 \(\overline{bel}(x_t)\) 的近似表示。
- (2.2) 計算的是對於每個 particle 的 importance weight，下文會解釋推導過程。
- (3) 實現了 importance sampling（請參考前文），利用 importance weight 抽換 particles。在 importance sampling 以前，M 個 particles 按照 \(\overline{bel}(x_t)\) 分布，而 importance sampling 以後 M 個 particles 就會按照 \(bel(x_t)\) 分布了。（註：\(bel(x_t) = \eta \ p(z_t|x_t^{[m]}) \ \overline{bel}(x_t))\)）
Particle Filter 的式子推導
在推導式子時我們用 \(bel(x_{0:t}) = p(x_{0:t}|u_{1:t}, z_{1:t})\) 代替 \(bel(x_t)\)（以下省略 \(u_t\)）： \[ p(x_{0:t}|z_{1:t}) = p(x_{0,t}|z_t, z_{1:t-1}) \\ =\eta \ p(z_t|x_{0:t}, z_{1:t-1})\ p(x_{0:t}|z_{1:t-1})\hspace{1cm} Bayes \\ = \eta \ p(z_t|x_t)\ p(x_{0:t}|z_{1:t-1}) \hspace{1cm} Markov\\ = \eta \ p(z_t|x_t)\ p(x_t|x_{0:t-1},z_{1:t-1})\ p(x_{0:t-1}|z_{1:t-1}) \\ = \eta \ p(z_t|x_t)\ p(x_t|x_{t-1})\ p(x_{0:t-1}|z_{1:t-1}) \hspace{1cm} Markov \] 另外，在 (2.1) 中我們從 \(p(x_t|u_t, x_{t-1}^{[m]})\) sample 一個樣本： \[ p(x_t|x_{t-1}^{[m]})=p(x_t|x_{t-1})bel(x_{0:t-1}) = p(x_t|x_{t-1})p(x_{0:t-1}|z_{1:t-1}) \]在 importance sampling 的討論中，我們稱無法直接產生樣本的分布為目標分布，而容易產生樣本的分布為建議分布。在 Particle Filter 中，目標分布為：\[ \eta \ p(z_t|x_t)\ p(x_t|x_{t-1})\ p(x_{0:t-1}|z_{1:t-1}) \] 而建議分布為：\[ p(x_t|x_{t-1})p(x_{0:t-1}|z_{1:t-1}) \] 因此兩者相除即可得到 importance weight： \[ w_t^{[m]}=\eta \ p(z_t|x_t) \] 正是演算法中的步驟 (2.2)。
實作上的細節
可以參考此文章。
沒有留言:
張貼留言