粒子濾波自適應(yīng)機制研究綜述

摘 要:針對粒子濾波固有的缺陷，結(jié)合移動機器人領(lǐng)域的研究應(yīng)用成果，分別從樣本數(shù)目自適應(yīng)、重采樣自適應(yīng)、建議分布自適應(yīng)、運動/似然模型自適應(yīng)以及與其他方法的集成等幾個方面對粒子濾波自適應(yīng)機制當前研究的關(guān)鍵技術(shù)進行了歸納總結(jié)，并且對該研究領(lǐng)域需要解決的研究難點進行了總結(jié)，對進一步研究的方向進行了展望。

關(guān)鍵詞:粒子濾波; 自適應(yīng)機制; 樣本數(shù)目; 重采樣; 建議分布; 運動/似然模型

中圖分類號:TP24

文獻標志碼:A

文章編號:1001-3695(2010)02-0417-06

doi:10.3969/j.issn.1001-3695.2010.02.005

Survey on adaptive mechanisms of particle filter

YU Jin-xia1，2， TANG Yong-li1，3， LIU Wen-jing1

(1.College of Computer Science Technology， Henan Polytechnic University， Jiaozuo Henan 454003， China; 2.Jiangsu Provincial Key Laboratory of Image Processing Image Communication， Nanjing University of Posts Communication， Nanjing 210003， China; 3.Dept. of Compu-ter Science Technology， Tsinghua University， Beijing 100084， China)

Abstract:Aimed at the inherent deficiency in particle filter and combined with the up-to-date research and application in the mobile robot field， this paper summarized some key technologies in current study from the adaptive mechanism of sample size respectively， the resampling strategy， proposal distribution， motion/likelihood model and the integration with other methods. At the same time， concluded the main challenges that needed to be solved in this field and also presented some future trends about the technology of these difficulties.

Key words:particle filter; adaptive mechanisms; sample size; resampling; proposal distribution; motion/likelihood model

0 引言

粒子濾波(PF)也稱序列蒙特卡羅(sequential Monte Carlo，SMC)，源于Gordon等人[1]提出的一種基于序列重要性采樣(sequential importance samping，SIS)的自舉(bootstrap)非線性濾波方法。PF的核心思想是用隨機加權(quán)的樣本(也稱粒子)集合來近似表征后驗概率密度函數(shù)。原則上，PF可以用于任意非線性非高斯動態(tài)系統(tǒng)的狀態(tài)遞推估計或概率推理研究，近年在移動機器人領(lǐng)域如定位[2]、目標跟蹤[3]、并發(fā)定位與地圖創(chuàng)建[4]以及故障診斷[5]得到成功應(yīng)用。

基于SIS的PF算法潛在的問題是樣本退化問題(degeneracy)，也即在濾波過程中經(jīng)過幾次迭代，除了一個樣本外其余樣本的重要性權(quán)重均很小。文獻[6]指出:重要性權(quán)重的方差隨著時間增長而增大，因而樣本退化是不可避免的。這樣，大量的計算時間浪費在更新權(quán)重較小的樣本上。針對樣本退化問題，可以增加樣本大小至無窮來解決，但很低效。

為了解決樣本退化問題，采樣重要性重采樣(sampling-importance resamping，SIR)被引入PF中。但是SIR帶來新的問題[7]，由于權(quán)值越大的樣本子代越多，相反則子代越少甚至無子代。這樣重采樣后樣本集中樣本多樣性喪失，從而不足以用來近似表征后驗密度，尤其是在過程噪聲較小時問題更嚴重。最糟糕的情形就是新的樣本集實際都是某一個最健壯樣本的子代，這就是樣本枯竭(impoverishment)問題。

為解決這些問題，國內(nèi)外大量文獻對此進行了深入剖析[7~13]，提出的主要解決辦法有建議分布的選擇、重采樣策略的改進、有效推理的執(zhí)行、自適應(yīng)機制的引入以及與其他方法的集成。其中，引入自適應(yīng)機制的PF稱為自適應(yīng)粒子濾波。由于在對整個狀態(tài)空間處理中，概率密度可能會隨著時間的變化發(fā)生巨大改變。在PF中引入自適應(yīng)機制，可改進PF執(zhí)行和計算的有效性從而降低計算誤差。在PF自適應(yīng)機制研究方面，目前主要提出了樣本數(shù)目自適應(yīng)[14~27]、重采樣自適應(yīng)[6，28~33]、建議分布自適應(yīng)[28，34~37]、運動/似然模型自適應(yīng)[38~41]以及結(jié)合其他機制的自適應(yīng)方法[42~46]。

對于非線性、非高斯及多模分布的遞歸Bayesian狀態(tài)估計問題，基于自適應(yīng)機制的PF研究盡管只有十多年，但是已經(jīng)成為研究熱點問題。為此，國內(nèi)外學者展開了諸多研究，提出了許多研究思路和實用算法。在此基礎(chǔ)之上，本文針對粒子濾波固有的缺陷，對PF自適應(yīng)機制所開展的研究進行綜述。首先介紹了PF的基本算法及其當前依然存在的問題;然后結(jié)合移動機器人領(lǐng)域的研究應(yīng)用成果，對于當前PF自適應(yīng)機制研究的關(guān)鍵技術(shù)進行了歸納總結(jié);最后通過對該研究領(lǐng)域需要解決的研究難點進行分析，對進一步研究的方向進行了展望。

1 PF基本算法

1.1 PF基本算法

不失一般性，假定系統(tǒng)的狀態(tài)方程和測量方程描述如下:

xt=f(xt-1，ut-1)+wtzt=h(xt)+vt(1)(2)

其中:xt表示t時刻的系統(tǒng)狀態(tài);ut-1表示t-1時刻的系統(tǒng)輸入;zt表示t時刻的系統(tǒng)測量;wt和vt分別表示t時刻的過程噪聲和測量噪聲(它們獨立同分布)。狀態(tài)方程式(1)刻畫了系統(tǒng)的狀態(tài)轉(zhuǎn)移概率p(xt|xt-1，ut-1)，測量方程式(2)刻畫了似然概率p(zt|xt)。

從貝葉斯濾波角度，在給定系統(tǒng)輸入u1:t-1=u1，…，ut-1和測量數(shù)據(jù)z1:t=z1，…，zt，問題求解的核心是估計后驗分布p(xt|z1:t，u0:t-1)。假設(shè)xt服從一階Markov過程，且初始狀態(tài)x0的概率分布p(x0|z0)≡p(x0)，則后驗分布p(xt|z1:t，u0:t-1)的估計分為預測/更新遞歸執(zhí)行。

a)預測。依據(jù)前一時刻狀態(tài)的后驗信度Bel(xt-1)也即概率分布p(xt-1|z1:t-1，u0:t-2)，結(jié)合狀態(tài)方程式(1)來預測當前t時刻狀態(tài)xt的先驗信度Bel-(xt)。

Bel-(xt)=p(xt|z1:t-1，u0:t-1)=Bayes規(guī)則

∫p(xt|xt-1，z1:t-1，u0:t-1)p(xt-1|z1:t-1，u0:t-2)dxt-1=Markov假設(shè)

∫p(xt|xt-1，ut-1)p(xt-1|z1:t-1，u0:t-2)dxt-1=

∫p(xt|xt-1，ut-1)狀態(tài)方程Bel(xt-1)后驗信度dxt-1(3)

b)更新。利用測量方程式(2)，結(jié)合當前的感知測量信息zt來更新當前t時刻狀態(tài)xt的后驗信度Bel(xt)。

Bel(xt)=p(xt|z1:t，u0:t-1)=Bayes規(guī)則

p(zt|xt，z1:t-1，u0:t-1)p(xt|z1:t-1，u0:t-1)p(zt|z1:t-1，u0:t-1)=Markov假設(shè)

p(zt|xt)p(xt|z1:t-1，u0:t-1)p(zt|z1:t-1)=

η標準化因子p(zt|xt)測量方程Bel-(xt)先驗信度(4)

其中:標準化因子η-1=p(zt|z1:t-1)=∫p(zt|xt)p(xt|z1:t-1，u0:t-1)dxt。

粒子濾波是貝葉斯濾波的變種，它采用Ns個隨機加權(quán)的樣本集合{xit，wit}i=1，…，Ns來近似表征后驗概率密度函數(shù)p(xt|z1:t)=∑Nsi=1witδ(xt-xit)。因而，式(3)中求解Bel-(xt)的積分運算可以轉(zhuǎn)換為樣本的求和運算，即

Bel-(xt)=∑Nsi=1p(xt|xit-1，ut-1)Bel(xt-1)=

∑Nsi=1witδ(xt-xit)Bel(xt-1)(5)

其中:δ(#8226;)表示Dirac delta函數(shù)，權(quán)重滿足歸一化條件∑Nsi=1wit=1。當Ns→∞時，利用式(4)(5)的樣本可以近似達到真實后驗分布p(xt|z1:t，u0:t-1)。

PF算法開始時從初始信度p(x0)采樣，接著對每個時間步執(zhí)行預測—更新—重采樣遞歸循環(huán)過程。式(6)為形式化PF的執(zhí)行步驟，它源于應(yīng)用Beyes規(guī)則到后驗概率中，接著使用Markov假設(shè)，該公式從右到左執(zhí)行。

p(xt|z1:t，u0:t-1)當前的PDF重采樣=

η標準化因子p(zt|xt)測量方程更新

∫p(xt|xt-1，ut-1)狀態(tài)方程p(xt-1|z1:t-1，u0:t-2)先前的PDFdxt-1預測(6)

1.2 存在的問題

現(xiàn)有的粒子濾波算法大多使用固定大小的樣本數(shù)目[2]，這顯然非常低效，但是樣本數(shù)目增大在導致近似誤差減少的同時增加了計算復雜度。文獻[1]指出，樣本數(shù)目與狀態(tài)空間維數(shù)、建議分布與后驗分布的重合程度、規(guī)定的時間步長有關(guān)。

重采樣技術(shù)是為了解決SIS算法的退化而引入的，但是重采樣不僅引入了額外的蒙特卡羅誤差，而且可能導致樣本多樣性喪失出現(xiàn)樣本耗盡問題。針對這些問題，一種解決途徑就是限制重采樣的次數(shù)，以避免在不確定條件下濾波太快地收斂到最大似然狀態(tài)，但是過少的重采樣將導致濾波器發(fā)散。

建議分布(也稱重要性密度)q(#8226;)是指概率分布與p相同，概率密度分布已知且容易采樣的分布函數(shù)。由于很難直接從后驗概率分布p(xt|z1:t，u0:t-1)(簡寫為p)采樣，樣本采集需要借助建議分布q來實現(xiàn)。選擇一個好的建議分布能夠有效地防止樣本退化。在一些粒子濾波的應(yīng)用中，運動模型p(xt|xt-1，ut)被用做建議分布在粒子濾波預測步中執(zhí)行采樣;此外，似然模型p(zt|xt)在粒子濾波更新步中起著重要的作用。因而，針對運動/似然模型提出的自適應(yīng)機制有運動模型自適應(yīng)以及似然模型自適應(yīng)。

針對PF固有的缺陷及不足，可以考慮集成其他方法來改進。針對引入重采樣技術(shù)所造成的樣本多樣性的喪失，目前粒子濾波研究的一個方向是與進化機制相結(jié)合來改善樣本集的多樣性。針對狀態(tài)自身的不確定性，自適應(yīng)產(chǎn)生的新樣本可能具有較低的權(quán)重，因而模糊自適應(yīng)粒子濾波也被提出。

2 關(guān)鍵技術(shù)研究

在對整個狀態(tài)空間處理過程中，概率密度可能會隨時間的變化發(fā)生巨大改變。在粒子濾波中引入自適應(yīng)機制，可以改進粒子濾波執(zhí)行和計算的有效性，從而有效地降低誤差。

2.1 樣本數(shù)目自適應(yīng)

目前還沒有方法定量地確定樣本數(shù)目，已提出的自適應(yīng)調(diào)整樣本數(shù)目的方法有Koller等人[14]提出的基于似然度自適應(yīng)法、Fox[15]提出的KLD采樣法、Karlsson等人[16]提出的樣本數(shù)目控制器、段琢華等人[17]提出的復合樣本數(shù)目自適應(yīng)調(diào)整方法。

1)基于似然度的自適應(yīng)方法 粒子濾波算法在重采樣時，由于只有現(xiàn)有的樣本作為下個采樣周期的基礎(chǔ)，沒有開采樣本空間新的部分。為了從樣本空間未采樣的區(qū)域產(chǎn)生樣本，Koller等人[14]提出了基于似然度的樣本數(shù)目自適應(yīng)方法(likelihood-based adaptation)。該方法利用觀測的似然度p(zt|xt)來決定樣本數(shù)目，即所需的粒子數(shù)應(yīng)能保證非歸一化似然度的和超過某一預定的門限。相對于固定樣本數(shù)目的粒子濾波，基于似然度的自適應(yīng)方法顯示了其優(yōu)越性，并已應(yīng)用于動態(tài)貝葉斯網(wǎng)絡(luò)[14]、移動機器人定位[18]、目標跟蹤[19]。但是，由于基于似然度的自適應(yīng)方法直接與重要性樣本的方差屬性關(guān)聯(lián)，也即重要性樣本的方差是建議分布與目標分布的誤匹配函數(shù)，對于高似然性的環(huán)境或?qū)ΨQ性的環(huán)境而言，該方法將失效。

2)KLD采樣方法 Fox等人[18]首先將基于似然度的自適應(yīng)方法應(yīng)用于移動機器人定位中，在此研究基礎(chǔ)上又提出了KLD采樣方法(Kullback-Leiber divergence sampling)[15，20，21]。KLD采樣方法是樣本數(shù)目自適應(yīng)中的主流方法，通過假定真實后驗是離散、分段、恒定的分布諸如離散密度樹或多維的直方圖，引進KL距離K(p，q)=∑xp(x)log(p(x)/q(x))來評估基于采樣的最大似然估計p與真實后驗分布q之間的概率密度差異。如果選擇樣本數(shù)為N=(1/2ε)χ2k-1，1-δ，則近似分布與真實分布的KL距離以1-δ的概率小于或等于ε。其中，χ2k-1，1-δ表示具有k-1個自由度的卡方分布的1-δ分位數(shù)。KLD采樣方法已用于動態(tài)貝葉斯網(wǎng)絡(luò)[22]、移動機器人定位[20，23~26]。

KLD采樣方法使用經(jīng)驗分布推導誤差邊界，隱含地假設(shè)樣本從真實分布抽取。盡管考慮了有關(guān)真實后驗分布復雜性的信息，卻沒有考慮真實與建議分布之間的差異。為克服這一問題，Soto對KLD采樣方法進行了改進[27]。其核心思想是計算從建議分布采樣的樣本數(shù)目NIS，使得其與從真實分布采樣(蒙特卡羅采樣)的樣本數(shù)目N有相同的近似精度，即NIS=σ2ISvar(x)#8226;12εχ2k-1，1-δ。其中:σIS和var(x)使用蒙特卡羅積分估計。

3)樣本數(shù)目控制器 與KLD采樣方法不同，Karlsson等人[16]根據(jù)不同樣本數(shù)目的兩個粒子濾波器表示的近似分布之間的差異，在重采樣步利用樣本數(shù)目控制器(particle number controller)對樣本數(shù)目進行調(diào)整。這種差異利用粒子濾波器的某種統(tǒng)計量的差異εt=‖μ(1)t-μ(2)t‖來刻畫，如均值、概率密度函數(shù)(probability density function)及累積密度函數(shù)(cumulative density function)。其代價是一個額外的粒子濾波器的時間以及空間開銷。

4)復合樣本數(shù)目自適應(yīng)調(diào)整方法 結(jié)合KLD采樣方法和樣本數(shù)目控制器，段琢華等人[17]提出一種復合粒子數(shù)目自適應(yīng)調(diào)整方法。其基本思想為在重采樣階段抽取樣本數(shù)目不同的兩個樣本集(代表同一分布的兩種近似)，根據(jù)兩個近似分布的KL距離自適應(yīng)地調(diào)整粒子數(shù)目。若KL 距離較大，則增加粒子數(shù)目，反之則減少粒子數(shù)目。該方法有以下兩方面的改進:a)不增加額外的粒子濾波器，而是額外地抽取一個粒子數(shù)目不同的粒子集;b)利用粒子數(shù)目不同的兩個粒子集表示近似分布的KL 距離描述兩者的差異。

2.2 重采樣自適應(yīng)

目前，針對重采樣提出的自適應(yīng)機制有:Doucet等人提出的基于有效樣本大小的重采樣自適應(yīng)[6，28~30]、Lenser等人提出的基于傳感器的重采樣自適應(yīng)[31，32]、梁志偉等人提出的基于歸一化前后權(quán)重校驗的重采樣自適應(yīng)[33]。

1)基于有效樣本大小的重采樣自適應(yīng) 由于頻繁/過少重采樣均會出現(xiàn)負面效應(yīng)，為保證能夠有合適的重采樣次數(shù)，Liu提出了有效樣本大小(efficient sample size，ESS)的概念[47]。基于有效樣本大小ESS估計值N^eff，Doucet等人[6]提出了重采樣自適應(yīng)，也即N^eff小于固定閾值Nth，則在SIS算法中執(zhí)行重采樣，否則不執(zhí)行。該方法在機器人領(lǐng)域得到了有效的應(yīng)用[28，29]。

ESS考慮樣本權(quán)重的分布，卻沒有考慮PF中樣本可能相同。為處理這一問題，濃縮有效樣本數(shù)(condensed number of effective particles)Neffc被提出[30]。Neffc定義為Neff(Pc)，其中Pc表示對于樣本集P中相同樣本只有一個備份的樣本集，且wci=∑j s.t. pi-pjwj。

2)基于傳感器的重采樣自適應(yīng) Lenser等人[31]提出了基于傳感器的重采樣技術(shù)(sensor based resampling)，其基本思想是場所樣本的平均概率是與那些覆蓋機器人真實位置空間的場所樣本成比例的。如果樣本表示的場所概率小于來自傳感器的讀數(shù)，那么這些樣本將重新對傳感器的概率密度p(zt|xt)進行采樣。在此基礎(chǔ)上計算新樣本數(shù)目ns=n×max(0，1-/pth)。其中:=∑ip(zi|xi)/n是所有樣本基于觀測值的概率均值;n是樣本數(shù)目;pth是人為設(shè)定的閾值。

在此研究基礎(chǔ)上，高慶吉等人[32]提出了自適應(yīng)感知復位定位算法(adaptive sensor resetting localization，ASRL)，并將pth改為μp2mt，m表示觀測信息的數(shù)量，μ為調(diào)整系數(shù)，pt是人為設(shè)定閾值。當>μp2mt時，不產(chǎn)生樣本;當≤μp2mt時，從p(zt|xt)的概率分布中抽樣替代原樣本集中的一些樣本。

3)基于歸一化前后權(quán)重校驗的重采樣自適應(yīng) 梁志偉等人[33]提出了一種分布式感知協(xié)作的擴展Monte Carlo定位方法。該方法在感知更新后，對于未歸一化和歸一化后的權(quán)重進行如下兩個檢驗過程，以采用不同的重采樣方法進行位姿的估計:

a)歸一化后權(quán)重的過收斂檢驗過程。不管信息熵如何變化，當有效樣本大小ESS低于某一閾值時(采樣數(shù)目的百分比k)，則引入新采樣的數(shù)目為n=C(N-ESS)，其中C為常數(shù);否則，當信息熵的變化量超過一定的閾值，就需要引入新的采樣，引入新采樣的數(shù)目為n=(1-λ)(N-ESS)。其中λ為(0，1)內(nèi)的數(shù)。

b)未歸一化權(quán)重的均勻性檢驗過程。由于預測更新后的采樣為均勻分布，而感知更新過程只是重新對采樣賦權(quán)重，因此權(quán)重之和為W=(1/Nt)∑Nti=1p(zt|x(i)t)。W小于設(shè)定的閾值Wth表明采樣集與感知信息的偏差較大，設(shè)置重采樣數(shù)目為整個采樣集數(shù)目，并利用環(huán)境傳感器的檢測模型進行重采樣;否則，表明當前采樣分布為位姿分布的較好估計，執(zhí)行重要性重采樣過程。

2.3 建議分布自適應(yīng)

目前，針對建議分布提出的自適應(yīng)機制有West[34]提出的根據(jù)樣本信息逐步修正的建議分布自適應(yīng)、Gresetti等人[28]提出的高斯近似建議分布自適應(yīng)、Beeson等人[35]提出的收縮/增長建議分布自適應(yīng)以及結(jié)合其他方法的建議分布自適應(yīng)[36，37]。

1)根據(jù)樣本信息逐步修正的建議分布自適應(yīng) West[34]提出了一種根據(jù)樣本信息逐步修正建議分布的自適應(yīng)方法。其基本思路為:a)選擇一個初始建議分布g0(θ)，采樣n0個樣本并計算其權(quán)重，樣本信息為Γ0={g0，n0，Θ0，Ω0}。其中:Θ0={θ0，j，j=1，…，n0}為樣本集合;Ω0={w0，j，j=1，…，n0}為對應(yīng)樣本的權(quán)重。計算p(θ)均值和方差的估計值0和V0。b)構(gòu)造修改的建議分布g1(θ)=∑n0j=1w0，jd(θ|θ0，j，V0h2)。其中d(θ|m，M)表示模式為m、尺度矩陣為M的變量橢圓對稱密度函數(shù)。通過g1(θ)采樣更大數(shù)目n1的樣本，用Γ1={g1，n1，Θ1，Ω1}代替Γ0。據(jù)此類推，根據(jù)需要進一步修改建議分布。該方法不足在于計算開銷大，且會導致復雜的混合分布。

2)高斯近似建議分布自適應(yīng) 建議分布的最優(yōu)選擇和樣本權(quán)重的方差相關(guān)[48]，Gresetti等人[28]據(jù)此提出高斯近似建議分布自適應(yīng)方法。考慮機器人利用激光雷達進行環(huán)境建模時，似然函數(shù)p(zt|m(i)t-1，xt)決定p(zt|m(i)t-1，xt)p(xt|x(i)t-1，ut)。這里利用步長L(i)={x|p(zt|m(i)t-1，x)>ε}決定的常量k近似p(xt|x(i)t-1，ut)。采用高斯近似建議分布的最大似然函數(shù)p(xt|m(i)t-1，x(i)t-1，zt，ut)N(μ(i)t，Σ(i)t)。在這種近似下，可以獲得最適合采樣的形式。對于每個樣本，μ(i)t、Σ(i)t可以通過評估樣本集的最大似然函數(shù)獲得，樣本集中的樣本{xj}對應(yīng)掃描匹配中的局部最大化。對于每個樣本都執(zhí)行μ(i)t和Σ(i)t的計算以及掃描匹配過程，樣本{xj}被選擇來覆蓋依靠里程計最新讀數(shù)不確定的區(qū)域xj∈{xt|p(xt|xt-1，ut)>χ}，密度依靠地圖的精度。

3)收縮/增長建議分布自適應(yīng) 在此研究基礎(chǔ)之上，Beeson等人[35]提出兩種方法來實現(xiàn)建議分布自適應(yīng):a)收縮建議分布。當建議分布過高估計真實后驗分布的方差，通過利用由Grisetti等人[28]提出的建議分布自適應(yīng)方法來實現(xiàn)較好的定位。為了獲得新的建議的最佳形式，基于似然峰值的分布利用高斯進行近似，高斯分布的均值和方差利用加權(quán)樣本的均值和方差來評估，其中樣本從原始建議中采樣，利用規(guī)格化似然進行加權(quán)。b)增長建議分布。當建議分布過低評估真實后驗分布，通過似然度分值，即非規(guī)格化權(quán)重p(o|x′j，m)確定如何增長建議分布來搜索高似然度。通過設(shè)置最大似然度分值的較低閾值，如果所有似然度分值小于該閾值，通過增加當前建議分布三個維度的標準方差σ的2~5倍產(chǎn)生新的建議分布。

4)結(jié)合其他方法的建議分布自適應(yīng) 針對UKF(unscen-ted Kalman filter)作為建議分布進行狀態(tài)估計的缺點，鄧小龍等人[36]通過融合UKF和強跟蹤濾波器STF(strong tracking filter)提出一種新的自適應(yīng)建議分布。該方法通過UKF構(gòu)造粒子群，粒子群中每個粒子的每個抽樣樣本點(Sigma點)用STF來更新，即用STF算法在線調(diào)節(jié)因子來相應(yīng)調(diào)整濾波增益，從而使算法具有自適應(yīng)性。

針對SIR算法從建議分布中采樣時沒有考慮當前觀測值的不足，結(jié)合Pitt等人[49]的輔助粒子濾波(auxiliary particle filter)算法，Cornebise等人[37]通過考慮當前觀測前后的輔助建議分布μauxN和改進建議分布πauxN之間的KLD或卡方(Chi-square distance，CSD)距離最小化來實現(xiàn)建議分布自適應(yīng)，即|dKL(μauxN‖πauxN)-ε({N，i}Ni=1)|→0，|dχ2(μauxN‖πauxN)-CV2({N，i}Ni=1)|→0。其中，ε(#8226;)和CV2(#8226;)分別表示其經(jīng)驗估計值，N，i表示標準化權(quán)重。

2.4 運動/似然模型自適應(yīng)

1)運動模型自適應(yīng) Milstein等人[38]針對路面的變化對運動模型造成的誤差進行分析，獲得運動模型的方差參數(shù)來動態(tài)更新運動模型。將差分驅(qū)動的移動機器人的運動模型依靠三個參數(shù)標志，即距離誤差、轉(zhuǎn)動誤差和漂移誤差(kr，kθ，kd)。用r、θ分別表示增量距離與轉(zhuǎn)角，r、θ則表示依據(jù)運動模型獲得的預測值，那么運動模型的誤差分布表示為r=N(r，kr#8226;r)，θ=N(θ，kθ#8226;θ+kd#8226;r)，其中每個分布都是單一高斯分布。在MCL中通過給定一組r、θ，r、θ來優(yōu)化運動模型誤差參數(shù)(kr，kθ，kd)。

Kaboli等人[39]依據(jù)Bayesian方法，提出了MCL中運動和傳感器模型的自調(diào)整方法。首先利用專家知識編碼進行模型參數(shù)的先驗分布，給出訓練數(shù)據(jù)D=(u1:t，z1:t)和模型參數(shù)的先驗分布Pr(θ)，目標就是從機器人采集的數(shù)據(jù)中計算相對應(yīng)模型參數(shù)的后驗分布Pr(θ|D);利用混合MCMC(Markov chain Monte Carlo)過程對模型后驗分布實現(xiàn)精確的模型參數(shù)采樣θi。對于采集到的模型樣本θi，利用樣本均值θmean和最大化后驗樣本θMAP作為參數(shù)矢量來構(gòu)建后驗運動模型和傳感器模型。

Lee[40]提出一種運動模型過程噪聲自適應(yīng)UKF方法。假設(shè)t時刻狀態(tài)st的均值t和方差Pt，運動模型p(st|st-1，ut-1)=F(st-1，ut-1)+W(t)的隨機噪聲W(t)服從高斯分布(0，Qt)，初始化狀態(tài)變量及協(xié)方差矩陣，設(shè)置自適應(yīng)因子factoranneal以及過程噪聲Qt允許的最小方差minQt，sαt=[st]，Pαt=PtPswtPswtQt。其中Pswt是狀態(tài)評估誤差和過程噪聲間的關(guān)聯(lián)方差。利用自適應(yīng)算法對于過程噪聲Qt進行自適應(yīng)預測評估Q^+t+1=max(factoranneal×Q^-t+1，minQt)。其中Q^-t+1表示t+1時刻的狀態(tài)噪聲協(xié)方差的期望值。

2)似然模型自適應(yīng) Pfaff等人[41]認為似然模型p(z|x)在粒子濾波更新步中起著重要的作用，通過研究提出動態(tài)似然模型方法。a)基于距離傳感器建立似然模型，其核心思想是混合使用四種不同的建議分布來近似距離傳感器的噪聲和誤差特性:使用高斯分布phit(z|d)對在測量方向上鄰近物體的激光束的似然度建模;使用一致分布prand(z|d)表示隨機測量;使用指數(shù)分布pshort(z|d)對地圖中沒有的物體或者不同傳感器間交互作用進行建模;使用一致分布pmax(z|d)表示最大測距造成的檢測誤差。這四種建議分布進行加權(quán)平均，且加權(quán)系數(shù)需要滿足一定的約束條件。b)自適應(yīng)調(diào)整服從高斯概率分布phit(z|d)的方差，其核心思想是對k-近鄰障礙的密度進行評估時利用自適應(yīng)方差測量，實現(xiàn)每個樣本i覆蓋空間的近似計算。

2.5 結(jié)合其他機制的自適應(yīng)方法

1)自適應(yīng)進化粒子濾波 厲茂海等人[42]提出了基于自適應(yīng)進化策略的粒子濾波:將p(zt|xt)定義為適應(yīng)度函數(shù)，利用進化操作中的交叉和變異對樣本表示的系統(tǒng)狀態(tài)進行優(yōu)化，并采用Metropolis算法確保經(jīng)過進化的粒子仍能準確近似后驗。其中，交叉和變異操作分別以概率pc和pm自適應(yīng)進行，當個體適應(yīng)度趨于一致或趨于局部最優(yōu)時，pc和pm增加;當適應(yīng)度比較分散時，令pc和pm減少。

Duan等人[43]將變異算子引入自適應(yīng)粒子濾波器，構(gòu)造自適應(yīng)進化粒子濾波器算法。其主要思想為根據(jù)樣本的未歸一化權(quán)重調(diào)整變異參數(shù)。首先從{x[i]t，w[i]t}Ni=1重采樣N個粒子{[i]t，1/N}Ni=1。設(shè)粒子[i]t從x[j]t采樣得到，x[j]t的非規(guī)格化權(quán)為w[j]tWt(規(guī)格化因子乘以規(guī)格化權(quán)重)，[i]t通過以下步驟變異:x^[i]t~N([i]t，(σxt)2)，y^[i]t~N([i]t，(σyt)2)，θ^[i]t~N([i]t，(σθt)2)。其中，變異參數(shù)σxt、σyt、σθt設(shè)置為σxt=cx(1-Wtw[j]t)，σyt=cy(1-Wtw[j]t)，σθt=cθ(1-Wtw[j]t)，cx、cy、cθ為常量因子。

2)模糊自適應(yīng)粒子濾波 Duan等人[44]針對移動機器人航跡推算系統(tǒng)傳感器故障診斷問題，提出了一種模糊自適應(yīng)粒子濾波器方法。首先利用模糊邏輯表示領(lǐng)域知識，根據(jù)領(lǐng)域知識將狀態(tài)空間自適應(yīng)地約束到全狀態(tài)空間的某一模糊子集。移動機器人可能處于靜止(M1)、直線運動(M2)、繞左輪轉(zhuǎn)動(M3)、繞右輪轉(zhuǎn)動(M4) 及其他轉(zhuǎn)動模式(M5)。采用模糊集合表示移動機器人的運動狀態(tài)，并定義其相應(yīng)的隸屬度函數(shù)μm。結(jié)合上述領(lǐng)域知識計算條件轉(zhuǎn)移概率p(st+1=j|st=i，uLt，uRt)。此后結(jié)合前面提出的復合樣本數(shù)目自適應(yīng)方法[17]，構(gòu)造了一種模糊自適應(yīng)粒子濾波方法。

Kim等人[45]提出一種模糊自適應(yīng)粒子濾波方法。該方法通過利用觀測的概率密度函數(shù)，結(jié)合模糊邏輯方法計算其梯度信息，沿著梯度遞減方向在高似然區(qū)域基于似然度的自適應(yīng)方法產(chǎn)生新樣本。首先定義觀測的概率密度函數(shù)的梯度信息Δq=q(xt)-q(xt-1);接著利用模糊邏輯方法產(chǎn)生新樣本xi+Nt=xit+αγ。其中:α表示步長參數(shù);N表示粒子濾波器在t時刻的樣本數(shù);γ表示依據(jù)模糊規(guī)則定義的輸出變量，該規(guī)則的輸入變量分別是當前觀測的概率密度函數(shù)q(xt)和梯度函數(shù)Δq。

石旭生等人[46]根據(jù)量測信息實時地重新調(diào)整粒子數(shù)，通過監(jiān)測殘差來驗證濾波器是否工作得很好。殘差定義為rt=zt-t。其中zt和t為t時刻實際的測量值和濾波器估計的值。估計的平均誤差eM，t=1M∑ti=t-M+1rTiri，通過調(diào)整粒子數(shù)的大小來使定義的平均誤差最小。基于模糊邏輯的自適應(yīng)粒子濾波主要思想是動態(tài)地調(diào)整N，使得實際的測量和濾波后得到的測量值估計之間的殘差減少，如果殘差處于一個預先設(shè)定好的取值范圍內(nèi)，濾波器工作得很好，則不需要改變N值。如果殘差大于期望值時，則增大N值;另一方面，如果估計誤差小于一個閾值，則減少N值。

3 總結(jié)與展望

針對PF算法樣本退化及枯竭問題，引入自適應(yīng)機制可改進執(zhí)行和計算的有效性從而降低計算誤差。自適應(yīng)PF算法已經(jīng)成為當前的研究熱點，但也存在著一些亟待解決的問題。

a)收斂性問題。算法實現(xiàn)中收斂與否的正確判斷以及用嚴格的數(shù)學方法給出其結(jié)論，此外，算法對狀態(tài)評估要求具有一定的收斂速度。目前的研究成果對于算法收斂提供了一定的理論依據(jù)[50~52]:建議分布幾乎肯定收斂于后驗概率;狀態(tài)估計均方誤差的收斂性。但是要求的條件依然很強，只有樣本數(shù)目Np隨時間增加而增加或者濾波器有能力忘記指數(shù)級增長的誤差，算法的一致收斂才能確保。目前，關(guān)于收斂性研究大多集中于非線性濾波的誤差極限研究上。關(guān)于這方面的研究還有待進一步深入下去。

b)實時性問題。實時處理主要考慮的是傳感器的高速數(shù)據(jù)率與處理器的有限處理能力的矛盾。因計算時間和粒子數(shù)目直接相關(guān)，故該問題也可歸結(jié)為如何在估計精度和粒子數(shù)之間作適當折中。針對基于樣本數(shù)目自適應(yīng)的PF算法計算量繁重的問題，文獻[53，54]初步探討了如何處理濾波器更新速率小于傳感器采樣速率，以及如何自適應(yīng)樣本數(shù)目以便最優(yōu)化計算資源等問題。在實際應(yīng)用中，尤其遭遇尺度問題時，即空間緯度Nx成百上千地遞增時如何維持合適的計算時間，使估計精度滿足要求，仍有待于今后深入的研究。

c)魯棒性問題。由于在每個遞歸過程中樣本的不精確性，累積誤差可能呈指數(shù)級增加。對于SIS或SIR濾波器而言，偏差和方差都將隨著時間增加而增加。這使得算法的魯棒性話題極為重要。相關(guān)研究結(jié)果[55]顯示，即使混合建議分布也不能較好地處理目標分布的長尾行為，異常可能造成濾波器發(fā)散或產(chǎn)生較差的濾波性能。魯棒性改進的關(guān)鍵就是魯棒的建議或似然模型的建立。如何在線自適應(yīng)評估更精確的非線性，動態(tài)模型和系統(tǒng)噪聲特性，值得進一步研究。這可以與相關(guān)性評估和統(tǒng)計學習一些嚴格的理論結(jié)果關(guān)聯(lián)，如度量熵、信息復雜度等。

d)如何選擇有效樣本大小依舊缺乏嚴格的理論證明。有效樣本數(shù)目依靠所選擇的建議分布，好的建議分布其誤差隨著樣本數(shù)目Np的增加呈線性變化減小到零;差的建議分布則無論樣本數(shù)目Np多大，誤差均會隨著空間維度Nx呈指數(shù)級增加[56]。此外，如何將其他方法與自適應(yīng)機制集成以及將多種自適應(yīng)機制結(jié)合仍然值得探討。通過定性分析多種方法集成以及各種方法之間的相互影響、定量分析參數(shù)設(shè)置對效率和精度的影響，以期有效地提高算法的精度和效率。

參考文獻:

[1]GORDON N J， SALMOND D J， SMITH A F M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation[J]. IEEE Proceedings on Radar and Signal Processing， 1993， 140(2):107-113.

[2]DELLAERT F， BURGARD W， FOX D， et al. Monte Carlo localization for mobile robots[C]//Proc of IEEE International Conference on Robotics and Automation. Detroit: IEEE Press， 1999: 1322-1328.

[3]SCHULZ D， BURGARD W， FOX D， et al. Tracking multiple mo-ving targets with a mobile robot using particle filters and statistical data association[C]//Proc of IEEE International Conference on Robo-tics and Automation. Seoul， Korea: IEEE Press， 2001:1665-1670.

[4]MONTEMERLO M， THRUN S， KOLLER D， et al. FastSLAM: a factored solution to simultaneous localization and mapping problem[C]//Proc of the National Conference on Artificial Intelligence. Edmonton， Canada: AAAI Press， 2002:593-598.

[5]VERMA V， GORDON G， SIMMONS R， et al. Particle filters for ro-ver fault diagnosis[J]. IEEE Robotics Automation Magazine Special Issue on Human Centered Robotics and Dependability， 2004， 11(2):1-4.

[6]DOUCET A， GODSILL S J， ANDRIEU C. On sequential Monte Carlo sampling methods for Bayesian filtering[J]. Statistics and Computing， 2000， 10(3):197-208.

[7]ARULAMPALAM M S， MASKELL S， GORDON N， et al. A tutorial on particle filters for online nonlinear/non-GaussianBayesian tracking[J]. IEEE Trans on Signal Processing， 2002， 50(2):174-188.

[8]CHEN Z. Bayesian filtering: from Kalman filters to particle filters， and beyond[R]. Hamilton: McMaster University， 2003.

[9]胡士強， 敬忠良. 粒子濾波算法綜述[J]. 控制與決策， 2005， 20(4):361-365， 371.

[10]夏克寒， 許化龍， 張樸睿. 粒子濾波的關(guān)鍵技術(shù)及應(yīng)用[J]. 電光與控制， 2005， 12(6):1-4， 19.

[11]楊小軍， 潘泉， 王睿， 等. 粒子濾波進展與展望[J]. 控制理論與應(yīng)用， 2006， 23(2):261-267.

[12]于金霞， 蔡自興， 段琢華. 基于粒子濾波的移動機器人定位關(guān)鍵技術(shù)研究綜述[J]. 計算機應(yīng)用研究， 2007， 24(11):9-14.

[13]程水英， 張劍云. 粒子濾波綜述[J]. 宇航學報， 2008， 29(4):1099-1111.

[14]KOLLER D， FRATKINA R. Using learning for approximation in stochastic processes[C]//Proc of the 15th International Conference on Machine Learning. San Francisco:Morgan Kaufmann Publishers， 1998:287-295.

[15]FOX D. KLD-sampling:adaptive particle filters[J]. Advances in Neural Information Processing Systems， 2001， 14(1):713- 720.

[16]KARLSSON R， GUSTAFSSON F. Monte Carlo data association for multiple target tracking[C]//Proc of IEEE Colloquium on Target Tracking: Algorithms and Applications. 2001:1-5.

[17]段琢華， 蔡自興， 于金霞. 移動機器人軟故障檢測與補償?shù)淖赃m應(yīng)粒子濾波算法[J]. 中國科學E輯: 信息科學， 2008， 38(4):565-578.

[18]FOX D， BURGARD W， DELLAERT F， et al. Monte Carlo localization: efficient position estimation for mobile robots[C]//Proc of the 16th National Conference on Artificial Intelligence. Orlando:AAAI Press， 1999: 343-349.

[19]BOLIC M， SANGJIN H， DJURIC P M. Performance and complexity analysis of adaptive particle filtering for tracking applications[C]//Proc of the 16th Asilomar Conference on Signals， Systems ， and Computers. Asilomar: IEEE Press， 2002:853-857.

[20]FOX D. KLD-sampling: adaptive particle filters and mobile robot localization[J]. Advances in Neural Information Processing Systems， 2001，14(1):26-32.

[21]FOX D. Adapting the sample size in particle filters through KLD-sampling [J]. International Journal of Robotic Research， 2003， 22(12):985-1003.

[22]陳棟梁， 王浩， 姚宏亮， 等. 基于自適應(yīng)粒子濾波的動態(tài)貝葉斯網(wǎng)推理算法[J]. 計算機應(yīng)用， 2007， 27(2): 369-372.

[23]JIANG Zheng-wei， GU Yuan-tao. Novel adaptive particle filters in robot localization[J]. Acta Automatica Sinica， 2005， 31(6):833-838.

[24]方正， 佟國峰， 徐心和. 一種魯棒高效的移動機器人定位方法[J]. 自動化學報， 2007，33(1):48-53.

[25]張恒， 樊小平， 瞿志華. 基于多假設(shè)跟蹤的移動機器人自適應(yīng)蒙特卡羅定位研究[J]. 自動化學報， 2007，33(9):941-946.

[26]XIA Yi-min， YANG Yi-min. Mobile robot localization method based on adaptive particle filter[C]//Lecture Notes in Artificial Intelligence. Berlin:Springer， 2008:963-972.

[27]SOTO A. Self adaptive particle filter[C]//Proc of International Joint Conference on Artificial Intelligence. Edinburgh， Scotland: Professional Book Center， 2005:1398-1406.

[28]GRISETTI G， STACHNISS C， BURGARD W. Improving grid-based SLAM with Rao-Blackwellized particle filters by adaptive proposals and selective resampling[C]//Proc of IEEE International Conference on Robotics and Automation. Barcelona， Spain: IEEE Press， 2005:2443-2448.

[29]LI Mao-hai， HONG Bing-rong， CAI Ze-su， et al. Novel Rao-Blackwellized particle filter for mobile robot SLAM using monocular vision[J]. International Journal of Intelligent Technology， 2006， 1(1):63-69.

[30]SULIVAN J， CAMPBELL M， LIPSON H. Particle filters as exploration tools for autonomous rovers[C]//Proc of the AIAA Guidance， Navigation and Control Conference. San Francisco: AIAA Press， 2005:6447-6458.

[31]LENSER S， VELOSO M. Sensor resetting localization for poorly mo-delled mobile robots[C]//Proc of IEEE International Conference on Robotics and Automation. San Francisco:IEEE Press， 2000:1225-1232.

[32]高慶吉， 雷亞莉， 胡丹丹， 等. 基于自適應(yīng)感知復位算法的移動機器人定位[J]. 電子學報， 2007， 35(11):2166-2171.

[33]梁志偉， 馬旭東， 戴先中. 分布式感知協(xié)作的擴展Monte Carlo定位算法[J]. 機器人， 2008， 30(3): 210-216.

[34]WEST M. Mixture models， Monte Carlo， Bayesian updating and dynamic models[J]. Computing Science and Statistics， 1993， 24:325-333.

[35]BEESON P， MURARKA A， KUIPERS B. Adapting proposal distributions for accurate， efficient mobile robot localization[C]//Proc of IEEE International Conference on Robotics and Automation. Orlando:IEEE Press， 2006:49-55.

[36]鄧小龍， 謝劍英， 郭為忠. 用于狀態(tài)估計的自適應(yīng)粒子濾波[J]. 華南理工大學學報:自然科學版， 2006， 34(1):57-61.

[37]CORNEBISE J， MOULINES E， OLSSON J. Adaptive methods for sequential importance sampling with application to state space models[J]. Statistics and Computing， 2008，18(4):461-480.

[38]MILSTEIN A， WANG T. Localization with dynamic motion models-determining motion model parameters dynamically in Monte Carlo localization[C]//Proc of the 3rd International Conference on Informa-tics in Control， Automation and Robotics. 2006:120-127.

[39]KABOLI A， BOWLING M， MUSILEK P. Bayesian calibration for Monte Carlo localization[C]//Proc of the 21st National Conference on Artificial Intelligence. Boston:AAAI Press， 2006:964-969.

[40]LEE D J. Nonlinear Bayesian filtering with applications to estimation and navigation[D]. Texas: Texas AM University， 2005.

[41]PFAFF P， BURGARD W， FOX D. Robust Monte-Carlo localization using adaptive likelihood models[C]//Proc of European Robotics Symposium. Berlin:Springer， 2006:181-194.

[42]厲茂海， 洪炳熔， 羅榮華. 用改進的Rao-Blackwellized粒子濾波器實現(xiàn)移動機器人同時定位和地圖創(chuàng)建[J]. 吉林大學學報:工學版， 2007， 37(2):401-406.

[43]DUAN Zuo-hua， CAI Zi-xing. Evolutionary particle filter for robust simultaneous localization and map building with laser range finder[C]//Proc of the 4th International Conference on Natural Computation. Washington DC:IEEE Computer Society， 2008:443-447.

[44]DUAN Zuo-hua， CAI Zi-xing， YU Jin-xia. Fuzzy adaptive particle filter algorithm for mobile robot fault diagnosis[C]//Proc of the 13th International Conference on Neural Information Processing. Heidelberg:Springer， 2006:711-720.

[45]KIM Y J， WON C H， PARK J M， et al. Fuzzy adaptive particle filter for a positioning beacon system[C]//Proc of International Conference on Control， Automation and Systems. Seoul， Korea: IEEE Press， 2007:1198-1202.