一種多火星飛行器路徑規劃方法

敖海躍 劉燕斌 李 瑜

1.南京航空航天大學航天學院，南京 211106 2.北京空天技術研究所，北京 100074

0 引言

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

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

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

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

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

1 多火星飛行器路徑規劃系統建模

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

1.1 威脅源建模

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

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

圖1 Voronoi圖法環境建模

1.2 路徑代價建模

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

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

(1)

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

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

Jthreat=1010×Jfuel

(2)

式中：Jthreat為每條邊為危險區代價。

1.3 火星飛行器的飛行性能

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

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

(3)

式中li為第i條分段的長度，Lmax為最大航程。

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

θj≤θmax

(4)

式中θj為第j個節點處的轉向角，θmax為最大轉向角。

2 多火星飛行器路徑規劃方法

2.1 多火星飛行器路徑規劃總體結構

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

圖2 多火星飛行器路徑規劃的總體結構

2.2 改進鴿群優化算法

針對標準鴿群優化算法易陷入局部最優、收斂精度低的缺點，為了提高路徑規劃問題的全局求解能力和最優解質量，本文在標準鴿群優化算法的基礎上，利用柯西變異、學習因子和梯度信息3種策略改進標準鴿群優化算法。

2.2.1 標準鴿群優化算法流程

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

首先，初始化鴿群優化算法中的種群數量、迭代次數等信息，確定適應度值的計算方法。同時隨機初始化鴿群的速度與位置。第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)，當前鴿群中最優個體的速度為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]上均勻分布的隨機數。

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

(9)

(10)

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

(11)

式中，NP(t)為第t次迭代后鴿子種群數量，F為適應度函數。

2.2.2 柯西變異

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

本文選取標準柯西逆累積分布函數對鴿子個體產生變異，標準柯西逆累積分布函數如式所示。在初始化后和地圖羅盤算子后對全局最優Xg進行柯西變異，若變異后更優，則按式更新全局最優Xg。

(12)

Xg→Xg·kCauchy

(13)

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

2.2.3 交流因子

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

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

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

(14)

(15)

c2=1-c1

(16)

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

2.2.4 梯度信息

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

(17)

式中NP表示鴿群的數量。

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

(18)

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

圖3 GCCPIO流程圖

3 仿真校驗

為驗證基于改進鴿群優化算法的多火星飛行器路徑規劃方法的可行性和性能，在300m×300m坐標系內進行不同威脅環境下的仿真實驗。飛行器的約束為最大航程424m，最大轉向角45°。本文考慮3架飛行器和3個目標的情況，危險區均為圓形，半徑為10m。在不同威脅環境下分別測試利用Voronoi圖和Dijkstra算法的傳統協同路徑規劃方法(下文簡稱VD法)以及本文提出的基于GCCPIO的協同路徑規劃方法(下文簡稱VDP法)的性能。飛行器、目標的坐標如表1所示：

表1 飛行器、目標參數

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

(19)

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

圖4 一般威脅環境下VD法得到的路徑

圖5 一般威脅環境下VDP法得到的路徑

當增加環境復雜度時，仍按照表1實驗參數進行測試，測試結果如圖6～ 7所示。

圖6 復雜威脅環境下VD法得到的路徑

圖7 復雜威脅環境下VDP法得到的路徑

在2種威脅環境下，分別使用VD法和VDP法得到的測試結果見表2。

表2 2種環境下2種路徑規劃方法的測試結果

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

4 結論

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