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

敖海躍 劉燕斌 李 瑜

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

0 引言

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

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

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

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

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

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

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

1.1 威脅源建模

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

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

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

1.2 路徑代價(jià)建模

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

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

(1)

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

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

Jthreat=1010×Jfuel

(2)

式中：Jthreat為每條邊為危險(xiǎn)區(qū)代價(jià)。

1.3 火星飛行器的飛行性能

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

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

(3)

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

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

θj≤θmax

(4)

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

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

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

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

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

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

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

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

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

首先，初始化鴿群優(yōu)化算法中的種群數(shù)量、迭代次數(shù)等信息，確定適應(yīng)度值的計(jì)算方法。同時(shí)隨機(jī)初始化鴿群的速度與位置。第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)個(gè)體的速度為Vg，位置為Xi，迭代更新方法為：

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

(7)

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

(8)

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

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

(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 柯西變異

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

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

(12)

Xg→Xg·kCauchy

(13)

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

2.2.3 交流因子

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

本文在鴿群優(yōu)化算法中引入交流因子，來(lái)調(diào)節(jié)全局最優(yōu)位置在地圖羅盤算子階段的影響權(quán)重，使算法后期具有較強(qiáng)的局部搜索能力。交流因子隨著迭代次數(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ù)，視具體問(wèn)題取值。

2.2.4 梯度信息

鴿群優(yōu)化算法依賴?guó)澣旱碾S機(jī)搜索，沒(méi)有考慮具體問(wèn)題的特性，不利用求解對(duì)象的梯度信息，但利用梯度信息可以使鴿群的移動(dòng)更有針對(duì)性和效率[20]。一個(gè)多元函數(shù)f的梯度可以表示如下：

(17)

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

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

(18)

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

圖3 GCCPIO流程圖

3 仿真校驗(yàn)

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

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

實(shí)驗(yàn)中GCCPIO相關(guān)參數(shù)設(shè)置為：種群個(gè)數(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)境下的仿真測(cè)試結(jié)果如圖4～ 5所示，其中菱形為飛行器的起始點(diǎn)，五角星為目標(biāo)點(diǎn)，黑色填充圓形為危險(xiǎn)區(qū)。

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

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

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

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

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

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

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

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

4 結(jié)論

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