具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃

朱 黔，周 銳

具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃

朱 黔，周 銳*

（北京航空航天大學(xué) 自動(dòng)化科學(xué)與電氣工程學(xué)院，北京100083）

為獲得目標(biāo)有效信息，無人機(jī)（UAVs）執(zhí)行偵察任務(wù)時(shí)針對不同目標(biāo)所需的持續(xù)偵察時(shí)間存在一定的差異。本文假設(shè)無人機(jī)在目標(biāo)持續(xù)偵察過程中保持定直平飛以確保有效偵察，針對至多3個(gè)偵察任務(wù)重疊的情況，通過幾何分析，提出了存在偵察任務(wù)重疊情況下的多偵察任務(wù)同時(shí)偵察方法。在考慮偵察任務(wù)重疊和多機(jī)協(xié)同偵察的同時(shí)，以最小化偵察路徑長度為性能指標(biāo)，相鄰偵察點(diǎn)間采用Dubins曲線迸行航路規(guī)劃，利用引入精英機(jī)制的混合粒子群優(yōu)化算法實(shí)現(xiàn)偵察任務(wù)序列優(yōu)化，實(shí)現(xiàn)具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃。仿真結(jié)果表明提出算法的有效性。

無人機(jī)；偵察任務(wù)重疊；協(xié)同航路規(guī)劃；精英機(jī)制；混合粒子群優(yōu)化算法

近年來無人機(jī)被廣泛運(yùn)用于邊界巡邏、目標(biāo)跟蹤及災(zāi)難救援等多個(gè)領(lǐng)域［1-2］，而執(zhí)行偵察任務(wù)也是無人機(jī)目前的一個(gè)主要應(yīng)用領(lǐng)域［3］。

無人機(jī)執(zhí)行任務(wù)時(shí)為有效監(jiān)控并獲得目標(biāo)信息，應(yīng)該使目標(biāo)持續(xù)處于偵察傳感器的監(jiān)控范圍內(nèi)，并保持一段時(shí)間，即滿足一定的持續(xù)偵察時(shí)間要求。文獻(xiàn)［4］利用遺傳算法（GA）實(shí)現(xiàn)無視線遮擋情況下的最短偵察路徑規(guī)劃；田菁和沈林成［5］針對時(shí)敏目標(biāo)，以最小化未被偵察目標(biāo)數(shù)目和偵察代價(jià)為性能目標(biāo)，采用Pareto最優(yōu)實(shí)現(xiàn)偵察序列優(yōu)化；文獻(xiàn)［6］中以單位時(shí)間內(nèi)偵察目標(biāo)數(shù)量作為偵察效能評估指標(biāo)。上述文章雖充分考慮偵察任務(wù)中的各種偵察性能要求，但是卻沒有考慮偵察任務(wù)中對于指定偵察任務(wù)存在持續(xù)偵察時(shí)間的約束，也并未考慮偵察任務(wù)重疊的情況。雖然文獻(xiàn)［7］中通過設(shè)定采樣路標(biāo)的方法來考慮偵察任務(wù)重疊的情況，但并未考慮同時(shí)完成多個(gè)偵察任務(wù)。

無人機(jī)執(zhí)行偵察任務(wù)可以歸結(jié)為旅行商問題，旅行商問題是一個(gè)著名的NP難問題，只能采用啟發(fā)式算法近似求解，遺傳算法［8］、蟻群算法［9］及粒子群［10］等算法都可求解旅行商問題。也有很多改進(jìn)方法如將貪婪算法和遺傳算法相結(jié)合，通過自適應(yīng)調(diào)節(jié)遺傳參數(shù)實(shí)現(xiàn)TSP問題求解［11］；利用互信息對蟻群算法中的概率算子增加新的影響因子，實(shí)現(xiàn)旅行商問題求解［12］。而多機(jī)協(xié)同偵察可以歸結(jié)為多旅行商問題，Yu等［13］采用兩層混合算法求解多旅行商問題，利用 kmeans聚類和改進(jìn)遺傳算法將問題轉(zhuǎn)化為單旅行商問題求解；而利用局部搜索［14］解決多基地多旅行商問題也獲得了很好的效果。

本文假設(shè)各個(gè)偵察點(diǎn)的偵察進(jìn)入方向由相鄰偵察點(diǎn)確定，當(dāng)偵察進(jìn)入方向確定后，需要在相鄰兩個(gè)偵察點(diǎn)之間進(jìn)行航路規(guī)劃。Dubins［15］證明Dubins曲線是滿足最大曲率約束和兩點(diǎn)航向約束的最短可能路徑，并且Dubins曲線在目標(biāo)攔截路徑規(guī)劃［16］、最短時(shí)間集結(jié)［17］及障礙環(huán)境下的最短路徑規(guī)劃［18］等領(lǐng)域中都取得了很好的效果。

本文針對存在至多3個(gè)重疊偵察任務(wù)的情況，通過幾何分析，明確提出了多偵察點(diǎn)同時(shí)偵察方法；基于相鄰2個(gè)偵察點(diǎn)的位置信息確定當(dāng)前偵察點(diǎn)的偵察進(jìn)入方向，并利用Dubins曲線完成相鄰兩個(gè)偵察點(diǎn)之間的航路規(guī)劃。本文將精英機(jī)制引入到文獻(xiàn)［19］提出的混合粒子群優(yōu)化（Hybird Particle Swarm Optim ization，HPSO）算法，形成具有精英機(jī)制的混合粒子群優(yōu)化（Elite HPSO，EHPSO）算法。利用隨機(jī)搜索方法初始化粒子群，以最小化偵察路徑長度為目標(biāo)，獲取最優(yōu)偵察任務(wù)序列，實(shí)現(xiàn)具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃。

1 偵察任務(wù)描述

1．1 無人機(jī)偵察傳感器模型

偵察傳感器通常安置在機(jī)載萬向節(jié)上。如圖1所示，萬向節(jié)系統(tǒng)是一個(gè)可三自由度轉(zhuǎn)動(dòng)的系統(tǒng)，最常采用的是十字軸式，它由兩個(gè)相交為十字的軸連接而成。設(shè)傳感器系統(tǒng)萬向節(jié)兩轉(zhuǎn)動(dòng)軸之間的最大夾角為 θ，不考慮無人機(jī)姿態(tài)角的變化，傳感器在距離地面高度h處的探測范圍就是以傳感器在地平面的投影為圓心、h·tanθ為半徑的圓。圖中陰影部分為機(jī)載傳感器可探測區(qū)域稱為偵察圓，Reff＝h·tanθ稱為有效偵察半徑。

圖1 機(jī)載傳感器偵察模型Fig.1 Airborne sensor reconnaissance model

1．2 具有持續(xù)偵察時(shí)間約束的任務(wù)點(diǎn)偵察

本文假設(shè)無人機(jī)定高常速飛行，在探測過程中為保證探測傳感器穩(wěn)定，要求執(zhí)行偵察任務(wù)過程中無人機(jī)保持定直平飛。由于不同偵察點(diǎn)的屬性和價(jià)值不同，因而需要的持續(xù)偵察時(shí)間也不同，需滿足如下持續(xù)偵察時(shí)間約束：

式中：ti、timin和tieff分別為第i個(gè)偵察點(diǎn)的持續(xù)偵察時(shí)間、所需要的最短持續(xù)偵察時(shí)間和有效持續(xù)偵察時(shí)間；M為待偵察的偵察點(diǎn)數(shù)目。

由于假設(shè)無人機(jī)以常速v0定速飛行，式（1）可以轉(zhuǎn)換為如下距離公式：

式中：Di、Dimin和Dieff分別為第i個(gè)偵察點(diǎn)有效偵察距離、所需要的最小有效偵察距離和有效偵察距離。如圖2所示O為待偵察點(diǎn)位置，Reff為有效偵察半徑，沿圖上路徑Deff的偵察進(jìn)入方向，即可滿足最短持續(xù)偵察時(shí)間tmin要求，且R′為此偵察過程中距離目標(biāo)的最近距離。由于同一偵察點(diǎn)有效偵察距離Deff不唯一，需做如下假設(shè)：

1）任一偵察點(diǎn)最短持續(xù)偵察時(shí)間滿足約束：tmin≤2Reff／v0

2）有效偵察路徑Deff的進(jìn)入方向由相鄰兩個(gè)偵察點(diǎn)相對位置確定。對第 i個(gè)偵察點(diǎn)進(jìn)行偵察，Deff進(jìn)入方向由第i-1和第i+1個(gè)偵察點(diǎn)確定，偵察進(jìn)入方向與第i-1指向第i+1個(gè)偵察點(diǎn)的方向一致，且Deff位于靠近相鄰偵察點(diǎn)的一側(cè)。

圖2 有效偵察距離Fig.2 Effective reconnaissance distance

1．3 偵察任務(wù)重疊情況下的同時(shí)偵察方案

如圖3所示，任務(wù)點(diǎn)1、2的有效持續(xù)偵察時(shí)間要求分別為 t1eff、t2eff，對應(yīng)的有效偵察距離為D1eff、D2eff。由于存在偵察任務(wù)重疊，可尋找滿足式（3）的有效偵察距離Deff實(shí)現(xiàn)對兩個(gè)偵察點(diǎn)同時(shí)偵察。無人機(jī)沿著Deff進(jìn)行偵察時(shí)，可以在D′1eff完成對O1的偵察，在D′2eff完成對O2的偵察，同時(shí)偵察可以有效縮短持續(xù)偵察任務(wù)時(shí)間。

由于任意M個(gè)偵察點(diǎn)隨機(jī)分布可能存在偵察任務(wù)重疊的情況，需進(jìn)行聚類分析。以各個(gè)偵察點(diǎn)的歐式距離為聚類原則，假設(shè)任意M個(gè)偵察點(diǎn)會(huì)分成M′個(gè)類，分類結(jié)果應(yīng)滿足如下約束：

式（4）表明任意兩個(gè)不同類的偵察點(diǎn)之間的距離必定大于2倍有效偵察半徑；式（5）表明相同類中的任一偵察點(diǎn)肯定存在至少一個(gè)偵察點(diǎn)與它的距離小于2倍有效偵察半徑。

為確保能夠同時(shí)對多個(gè)重疊偵察點(diǎn)進(jìn)行偵察，需同時(shí)滿足各自的持續(xù)偵察時(shí)間約束。如圖4所示，本文針對最多3個(gè)重疊偵察任務(wù)（當(dāng)超過3個(gè)偵察點(diǎn)時(shí)會(huì)出現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)，而定直平飛無法穿過所有偵察圓，此時(shí)的解決方法是選擇盡可能多的重疊偵察任務(wù)進(jìn)行偵察），采用幾何分析，提出多偵察任務(wù)重疊時(shí)同時(shí)偵察路徑選擇方案如下：

圖3 2個(gè)偵察任務(wù)重疊示意圖Fig.3 Two overlapping reconnaissance missions’s schematic diagram

圖4 3個(gè)偵察任務(wù)重疊示意圖Fig.4 Three overlapping reconnaissancemissions’s schematic diagram

記偵察圓圓心O1、O3連線的中點(diǎn)為O′。3個(gè)偵察圓存在共同重疊區(qū)域的情況經(jīng)坐標(biāo)旋轉(zhuǎn)如圖4（a）所示，設(shè)偵察點(diǎn)O2具有3個(gè)偵察點(diǎn)中最大持續(xù)偵察時(shí)間t2min；如圖4（b）和圖4（c）所示，針對3個(gè)偵察圓不存在共同重疊區(qū)域的情況，設(shè)偵察點(diǎn)O2的持續(xù)偵察時(shí)間t2min大于偵察點(diǎn)O1的持續(xù)偵察時(shí)間t1min，偵察點(diǎn)O3的持續(xù)偵察時(shí)間為t3min。過O′分別做滿足與O2偵察圓的相交弦長等于有效偵察距離D2eff＝v0·t2min的兩條直線，與O2分別交于點(diǎn)A2、A′2、B2、B′2，直線O′A2、O′B2分別與圓O1、O3交于點(diǎn)A1、A′1、B1、B′1、A3、A′3、B3、B′3。圖中帶顏色區(qū)域?yàn)橥瑫r(shí)完成偵察任務(wù)的可能區(qū)域，紅色區(qū)域?yàn)?個(gè)偵察圓的共同重疊區(qū)域，藍(lán)色區(qū)域?yàn)閮蓚€(gè)偵察圓的共同重疊區(qū)域，黃色區(qū)域代表單個(gè)偵察圓存在的可行區(qū)域。由于要求無人機(jī)在執(zhí)行偵察任務(wù)時(shí)定直平飛，可以得到如下結(jié)論：

結(jié)論1 如圖4（a）三偵察點(diǎn)存在共同可行偵察區(qū)域，若滿足則一定存在滿足同時(shí)偵察的可行路徑。

結(jié)論2 如圖4（b）所示，若3個(gè)偵察任務(wù)不存在共同可行偵察區(qū)域，且可行區(qū)域不含偵察點(diǎn)O1和O3，若滿足則一定存在滿足同時(shí)偵察的可行路徑。

結(jié)論3 如圖4（c）所示，偵察可行區(qū)域包含偵察點(diǎn)O1和O3，則一定存在滿足同時(shí)偵察的可行路徑。

結(jié)論1和2證明：O′為圓O1、O3對應(yīng)的圓心連線的中點(diǎn)，有O′O1＝O′O3。利用幾何關(guān)系可知：圓心O1、O3到弦和的距離相等。由于圓O1、O3半徑相等，可得同理有可知過點(diǎn)O′的直線與圓O1、O3的相交弦都相等，即 O1、O3的有效持續(xù)偵察距離恒等。

如圖4（a）和圖4（b）所示，在滿足O2持續(xù)偵察時(shí)間后，可行區(qū)域不含有過偵察點(diǎn)O1、O3的直線。由圖上繞O′將弦旋轉(zhuǎn)至依據(jù)O1、 O3的可行持續(xù)偵察距離變化趨勢，可選有效持續(xù)偵察距離如下：

結(jié)論3證明：基于結(jié)論1和2的證明，且可行區(qū)域包含偵察點(diǎn)O1、O3。當(dāng)偵察路徑穿過偵察點(diǎn)O1、O3，其有效持續(xù)偵察距離為2Reff，可知O1、O3可行偵察區(qū)域內(nèi)的有效持續(xù)偵察距離如下：

故一定存在滿足同時(shí)偵察的可行路徑。而存在共同重疊區(qū)域的3個(gè)偵察圓當(dāng)可行區(qū)域包含偵察點(diǎn)的情況是結(jié)論3的特例，由于篇幅不再證明。

若基于上述方法無法找到滿足要求的同時(shí)偵察路徑，則選取其中兩個(gè)偵察點(diǎn)進(jìn)行同時(shí)偵察，并對剩余偵察點(diǎn)進(jìn)行單獨(dú)偵察。

1．4 相鄰偵察任務(wù)點(diǎn)間的航路規(guī)劃

由于偵察進(jìn)入點(diǎn)位置和方向依據(jù)偵察任務(wù)序列確定，對應(yīng)偵察離開方向也唯一確定。所以相鄰偵察點(diǎn)之間的航路規(guī)劃是一個(gè)具有起始角度θs和終端角度θf約束的路徑規(guī)劃問題。如圖 5所示，文獻(xiàn)［15］已證明Dubins曲線是滿足最大曲率約束和航向約束的兩點(diǎn)之間最短路徑。Dubins曲線由直線段和弧線段構(gòu)成，最短Dubins曲線必然是曲線集｛LSL，RSR，RSL，LSR，RLR，LRL｝中的一種（其中：L表示左圓?。籖表示右圓??；S表示直線段），并能夠準(zhǔn)確獲得Dubins曲線形式和長度。因此本文采用Dubins曲線實(shí)現(xiàn)相鄰偵察點(diǎn)之間的航路規(guī)劃。

圖5 Dubins路徑模型Fig.5 Dubins path model

2 多機(jī)協(xié)同偵察航路規(guī)劃

設(shè)共有M個(gè)偵察點(diǎn)，N架無人機(jī)。每個(gè)偵察點(diǎn)滿足持續(xù)偵察時(shí)間約束：

由于偵察進(jìn)入點(diǎn)的確定，并盡可能縮短持續(xù)偵察時(shí)間，將上述約束改為

設(shè)每架飛機(jī)的初始位置分別為（xi0，yi0），i＝1，2，…，N。

本文對應(yīng)含有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃問題構(gòu)建模型如下：

設(shè)xijk∈｛0，1｝為決策變量，當(dāng)xijk＝1表明第k架無人機(jī)執(zhí)行從第i個(gè)偵察點(diǎn)到第j個(gè)偵察點(diǎn)的偵察任務(wù)，設(shè)xk＝｛xijk｝（M+1）×（M+1）為第k架無人機(jī)的決策變量矩陣，Ω為當(dāng)前無人機(jī)所有可能決策變量矩陣集合，代表所有可能的偵察任務(wù)序列。對應(yīng)第k架無人機(jī)的偵察航路長度為

無人機(jī)在執(zhí)行任務(wù)過程中，考慮最大飛行距離約束如下：

式（7）和式（8）表示每個(gè)偵察點(diǎn)僅能被一架無人機(jī)偵察一次；式（9）和式（10）表示每架無人機(jī)初始和結(jié)束都要返回各自初始位置；式（11）表示第k架無人機(jī)從第i個(gè)偵察結(jié)束位置（xiE，yiE，θiE）到第 j個(gè)偵察初始位置（xjS，yjS，θjS）采用Dubins曲線獲得長度為Dijmin的最短偵察路徑；式（12）表示對應(yīng)第i個(gè)偵察點(diǎn)偵察過程中滿足相應(yīng)持續(xù)偵察時(shí)間約束；式（13）計(jì)算第k架無人機(jī)的整條偵察路徑長度，式（14）表示無人機(jī)具有最大飛行距離約束。

［20］以最小化偵察路徑長度為設(shè)計(jì)目標(biāo)，考慮典型的3種協(xié)同航路規(guī)劃性能指標(biāo)：

1）MinSum以最小化所有無人機(jī)偵察路徑長度之和為目標(biāo)，其性能指標(biāo)如式（15）所示：

2）MinMax以最小化所有無人機(jī)偵察路徑長度中的最大值為目標(biāo)，其性能指標(biāo)如式（16）所示：

3）MinAvg以最小化所有無人機(jī)偵察路徑長度差值為目標(biāo)，其性能指標(biāo)如式（17）所示：

3 引入精英機(jī)制的混合粒子群算法

參考文獻(xiàn)［19］中所提出的混合粒子群優(yōu)化算法，采用隨機(jī)搜索的方法初始化粒子群，并引入精英機(jī)制對算法進(jìn)行改進(jìn)。實(shí)現(xiàn)對具有持續(xù)偵察時(shí)間約束的多無人機(jī)協(xié)同航路規(guī)劃問題求解。

3．1 編 碼

設(shè)共有M個(gè)偵察點(diǎn)，按照順序?qū)個(gè)偵察點(diǎn)進(jìn)行編號(hào)，對應(yīng)為1，2，…，M。設(shè)共有N架無人機(jī)，對應(yīng)序號(hào)依次為1，2，…，N，修改無人機(jī)的編碼對應(yīng)為M+1，M+2，…，M+N。采用單一編碼對粒子進(jìn)行編碼。假設(shè)共有8個(gè)偵察點(diǎn)，2架無人機(jī)，則隨機(jī)生成一個(gè)粒子的編碼如下：

1 5 8 9 2 7 3 4 6 1 0

3．2 初始化粒子

通常進(jìn)化算法都是通過隨機(jī)生成形成初始種群，初始種群的適應(yīng)度可能會(huì)較差，而這也會(huì)對收斂速度造成一定的影響。本文為提高初始粒子適應(yīng)值，采用隨機(jī)搜索的方法，初始化粒子群。

首先為各架無人機(jī)隨機(jī)選擇一組不重復(fù)的偵察點(diǎn)，形成當(dāng)前偵察點(diǎn)集｛P1，P2，…，PN｝，然后在剩余的偵察點(diǎn)中選擇各自距當(dāng)前偵察點(diǎn)距離最近的點(diǎn)，形成最近偵察點(diǎn)集合｛P′1，P′2，…，P′N｝，從最近點(diǎn)集合中選取使距離值增加最少的偵察點(diǎn)對應(yīng)添加到相應(yīng)無人機(jī)偵察序列中，并對應(yīng)修正當(dāng)前偵察點(diǎn)集，直到所有的偵察點(diǎn)都添加到偵察序列中，即利用隨機(jī)搜索方法生成一個(gè)初始化粒子。

3．3 交 叉

傳統(tǒng)粒子群算法依據(jù)個(gè)體和群體極值對粒子進(jìn)行更新，在求解旅行商問題時(shí)通過對速度算式重建，通過交換子和交換序?qū)崿F(xiàn)粒子更新。混合粒子群主要引入遺傳算法中的交叉思想，通過當(dāng)前粒子與個(gè)體極值和群體極值分別進(jìn)行交叉，替代交換子和交換序。選擇偵察航路長度的倒數(shù)作為粒子適應(yīng)值，當(dāng)交叉后的粒子適應(yīng)值有所改善時(shí)，替換原有粒子。具體交叉方法如下。

當(dāng)前個(gè)體粒子信息為：當(dāng)前個(gè)體最優(yōu)粒子信息為：

隨機(jī)生成交叉位為：4和7，對應(yīng)取出個(gè)體最優(yōu)粒子的待交叉片段如下：

相應(yīng)替換當(dāng)前粒子對應(yīng)片段，生成新粒子：

考慮待交叉片段中可能包含重復(fù)偵察點(diǎn)，需用未包含偵察點(diǎn)對應(yīng)替換，修正交叉后粒子如下：

當(dāng)交叉后粒子的適應(yīng)值優(yōu)于原粒子的適應(yīng)值時(shí)，對應(yīng)替換原粒子，實(shí)現(xiàn)粒子更新。

3．4 變 異

隨機(jī)生成兩個(gè)自然數(shù)，作為變異位置點(diǎn)，若變異位置點(diǎn)分別為4和7，具體的變異操作如下。

當(dāng)前個(gè)體粒子信息為：變異后的粒子信息為：

當(dāng)變異后的粒子適應(yīng)值優(yōu)于原粒子時(shí)對應(yīng)替換原粒子，實(shí)現(xiàn)粒子更新。

3．5 精英機(jī)制

在很多優(yōu)化算法中，都會(huì)保留精英個(gè)體以替代交叉變異后群體中適應(yīng)值最差的個(gè)體，以確保適應(yīng)值高的精英個(gè)體可以得到保留和延續(xù)。

當(dāng)求解空間很復(fù)雜并存在多個(gè)局部最優(yōu)解時(shí)，基本的粒子群算法很容易收斂到局部最優(yōu)而無法找到全局最優(yōu)?；诰C(jī)制［21］的啟發(fā)，可能部分適應(yīng)值排在前列的粒子比單一最優(yōu)粒子具有更好的學(xué)習(xí)優(yōu)勢，可以提高粒子多樣性。引入精英機(jī)制是為每一個(gè)粒子創(chuàng)建一個(gè)個(gè)體最優(yōu)團(tuán)體，為群體最優(yōu)粒子創(chuàng)建一個(gè)群體最優(yōu)團(tuán)體。在每一次迭代循環(huán)過程中，精英機(jī)制主要體現(xiàn)在交叉過程中。當(dāng)前粒子分別與個(gè)體最優(yōu)團(tuán)體中的粒子分別進(jìn)行交叉，再與群體最優(yōu)團(tuán)體中的粒子分別進(jìn)行交叉，當(dāng)適應(yīng)值有所改善時(shí)，替換原有粒子，實(shí)現(xiàn)粒子更新。引入精英機(jī)制可以有效增加粒子多樣性，避免過早收斂到局部最優(yōu)。

3．6 算法結(jié)構(gòu)

如圖6所示，具有精英機(jī)制的混合粒子群算法的基本流程如下：

采用隨機(jī)搜索方法，添加最近偵察點(diǎn)形成初始偵察序列，實(shí)現(xiàn)粒子群信息初始化。

圖6 引入精英機(jī)制的混合粒子群優(yōu)化算法流程Fig.6 EHPSO algorithm flow

在每個(gè)迭代周期，將當(dāng)前粒子分別與個(gè)體和群體最優(yōu)團(tuán)體中的粒子進(jìn)行交叉，并進(jìn)行個(gè)體變異，當(dāng)適應(yīng)值有所改善時(shí)完成粒子更新。

當(dāng)滿足迭代周期時(shí)，獲得最優(yōu)偵察序列信息，實(shí)現(xiàn)具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃。

4 仿真對比

仿真實(shí)驗(yàn)中，設(shè)定一個(gè)5 000m×5 000m的偵察區(qū)域，隨機(jī)生成具有偵察任務(wù)重疊的20個(gè)偵察點(diǎn)位置和對應(yīng)持續(xù)偵察時(shí)間，分別考慮MinSum、MinMax和MinAvg 3種性能指標(biāo)，利用兩架初始位置分別為（0m，0m），（500m，0m）的無人機(jī)對全部偵察點(diǎn)進(jìn)行偵察，利用引入精英機(jī)制的混合粒子群算法對具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃問題求解。以MinMax作為性能指標(biāo)，并與混合粒子群算法和遺傳算法進(jìn)行對比，具體仿真結(jié)果如圖7～圖10所示，具體仿真參數(shù)如表1所示。

圖7 3個(gè)重疊偵察任務(wù)航路規(guī)劃Fig.7 Three overlapping reconnaissance missions’path planning

圖8 3個(gè)重疊偵察任務(wù)收斂曲線對比Fig.8 Three overlapping reconnaissance m issions’convergence curves comparison

圖9 2個(gè)重疊偵察任務(wù)航路規(guī)劃Fig.9 Two overlapping reconnaissancemissions’path planning

圖10 2個(gè)重疊偵察任務(wù)收斂曲線對比Fig.10 Two overlapping reconnaissance missions’convergence curves comparison

表1 仿真參數(shù)設(shè)置Tab le 1 Sim u lation param eter setting

具有精英機(jī)制的混合粒子群算法的其余參數(shù)設(shè)置與混合粒子群一致，參見文獻(xiàn)［19］。

4．1 M inM ax性能指標(biāo)下的協(xié)同航路規(guī)劃結(jié)果

由圖7～圖10可以看出，無人機(jī)在偵察過程中，由偵察進(jìn)入點(diǎn)進(jìn)入，保持定直平飛實(shí)現(xiàn)目標(biāo)持續(xù)偵察。當(dāng)存在3個(gè)或2個(gè)偵察任務(wù)重疊時(shí)，利用本文提出算法能夠?qū)崿F(xiàn)對重疊偵察任務(wù)同時(shí)偵察。圖7中偵察點(diǎn)6、9、19 3個(gè)偵察任務(wù)重疊，偵察點(diǎn)19具有最大持續(xù)偵察時(shí)間為15.8973 s，對應(yīng)持續(xù)偵察距離為317.946m。而在可行偵察區(qū)域選擇偵察進(jìn)入方向時(shí)，考慮相鄰偵察點(diǎn)位置信息，最終確定的有效持續(xù)偵察距離為346.782 5 m，其他2個(gè)偵察任務(wù)也都滿足結(jié)論1的條件，可以同時(shí)完成3個(gè)重疊偵察任務(wù)。相比分別對每個(gè)偵察點(diǎn)進(jìn)行偵察，同時(shí)偵察能有效縮短偵察時(shí)間。

當(dāng)相鄰偵察點(diǎn)距離很近時(shí)為確保獲得偵察進(jìn)入方向，Dubins曲線會(huì)存在一段圓弧確保進(jìn)入航向，如圖7的偵察點(diǎn)10所示。對應(yīng)調(diào)整無人機(jī)最小轉(zhuǎn)彎半徑，則對應(yīng)規(guī)劃路徑也會(huì)相應(yīng)發(fā)生變化。

圖8和圖10為分別采用EHPSO、HPSO和GA求解問題時(shí)對應(yīng)的收斂曲線。可以看出，利用隨機(jī)搜索生成初始化粒子群，采用精英機(jī)制對交叉操作進(jìn)行改進(jìn)，EHPSO算法的收斂性和粒子的多樣性較比HPSO和GA都有一定的改善，證明EHPSO對本文問題求解的有效性。

4．2 3種性能指標(biāo)仿真對比

為驗(yàn)證本文算法的有效性，針對MinMax、MinSum和MinAvg 3種不同的典型協(xié)同航路規(guī)劃性能指標(biāo)進(jìn)行仿真對比，具體的結(jié)果如表2所示。

表2 仿真性能對比Tab le 2 Sim u lation perform ance com parison

由表2可以看出，采用同時(shí)偵察方案較比依次對重疊偵察任務(wù)進(jìn)行分別偵察可有效縮短偵察路徑，證明本文提出的同時(shí)偵察方案的有效性。針對MinSum性能指標(biāo)，不考慮偵察最大飛行距離時(shí)均為一架無人機(jī)完成所有偵察任務(wù)，造成偵察任務(wù)分配不均衡；此時(shí)考慮偵察最大飛行距離，則對應(yīng)兩架飛機(jī)偵察任務(wù)分配較為均衡，以加和最短完成偵察任務(wù)；針對MinAvg性能指標(biāo)，若不考慮最大飛行距離，其結(jié)果嚴(yán)重依賴初始粒子，隨機(jī)性很大；考慮最大飛行距離約束，則兩架飛機(jī)在滿足最大飛行距離約束前提下，偵察規(guī)劃路徑長度盡可能接近。針對不同性能指標(biāo)和附加約束，利用本文提出的EHPSO可獲得各種性能指標(biāo)下滿意的規(guī)劃結(jié)果，也驗(yàn)證本文提出算法的有效性。

采用EHPSO求解本文問題，可能會(huì)獲得近似最優(yōu)解，為驗(yàn)證本文提出EHPSO算法的有效性，以MinMax作為性能指標(biāo)對以上兩組案例分別做10組重復(fù)試驗(yàn)，具體結(jié)果如表3和表4所示。

表3 兩任務(wù)重疊仿真結(jié)果統(tǒng)計(jì)Tab le 3 Sim ulation result statistics for tw o m ission over lapping

表4 三任務(wù)重疊仿真結(jié)果統(tǒng)計(jì)Tab le 4 Sim u lation resu lt statistics for th ree m ission overlapping

由統(tǒng)計(jì)結(jié)果可以看出：采用隨機(jī)搜索初始化粒子群，可以有效提高初始粒子適應(yīng)值，加快收斂速度；利用精英最優(yōu)團(tuán)體取代單個(gè)個(gè)體和群體最優(yōu)，與個(gè)體粒子分別進(jìn)行交叉操作，可有效提高粒子多樣性，提高算法收斂速度和尋優(yōu)能力。

5 結(jié) 論

主要針對具有持續(xù)偵察時(shí)間約束的多機(jī)協(xié)同路徑規(guī)劃問題進(jìn)行研究。結(jié)論如下：

1）提出3個(gè)以下重疊偵察任務(wù)的同時(shí)偵察方案，能有效縮短偵察路徑長度?；贒ubins曲線和偵察點(diǎn)有效偵察路徑，完成具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃。

2）采用具有精英機(jī)制的改進(jìn)混合粒子群算法實(shí)現(xiàn)偵察序列優(yōu)化，通過隨機(jī)搜索初始化粒子群，采用精英機(jī)制改進(jìn)粒子交叉操作，可有效增加粒子多樣性，提高算法的收斂速度和尋優(yōu)能力。

考慮偵察過程中的地形遮擋、三維地形偵察也是作者未來的研究方向。

參考文獻(xiàn)（References）

［1］YANG K，KANG Y，SUKKARIEH S.Adaptive nonlinearmodel predictive path-following control for a fixed-wing unmanned aer-ial vehicle［J］.International Journal of Control Automation＆Systems，2013，11（1）：65-74.

［2］CETIN O，ZAGLI I.Continuous airborne communication relay approach using unmanned aerial vehicles［J］.Journal of Intelligent＆Robotic Systems，2012，65（1-4）：549-562.

［3］GENG L，ZHANG Y F，WANG P F，et al.UAV surveillance mission planning with gimbaled sensors［C］∥Control＆Automation（ICCA）.Piscataway，NJ：IEEE Press，2014：320-325.

［4］OBERMEYER K J.Path p lanning for a UAV performing reconnaissance of static ground targets in terrain［C］∥AIAA Guidance，Navigation，and Control Conference and Exhibit.Reston：AIAA，2009.

［5］田菁，沈林成.多基地多無人機(jī)協(xié)同偵察問題研究［J］.航空學(xué)報(bào)，2007，28（4）：913-921.

TIAN J，SHEN L C.Research on multi-basemulti-UAV cooperative reconnaissance problem［J］.Acta Aeronautica et Astronautica Sinica，2007，28（4）：913-921（in Chinese）.

［6］李響，邢清華，董濤.無人機(jī)編隊(duì)協(xié)同偵察效能研究［J］.火力與指揮控制，2013，38（10）：103-110.

LIX，XING Q H，DONG T.Research on cooperative reconnaissance effectiveness of UAV formation［J］.Fire Control＆Command Control，2013，38（10）：103-110（in Chinese）.

［7］OBERMEYER K J，OBERLIN P，DARBHA S.Sampling-based path planning for a visual reconnaissance unmanned air vehicle［J］.Journal of Guidance，Control，and Dynamics，2012，35（2）：619-631.

［8］王劍文，戴光明，謝柏橋，等.求解TSP問題算法綜述［J］.計(jì)算機(jī)工程與科學(xué)，2008，30（2）：72-74.

WANG JW，DAIG M，XIE B Q，et al.A survey of solving the traveling salesman problem［J］.Computer Engineering＆Science，2008，30（2）：72-74（in Chinese）.

［9］宗德才，王康康，丁勇.蟻群算法求解旅行商問題綜述［J］.計(jì)算機(jī)與數(shù)字工程，2014，42（11）：2004-2013.

ZONG D C，WANG K K，DING Y.Review of ant colony algorithm for solving traveling salesman problem［J］.Computer＆Digital Engineering，2014，42（11）：2004-2013（in Chinese）.

［10］黃嵐，王康平，周春光，等.粒子群優(yōu)化算法求解旅行商問題［J］.吉林大學(xué)學(xué)報(bào)（理學(xué)版），2003，41（4）：477-480.

HUANG L，WANG K P，ZHOU C G，et al.Particle swarm optimization for traveling salesman problems［J］.Journal of Jilin University（Science Edition），2003，41（4）：477-480（in Chinese）.

［11］于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問題［J］.控制與決策，2014，29（8）：1483-1488.

YU Y Y，CHEN Y，LIT Y.Improved genetic algorithm for solving TSP［J］.Control and Decision，2014，29（8）：1483-1488（in Chinese）.

［12］杜占瑋，楊永健，孫永雄，等.基于互信息的混合蟻群算法及其在旅行商問題上的應(yīng)用［J］.東南大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，41（3）：478-481.

DU ZW，YANG Y J，SUN Y X，et al.Hybrid ant colony algorithm based on mutual information and its application to traveling salesman problem［J］.Journal of Southeast University（Natural Science Edition），2011，41（3）：478-481（in Chinese）.

［13］YU Q S，WANG D，LIN D M，et al.A novel two-level hybrid algorithm formultiple traveling salesman problems［C］∥3 rd International Conference on Swarm Intelligence，ICSI 2012.Heidelberg：Springer Verlag，2012：497-503..

［14］LEVIN A，YOVEl U.Local search algorithms formultiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees［J］.Journal of Combinatorial Optimization，2014，28（4）：726-747.

［15］DUBINS L E.On curves ofminimal length with a constraint on average curvature，and with prescribed initial and terminal positions and tangents［J］.American Journal of Mathematics，1957，79（3）：497-516.

［16］MEYER Y，ISAIAH P，SHIMA T.On Dubins paths to intercept a moving target［J］.Automatica，2015，53：256-263.

［17］BHATIA A，F(xiàn)RAZZOLI E.Decentralized algorithm for minimum-time rendezvous of Dubins vehicles［C］∥American Control Conference.Piscataway：IEEE Press，2008：1343-1349.

［18］WANG Z，LIY.A target visiting path planning algorithm for the fixed-wing UAV in obstacle environment［C］∥6 th IEEE Chinese Guidance，Navigation and Control Conference，CGNCC 2014.Piscataway：IEEE Press，2014：2774-2778.

［19］史峰.MATLAB智能算法30個(gè)案例分析［M］.北京：北京航空航天大學(xué)出版社，2011：144-149.

SHIF.Analysis of intelligent algorithm in 30 MATLAB cases［M］.Beijing：Beihang University Press，2011：144-149（in Chinese）.

［20］SEGUI-GASCO P，SHIN H S，TSOURDOSA，et al.A combinatorial auction framework for decentralised task allocation［C］∥2014 IEEE Globecom Workshops，GC Wkshps 2014.Piscataway，NJ：IEEE Press，2014：1445-1450.

［21］CHEN P H.Two-level hierarchical approach to unit commitment using expert system and elite PSO［J］.IEEE Transactions on Power Systems，2012，27（2）：780-789.

Tel.：010-82339232

E-mail：zhr＠buaa.edu.cn

Cooperative path p lanning w ith reconnaissance duration tim e constraints

ZHU Qian，ZHOU Rui*

（School of Automation Science and Electrical Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100083，China）

When perform ing reconnaissance tasks，unmanned aerial vehicles（UAVs）keep reconnoitering the targets during different reconnaissance time for acquiring effective target information.It is assumed that UAVs fly in a straight line，which is suitable for better reconnaissance results during reconnaissance m issions.A new simultaneous reconnaissance scheme was proposed by geometrical analysis for less than or equal to three reconnaissance mission overlapping.For the purpose of m inimizing cooperative reconnaissance path length，modified hybrid particle swarm optimization algorithm with elitism mechanism was used to optimize the reconnaissance sequence，and the path p lanning was imp lemented between consecutive reconnaissance m issions by Dubins path，with consideration of reconnaissance missions overlapping and reconnaissance duration time constraints.Simulation results demonstrate the effectiveness of the proposed method.

unmanned aerial vehicle；reconnaissance missions overlapping；cooperative path planning； elitism mechanism；hybrid particle swarm optim ization algorithm

2015-09-18；Accep ted：2015-09-30；Pub lished online：2015-11-19 10：38

s：National Natural Science Foundation of China（61273349，61175109）

TP391

A

1001-5965（2016）10-2130-09

朱黔 男，博士研究生。主要研究方向：多無人機(jī)協(xié)同控制。E-mail：ZhuQian＠buaa.edu.cn

周銳 男，博士，教授，博士生導(dǎo)師。主要研究方向：無人機(jī)自主控制、任務(wù)規(guī)劃與管理、多飛行器協(xié)同控制等。

http：∥bhxb.buaa.edu.cn jbuaa＠buaa.edu.cn

DO I：10.13700／j.bh.1001-5965.2015.0613

2015-09-18；錄用日期：2015-09-30；網(wǎng)絡(luò)出版時(shí)間：2015-11-19 10：38

www.cnki.net／kcms／detail／11.2625.V.20151119.1038.011.htm l

國家自然科學(xué)基金（61273349，61175109）

*通訊作者：Tel.：010-82339232 E-mail：zhr＠buaa.edu.cn

朱黔，周銳.具有持續(xù)偵察時(shí)間約束的協(xié)同航路規(guī)劃［J］.北京航空航天大學(xué)學(xué)報(bào)，2016，42（10）：2130-2138.

ZHU Q，ZHOU R.Cooperative path planning with reconnaissance duration time constraints［J］.Journal of Beijing University of Aeronautics and Astronautics，2016，42（10）：2130-2138（in Chinese）.

URL：www.cnki.net／kcms／detail／11.2625.V.20151119.1038.011.htm l

*Correspond ing au thor.Tel.：010-82339232 E-mail：zhr＠buaa.edu.cn