敖海躍 劉燕斌 李 瑜

1.南京航空航天大學(xué)航天學(xué)院，南京 211106 2.北京空天技術(shù)研究所，北京 100074

0 引言

火星探測一直是國際上深空探測的重點和熱點[1]，1960年開始美國和蘇聯(lián)在火星探測領(lǐng)域進行了激烈的競爭，在2020年7月的火星探測窗口期，中國的火星探測器“天問一號”、美國的“毅力號”和阿聯(lián)酋的“希望號”相繼發(fā)射升空，將國際火星探測又推向一個新的高潮[2]。

火星環(huán)繞器能拍攝較為清晰的衛(wèi)星照片，且工作壽命較長，但是無法做細致的探測；火星著陸車可以對火星表面進行細致的探測，但是探測范圍很小，且火星著陸車的移動受到火星表面復(fù)雜地形的嚴(yán)重限制[3]；而火星飛行器則可以進行較為細致的探測，同時擁有較大的探測范圍[4]，因此火星飛行器在國內(nèi)外獲得了廣泛的研究。隨著火星探測的深入、任務(wù)多樣性程度的增加，由于單飛行器的探測范圍和探測效率有限，有些任務(wù)依靠單架飛行器難以完成。而通過實現(xiàn)多架火星飛行器間的有效協(xié)同，則可以提高探測任務(wù)的效率[5]，因此多飛行器的協(xié)同任務(wù)規(guī)劃問題被廣泛研究。

路徑規(guī)劃是協(xié)同任務(wù)規(guī)劃的重點，對提高飛行器的生存率和任務(wù)完成率有重要意義。路徑規(guī)劃是指給定起始點和目標(biāo)點，考慮危險區(qū)等信息，在多種約束下，尋找到一條符合特定指標(biāo)的最優(yōu)路徑[6]。目前有很多經(jīng)典的路徑規(guī)劃算法：Dijkstra算法是較為經(jīng)典的用于搜索最短路徑的算法[7-8]，可在帶有權(quán)重的復(fù)雜圖中得到最短路徑；A*算法基于Dijkstra算法，引入了啟發(fā)式策略的思想[9]，該算法在很多場景都得到了較好的運用，但是對于復(fù)雜的地圖信息求解的時間復(fù)雜度很高；人工勢場法引入了虛擬力，規(guī)劃出的路線較為平滑，且實時性好[10]，但是存在目標(biāo)點不可達的問題。

隨著智能優(yōu)化算法的興起，鴿群優(yōu)化(PIO)算法、遺傳算法和蟻群算法等也被應(yīng)用到飛行器的路徑規(guī)劃中[11-12]。但是由于智能優(yōu)化算法也存在易陷入局部最優(yōu)的問題，規(guī)劃出的路徑通常為次優(yōu)而非最優(yōu)[13]，所以若想將智能優(yōu)化算法更好地應(yīng)用于路徑規(guī)劃中，還需要將智能優(yōu)化算法進行改進[11]。

文獻[14]在Voronoi圖上使用A*算法實現(xiàn)戰(zhàn)術(shù)導(dǎo)彈的路徑規(guī)劃，但得到的路徑代價和轉(zhuǎn)向角較大；文獻[15]使用改進粒子群優(yōu)化算法實現(xiàn)飛行器路徑規(guī)劃，但是當(dāng)問題維度升高時規(guī)劃可能失敗。本文針對多火星飛行器，提出一種基于改進鴿群優(yōu)化算法的多機協(xié)同路徑規(guī)劃方法，首先利用Dijkstra算法對Voronoi圖劃分的二維平面進行路徑預(yù)規(guī)劃，再利用改進鴿群優(yōu)化算法進行路徑優(yōu)化。相比于文獻[14-15]，該方法能保證規(guī)劃成功且得到代價和轉(zhuǎn)向角更小的路徑。同時針對標(biāo)準(zhǔn)鴿群優(yōu)化算法易陷入局部最優(yōu)、收斂精度低的問題，本文提出采用柯西變異、交流因子和梯度信息改進的鴿群優(yōu)化算法。

1 多火星飛行器路徑規(guī)劃系統(tǒng)建模

多火星飛行器進行路徑規(guī)劃的過程，首先要根據(jù)環(huán)境中各種危險區(qū)的分布情況，建立威脅模型。然后，對環(huán)境空間進行劃分，建立相應(yīng)的路徑代價模型。此外，路徑必須滿足火星飛行器的飛行性能，這樣才能保證規(guī)劃出的路徑具有實際意義。

1.1 威脅源建模

Voronoi圖是一種表示點或?qū)嶓w集合近似信息的幾何結(jié)構(gòu)，被廣泛應(yīng)用于路徑規(guī)劃問題中[14]。根據(jù)環(huán)境威脅信息，取所有危險區(qū)的中心，依次生成危險區(qū)中心的中垂線(即Voronoi邊)，將二維平面進行劃分，生成初始的可飛路徑集。由于Voronoi邊上的點到相鄰的兩個危險區(qū)中心的距離相等，所以飛行器沿著Voronoi邊飛行受到兩個相鄰危險區(qū)的威脅最小，安全系數(shù)較高。

如圖1所示，Voronoi圖中黑色填充的圓形是300m×300m飛行空域內(nèi)的危險區(qū)，虛線表示的是Voronoi邊，多機路徑規(guī)劃問題可以簡化為在Voronoi圖中尋找從起始點到目標(biāo)點飛行代價最小的可飛路徑。

圖1 Voronoi圖法環(huán)境建模

1.2 路徑代價建模

威脅源建模后，還要為每條Voronoi邊分配代價。由于多火星飛行器路徑規(guī)劃的目的是：在保證飛行器安全的前提下，盡可能地節(jié)省燃料，故本文主要考慮燃料代價和危險區(qū)代價。

飛行器可沿著Voronoi邊的兩個方向飛行，假設(shè)所有的飛行器都以恒定的速度飛行，那么每條邊的長度和飛行該段距離所需時間成正比，同時也和燃料消耗成正比。每條邊燃料的代價可以表示為：

(1)

式中：(x1,y1)為一條邊的起始點坐標(biāo)，(x2,y2)為結(jié)束點坐標(biāo)，Jfuel為該條邊的燃料代價。

本文主要考慮因火星的地形和氣象等因素而產(chǎn)生的危險區(qū)，穿越該類危險區(qū)產(chǎn)生的代價非常昂貴，以至于飛行器不會選擇進入危險區(qū)。若某條Voronoi邊與危險區(qū)相交，所產(chǎn)生的危險區(qū)代價可表示為：

Jthreat=1010×Jfuel

(2)

式中：Jthreat為每條邊為危險區(qū)代價。

1.3 火星飛行器的飛行性能

路徑規(guī)劃時必須考慮火星飛行器的飛行性能，否則得到的路徑就沒有意義。由于本文在二維平面內(nèi)進行路徑規(guī)劃，所以主要考慮火星飛行器的最大航程約束和最大轉(zhuǎn)向角約束。

飛行器在飛行的過程中，受到燃料和任務(wù)時間的限制，不能無限地飛行，假設(shè)一條完整的飛行路徑由n條分段組成，則存在飛行器的最大航程約束：

(3)

式中l(wèi)i為第i條分段的長度，Lmax為最大航程。

本文以最大轉(zhuǎn)向角描述飛行器的機動能力。假設(shè)一條完整的飛行路徑有m個節(jié)點，則存在飛行器的最大轉(zhuǎn)向角約束：

θj≤θmax

(4)

式中θj為第j個節(jié)點處的轉(zhuǎn)向角，θmax為最大轉(zhuǎn)向角。

2 多火星飛行器路徑規(guī)劃方法

2.1 多火星飛行器路徑規(guī)劃總體結(jié)構(gòu)

本文提出的基于改進鴿群優(yōu)化算法的多火星飛行器路徑規(guī)劃方法在總體上采用分層規(guī)劃的結(jié)構(gòu)，分為路徑規(guī)劃層、協(xié)同規(guī)劃層和路徑優(yōu)化層。首先在路徑規(guī)劃層，利用Dijkstra算法在Voronoi圖上為每一架飛行器預(yù)規(guī)劃出到每一個目標(biāo)點的備選路徑[16]，并用視線路徑法對預(yù)規(guī)劃路徑進行縮短[8]，初步消除不必要的轉(zhuǎn)彎。然后在協(xié)同規(guī)劃層，通過求解多維多選擇背包問題(MMKP)在所有的備選路徑中確定每一架飛行器的唯一路徑。最后在路徑優(yōu)化層，利用改進鴿群優(yōu)化算法優(yōu)化路徑規(guī)劃層得到的路徑，得到代價更小且符合火星飛行器飛行性能的最終路徑。圖2描述了基于改進鴿群優(yōu)化算法的多火星飛行器路徑規(guī)劃方法的總體結(jié)構(gòu)。

圖2 多火星飛行器路徑規(guī)劃的總體結(jié)構(gòu)

2.2 改進鴿群優(yōu)化算法

針對標(biāo)準(zhǔn)鴿群優(yōu)化算法易陷入局部最優(yōu)、收斂精度低的缺點，為了提高路徑規(guī)劃問題的全局求解能力和最優(yōu)解質(zhì)量，本文在標(biāo)準(zhǔn)鴿群優(yōu)化算法的基礎(chǔ)上，利用柯西變異、學(xué)習(xí)因子和梯度信息3種策略改進標(biāo)準(zhǔn)鴿群優(yōu)化算法。

2.2.1 標(biāo)準(zhǔn)鴿群優(yōu)化算法流程

鴿群優(yōu)化(pigeon-inspired optimization, PIO)算法[17]模型的建立主要包括：鴿群速度、位置等信息的初始化，在算法前期利用地圖羅盤算子更新鴿群的速度與位置，在后期利用地標(biāo)算子進行更新。

首先，初始化鴿群優(yōu)化算法中的種群數(shù)量、迭代次數(shù)等信息，確定適應(yīng)度值的計算方法。同時隨機初始化鴿群的速度與位置。第i只鴿子的位置Xi、速度Vi可表示為：

Xi=[Xi(1)Xi(2) …Xi(n)]T

(5)

Vi=[Vi(1)Vi(2) …Vi(n)]T

(6)

算法前期利用地圖羅盤算子迭代更新，第i只鴿子在第t次迭代中的速度為Vi(t)，位置為Xi(t)，當(dāng)前鴿群中最優(yōu)個體的速度為Vg，位置為Xi，迭代更新方法為：

Vi(t)=Vi(t-1)·exp(-Rt)+
r·(Xg-Xi(t-1))

(7)

Xi(t)=Xi(t-1)+Vi(t)

(8)

式中，R為地磁因子，視具體問題取值。r為在[0,1]上均勻分布的隨機數(shù)。

算法后期利用地標(biāo)算子迭代更新，第i只鴿子在第t次迭代中的位置為Xi(t)，當(dāng)前鴿子的中心位置為Xc，更新后根據(jù)適應(yīng)度值的大小將所有鴿子進行排序，每次迭代淘汰掉一半的鴿子，迭代更新方法為：

(9)

(10)

Xi(t)=Xi(t-1)+r·(Xc-Xi(t-1))

(11)

式中，NP(t)為第t次迭代后鴿子種群數(shù)量，F(xiàn)為適應(yīng)度函數(shù)。

2.2.2 柯西變異

柯西分布在原點處峰值較小，而兩端的分布較長，利用柯西變異可在當(dāng)前變異個體附近產(chǎn)生較大擾動。因此，可通過引入柯西變異來增加種群的多樣性，解決鴿群優(yōu)化算法易陷入局部最優(yōu)的問題[18]。

本文選取標(biāo)準(zhǔn)柯西逆累積分布函數(shù)對鴿子個體產(chǎn)生變異，標(biāo)準(zhǔn)柯西逆累積分布函數(shù)如式所示。在初始化后和地圖羅盤算子后對全局最優(yōu)Xg進行柯西變異，若變異后更優(yōu)，則按式更新全局最優(yōu)Xg。

(12)

Xg→Xg·kCauchy

(13)

式中：kCauchy為柯西算子，r為[0,1]上均勻分布的隨機數(shù)。

2.2.3 交流因子

鴿群優(yōu)化算法在地圖羅盤算子后期存在過早收斂的問題，所以在算法尋優(yōu)的過程中，可以通過控制后期局部搜索的速度避免這一問題[19]。

本文在鴿群優(yōu)化算法中引入交流因子，來調(diào)節(jié)全局最優(yōu)位置在地圖羅盤算子階段的影響權(quán)重，使算法后期具有較強的局部搜索能力。交流因子隨著迭代次數(shù)的增加從0非線性地增加到1。因此將鴿群優(yōu)化算法中速度更新公式更改為：

Vi(t)=c1·Vi(t-1)+c2·r·(Xg-Xi(t-1))

(14)

(15)

c2=1-c1

(16)

式中c1為慣性權(quán)重，c2為交流因子，A、B、C為常數(shù)，視具體問題取值。

2.2.4 梯度信息

鴿群優(yōu)化算法依賴鴿群的隨機搜索，沒有考慮具體問題的特性，不利用求解對象的梯度信息，但利用梯度信息可以使鴿群的移動更有針對性和效率[20]。一個多元函數(shù)f的梯度可以表示如下：

(17)

式中NP表示鴿群的數(shù)量。

本文利用梯度信息影響鴿群的迭代更新。在地圖羅盤算子階段，鴿群中有一定比例P1的鴿子將沿著當(dāng)前位置的負(fù)梯度方向前進。以第i只鴿子在第t次迭代中，其速度更新公式改為：

(18)

利用柯西變異、交流因子和梯度信息的改進鴿群優(yōu)化算法(GCCPIO)的流程圖如圖3所示。

圖3 GCCPIO流程圖

3 仿真校驗

為驗證基于改進鴿群優(yōu)化算法的多火星飛行器路徑規(guī)劃方法的可行性和性能，在300m×300m坐標(biāo)系內(nèi)進行不同威脅環(huán)境下的仿真實驗。飛行器的約束為最大航程424m，最大轉(zhuǎn)向角45°。本文考慮3架飛行器和3個目標(biāo)的情況，危險區(qū)均為圓形，半徑為10m。在不同威脅環(huán)境下分別測試?yán)肰oronoi圖和Dijkstra算法的傳統(tǒng)協(xié)同路徑規(guī)劃方法(下文簡稱VD法)以及本文提出的基于GCCPIO的協(xié)同路徑規(guī)劃方法(下文簡稱VDP法)的性能。飛行器、目標(biāo)的坐標(biāo)如表1所示：

表1 飛行器、目標(biāo)參數(shù)

實驗中GCCPIO相關(guān)參數(shù)設(shè)置為：種群個數(shù)取300，NC1max=80,NC2max=20，R=0.5，A=1.2，B=0.5，C=-1，P1=5%，路徑分為20段，適應(yīng)度函數(shù)的公式如下：

(19)

在一般威脅環(huán)境下的仿真測試結(jié)果如圖4～ 5所示，其中菱形為飛行器的起始點，五角星為目標(biāo)點，黑色填充圓形為危險區(qū)。

圖4 一般威脅環(huán)境下VD法得到的路徑

圖5 一般威脅環(huán)境下VDP法得到的路徑

當(dāng)增加環(huán)境復(fù)雜度時，仍按照表1實驗參數(shù)進行測試，測試結(jié)果如圖6～ 7所示。

圖6 復(fù)雜威脅環(huán)境下VD法得到的路徑

圖7 復(fù)雜威脅環(huán)境下VDP法得到的路徑

在2種威脅環(huán)境下，分別使用VD法和VDP法得到的測試結(jié)果見表2。

表2 2種環(huán)境下2種路徑規(guī)劃方法的測試結(jié)果

測試結(jié)果顯示，使用傳統(tǒng)的VD法得到的路徑因轉(zhuǎn)向角過大而不滿足飛行器的約束。而不論是在一般的還是較復(fù)雜的威脅環(huán)境下，本文提出的基于改進鴿群優(yōu)化算法的多火星飛行器路徑規(guī)劃方法都能得到滿足約束的可飛路徑，克服了傳統(tǒng)VD法所得路徑不平滑的問題，且具有代價更小的優(yōu)勢。

4 結(jié)論

提出了一種融合經(jīng)典路徑規(guī)劃算法和改進鴿群優(yōu)化算法的協(xié)同路徑規(guī)劃方法，設(shè)計了基于3種策略改進的鴿群優(yōu)化算法，可為保持一定高度飛行的多火星飛行器提供二維平面內(nèi)的可飛協(xié)同路徑。與經(jīng)典路徑規(guī)劃方法相比，該方法所得路徑轉(zhuǎn)向角更小，在解決多火星飛行器路徑優(yōu)化問題中具有較好的應(yīng)用前景。