基于遺傳算法與Dubins理論的高速無人系統(tǒng)在多障礙環(huán)境中的路徑規(guī)劃

李 艷，郭繼峰，羅汝斌

（1.北京宇航系統(tǒng)工程研究所，北京 100074；2.哈爾濱工業(yè)大學(xué)航天學(xué)院，哈爾濱 150001）

1 引 言

美國國防部2018年8月發(fā)布了《2017—2042財(cái)年無人系統(tǒng)綜合路線圖》[1]，對無人系統(tǒng)的發(fā)展提供了總體戰(zhàn)略指南。在此路線圖中，無人系統(tǒng)自主性作為4 個(gè)關(guān)鍵主題內(nèi)容之一，是美軍近年來對無人系統(tǒng)重點(diǎn)布局的發(fā)展方向。而無人系統(tǒng)自主導(dǎo)航是實(shí)現(xiàn)無人系統(tǒng)高度自主性的關(guān)鍵技術(shù)。無人系統(tǒng)自主導(dǎo)航包括4 個(gè)基本要求，即感知、定位、路徑規(guī)劃、運(yùn)動控制，其中路徑規(guī)劃是最重要的部分之一。目前，無人系統(tǒng)的路徑規(guī)劃算法可以分為經(jīng)典方法和啟發(fā)式方法[2-3]，如圖1 所示。

圖1 路徑規(guī)劃算法的基本分類Fig.1 Basic classification of path planning algorithms

目前，主要的經(jīng)典方法包括單元分解法（Cell Decomposition Method，CD）、勢場法（Potential Field Method，PFM）、基于采樣的方法（Sampling- Based Method，SBP）和Dubins 算法。在CD 中，機(jī)器人配置的自由空間被劃分為稱為單元的小區(qū)域，目標(biāo)是提供一條無碰撞路徑，以到達(dá)目標(biāo)。基于該方法的機(jī)器人路徑規(guī)劃應(yīng)用見文獻(xiàn)[4-5]。在PFM 中，障礙物和目標(biāo)分別被賦予排斥力和吸引力，這樣機(jī)器人就能夠在遠(yuǎn)離障礙物的同時(shí)朝著目標(biāo)移動[6]。為了解決動力學(xué)環(huán)境中的路徑規(guī)劃問題，文獻(xiàn)[7]中引入了對經(jīng)典PFM 的修改。SBP 算法的規(guī)劃方案由于其在復(fù)雜的現(xiàn)實(shí)世界規(guī)劃問題中的能力而受到相當(dāng)大的關(guān)注。目前，應(yīng)用最多的SBP 算法包括概率路線圖（Probabilistic Route Map ， PRM ）和快速探索隨機(jī)樹（Rapid-exploration Random Tree，RRT）[8]。盡管連接隨機(jī)采樣點(diǎn)的概念在這兩種方法中都是基本的，但這兩種方法在構(gòu)建連接點(diǎn)的方式上是不同的。文獻(xiàn)[9]對SBP 的工作進(jìn)行了全面調(diào)查。而RRT 因其計(jì)算效率和有效性以及相對快速地找到可行運(yùn)動計(jì)劃的能力而受到了相當(dāng)多的關(guān)注，即使在高維空間中也有一定的應(yīng)用[10]。上述方法把機(jī)器人當(dāng)作質(zhì)點(diǎn)，未考慮其自身的運(yùn)動約束以及由于其最小轉(zhuǎn)彎半徑對于避障帶來的影響，而Dubins 曲線是給定始末方向以及在轉(zhuǎn)彎半徑有約束的情況下兩點(diǎn)之間的最短曲線，被廣泛應(yīng)用于自主機(jī)器人的路徑規(guī)劃中。文獻(xiàn)[11]將Dubins算法應(yīng)用到無人機(jī)的避障規(guī)劃中，實(shí)現(xiàn)了無人機(jī)的實(shí)時(shí)避障規(guī)劃。

然而，經(jīng)典方法應(yīng)用于實(shí)時(shí)運(yùn)動規(guī)劃時(shí)會有一定的缺陷，這些算法容易傾向于鎖定在某些局部最優(yōu)值中而忽略了全局最優(yōu)路徑。而且，它們中的一些可能無法在存在多個(gè)障礙物的環(huán)境中提供合適的解決方案。啟發(fā)式方法解決了這一問題。

常用的啟發(fā)式方法包括神經(jīng)網(wǎng)絡(luò)、模糊邏輯和自然啟發(fā)法。神經(jīng)網(wǎng)絡(luò)由于具有非線性映射、學(xué)習(xí)能力和并行處理等優(yōu)點(diǎn)，已成功地應(yīng)用于機(jī)器人路徑規(guī)劃中[12-13]。在模糊邏輯算法中，機(jī)器人導(dǎo)航是基于一組if-then 規(guī)則。在文獻(xiàn)[14-15]中，引入了基于模糊邏輯的不同方法來解決機(jī)器人路徑規(guī)劃問題。一些受生物學(xué)行為啟發(fā)而廣為人知的算法已成功地應(yīng)用于機(jī)器人路徑規(guī)劃[16]，如遺傳算法[11-15,17]、粒子群優(yōu)化[18]和蟻群優(yōu)化[19]。其中，遺傳算法是一種基于自然遺傳學(xué)的優(yōu)化工具，它利用了自然選擇、交叉和變異等過程的優(yōu)勢，在解決組合優(yōu)化問題上具有很大的潛力。

本文結(jié)合遺傳算法與Dubins 理論，提出了求解高速無人系統(tǒng)在多障礙環(huán)境下的路徑規(guī)劃算法。本文首先分別介紹了傳統(tǒng)遺傳算法和Dubins理論，然后提出了基于遺傳算法與Dubins 理論的路徑規(guī)劃算法，在算法設(shè)計(jì)中，對路徑的編碼方式做了深入的研究，使得其適合在多障礙場景中采用遺傳算法求解滿足高速無人系統(tǒng)運(yùn)動約束的最優(yōu)路徑。

2 基本問題模型

2.1 遺傳算法

遺傳算法使用了群體搜索技術(shù)，將種群代表一組問題的解，通過對當(dāng)前種群施加選擇、交叉和變異等一系列遺傳操作，產(chǎn)生新一代的種群，并逐步使種群進(jìn)化到包含近似最優(yōu)解的狀態(tài)。遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性。該算法主要流程如圖2 所示。

圖2 遺傳算法基本流程Fig.2 Basic process of genetic algorithm

2.2 Dubins 理論

Dubins 于1957年提出了Dubins 曲線理論，主要內(nèi)容是在滿足一定曲率條件下，連接同一平面內(nèi)具有特定方向向量的任意兩點(diǎn)的最短軌跡是曲線[20]。在沒有其他約束因素的情況下，同一平面上的任意兩點(diǎn)的最短路徑是直線，但是在有一定的曲率約束的情況下，最短的路徑則是圓弧。Dubins 曲線理論主要用來求解有曲率約束的最短路徑。

通過選擇兩條與兩個(gè)圓相切的切線中的一條，可以得到Dubins 路徑，其中起始和終止位置都在圓弧上。圓弧的半徑是曲率半徑，它由無人系統(tǒng)的轉(zhuǎn)彎半徑?jīng)Q定，圓弧中心就是曲率中心，于是該問題就簡化為尋找兩個(gè)圓弧的公切線。兩圓之間有兩種公切線：內(nèi)切線、外切線。

在給定位姿點(diǎn)下，無人系統(tǒng)可以向左轉(zhuǎn)和向右轉(zhuǎn)，路徑可以以順時(shí)針方向和逆時(shí)針方向結(jié)束。一個(gè)給定的位姿點(diǎn)上有兩種轉(zhuǎn)彎方式，因此有兩個(gè)相切圓，如圖3 所示。一個(gè)向右轉(zhuǎn)彎，在弧段 1C上標(biāo)記R，另一個(gè)是向左轉(zhuǎn)彎，在弧段 2C上標(biāo)記L，一個(gè)位姿點(diǎn)可以產(chǎn)生4 條Dubins 路徑。即LSL，LSR，RSL，RSR， 如圖4 所示。

圖3 相切圓Fig.3 Tangent circles

圖4 4 種Dubins 路徑Fig.4 Four Dubins paths

無人系統(tǒng)路徑規(guī)劃問題是指在已知環(huán)境下，給定起點(diǎn)和終點(diǎn)，使無人系統(tǒng)在一定的優(yōu)化目標(biāo)下無碰撞地由起點(diǎn)飛到終點(diǎn)。在這種情況下，障礙的位置和大小是已知的，無人系統(tǒng)的性能是已知的。在本文中，最優(yōu)目標(biāo)是使無人系統(tǒng)的飛行路徑最短。本文主要考慮的約束條件是無人系統(tǒng)的最小轉(zhuǎn)彎半徑。

3 基于遺傳算法與Dubins 理論的路徑規(guī)劃算法

本文提出基于遺傳算法和Dubins 原理的高速無人系統(tǒng)路徑規(guī)劃方法。其中，遺傳算法用于求解最優(yōu)路徑，Dubins 原理用于滿足無人系統(tǒng)的約束條件。遺傳算法可以解決多障礙環(huán)境下的路徑規(guī)劃問題，但其規(guī)劃出的路徑?jīng)]有考慮無人系統(tǒng)最小轉(zhuǎn)彎半徑這一約束條件，大多數(shù)都是不可飛路徑；基于Dubins 理論的路徑規(guī)劃算法考慮了無人系統(tǒng)最小轉(zhuǎn)彎半徑的約束，求解得到的路徑為可飛路徑，并且還使得到達(dá)終點(diǎn)的速度方向可控，具有很高的實(shí)用性，但不能解決多障礙環(huán)境下的路徑規(guī)劃問題。將兩者結(jié)合可得到一種有效解決多障礙環(huán)境下路徑規(guī)劃問題的方法，此方法使得規(guī)劃出的路徑平滑可飛，終點(diǎn)速度方向可控，其難點(diǎn)在于對路徑的編碼上，本文提出了一種針對障礙物的編碼方式，有效地解決了上述問題。

3.1 針對障礙物的路徑編碼方式

在已知無人系統(tǒng)出發(fā)點(diǎn)Ps(xs,ys)、初始速度方向vs，終點(diǎn)Pf(xf,yf)、終點(diǎn)速度向量vf，最小轉(zhuǎn)彎半徑R和障礙圓模型Dk(k=1,2,…,n)的位置和大小的情況下，所求的路徑是一條至少與l(l∈ [ 0,n])個(gè)障礙圓相切的曲線。則問題轉(zhuǎn)化為求最短路徑(Cs,Cf)=(Cs,W,Cf)的問題，其中W是該路徑遍歷的各個(gè)障礙圓序列組成的集合，其中有l(wèi)個(gè)障礙圓與路徑相切。編碼方式要包含W中的所有可能，一種可行的編碼方式是采用冗余二進(jìn)制編碼的方式[11]。假設(shè)有4 個(gè)障礙物，若要表示所有的情況則至少需要3 位二進(jìn)制編碼。編碼方式如表1 所示。

表1 遺傳算法編碼表1Table 1 Genetic algorithm coding table1

利用上述編碼方式，可表示的一種路徑的編碼方式是(001, 100, 011, 111)，其表示的路徑序列為(D2, Blank,D4, Blank)，則這種序列得出的路 徑為(Cs,D2,D4,Cf)，表示由起始點(diǎn)出發(fā)，先與第2 個(gè)障礙圓相切，再與第4 個(gè)障礙圓相切最后到達(dá)終點(diǎn)。這種編碼方式只是給出了路徑遍歷障礙圓的順序，并沒有給出與障礙圓相切的方式，即這種編碼方式給出的路徑不唯一。為了使得到的路徑唯一，本文將有向曲線與圓的相切方式也加入到編碼方式中。

所有操作都在超凈實(shí)驗(yàn)室內(nèi)完成，室溫25 °C。采用Baseline拋光液，其成分為：20%(質(zhì)量分?jǐn)?shù))硅溶膠，5%(體積分?jǐn)?shù))FAOI螯合劑(河北工業(yè)大學(xué)自主研發(fā)，含有多羧基多胺基，具備13個(gè)以上螯合環(huán))，0.05%(體積分?jǐn)?shù))雙氧水。所用表面活性劑分別為弱堿性的FAOA和AEO(其分子結(jié)構(gòu)見圖1，R表示12個(gè)碳的鏈狀烷基，n為常數(shù))。

考慮到有向曲線與圓的相切方式時(shí)，路徑的編碼方式將發(fā)生變化。每一個(gè)圓都有兩種情況，圓在切線左邊或者圓在切線右邊，在編碼時(shí)每個(gè)圓就有兩種編碼方式分別代表以上兩種情況。根據(jù)以上方法對上述4 個(gè)障礙圓編碼，總共有12 種情況，需要4 位二進(jìn)制編碼。編碼方式如表2 所示。

表2 遺傳算法編碼表2Table 2 Genetic algorithm coding table2

根據(jù)上述編碼，可表示的一條路徑是(0000， 0100，1111，0111)，即路徑序列為(D1，D3，Blank，D4)，其表示的路徑如圖5 所示。以上編碼的路徑只能保證路徑不與障礙物D1，D3與D4發(fā)生碰撞，并不能保證不與其他障礙物發(fā)生碰撞。在適應(yīng)度函數(shù)的設(shè)計(jì)中，通過增加碰撞檢測解決這一問題。

圖5 障礙圓之間的Dubins 路徑Fig.5 Dubins paths between obstacle circles

3.2 適應(yīng)度函數(shù)

本文所規(guī)劃的路徑是由起點(diǎn)到終點(diǎn)的無碰撞最短路徑。所以，適應(yīng)度函數(shù)應(yīng)該能滿足無碰撞和最短這兩個(gè)條件。本文采用路徑長度的倒數(shù)作為目標(biāo)函數(shù)，在計(jì)算路徑長度時(shí)，若當(dāng)前路徑與障礙物相交，則將當(dāng)前路徑的長度給一個(gè)較大值，以保證所求路徑與障礙物不相交。所設(shè)計(jì)的遺傳算法適應(yīng)度函數(shù)為

式中，L為路徑的長度；K為調(diào)節(jié)系數(shù)，其主要是因?yàn)長的值遠(yuǎn)大于1，所以求得的適應(yīng)度函數(shù)值非常小，不利于種群的進(jìn)化，所以乘以一個(gè)與L同量級的數(shù)調(diào)節(jié)適應(yīng)度函數(shù)的值，保證種群的正常進(jìn)化。

4 仿真驗(yàn)證

4.1 飛行環(huán)境建模

在高速無人系統(tǒng)執(zhí)行任務(wù)的過程中，將會面臨敵方的探測雷達(dá)、攔截導(dǎo)彈、電子干擾等威脅，這些威脅的作用范圍一般為不規(guī)則的幾何形狀。在本文研究中，為了統(tǒng)一威脅障礙建模，方便計(jì)算，將高速無人系統(tǒng)可能遇到的威脅障礙抽象為圓形模型，即威脅障礙是以其中心點(diǎn)為圓心的圓形區(qū)域,此圓形區(qū)域是包絡(luò)威脅障礙的最小圓形區(qū)域。同時(shí)，考慮到無人系統(tǒng)自身的體積大小以及導(dǎo)航制導(dǎo)控制系統(tǒng)帶來的誤差，直接在上述圓形障礙物基礎(chǔ)上進(jìn)行避障將有一定的風(fēng)險(xiǎn)?；诎踩钥紤]，我們在障礙物的大小上增加距離為ΔRs的安全距離，在增加安全距離之后，障礙物的作用半徑將增加至Rs(i)=R(i) +ΔRs。安全距離ΔRs的取值可根據(jù)無人系統(tǒng)的體積大小，飛行速度，導(dǎo)航制導(dǎo)控制系統(tǒng)誤差等因素綜合考慮。綜上所述，經(jīng)過飛行環(huán)境建模之后的威脅區(qū)域半徑RD為：

式中，RD(i)為考慮高速無人系統(tǒng)最小轉(zhuǎn)彎半徑之后的第i個(gè)威脅障礙區(qū)域的半徑；rmin為無人系統(tǒng)的最小轉(zhuǎn)彎半徑；R(i)為包絡(luò)第i個(gè)威脅障礙區(qū)域的最小圓的半徑。表3 所示為一個(gè)考慮了多種威脅的飛行環(huán)境，最小轉(zhuǎn)彎半徑取值為rmin=173 km，安全距離取值為ΔRs=20 km。

表3 考慮多種威脅的飛行環(huán)境建模Table 3 Modeling the flight environment under multiple threats

假設(shè)飛行器的起點(diǎn)為(0, 500) km，終點(diǎn)為(3000, 1000) km，根據(jù)上述步驟構(gòu)建的飛行環(huán)境如圖6 所示。其中，紅色多邊形填充區(qū)域?yàn)楦魍{的實(shí)際形狀，紅色實(shí)線圓表示包圍實(shí)際威脅區(qū)域的最小包絡(luò)圓，粉色點(diǎn)線表示考慮無人系統(tǒng)最小轉(zhuǎn)彎半徑之后的威脅圓，綠色虛線圓為增加安全距離之后的威脅圓。

圖6 包含多種威脅的飛行環(huán)境Fig.6 A flight environment with multiple threats

4.2 無人系統(tǒng)最小轉(zhuǎn)彎半徑

根據(jù)上述方程，可以得到無人系統(tǒng)的最小轉(zhuǎn)彎半徑rmin為：

式中，g為重力加速度。

4.3 仿真結(jié)果

我們使用第3 節(jié)提出的算法，在4.1 節(jié)描述的飛行環(huán)境中規(guī)劃無人系統(tǒng)從起始狀態(tài)到終止?fàn)顟B(tài)的路徑。所求飛行環(huán)境中，共有11 個(gè)障礙物，每個(gè)障礙物需要6 個(gè)二進(jìn)制編碼表示，所以共需66 位二進(jìn)制編碼才能表示一條路徑。初始種群大小設(shè)置為500，最大進(jìn)化代數(shù)為50，交配概率為0.95，變異概率為0.1，選擇步驟選用輪盤賭選擇方式，交叉步驟選用單點(diǎn)交叉方式，變異步驟選用基本位變異方式。適應(yīng)度函數(shù)中參數(shù)K的值設(shè)為1000 km。假設(shè)無人系統(tǒng)的飛行速度為1 km/s，最大滾轉(zhuǎn)角為30°，根據(jù)式(4)可求得無人系統(tǒng)的最小轉(zhuǎn)彎半徑為173 km。我們將本文提出的算法與兩個(gè)傳統(tǒng)算法進(jìn)行對比，即A*算法[21]與基于Dubins 曲線修正的A*算法[22]。A*算法是一種常用的路徑搜索算法，用于在離散環(huán)境中搜索從起點(diǎn)到終點(diǎn)的最優(yōu)路徑，但其搜索出的路徑由折線段構(gòu)成，路徑連接處不滿足無人系統(tǒng)的運(yùn)動約束條件，故不能單獨(dú)用于具有運(yùn)動約束的無人系統(tǒng)路徑規(guī)劃中?；贒ubins 曲線修正的A*算法對A*算法搜索出的路徑進(jìn)行了平滑處理，使路徑連接處滿足無人系統(tǒng)的運(yùn)動約束，使其可用于實(shí)際應(yīng)用。

4.3.1 靜態(tài)環(huán)境仿真

在上述靜態(tài)環(huán)境中，進(jìn)行了算法性能的對比實(shí)驗(yàn)。對于每一種算法，在上述飛行環(huán)境中進(jìn)行了100 次隨機(jī)實(shí)驗(yàn)，在每次實(shí)驗(yàn)中，固定障礙物不變，隨機(jī)選取無人系統(tǒng)的初始狀態(tài)以及終點(diǎn)狀態(tài)，計(jì)算規(guī)劃路徑的長度。各算法性能對比結(jié)果如表4 所示。

表4 路徑規(guī)劃算法性能對比結(jié)果Table 4 Path planning algorithm performance comparison results

由表4 可知，A*算法規(guī)劃的路徑最短，使用Dubins 曲線修正的A*算法規(guī)劃的路徑最長，基于遺傳算法與Dubins 曲線規(guī)劃方法規(guī)劃出的路徑長度在兩者之間。A*算法能夠規(guī)劃出最短的路徑是因?yàn)槠洳豢紤]無人系統(tǒng)的運(yùn)動約束，規(guī)劃出的路徑是由直線段連接而成的，無法滿足無人系統(tǒng)的最小轉(zhuǎn)彎半徑，不可實(shí)際應(yīng)用于高速無人系統(tǒng)的路徑規(guī)劃中。使用Dubins 曲線修正的A*算法規(guī)劃的路徑最長，是由于其直接在A*規(guī)劃的路徑上進(jìn)行了修正，無法充分利用飛行環(huán)境的特征，只能求得次優(yōu)解。而基于遺傳算法與Dubins 曲線的規(guī)劃方法從全局考慮，結(jié)合無人系統(tǒng)的約束條件與飛行環(huán)境，將可行路徑進(jìn)行編碼，使用遺傳算法進(jìn)行搜索求解，理論上在足夠大的種群規(guī)模與迭代次數(shù)下，可以搜索得到最優(yōu)解。一般規(guī)模的問題無須設(shè)置大規(guī)模種群與高迭代次數(shù)即可求解到最優(yōu)解。通過以上性能對比實(shí)驗(yàn)結(jié)果分析可知，本文提出的算法可得到滿足無人系統(tǒng)運(yùn)動約束以及初始狀態(tài)與終止?fàn)顟B(tài)約束的最短路徑。

以下仿真實(shí)例直觀地展示了各種規(guī)劃算法的特點(diǎn)。仿真實(shí)驗(yàn)設(shè)置為：無人系統(tǒng)初始位置為(0, 500) km，初始速度為(1, 0) km/s,目標(biāo)位置為(3000, 1000) km，目標(biāo)速度為(0, -1) km/s，飛行環(huán)境中各威脅障礙均為靜止?fàn)顟B(tài)。仿真結(jié)果如圖7 所示。

圖7(a)所示為在上述飛行環(huán)境中各算法所規(guī)劃出的路徑。藍(lán)色實(shí)線為本文提出的基于遺傳算法與Dubins 曲線規(guī)劃方法規(guī)劃出的路徑，路徑總長為3460.5 km，路徑與3 個(gè)障礙圓相切，同時(shí)在初始點(diǎn)與目標(biāo)點(diǎn)處生成最小轉(zhuǎn)彎半徑圓，路徑與起始圓以及終止圓相切，滿足速度矢量約束。深綠色實(shí)線為A*算法規(guī)劃出的路徑，路徑長度為3369.4 km?？梢钥闯觯m然A*算法可以規(guī)劃出更短的路徑，但路徑由多條折線段構(gòu)成，在路徑連接處不夠平滑，無法滿足無人系統(tǒng)的運(yùn)動約束，且在終點(diǎn)處沒有滿足速度矢量約束，故不能實(shí)際應(yīng)用。黃色實(shí)線為在A*算法規(guī)劃的路徑基礎(chǔ)上經(jīng)過Dubins 曲線修正后的路徑。經(jīng)過Dubins 曲線的修正，路徑連接處由滿足無人系統(tǒng)運(yùn)動約束的圓弧連接，且在終點(diǎn)處通過圓弧連接直線路徑，使規(guī)劃出的路徑滿足終點(diǎn)速度矢量約束。通過以上修正過程，路徑長度增加到4208.1 km，長于基于遺傳算法與Dubins 曲線規(guī)劃方法規(guī)劃出的路徑長度。

圖7(b)所示為基于遺傳算法與Dubins 曲線規(guī)劃方法的迭代求解過程。曲線所示為種群的適應(yīng)度函數(shù)值變化情況。由圖中結(jié)果可知，種群的最大適應(yīng)度與平均適應(yīng)度在不斷增大，表明種群朝著有利的方向進(jìn)化，所求得的路徑逐步變短，最 后收斂到最短路徑。

圖7 靜態(tài)環(huán)境仿真結(jié)果Fig.7 Static environment simulation results

4.3.2 動態(tài)環(huán)境仿真

我們使用一次典型的仿真實(shí)驗(yàn)說明本文所提算法的動態(tài)避障過程。仿真場景設(shè)置為：無人系 統(tǒng)初始位置為(0, 500) km，初始速度為(1, 0) km/s,目標(biāo)位置為(3000, 1000) km，目標(biāo)速度為(0, -1) km/s，飛行環(huán)境中探測雷達(dá)-2 向y軸正向按照0.2 km/s 的速度運(yùn)動。仿真結(jié)果如圖8 所示。

圖8 展示了基于遺傳算法與Dubins 曲線規(guī)劃方法在動態(tài)環(huán)境中的避障過程。在t=0 s 時(shí)，首先規(guī)劃出一條從起始點(diǎn)到終點(diǎn)的路徑，與圖8 所示結(jié)果一致。隨著無人系統(tǒng)以及移動探測雷達(dá)-2 的持續(xù)運(yùn)動，無人系統(tǒng)持續(xù)更新路徑，在t=700 s 時(shí)規(guī)劃的路徑如圖8(b)所示，可見由于探測雷達(dá)-2 的移動，無人系統(tǒng)在之前的路徑上重新規(guī)劃了新的路徑。圖8(c)所示為在t=1010 s 時(shí)規(guī)劃的路徑，此時(shí)無人系統(tǒng)仍然具有被探測雷達(dá)-2 發(fā)現(xiàn)的風(fēng)險(xiǎn)，因此規(guī)劃的路徑與其威脅圓相切。隨著無人系統(tǒng)的運(yùn)動以及探 測雷達(dá)-2 的運(yùn)動，無人系統(tǒng)躲避開探測雷達(dá)-2 的探測威脅，在t=1560 s 時(shí)規(guī)劃的路徑如圖8(d)所示。根據(jù)以上仿真實(shí)例結(jié)果，說明基于遺傳算法與Dubins 曲線的規(guī)劃方法可應(yīng)用于動態(tài)環(huán)境中。

圖8 動態(tài)環(huán)境仿真結(jié)果Fig.8 Dynamic environment simulation results

在實(shí)際應(yīng)用中，一個(gè)關(guān)鍵問題是算法的實(shí)時(shí)性問題。而本文所提方法的復(fù)雜度與環(huán)境中的障礙物個(gè)數(shù)直接相關(guān)，其直接影響表示路徑所需的二進(jìn)制位數(shù)，障礙物越多，路徑編碼越長，運(yùn)算時(shí)間也越長。為此，以下測試障礙物個(gè)數(shù)對算法實(shí)時(shí)性的影響。使用的測試平臺為筆記本電腦，其CPU 具有4 個(gè)核心，基頻為2.1 GHz。種群大小設(shè)置為500，最大進(jìn)化代數(shù)為50。仿真結(jié)果如圖9 所示。從結(jié)果中可以看到，當(dāng)障礙物個(gè)數(shù)小于20 時(shí)，程序運(yùn)行時(shí)間小于1 s，當(dāng)障礙物個(gè)數(shù)等于30 時(shí)，程序運(yùn)行時(shí)間為1.8992 s?？紤]到高速無人系統(tǒng)的運(yùn)動速度為km/s 級。因此，若能提前在數(shù)十公里外發(fā)現(xiàn)威脅障礙，則無人系統(tǒng)具有充足的時(shí)間進(jìn)行規(guī)劃，滿足規(guī)劃實(shí)時(shí)性需求。

圖9 算法運(yùn)行時(shí)間測試結(jié)果Fig.9 Algorithm running time test results

5 結(jié) 論

本文結(jié)合遺傳算法與Dubins 理論，提出了求解高速無人系統(tǒng)在多障礙環(huán)境下的路徑規(guī)劃算法。所提算法使用遺傳算法搜索最短路徑，Dubins 曲線滿足無人系統(tǒng)的約束條件。在算法設(shè)計(jì)中，對路徑的編碼方式做了深入的研究，使得其適合采用遺傳算法求解。由仿真結(jié)果可見，所提算法可在多障礙環(huán)境中求得最短且平滑可飛的路徑。 本文在求解最優(yōu)路徑時(shí)，假定無人系統(tǒng)在二維平面內(nèi)運(yùn)動，沒有考慮在三維空間運(yùn)動的情景，后續(xù)將進(jìn)一步研究求解三維空間中滿足無人系統(tǒng)約束的最優(yōu)路徑的方法。