智能優(yōu)化算法在無人機(jī)航跡規(guī)劃應(yīng)用研究

雷 蕾

(海軍裝備研究院 北京 100073)

智能優(yōu)化算法在無人機(jī)航跡規(guī)劃應(yīng)用研究

雷 蕾

(海軍裝備研究院 北京 100073)

智能優(yōu)化算法具備計(jì)算效率高,適應(yīng)性強(qiáng)的特點(diǎn),通過對智能優(yōu)化算法在無人機(jī)航跡規(guī)劃的研究,分析無人機(jī)航跡規(guī)劃模型,提出無人機(jī)航跡規(guī)劃的約束條件,闡述了目前國內(nèi)外應(yīng)用和研究的幾種航跡規(guī)劃算法,并對無人機(jī)航跡規(guī)劃算法的發(fā)展趨勢進(jìn)行了展望。

無人機(jī); 航跡規(guī)劃; 智能優(yōu)化算法

Class Number TP391

1 引言

隨著計(jì)算機(jī)、通信技術(shù)、自動(dòng)化的發(fā)展,無人飛行器的種類更加豐富,具有協(xié)調(diào)性強(qiáng)、技術(shù)密集、系統(tǒng)復(fù)雜的特點(diǎn),因此對無人飛行器航跡規(guī)劃工作人員提出了愈來愈高的要求。同時(shí),隨著現(xiàn)代無人飛行器航跡規(guī)劃難度、危險(xiǎn)度以及要求的不斷增加,通過操作人員手工操作成功完成復(fù)雜的飛行任務(wù)越來越困難。面對這種情況,無人機(jī)航跡規(guī)劃技術(shù)成為一種有效的解決途徑。

由于無人機(jī)面臨的戰(zhàn)場環(huán)境將是異常復(fù)雜遼闊,規(guī)劃約束條件眾多,模糊性大,各因素之間存在強(qiáng)耦合及其自身獨(dú)特的控制和任務(wù)方式,航跡規(guī)劃在處理這些因素時(shí)面臨極大的挑戰(zhàn)。許多學(xué)者已對航跡規(guī)劃方法問題作了大量工作,就此作了不同程度的敘述。采用分層規(guī)劃方法進(jìn)行航跡規(guī)劃,根據(jù)規(guī)劃層次不同,可以將航跡規(guī)劃算法分成兩大類:任務(wù)級航跡規(guī)劃和戰(zhàn)術(shù)級航跡規(guī)劃。任務(wù)級航跡規(guī)劃可以采用較粗糙的數(shù)字地圖和簡化的性能模型,其目的是獲得參考航跡,從而減少戰(zhàn)術(shù)級航跡規(guī)劃的搜索空間,任務(wù)級航跡艦劃包括網(wǎng)絡(luò)法、符號規(guī)劃方法、試探法和知識推理法等方法。戰(zhàn)術(shù)級航跡規(guī)劃實(shí)質(zhì)是個(gè)軌跡優(yōu)化問題,可以運(yùn)用最優(yōu)控制理論求解戰(zhàn)術(shù)級突防航跡問題,采用動(dòng)態(tài)規(guī)劃算法或A*算法得到優(yōu)化航跡。另外,模擬退火算法和遺傳算法也在航跡規(guī)劃問題中得到廣泛應(yīng)用,而蟻群算法是這幾年發(fā)展起來的一種新方法。對于規(guī)劃無人機(jī)航跡的問題,需要協(xié)調(diào)許多約束條件,在理論上還沒有一種通用的航跡規(guī)劃算法。因此,在不同條件約束下,尋找航跡規(guī)劃時(shí)間更短,尋優(yōu)更好的航跡規(guī)劃算法具有重要的現(xiàn)實(shí)意義。

2 無人機(jī)航跡規(guī)劃問題分析

無人機(jī)在執(zhí)行任務(wù)時(shí),會受到如禁飛區(qū)、障礙物、險(xiǎn)惡地形等復(fù)雜地理環(huán)境的限制,因此在航跡規(guī)劃時(shí),應(yīng)盡量避開這些區(qū)域,可將這些區(qū)域在地圖上標(biāo)識為禁飛區(qū)域,以提升無人機(jī)工作效率。此外,飛行區(qū)域內(nèi)的氣象因素也將影響任務(wù)效率,應(yīng)充分考慮大風(fēng)、雨雪等復(fù)雜氣象下的氣象預(yù)測與應(yīng)對機(jī)制。因此,無人機(jī)航跡規(guī)劃技術(shù)需要考慮約束條件、飛行環(huán)境、突防安全等基本因素。

1) 飛行器的物理限制。在航跡規(guī)劃過程中必須考慮無人機(jī)自身性能限制,否則無人機(jī)可能不能按照規(guī)劃航跡飛行,無人機(jī)的自身性能對航跡規(guī)劃的約束主要有:最大偏轉(zhuǎn)角,它限制在生成擴(kuò)展航跡時(shí)無人機(jī)水平面的偏轉(zhuǎn)角度,生成的新航跡段偏轉(zhuǎn)角只能小于或等于無人機(jī)限定的最大角度;最大俯仰角,它限制在生成擴(kuò)展航跡時(shí)無人機(jī)在垂直平面上仰或俯沖的最大角度;最小航跡段長度,它用于限制無人機(jī)在改變飛行姿態(tài)之前飛出的最短距離;最低飛行高度,雖然飛行高度越低,被敵方發(fā)現(xiàn)的概率越低,但飛行越低無人機(jī)觸底的概率也會增加,所以需要對最低高度進(jìn)行限制。

2) 航跡距離約束。它限制規(guī)劃的無人機(jī)航跡的長度必須不大于一個(gè)預(yù)先設(shè)置的最大飛行距離。最大飛行距離對應(yīng)無人機(jī)所載燃料。

3) 實(shí)時(shí)性要求。實(shí)時(shí)性要求主要針對在線航跡規(guī)劃,由于飛行現(xiàn)場環(huán)境復(fù)雜多變,不可能規(guī)劃出滿足突發(fā)狀況的航跡,這樣就要求無人機(jī)具有實(shí)時(shí)規(guī)劃能力。實(shí)際的地形和敵情信息與事先獲得的信息總會有出入,一般認(rèn)為這種差異的影響不大,可以通過保留一定的安全裕度來解決。對于無人機(jī),航跡規(guī)劃往往由地面規(guī)劃員在起飛前做好,存儲在機(jī)載計(jì)算機(jī)內(nèi)。無人機(jī)起飛之后,就按預(yù)定的航跡飛行。從長遠(yuǎn)來看,無人機(jī)需要具有自主控制的能力,有部分的人工智能,因而往往還需要根據(jù)戰(zhàn)場實(shí)際情況進(jìn)行實(shí)時(shí)航跡規(guī)劃,這是由未來無人機(jī)所執(zhí)行的任務(wù)復(fù)雜性決定的。在這種情況下,無人機(jī)需要利用機(jī)載傳感器及我方的偵察通信系統(tǒng)實(shí)時(shí)探測敵方防御區(qū)域的各種信息,通過實(shí)時(shí)航跡規(guī)劃來消除規(guī)劃軌跡的偏差。由于機(jī)載傳感器的探測距離有限,實(shí)時(shí)航跡規(guī)劃往往只能局部修正規(guī)劃航跡。

航跡規(guī)劃的另一難點(diǎn)是進(jìn)行自適應(yīng)航跡規(guī)劃。自適應(yīng)航跡規(guī)劃是提高飛行器生存能力的重要方法。自適應(yīng)航跡規(guī)劃包括無人機(jī)在飛向目標(biāo)途中接受和分析近實(shí)時(shí)的威脅數(shù)據(jù),以致能改變預(yù)先規(guī)劃的航跡,達(dá)到減少受機(jī)動(dòng)威脅攻擊的目的。自適應(yīng)航跡規(guī)劃甚至可以改變飛行器的任務(wù)內(nèi)容,使得作戰(zhàn)任務(wù)更具靈活性。飛行器自適應(yīng)航跡修改需要得到實(shí)時(shí)信息,這種實(shí)時(shí)信息應(yīng)該具有某種標(biāo)準(zhǔn)格式和協(xié)議。航跡規(guī)劃算法中也應(yīng)具備一定的標(biāo)準(zhǔn)模式,以便快速響應(yīng)所輸入的信息。整個(gè)自適應(yīng)航跡規(guī)劃程序應(yīng)有一定的智能,目前這方面的研究還處于起步階段。

3 無人機(jī)航跡規(guī)劃方法研究

由于無人機(jī)所處的戰(zhàn)場環(huán)境異常復(fù)雜遼闊,規(guī)劃約束條件眾多,各因素之間又存在強(qiáng)耦合,再加上無人機(jī)自身獨(dú)特的控制方式,航跡規(guī)劃在處理這些因素時(shí)面臨極大挑戰(zhàn)。航跡規(guī)劃問題是一個(gè)NP問題,具有約束條件多、復(fù)雜性強(qiáng)、時(shí)效性要求高、規(guī)劃范圍大、直接求解比較困難的特點(diǎn),近年來國內(nèi)外學(xué)者已提出了許多不同的規(guī)劃方法。

其中,采用智能優(yōu)化算法求解無人機(jī)航跡規(guī)劃問題一般分為兩類,一類是確定型搜索算法,如:基于極小值原理的確定性計(jì)算方法和基于動(dòng)態(tài)規(guī)劃或A*算法的確定性狀態(tài)空間搜索方法;一類是不確定型搜索算法,如以隨機(jī)搜索為特征的模擬退火算法、遺傳算法和蟻群算法等優(yōu)化算法,由于這些算法模擬了自然界的物質(zhì)變化以及生物活動(dòng)和進(jìn)化的過程,具有一定的優(yōu)點(diǎn)和特點(diǎn),因而在航跡規(guī)劃應(yīng)用中得到了越來越多的重視。特別是遺傳算法由于不受搜索空間限制性假設(shè)約束,不要求優(yōu)化函數(shù)具備連續(xù)、可導(dǎo)等假設(shè),并隱含并行性,對于航跡規(guī)劃這種含有大量模糊信息、可以適應(yīng)威脅環(huán)境的變化,多約束的優(yōu)化問題來說,具有特別重要的意義。

3.1 A*算法

基于A*算法的航跡規(guī)劃是目前國內(nèi)外應(yīng)用較多的規(guī)劃算法,屬于一種經(jīng)典啟發(fā)式搜索算法,被許多學(xué)者應(yīng)用于無人機(jī)二維航跡規(guī)劃中。

A*算法基本思想:通過設(shè)定啟發(fā)函數(shù)來評估搜索到的擴(kuò)展航跡點(diǎn)代價(jià)值,通過比較選擇代價(jià)值最優(yōu)的航跡點(diǎn),直到到達(dá)目標(biāo)航跡點(diǎn)后完成航跡規(guī)劃?；贏*算法的無人機(jī)航跡規(guī)劃從起始航跡點(diǎn)出發(fā),通過不斷尋找最小代價(jià)值的下一個(gè)擴(kuò)展航跡點(diǎn),從而產(chǎn)生一組航跡點(diǎn)集,完成整個(gè)航跡規(guī)劃過程。A*算法的核心實(shí)際就是下一航跡點(diǎn)擴(kuò)展的過程,通過這一特點(diǎn),可以找到代價(jià)值最優(yōu)的飛行航跡。在確定最優(yōu)飛行航跡后,需要計(jì)算該航跡是否滿足航跡規(guī)劃時(shí)對燃油、航程、速度或時(shí)間等條件的約束。如果不能滿足航跡規(guī)劃約束條件,規(guī)劃航跡失敗,必須重新規(guī)劃并對參數(shù)適當(dāng)?shù)男薷摹?/p>

基于A*算法航跡規(guī)劃過程中建立open表和close表,其中open表用于記錄可行當(dāng)時(shí)沒有被采用的次優(yōu)航跡點(diǎn),close表用于存放已擴(kuò)展的代價(jià)值最小的航跡點(diǎn)。在航跡點(diǎn)擴(kuò)展過程中,也從open表中找出代價(jià)值最小的航跡點(diǎn),進(jìn)行擴(kuò)展并進(jìn)行分析,根據(jù)分析結(jié)果修改open表和close表,選擇最合適的航跡點(diǎn)。

基于A*搜索算法的航跡規(guī)劃計(jì)算簡單、易實(shí)現(xiàn),理論上可以實(shí)現(xiàn)全局最優(yōu)解收斂,同時(shí)也大大提高了搜索效率。但隨著搜索空間的擴(kuò)展,A*搜索算法的航跡規(guī)劃計(jì)算量也呈指數(shù)形式增長,收斂時(shí)間變長,尤其在三維航跡規(guī)劃中常常出現(xiàn)組合爆炸問題,同時(shí)航跡規(guī)劃效果對啟發(fā)函數(shù)有太強(qiáng)依賴性,得出的最優(yōu)航跡只是在該啟發(fā)函數(shù)下的最優(yōu),較好的啟發(fā)函數(shù)是通過試湊方法得出的,在遇到未知障礙物陷阱時(shí)可能會導(dǎo)致搜索失敗?；谝陨螦*搜索算法航跡規(guī)劃特點(diǎn)一般用于二維空間的全局航跡規(guī)劃。

3.2 Voronoi圖法

Voronoi圖作為計(jì)算幾何中非常重要的幾何圖形之一,被廣泛應(yīng)用許多領(lǐng)域中,具有簡單直觀的優(yōu)點(diǎn)。尤其在解決要求無人機(jī)離障礙物、威脅源的距離越遠(yuǎn)越好的問題,Voronoi圖方法具有很大的優(yōu)勢。

Voronoi圖法基本思想:首先根據(jù)無人機(jī)飛行環(huán)境威脅源和障礙物的分布情況,以威脅源和障礙物的中心點(diǎn)為基礎(chǔ)構(gòu)建出Voronoi圖的威脅模型;其次基于Voronoi圖計(jì)算出加權(quán)無向圖,并采用最短路徑搜索算法如Dijkstra算法搜索初始最短路徑。Voronoi圖法主要缺點(diǎn)在于存在不可行的尖角,主要是通過三次樣條插值法或B樣條法優(yōu)化路徑,把路徑中尖角剔除生成可行的最優(yōu)軌跡。

最優(yōu)軌跡的精度取決于構(gòu)建Voronoi圖的精度,當(dāng)威脅源或障礙物位置發(fā)生變化時(shí),需要再次構(gòu)建Voronoi圖并重新計(jì)算。Voronoi圖法可用于二維航跡規(guī)劃任務(wù)。

3.3 遺傳算法

遺傳算法(Genetic Algorithm，GA)是在20世紀(jì)70年代初期被Holland等提出的,它是將生物自然選擇與基因遺傳學(xué)機(jī)理與計(jì)算機(jī)結(jié)合起來的一種隨機(jī)搜索算法。

遺傳算法基本原理:按照某種編碼方式對個(gè)體編碼,采用選擇、交叉和變異三種遺傳因子模擬自然界中生物族群遺傳變異的現(xiàn)象,以適應(yīng)度值作為迭代過程中選取父代繁殖、交叉、變異的評價(jià)依據(jù),不斷向好的方向發(fā)展,最終產(chǎn)生最優(yōu)個(gè)體解決問題。

遺傳算法具有不易陷入局部最優(yōu)解,魯棒性好,不受搜索空間限制,不受假設(shè)約束,不要求優(yōu)化函數(shù)具備特殊特性以及隱含并行性等特點(diǎn)。

3.4 粒子群算法

粒子群算法(Particle Swarm Optimization，PSO)是由美國心理學(xué)家Eberhart博士、電子信息工程師Kennedy博士提出的一種模仿鳥群捕食行為的算法,是一個(gè)群體智能模型。

粒子群算法基本原理:首先,隨機(jī)初始化粒子,之后在粒子迭代時(shí),通過跟蹤兩個(gè)最優(yōu)值不斷的進(jìn)化自身找到最優(yōu)解,兩個(gè)最優(yōu)值一個(gè)是粒子本身找到的最優(yōu)解,另一種是全局粒子的最優(yōu)解。該算法類似遺傳算法,也是一種采用迭代的方法不斷優(yōu)化的算法。

粒子群算法的優(yōu)點(diǎn)在于簡單容易實(shí)現(xiàn)、通用性較強(qiáng)、搜索能力全面,缺點(diǎn)在于容易陷入局部最優(yōu)解、對參數(shù)的要求比較高。

3.5 蟻群算法

蟻群算法(Ant Colony Algorithm，ACA)是1991年由意大利學(xué)者M(jìn). Dorigo等提出的一種新興的啟發(fā)式搜索算法。該算法也是一種模擬算法,源于對自然界螞蟻覓食時(shí)最短路徑行為的研究。

蟻群算法基本原理:首先網(wǎng)格圖中信息素矩陣初始化,螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則,形成一條從起始點(diǎn)到目標(biāo)點(diǎn)的可行航跡,計(jì)算各螞蟻航跡的目標(biāo)函數(shù)得出最優(yōu)航跡,然后根據(jù)目標(biāo)函數(shù)和一定的信息素調(diào)整規(guī)則對網(wǎng)格圖中各點(diǎn)的信息素進(jìn)行調(diào)整,經(jīng)過數(shù)次迭代產(chǎn)生全局最優(yōu)航跡。

蟻群算法是一種很好的通用型算法,具有很好的魯棒性和全局并行計(jì)算能力,缺點(diǎn)在于搜索時(shí)間長,收斂后期易陷入局部最優(yōu)。

4 方法分析

本文綜合考慮國內(nèi)外學(xué)者研究航跡規(guī)劃算法經(jīng)驗(yàn)的基礎(chǔ)上,針對兩種類型算法特點(diǎn),對不同算法的分析如下:

1) 不確定型搜索算法是有方向性的自適應(yīng)搜索,在適應(yīng)度函數(shù)的驅(qū)使下,通過各種引導(dǎo)信息,如遺傳算法的交叉、變異,粒子群算法的速度和位置更新等手段,每次信息引導(dǎo)過程中的操作產(chǎn)生新個(gè)體,從而不斷擴(kuò)大搜索范圍,不斷向目標(biāo)方向逐步優(yōu)化,最終達(dá)到近似最優(yōu)解。因此,算法搜索范圍廣,易找到全局最優(yōu)解。不確定型搜索算法具有不受搜索空間限制,不受假設(shè)約束,不要求優(yōu)化函數(shù)具備特殊特性以及隱含并行性等特點(diǎn),因此,遺傳算法通用性和魯棒性強(qiáng)。

2) 相比確定型搜索算法,不確定型搜索算法在具有這些優(yōu)秀能力的同時(shí)也存在一些問題,如影響尋優(yōu)效率的初始種群質(zhì)量問題等。

因此,對無人機(jī)航跡規(guī)劃問題可采用兩種算法結(jié)合的方式進(jìn)行改進(jìn),例如通過A*結(jié)合遺傳算法,在遺傳算法的基礎(chǔ)上,采用稀疏A*算法搜索新航跡點(diǎn)的方法,產(chǎn)生初始種群進(jìn)而提高航跡規(guī)劃尋優(yōu)性能。稀疏A*算法由于計(jì)算比較簡單、易實(shí)現(xiàn),通過結(jié)合約束條件隨機(jī)選取航跡點(diǎn)的方式縮小了搜索空間,提高了搜索效率,減少搜索時(shí)間。同時(shí),由于稀疏A*算法僅需要為遺傳算法提供初始種群,不需要得到最優(yōu)航跡,所以大大降低了稀疏A*算法對啟發(fā)函數(shù)的依賴性,提高了算法的性能。

5 結(jié)語

無人機(jī)航跡規(guī)劃有多種算法,既有適于小范圍的規(guī)劃算法,可在無人機(jī)上進(jìn)行動(dòng)態(tài)修改;又有適于大范圍的規(guī)劃算法,可在已知信息下求得全局最優(yōu)解;既能進(jìn)行人為的智能規(guī)劃,又能在一定范圍內(nèi)進(jìn)行模型的自動(dòng)求解。應(yīng)在具體問題具體分析基礎(chǔ)上,發(fā)展高效的無人機(jī)航跡規(guī)劃方法。

隨著無人機(jī)所要執(zhí)行的任務(wù)越來越復(fù)雜,加上環(huán)境的不確定性,對航跡規(guī)劃的要求也將越來越高。未知威脅信息環(huán)境下的實(shí)時(shí)航跡規(guī)劃將是未來研究的重點(diǎn),高效的全局搜索方法和局部搜索方法混合使用將是無人機(jī)航跡規(guī)劃的一種趨勢。

[1] Zhonghua Hu, Min Zhao, Min Yao. Cooperative attack path planning for unmanned air vehicles Swarm based On grid model and bi-level programming[J]. Journal of Information & Compumdonal Science,2011,8(4):671-679.

[2] J. F. Gilmore. Autonomous vehicle planning analysis methodology[C]//The Proceeding of American Control Conference, Kluwer. Boston, MA,1991.

[3] C. Zheng, M. ding, C Zhou. Real-time route planning for unmanned air vehicle with an evolutionary algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence,2003,17(1):63-81.

[4] S. A. Bortoff. Path planning for UAVs[C]//the Proceedings of the American Control Conference, Chicago, USA,2000:364-368.

[5] 雷興明,邢昌風(fēng),吳玲,等.基于分布式約束優(yōu)化的多平臺導(dǎo)彈協(xié)同航路規(guī)劃[J].電子學(xué)報(bào),2012,40(10):2068-2072.

[6] 張同法,于雷,魯藝.多架無人機(jī)協(xié)同作戰(zhàn)的路徑規(guī)劃[J].火力與指揮控制,2009,34(2):143-145.

[7] 馬培蓓,紀(jì)軍.3種多導(dǎo)彈航跡規(guī)劃算法的比較[J].電光與控制,2010,17(10):28-32.

[8] 張同法,于雷,魯藝.多架無人機(jī)協(xié)同作戰(zhàn)的路徑規(guī)劃[J].火力與指揮控制,2009,34(2):143-145.

[9] W Zhang, Z Xing, G Wang, et al. Distributed stochastic search and distributed breakout: properties, comparison and applications to constrains optimization problems in sensor networks[J]. Artificial Intelligence,2005,161(1-2):55-87.

[10] 胡中華,趙敏.無人機(jī)任務(wù)規(guī)劃系統(tǒng)研究及發(fā)展[J].航天電子對抗,2009,25(4):49-52.

Application of Intelligent Optimization Algorithm in UAV Path Planning

LEI Lei

(Navy Equipment Research Institute, Beijing 100073)

Intelligent optimization algorithm has the characteristics of high computational efficiency and abaptability. By analyzing the intelligent optimization algorithm in the UAV route planning, the UAV route planning model is researched. And the restrictions of UAV trajectory planning are proposed. This paper describes several trajectory planning algorithms applied and researched at home and abroad. And the development trend of UAV flight path planning algorithms is prospected.

UAV, route planning, intelligent optimization algorithm

2016年8月13日,

2016年9月29日

雷蕾,女,碩士研究生,工程師，研究方向:軟件工程。

TP391

10.3969/j.issn.1672-9730.2017.02.009