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

?

基于知識(shí)板的協(xié)同粒子濾波算法

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

(西安理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，西安 710048)

在當(dāng)前的粒子濾波中，粒子可能出現(xiàn)退化現(xiàn)象和重采樣，導(dǎo)致樣本枯竭從而破壞粒子多樣性。針對(duì)該問題，借鑒知識(shí)板和協(xié)同進(jìn)化理論，提出一種基于知識(shí)板的協(xié)同粒子濾波算法。該算法對(duì)重要性密度函數(shù)進(jìn)行采樣，形成采樣粒子樣本，并將粒子劃分為若干個(gè)子采樣粒子群，對(duì)每個(gè)子采樣粒子群在不同的區(qū)域進(jìn)行搜索，通過子采樣粒子群之間的通信，最終找到動(dòng)態(tài)系統(tǒng)的最佳狀態(tài)估計(jì)。理論分析與仿真結(jié)果表明，該算法能提高經(jīng)典粒子濾波算法的群體多樣性，在加快收斂速度和降低計(jì)算復(fù)雜度方面有較大優(yōu)勢(shì)。

粒子濾波；多樣性；知識(shí)板；協(xié)同；采樣；優(yōu)化

1 概述

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

粒子濾波技術(shù)在非線性[5]、非高斯系統(tǒng)表現(xiàn)出來的優(yōu)越性，決定了它的應(yīng)用范圍非常廣泛。另外粒子濾波器[6]的多模態(tài)處理能力，是它應(yīng)用廣泛的原因之一。國(guó)際上粒子濾波已被應(yīng)用于各個(gè)領(lǐng)域。在經(jīng)濟(jì)學(xué)領(lǐng)域它被應(yīng)用在經(jīng)濟(jì)數(shù)據(jù)預(yù)測(cè)；在交通管制領(lǐng)域它被應(yīng)用在對(duì)車或人視頻監(jiān)控；另外，它還用于機(jī)器人的全局定位、協(xié)同跟蹤等領(lǐng)域[7]。

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

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

2 基于知識(shí)板的協(xié)同粒子濾波算法設(shè)計(jì)

2.1 粒子濾波算法

粒子濾波[8-9]基于Monte Carlo[10]思想和遞歸Bayes估計(jì)，是利用Monte Carlo方法求解Bayes估計(jì)中的積分。粒子濾波的核心思想是：根據(jù)動(dòng)態(tài)系統(tǒng)狀態(tài)向量的經(jīng)驗(yàn)條件分布，在動(dòng)態(tài)系統(tǒng)狀態(tài)空間產(chǎn)生一組隨機(jī)樣本集合，這些樣本稱為粒子；依據(jù)觀測(cè)的結(jié)果不斷調(diào)節(jié)粒子的位置和權(quán)重；根據(jù)調(diào)節(jié)后的粒子信息修正原先的經(jīng)驗(yàn)條件分布。

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

Step2更新。更新粒子的權(quán)值：

Step3重采樣。

2.2 KCPSO算法

KCPSO[11]基于知識(shí)板和協(xié)同進(jìn)化理論。知識(shí)板的局部知識(shí)集和全局知識(shí)集都是使用一個(gè)五元集合來表示，包括子群體或是整個(gè)群體的多樣性、搜索能力、生存狀態(tài)、最優(yōu)系統(tǒng)狀態(tài)、重要性權(quán)值信息。

子群體多樣性可以使用采樣粒子相對(duì)于當(dāng)前子采樣粒子群平均粒子位置的平均值來計(jì)算。而群體多樣性的計(jì)算可以使用各個(gè)子群體的最優(yōu)系統(tǒng)狀態(tài)估計(jì)相對(duì)于當(dāng)前所有子群體的平均最優(yōu)系統(tǒng)狀態(tài)估計(jì)的平均值來計(jì)算。

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

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

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

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

在子粒子群或整體粒子群處于成長(zhǎng)狀態(tài)，則在進(jìn)行局部搜索過程中，粒子的信息更新可以根據(jù)下式進(jìn)行：

當(dāng)任一子粒子群體處于偽成熟狀態(tài)時(shí)為協(xié)同行為，粒子的位置和速度更新方程如下：

2.3 KCPF算法

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

對(duì)系統(tǒng)進(jìn)行狀態(tài)估計(jì)時(shí)，首先在采樣過程中引入最新的觀測(cè)值，定義適應(yīng)度函數(shù)：

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

Step1 采樣粒子并初始化。

Step2計(jì)算重要性權(quán)值。

Step3根據(jù)最優(yōu)值更新采樣粒子，使采樣粒子不斷的向真實(shí)狀態(tài)靠近。

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

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

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

Step3.4 如果任一子采樣粒子群體的生存狀態(tài)為成熟狀態(tài)，則對(duì)子采樣粒子群中任一采樣粒子進(jìn)行重新初始化，并計(jì)算重要性權(quán)值。

Step3.5 計(jì)算每一個(gè)子采樣粒子群體中的采樣粒子適應(yīng)值(重要性權(quán)值)，統(tǒng)計(jì)分析每一個(gè)子采樣粒子群體的多樣性、搜索能力、生存狀態(tài)等，更新知識(shí)板上的知識(shí)元素，轉(zhuǎn)到步驟Step3.1。

Step6如果符合結(jié)束條件，則退出算法，否則，繼續(xù)Step1。

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

圖1 KCPF算法流程

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 控制系統(tǒng)狀態(tài)跟蹤實(shí)驗(yàn)

假設(shè)系統(tǒng)模型如下：

狀態(tài)方程：

觀測(cè)方程為：

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

圖2 EKF的置信區(qū)間分析

圖3 KCPF的置信區(qū)間分析

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

3.2 轉(zhuǎn)彎模型狀態(tài)跟蹤實(shí)驗(yàn)

假設(shè)機(jī)動(dòng)目標(biāo)的運(yùn)動(dòng)模型是協(xié)同轉(zhuǎn)彎模型，并假設(shè)空間維數(shù)是二維。假設(shè)目標(biāo)的初始位置為：=[–2 000 m,0]，初始速度為：=300+(為[0,1]之間的隨機(jī)數(shù))，仿真實(shí)驗(yàn)的時(shí)間長(zhǎng)度為：180 s，在第0~66 s處做勻速直線運(yùn)動(dòng)，在第67 s~85 s處做圓周運(yùn)動(dòng)，在第86 s~180 s處重新做勻速直線運(yùn)動(dòng)，轉(zhuǎn)彎處的加速度為50。采樣粒子3 000。

使用KCPF算法和EKF濾波算法跟蹤機(jī)動(dòng)目標(biāo)的軌跡及軸和軸方向的誤差如圖4~圖6所示。通過對(duì)比可以知道，EKF算法在機(jī)動(dòng)目標(biāo)跟蹤系統(tǒng)的運(yùn)動(dòng)模型和協(xié)同轉(zhuǎn)彎模型的時(shí)候，跟蹤誤差要比KCPF算法在機(jī)動(dòng)目標(biāo)跟蹤中的跟蹤誤差要大很多。因?yàn)榇蠖鄶?shù)目標(biāo)跟蹤系統(tǒng)是以協(xié)同轉(zhuǎn)彎模型為運(yùn)動(dòng)模型的，所以KCPF在目標(biāo)跟蹤中具有比較好的應(yīng)用?；谵D(zhuǎn)彎模型狀態(tài)跟蹤仿真實(shí)驗(yàn)也說明了KCPF算法在目標(biāo)跟蹤中應(yīng)用的有效性。

圖4 KCPF和EKF的跟蹤軌跡

圖5 KCPF的跟蹤誤差

圖6 EKF的跟蹤誤差

4 結(jié)束語(yǔ)

本文提出的KCPF算法借鑒KCPSO算法中基于知識(shí)板的協(xié)同理論，通過將采樣粒子群分為若干個(gè)子粒子群，各個(gè)子采樣粒子群在各自的解空間中進(jìn)行尋優(yōu)，同時(shí)通過知識(shí)板的通信，在算法的運(yùn)行過程中，保證采樣粒子的多樣性。另外由于KCPF算法是免重采樣的，解決了由重采樣帶來的樣本枯竭問題。基于控制系統(tǒng)狀態(tài)跟蹤和轉(zhuǎn)彎模型狀態(tài)跟蹤的仿真實(shí)驗(yàn)結(jié)果表明KCPF算法達(dá)到了優(yōu)化[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61073091, 61100173)；陜西省自然科學(xué)基金資助項(xiàng)目(2010JM8028)。

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

2012-09-26

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

10.3969/j.issn.1000-3428.2014.03.048