面向多平臺(tái)多目標(biāo)協(xié)同跟蹤的指派問(wèn)題*

宋志強(qiáng)，周獻(xiàn)中，徐　鋒

（1.南京大學(xué)工程管理學(xué)院，南京　210093；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院機(jī)電與信息技術(shù)學(xué)院，江蘇　蘇州　215009；3.北方自動(dòng)控制技術(shù)研究所，太原　030006）

?

面向多平臺(tái)多目標(biāo)協(xié)同跟蹤的指派問(wèn)題*

宋志強(qiáng)1，2，周獻(xiàn)中1，徐鋒3

（1.南京大學(xué)工程管理學(xué)院，南京210093；2.蘇州經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院機(jī)電與信息技術(shù)學(xué)院，江蘇蘇州215009；3.北方自動(dòng)控制技術(shù)研究所，太原030006）

摘要：針對(duì)多平臺(tái)多目標(biāo)協(xié)同跟蹤中要求多個(gè)無(wú)人地面平臺(tái)盡可能均勻地協(xié)同跟蹤多個(gè)目標(biāo)的特點(diǎn)，提出了改進(jìn)的離散粒子群優(yōu)化算法。首先采用連續(xù)型粒子群優(yōu)化算法中的速度和位置迭代公式，然后對(duì)粒子位置進(jìn)行離散編碼，使粒子編碼對(duì)應(yīng)于可行的指派方案；其次，在優(yōu)化算法中引入局部搜索，提高算法尋優(yōu)性能。最后將所提算法應(yīng)用于多平臺(tái)多目標(biāo)協(xié)同跟蹤中的指派問(wèn)題，并與未加入局部搜索的粒子群優(yōu)化算法比較，仿真結(jié)果表明，加入局部搜索后的離散粒子群優(yōu)化算法具有較好的尋優(yōu)性能。

關(guān)鍵詞：跟蹤任務(wù)分配，指派問(wèn)題，粒子編碼，離散粒子群優(yōu)化算法，局部搜索

0　引言

現(xiàn)代戰(zhàn)爭(zhēng)敵我雙方對(duì)抗的復(fù)雜性，要求指揮中心能夠根據(jù)戰(zhàn)場(chǎng)環(huán)境，快速、合理地指派多地面無(wú)人平臺(tái)（Unmanned Ground Vehicle，UGV）協(xié)同跟蹤多個(gè)目標(biāo)，最大限度地發(fā)揮協(xié)同跟蹤的優(yōu)勢(shì)。多平臺(tái)多目標(biāo)協(xié)同跟蹤中的平臺(tái)指派問(wèn)題是非常重要的一個(gè)環(huán)節(jié)。多平臺(tái)多目標(biāo)協(xié)同跟蹤問(wèn)題具有平臺(tái)規(guī)模較大的特點(diǎn)，為盡量降低平臺(tái)的運(yùn)動(dòng)能耗，提高多目標(biāo)跟蹤系統(tǒng)性能，需要將多平臺(tái)進(jìn)行合理指派，使它們能夠互相協(xié)作，協(xié)同跟蹤各個(gè)目標(biāo)。為此需要構(gòu)建多平臺(tái)多目標(biāo)協(xié)同跟蹤指派問(wèn)題數(shù)學(xué)模型，把多平臺(tái)多目標(biāo)協(xié)同跟蹤指派問(wèn)題轉(zhuǎn)化為受約束的組合優(yōu)化問(wèn)題，然后采用優(yōu)化算法求解指派問(wèn)題。

指派給被跟蹤目標(biāo)的平臺(tái)越多，則平臺(tái)可獲得的關(guān)于目標(biāo)的數(shù)據(jù)越可靠，從而可得到對(duì)該被跟蹤目標(biāo)更優(yōu)的跟蹤性能，在存在多個(gè)被跟蹤目標(biāo)情況下，就需要指揮中心合理指派平臺(tái)跟蹤目標(biāo)。本文將多平臺(tái)多目標(biāo)協(xié)同跟蹤中的平臺(tái)跟蹤任務(wù)分配看作一個(gè)廣義指派問(wèn)題，即平臺(tái)數(shù)m和目標(biāo)數(shù)n不相等，由指揮中心按照一定的指派原則和約束條件，給多平臺(tái)指派跟蹤任務(wù)，指派多個(gè)平臺(tái)跟蹤多個(gè)目標(biāo)，使其總作戰(zhàn)效果達(dá)到最優(yōu)或較優(yōu)。當(dāng)然，本文設(shè)計(jì)的基于粒子群優(yōu)化算法的指派方案也適合于平臺(tái)數(shù)m和目標(biāo)數(shù)n相等的情況。

1　多平臺(tái)多目標(biāo)指派問(wèn)題及數(shù)學(xué)模型

多平臺(tái)多目標(biāo)指派問(wèn)題描述：設(shè)有n個(gè)目標(biāo)，現(xiàn)有m（m×n）個(gè)UGV，指揮控制中心需指派UGV去協(xié)同跟蹤各個(gè)目標(biāo)。規(guī)則如下：每個(gè)平臺(tái)僅跟蹤一個(gè)目標(biāo)（允許多個(gè)平臺(tái)協(xié)同跟蹤同一個(gè)目標(biāo)），即指揮中心僅分配給每個(gè)平臺(tái)一個(gè)跟蹤任務(wù)，每項(xiàng)跟蹤任務(wù)可由多個(gè)平臺(tái)協(xié)同完成，即指揮中心可分配多個(gè)平臺(tái)跟蹤一個(gè)目標(biāo)，且保證各個(gè)平臺(tái)盡量均勻地跟蹤各個(gè)目標(biāo)，已知第i個(gè)UGV到第j個(gè)目標(biāo)的距離為dij（i=1，2，…，m；j=1，2，…，n），需確定最優(yōu)指派方案，使得所有UGV與目標(biāo)的距離之和盡量小。

根據(jù)要保證各個(gè)平臺(tái)盡量均勻地跟蹤各個(gè)目標(biāo)的規(guī)則，假設(shè)m=6，n=4時(shí)，則指派UGV1、UGV2跟蹤目標(biāo)T1，指派UGV3、UGV4跟蹤目標(biāo)T2，指派UGV5、UGV6分別跟蹤目標(biāo)T3、T4是一種可行的指派方案。而指派UGV1、UGV2、UGV3跟蹤目標(biāo)T1，UGV4、UGV5、UGV6分別跟蹤目標(biāo)T2、T3、T4為不可行的指派方案。假設(shè)m=9，n=3時(shí)，則指揮控制中心指派3個(gè)平臺(tái)群（每個(gè)群由3個(gè)UGV組成）各自跟蹤不同的目標(biāo)，這樣的規(guī)則約束可以使得多個(gè)平臺(tái)較均勻地承擔(dān)跟蹤任務(wù)。定義UGV-目標(biāo)指派矩陣Am×n表示指派方案，其元素為aij（i=1，2，…，m；j=1，2，…，n），aij取值為0或1，aij=1表示指派第i個(gè)UGV跟蹤第j個(gè)目標(biāo)，否則aij=0。現(xiàn)對(duì)上述問(wèn)題進(jìn)行建模：

目標(biāo)函數(shù)：

約束條件：

其中［.］表示取整操作。目標(biāo)函數(shù)（1）表示求解最優(yōu)指派方案使得指派總效益最優(yōu)（距離和最?。患s束條件（2）表示每個(gè)平臺(tái)僅能跟蹤一個(gè)目標(biāo)；約束條件（3）表示指揮中心均勻指派UGV跟蹤各個(gè)目標(biāo)，每個(gè)平臺(tái)至少跟蹤一個(gè)目標(biāo)；由dij組成的矩陣Dm×n=（dij）m×n為多平臺(tái)多目標(biāo)跟蹤指派問(wèn)題的UGV-目標(biāo)距離矩陣。

從模型可看出，多平臺(tái)多目標(biāo)跟蹤指派問(wèn)題屬于NP-hard問(wèn)題，當(dāng)平臺(tái)數(shù)及目標(biāo)數(shù)較大時(shí)，采用精確算法求解將非常耗時(shí)，而智能優(yōu)化算法在求解此類(lèi)問(wèn)題時(shí)具有較大的優(yōu)勢(shì)，典型的智能算法有遺傳算法、蟻群算法、粒子群優(yōu)化算法等。其中粒子群算法與遺傳算法、蟻群算法相比，粒子群優(yōu)化算法的實(shí)現(xiàn)更加方便、需設(shè)定的參數(shù)更少且粒子群優(yōu)化算法執(zhí)行速度更快［1］。故本文采用粒子群優(yōu)化算法解決多平臺(tái)多目標(biāo)協(xié)同跟蹤中的指派問(wèn)題。

2　離散粒子群優(yōu)化（DPSO）算法設(shè)計(jì)

2.1基本粒子群算法

粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［2］是一種進(jìn)化計(jì)算技術(shù)，由Kennedy和Eberhart提出，源于對(duì)鳥(niǎo)群捕食行為的研究。在PSO算法中，優(yōu)化問(wèn)題的解被抽象成無(wú)質(zhì)量和體積的粒子，并延伸到多維空間。粒子在多維空間中的位置為一個(gè)矢量，各個(gè)粒子的飛行速度也是一個(gè)矢量。通過(guò)各個(gè)粒子的相互協(xié)作與信息共享，并不斷調(diào)整粒子的速度和位置，從而使得整個(gè)粒子群向最優(yōu)解收斂。由于PSO算法具有實(shí)現(xiàn)簡(jiǎn)單和收斂速度快等特點(diǎn)，因此，自其提出以后，引起了國(guó)內(nèi)外學(xué)者的高度關(guān)注，成為群智能研究領(lǐng)域的主要算法之一，實(shí)驗(yàn)結(jié)果表明粒子群優(yōu)化算法能夠解決遺傳算法能夠解決的各類(lèi)優(yōu)化問(wèn)題［3］。自粒子群算法提出至今，學(xué)者們對(duì)其展開(kāi)了大量研究工作，對(duì)PSO算法進(jìn)行了各種改進(jìn)，主要有基于慣性加權(quán)因子的改進(jìn)［4］、基于加速度因子的改進(jìn)［5］、融合其他算法的PSO［6］等。

粒子群優(yōu)化算法最初用于連續(xù)空間的問(wèn)題優(yōu)化，其基本粒子群算法的數(shù)學(xué)描述如下：

其中，ω是慣性加權(quán)因子，c1、c2為加速度因子，rand1和rand2為0~1之間的隨機(jī)數(shù)。vmax為最大速度，用以限制粒子的飛行速度。pbesti為粒子個(gè)體極值，記錄當(dāng)前粒子歷史最優(yōu)位置。gbest為全局極值，記錄整個(gè)群體的歷史最優(yōu)位置。通過(guò)式（1）進(jìn)行速度更新，式（2）進(jìn)行位置更新，通過(guò)迭代，粒子能夠不斷更新，逐漸“飛”至最優(yōu)解所在位置。當(dāng)?shù)_(dá)到最大次數(shù)或搜索結(jié)果達(dá)到預(yù)設(shè)閾值時(shí)，優(yōu)化算法結(jié)束，最后輸出為PSO算法搜索到的最優(yōu)解。

2.2粒子編碼與迭代

粒子群算法主要用于求解連續(xù)、無(wú)約束的優(yōu)化問(wèn)題，在離散、具有約束的優(yōu)化問(wèn)題求解方面的應(yīng)用還比較少，為了將粒子群算法應(yīng)用于廣義指派問(wèn)題，必須將其離散化，文獻(xiàn)［7］采用離散化粒子群算法解決作戰(zhàn)彈藥分配問(wèn)題，但不適合求解m和n相差較大的問(wèn)題。本文采用基于連續(xù)空間的PSO算法，對(duì)粒子位置進(jìn)行離散編碼，得到指派問(wèn)題的可行解，采用連續(xù)空間PSO算法的速度、位置更新規(guī)則，使得算法計(jì)算簡(jiǎn)單、耗時(shí)短，較好地解決了多平臺(tái)多目標(biāo)跟蹤問(wèn)題中的多平臺(tái)指派問(wèn)題，能夠得到最優(yōu)解或較優(yōu)解。

針對(duì)第2節(jié)建立的m個(gè)UGV，n個(gè)目標(biāo)的多平臺(tái)多目標(biāo)指派問(wèn)題模型，采用長(zhǎng)度為m的由1~n組成的自然數(shù)串表示粒子位置X：

采用式（7）表示的粒子位置是一個(gè)m維矢量，是一種指派方案，粒子每一維的數(shù)值在1~n的自然數(shù)中取，xi=j表示第i維對(duì)應(yīng)的UGV跟蹤第j個(gè)目標(biāo)，j=1，2，…，n。但是上述粒子位置并不能保證這是一種可行指派方案，即并不能保證滿(mǎn)足約束條件（3），因此，需要對(duì)粒子位置更新式（6）產(chǎn)生的連續(xù)型位置矢量Xnew進(jìn)行離散化編碼，設(shè)計(jì)如下編碼方案：

Step 1：按Xnew的每一維度的數(shù)據(jù)進(jìn)行升序排序，將排序結(jié)果存于Xsort，并記錄下Xnew和Xsort之間的映射關(guān)系。

Step 2：對(duì)Xsort數(shù)組中索引（Index）為1~［m/n］*n（索引從1開(kāi)始編號(hào)）的數(shù)組根據(jù)索引對(duì)n取模的情況賦值：若Index Mod n≠0，則Xsort=Index Mod n；如果Index Mod n=0，則Xsort=n。若m-［m/n］*n≠0，則對(duì)索引為［m/n］*n~m的Xsort數(shù)組元素賦互不重復(fù)的1~m的隨機(jī)數(shù)。

Step 3：根據(jù)Step 1已記錄下的排序映射關(guān)系進(jìn)行逆向映射，即可得滿(mǎn)足約束條件的X'new的離散化編碼。

Step 4：編碼后的X'new為一個(gè)滿(mǎn)足約束條件的可行指派方案，粒子仍按照式（5）、式（6）更新速度和位置更新，對(duì)新得到的連續(xù)型新矢量Xnew再進(jìn)行編碼得到離散化X'new編碼，如此可一直進(jìn)行迭代求解。

該編碼方案建立了粒子位置矢量與可行離散解空間的映射關(guān)系，編碼后的粒子由于已將不可行解排除之外，因此，搜索范圍被大大壓縮，搜索效率顯著提高。圖1為粒子離散化可行編碼生成示例。

圖1粒子離散化可行編碼生成示例

2.3粒子適應(yīng)度計(jì)算

根據(jù)目標(biāo)函數(shù)式（1），按式（8）選取粒子的適應(yīng)度值：

經(jīng)過(guò)上述粒子速度、位置表示、編碼、適應(yīng)度計(jì)算等定義之后，就基本完成了改進(jìn)的離散粒子群優(yōu)化（IDPSO）算法的設(shè)計(jì)，為了使得IDPSO能夠獲得更好優(yōu)化效果，需加入2.4小節(jié)的局部搜索。

2.4加入局部搜索

為增加算法的尋優(yōu)能力，在算法中增加局部搜索操作。本文在得到一次粒子離散編碼后，計(jì)算其適應(yīng)度值之后，還要基于貪婪思想對(duì)當(dāng)前離散編碼的所有鄰域作局部搜索。

定義：矢量P的鄰域：所有交換兩個(gè)不同索引位置對(duì)應(yīng)值而得到的新矢量的集合稱(chēng)為P的鄰域。

局部搜索過(guò)程如下：

Step 1：對(duì)離散編碼X'new產(chǎn)生兩個(gè)不同位置的索引，交換兩處索引位置上的值，得到一個(gè)新的離散編碼。

Step 2：計(jì)算新的離散編碼對(duì)應(yīng)的適應(yīng)度值，若該適應(yīng)度值優(yōu)于當(dāng)前粒子適應(yīng)度值，則記錄下該離散編碼及適應(yīng)度值。

Step 3：遍歷離散編碼X'new的鄰域，若遍歷完則轉(zhuǎn)Step 4；否則轉(zhuǎn)Step 1。

Step 4：結(jié)束局部搜索，若離散編碼鄰域的適應(yīng)度值優(yōu)于X'new對(duì)應(yīng)的適應(yīng)度值，則用該離散編碼對(duì)應(yīng)的連續(xù)粒子位置更新粒子，否則仍用當(dāng)前連續(xù)粒子位置作下一次迭代。

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

仿真實(shí)驗(yàn)在安裝有Matlab 2010b編程環(huán)境的PC上進(jìn)行，PC機(jī)配置為Windows 7 Home操作系統(tǒng)，Intel（R）Core（TM）i3-2310 CPU@2.10 GHz，4 G內(nèi)存，500 G硬盤(pán)。假設(shè)在［0，5 000］m×［0，5 000］m的監(jiān)測(cè)區(qū)域內(nèi)存在3個(gè)目標(biāo)，指揮控制中心及平臺(tái)可通過(guò)攜帶的傳感器獲得目標(biāo)及自身的位置信息，監(jiān)測(cè)區(qū)域內(nèi)有9個(gè)可用UGV及若干備用UGV，9個(gè)可用UGV及3個(gè)目標(biāo)的分布圖如圖2所示。算法參數(shù)：ω采用隨迭代次數(shù)不斷線(xiàn)性下降的方式取值，取值范圍為（0.4，0.9）。c1=1.494 45，c2=1.494 45。

圖2多平臺(tái)多目標(biāo)分布圖

UGV-目標(biāo)距離矩陣如下所示：

得到的最優(yōu)指派矩陣A9×3如下所示：

若算法不加入局部搜索，則不能保證每次都得到最優(yōu)解，而運(yùn)行加入局部搜索的算法，種群規(guī)模Size為10，最大迭代次數(shù)為50，算法運(yùn)行100次，每次均能得到最優(yōu)解，即適應(yīng)度值Fitness=6 966.2，所以在算法中加入局部搜索很有必要。

4　結(jié)論

針對(duì)多平臺(tái)多目標(biāo)跟蹤中的UGV多于被跟蹤目標(biāo)的指派問(wèn)題，本文提出了一種改進(jìn)的離散粒子群優(yōu)化算法，為增加算法的尋優(yōu)能力，在算法中增加局部搜索操作，通過(guò)與未加入局部搜索的離散粒子群優(yōu)化算法在仿真實(shí)驗(yàn)中的比較，表明本文所提出算法在性能優(yōu)化方面的有效性。

參考文獻(xiàn)：

［1］陳翔，顧慶，王子元，等.一種基于粒子群優(yōu)化的成對(duì)組合測(cè)試算法框架［J］.軟件學(xué)報(bào)，2011，22（12）：2879-2893.

［2］KENNEDY J，EBERHART RC. Particle swarm optimization ［J］. In：Proc. of the IEEE Conf，on Neural Networks，Perth：IEEE Press，1995（4）：1942-1948.

［3］HASSAN R，COHANIM B，DE WECK O，et al. A comparison of particle swarm optimization and the genetic algorithm［C］//Proceedings of the 1st AIAA Multidisciplinary Design Optimization Specialist Conference，2005.

［4］EBERHART R C，SHI Y. Comparing inertia weights and constriction factors in particle swarm optimization［C］//Evolutionary Computation，2000，Proceedings of the 2000 Congress on. IEEE，2000.

［5］GUO W，CHEN G，F(xiàn)ENG X. A new strategy of acceleration coefficients for particle swarm optimization［C］//Computer Supported Cooperative Work in Design，2006，CSCWD'06. 10th International Conference on，IEEE，2006.

［6］高鷹，謝勝利.免疫粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40（6）：4-6.

［7］趙志寧，石全，張軍剛.基于改進(jìn)離散粒子群優(yōu)化算法的作戰(zhàn)彈藥分配研究［J］.數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2013，34（3）：205-211.

Research on Assignment Problem for Coordinated Tracking of Multi- platform Multi- target

SONG Zhi-qiang1，2，ZHOU Xian-zhong1，XU Feng3
（1. School of Management and Engineering，Nanjing University，Nanjing 210093，China；
2. Institute of Electrical and Information Technology，Suzhou Institute of Trade & Commerce，Suzhou 215009，China；3. North Automatic Control Technology Institute，Taiyuan 030006，China）

Abstract：Aiming at the characteristics of requiring multiple unmanned ground vehicles tracking multiple targets as evenly as possible in the coordinated tracking system of multi-platform multi-target，an improved discrete particle swarm optimization algorithm is proposed. Firstly，the iterative formula of speed and position of the particle swarm optimization algorithm in the continuous space are adopted，and then a discrete particle coding scheme is designed to the particle position，making the particle coding corresponding to the feasible assignment solution; Secondly，a local search is introduced，providing better optimization performance. Finally，the proposed algorithm is applied to the assignment problem of coordinated tracking for the multi-platform multi-target，and compared with particle swarm optimization algorithm without the local search. The simulation results show that the discrete particle swarm optimization algorithm with a local search has better optimization performance.

Key words：tracking task allocation，assignment problem，particle coding，discrete particle swarm optimization algorithm，local search

作者簡(jiǎn)介：宋志強(qiáng)（1977-），男，江蘇張家港人，副教授，博士研究生。研究方向：網(wǎng)絡(luò)化群智能系統(tǒng)的協(xié)調(diào)與控制。

*基金項(xiàng)目：國(guó)家自然科學(xué)基金（71171107）；裝備預(yù)研基金重點(diǎn)項(xiàng)目（9140A06050213BQX）

收稿日期：2015-01-12修回日期：2015-03-17

文章編號(hào)：1002-0640（2016）02-0032-04

中圖分類(lèi)號(hào)：O22

文獻(xiàn)標(biāo)識(shí)碼：A