基于知識板的協同粒子濾波算法

王雁鵬，王 磊，鄒 鋒，錢新橋

?

基于知識板的協同粒子濾波算法

王雁鵬，王 磊，鄒 鋒，錢新橋

(西安理工大學計算機科學與工程學院，西安 710048)

在當前的粒子濾波中，粒子可能出現退化現象和重采樣，導致樣本枯竭從而破壞粒子多樣性。針對該問題，借鑒知識板和協同進化理論，提出一種基于知識板的協同粒子濾波算法。該算法對重要性密度函數進行采樣，形成采樣粒子樣本，并將粒子劃分為若干個子采樣粒子群，對每個子采樣粒子群在不同的區域進行搜索，通過子采樣粒子群之間的通信，最終找到動態系統的最佳狀態估計。理論分析與仿真結果表明，該算法能提高經典粒子濾波算法的群體多樣性，在加快收斂速度和降低計算復雜度方面有較大優勢。

粒子濾波；多樣性；知識板；協同；采樣；優化

1 概述

20世紀60年代末自動控制領域引入粒子濾波(Particle Filtering, PF)方法并在70年代得到發展[1-2]。PF是基于Monte Carlo方法和Bayes估計理論，但粒子濾波有粒子退化現象[3]。1993年，Gordon等人提出自舉粒子濾波(bootstrap particle filtering)算法，該算法引入重新采樣的思想[4]。

粒子濾波技術在非線性[5]、非高斯系統表現出來的優越性，決定了它的應用范圍非常廣泛。另外粒子濾波器[6]的多模態處理能力，是它應用廣泛的原因之一。國際上粒子濾波已被應用于各個領域。在經濟學領域它被應用在經濟數據預測；在交通管制領域它被應用在對車或人視頻監控；另外，它還用于機器人的全局定位、協同跟蹤等領域[7]。

粒子濾波由于采用了重新采樣的思想，能夠在一定程度上緩和粒子退化的加劇及無效粒子的增加，但是又會產生一個新的問題，也就是樣本枯竭問題：隨著算法迭代的進行，樣本只是那些擁有較大權重的粒子經過反復復制后的后代，而擁有較小權重的粒子被丟棄，導致采樣樣本中有著大量的相同粒子，致使粒子多樣性丟失。

本文提出一種免重采樣的基于知識板的協同粒子濾波算法(Knowledge-based Cooperative Particle Filter, KCPF)，以期保證粒子多樣性，并且從某種程度上抑制粒子退化現象，最終提高算法在狀態估計中的性能。

2 基于知識板的協同粒子濾波算法設計

2.1 粒子濾波算法

粒子濾波[8-9]基于Monte Carlo[10]思想和遞歸Bayes估計，是利用Monte Carlo方法求解Bayes估計中的積分。粒子濾波的核心思想是：根據動態系統狀態向量的經驗條件分布，在動態系統狀態空間產生一組隨機樣本集合，這些樣本稱為粒子；依據觀測的結果不斷調節粒子的位置和權重；根據調節后的粒子信息修正原先的經驗條件分布。

粒子濾波算法過程描述如下：

Step2更新。更新粒子的權值：

Step3重采樣。

2.2 KCPSO算法

KCPSO[11]基于知識板和協同進化理論。知識板的局部知識集和全局知識集都是使用一個五元集合來表示，包括子群體或是整個群體的多樣性、搜索能力、生存狀態、最優系統狀態、重要性權值信息。

子群體多樣性可以使用采樣粒子相對于當前子采樣粒子群平均粒子位置的平均值來計算。而群體多樣性的計算可以使用各個子群體的最優系統狀態估計相對于當前所有子群體的平均最優系統狀態估計的平均值來計算。

Cs()是用來評價群體的搜索能力的，具體定義如下：

顯然，Cs()的值越大，該子群體的搜索能力越強，反之越弱。同樣，C()的值越大，整個群體的搜索能力越強，反之越弱。

Es()和E()描述的子群體和整個群體的生存狀態。 3個生存狀態分別定義為：

在對動態系統進行狀態估計時，每個采樣子粒子群都有它自己的生命周期，從初始化開始(對重要密度函數進行采樣，并對采樣粒子群粒子賦上初值)，經過成長，到成熟收斂，整個過程中的不同信息將不斷被抽取用于知識板上局部知識的更新。

在子粒子群或整體粒子群處于成長狀態，則在進行局部搜索過程中，粒子的信息更新可以根據下式進行：

當任一子粒子群體處于偽成熟狀態時為協同行為，粒子的位置和速度更新方程如下：

2.3 KCPF算法

KCPF核心思想：對重要性密度函數進行采樣形成采樣粒子樣本并對粒子樣本劃分若干個子采樣粒子群，每個子采樣粒子群在不同的局部區域進行搜索，并通過子采樣粒子群之間的通信，最終找到動態系統的最佳狀態估計。這樣做有2個好處：有利于維持種群搜索過程中的多樣性，防止粒子退化現象；可通過眾多局部極值點的搜索信息來引導對全局極值點的搜索，從而增加算法全局收斂的概率。

對系統進行狀態估計時，首先在采樣過程中引入最新的觀測值，定義適應度函數：

觀測值計算由式(8)獲得，算法具體步驟描述如下：

Step1 采樣粒子并初始化。

Step2計算重要性權值。

Step3根據最優值更新采樣粒子，使采樣粒子不斷的向真實狀態靠近。

Step3.1 如果滿足終止條件(重要性權值是否符合預設的閾值)，則轉到Step4；否則，轉到步驟Step3.2。

Step3.2如果任一子采樣粒子群體的生存狀態為成長狀態，則子采樣粒子群體按式(6)更新采樣粒子的速度和位置，否則轉到步驟Step3.3。

Step3.3 如果任一子采樣粒子群體的生存狀態為偽成熟狀態，則子采樣粒子群體按式(7)更新采樣粒子的速度和位置；否則，轉到步驟Step3.4。

Step3.4 如果任一子采樣粒子群體的生存狀態為成熟狀態，則對子采樣粒子群中任一采樣粒子進行重新初始化，并計算重要性權值。

Step3.5 計算每一個子采樣粒子群體中的采樣粒子適應值(重要性權值)，統計分析每一個子采樣粒子群體的多樣性、搜索能力、生存狀態等，更新知識板上的知識元素，轉到步驟Step3.1。

Step6如果符合結束條件，則退出算法，否則，繼續Step1。

KCPF算法流程描述如圖1所示。

圖1 KCPF算法流程

3 仿真實驗與結果分析

3.1 控制系統狀態跟蹤實驗

假設系統模型如下：

狀態方程：

觀測方程為：

在仿真實驗中，設定后驗概率密度分布中2.5%~97.5%的間隔范圍為置信度95%的置信區間，高置信水平的代價是寬的置信區間，通過保證置信區間中最有效的包含目標狀態的真實值而使目標估計具有最小的誤差。分別對EKF濾波算法、KCPF算法的置信區間進行分析，其中KCPF算法的采樣粒子數為2 000。仿真結果如圖2、圖3所示。

圖2 EKF的置信區間分析

圖3 KCPF的置信區間分析

通過圖2、圖3分析可以得知：EKF算法的置信區間最小，很明顯KCPF的置信區間是最大的，這也說明KCPF算法的效果要比較好，這是由于KCPF算法通過將采樣粒子樣本分解成若干子粒子樣本，增加了采樣粒子的多樣性，從而擴大了估計的置信區間，在置信區間中更好的包含了狀態的真實值的同時也使跟蹤的準確性有所增加。

3.2 轉彎模型狀態跟蹤實驗

假設機動目標的運動模型是協同轉彎模型，并假設空間維數是二維。假設目標的初始位置為：=[–2 000 m,0]，初始速度為：=300+(為[0,1]之間的隨機數)，仿真實驗的時間長度為：180 s，在第0~66 s處做勻速直線運動，在第67 s~85 s處做圓周運動，在第86 s~180 s處重新做勻速直線運動，轉彎處的加速度為50。采樣粒子3 000。

使用KCPF算法和EKF濾波算法跟蹤機動目標的軌跡及軸和軸方向的誤差如圖4~圖6所示。通過對比可以知道，EKF算法在機動目標跟蹤系統的運動模型和協同轉彎模型的時候，跟蹤誤差要比KCPF算法在機動目標跟蹤中的跟蹤誤差要大很多。因為大多數目標跟蹤系統是以協同轉彎模型為運動模型的，所以KCPF在目標跟蹤中具有比較好的應用。基于轉彎模型狀態跟蹤仿真實驗也說明了KCPF算法在目標跟蹤中應用的有效性。

圖4 KCPF和EKF的跟蹤軌跡

圖5 KCPF的跟蹤誤差

圖6 EKF的跟蹤誤差

4 結束語

本文提出的KCPF算法借鑒KCPSO算法中基于知識板的協同理論，通過將采樣粒子群分為若干個子粒子群，各個子采樣粒子群在各自的解空間中進行尋優，同時通過知識板的通信，在算法的運行過程中，保證采樣粒子的多樣性。另外由于KCPF算法是免重采樣的，解決了由重采樣帶來的樣本枯竭問題。基于控制系統狀態跟蹤和轉彎模型狀態跟蹤的仿真實驗結果表明KCPF算法達到了優化[12]粒子濾波的目的。

[1] Handschin J E, Mayne D Q. Monte Carlo Techniques to Estimate the Conditional Expectation in Multi-stage Non-linear Filtering[J]. International Journal of Control, 1969, 9(5): 547-559.

[2] Zaritsky V S, Svetnik V B, Shimelevich L I. Monte Carlo Techniques in Problems of Optimal Information Processing[J]. Automation and Remote Control, 1975, 36(3): 2015-2022.

[3] Godsill S, Clapp T. Improvement Strategies for Monte Carlo Particle Filters[J]. Signal Processing, 1998, 2(1): 17-23.

[4] Gordon N J, Salmond D J, Smith A F M. Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation[J]. Radar and Signal Processing, 1993, 140(2): 107-113.

[5] Carpenter J, Clifford P, Fearnhead R. Improved Particle Filter for Nonlinear Problems[J]. IEE Proceedings Radar, Sonar and Navigation, 1999, 146(1): 2-7.

[6] Nummiaro K, Koller-Meier E, van Gool L, et al. An Adaptive Color-based Particle Filter[J]. Image and Vision Computing, 2003, 21(1): 99-110.

[7] Hue C, Cadre J, Perez P. Tracking Multiple Objects with Particle Filtering[J]. IEEE Transactions on Aerospace and Electronic Systems, 2002, 38(3): 791-812.

[8] Doucet A, de Freitas N, Gordon N. An Introduction to Sequential Monte Carlo Methods. Sequential Monte Carlo Methods in Practical[M]. New York, USA: Springer-Verlag, 2001.

[9] Hu Xiaoli, Schon T B, Ljung L. A Basic Convergence Result for Particle Filtering[J]. IEEE Transactions on Signal Processing, 2008, 56(4): 1337-1348.

[10] Crisan D, Doucet A. Convergence of Sequential Monte Carlo Methods[M]. Cambridge, UK: Cambridge University Press, 2000.

[11] Jie Jin, Zeng Jianchao, Han Chongzhao, et al. Knowledge- based Cooperative Particle Swarm Optimization[J]. Applied Mathematics and Computation, 2008, 205(2): 861-873.

[12] Bergh F V D. An Analysis of Particle Swarm Optimizers[D]. Cape Town, South Africa: Department of Computer Science, University of Pretoria, 2002.

編輯 索書志

Cooperative Particle Filtering Algorithm Based on Knowledge Plate

WANG Yan-peng, WANG Lei, ZOU Feng, QIAN Xin-qiao

(School of Computer Science and Engineering, Xi’an University of Technology, Xi’an 710048, China)

For the degeneracy phenomenon of particles caused by evoluting and the impoverishment problem of particles caused by resampling. This paper proposes a novel particle filtering algorithm based on knowledge plate and coevolution. The main idea of this algorithm is to sample from the importance density function and generate particle samples which are divided into several sub-sample groups. Each sub-sample group searches among different area and finds the optimal state estimation of this dynamical system by means of the communication between each other. Theoretical analysis and experimental simulation results show that the proposed algorithm improves population diversity and has potential advantages in convergence rate and computational complexity, thus enhances the searching performance of the algorithm.

particle filtering; diversity; knowledge plate; cooperative; sampling; optimization

1000-3428(2014)03-0228-04

A

TP18

國家自然科學基金資助項目(61073091, 61100173)；陜西省自然科學基金資助項目(2010JM8028)。

王雁鵬(1985－)，男，碩士，主研方向：智能信息處理，系統可靠性分析與設計；王 磊(通訊作者)，教授、博士生導師；鄒 鋒，講師、博士；錢新橋，碩士。

2012-09-26

2013-01-12 E-mail：wangleeei@163.com

10.3969/j.issn.1000-3428.2014.03.048