基于蟻群算法的一種無人機(jī)二維航跡規(guī)劃方法研究

楊雅寧+藺勇

摘要：蟻群算法是一種啟發(fā)式搜索算法，具有全局搜索、強(qiáng)魯棒性、并行性等特點(diǎn)，近年來在無人機(jī)航跡規(guī)劃領(lǐng)域中的研究與應(yīng)用十分廣泛。本文針對(duì)中小型民用無人機(jī)的使用背景、模式和使用環(huán)境，引入對(duì)應(yīng)的航跡約束條件，基于蟻群算法提出了一種新的無人機(jī)二維航跡規(guī)劃方法，并進(jìn)行了仿真驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，該方法能夠有效的規(guī)劃出滿足飛行要求的最優(yōu)航跡路徑。

關(guān)鍵詞：無人機(jī)；航跡規(guī)劃；蟻群算法

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）28-0189-03

近幾年，隨著國(guó)內(nèi)無人機(jī)產(chǎn)業(yè)的迅猛發(fā)展，無人機(jī)在民用領(lǐng)域得到了廣泛應(yīng)用，主要用于執(zhí)行監(jiān)控安防、測(cè)繪勘察、農(nóng)情監(jiān)測(cè)、新聞采集、電影制作、災(zāi)害救援、電力巡線等任務(wù)，占據(jù)了無人機(jī)市場(chǎng)98%的銷售額。航跡規(guī)劃[1]技術(shù)是無人機(jī)飛行和任務(wù)控制系統(tǒng)的重要組成部分，也是實(shí)現(xiàn)無人機(jī)智能控制的關(guān)鍵技術(shù)之一，它是指在特定約束環(huán)境下，尋找滿足無人機(jī)機(jī)動(dòng)性能及作業(yè)環(huán)境信息限制的，從起飛點(diǎn)到任務(wù)點(diǎn)，再回著陸點(diǎn)的最優(yōu)飛行軌跡。因此，無人機(jī)航跡規(guī)劃問題可以轉(zhuǎn)化為帶有特定約束條件的TSP最優(yōu)路徑求解問題。蟻群算法是啟發(fā)式搜索算法的一種，自1992年由M. Dorigo等提出以來，基于其全局搜索、并行式分布計(jì)算、魯棒性強(qiáng)、易于其他算法結(jié)合等優(yōu)點(diǎn)，被廣泛應(yīng)用于求解TSP問題。經(jīng)過多年的研究與發(fā)展，呈現(xiàn)出了眾多的蟻群算法的改進(jìn)版本，為解決高難度復(fù)雜優(yōu)化問題提供了高效的手段，在無人機(jī)航跡規(guī)劃領(lǐng)域也得到了廣泛的研究與應(yīng)用[3]。

本文首先研究了中小型民用無人機(jī)的應(yīng)用背景、模式、環(huán)境和約束條件，分析了民用無人機(jī)的航跡規(guī)劃模型需求和現(xiàn)有基于蟻群算法的無人機(jī)航跡規(guī)劃問題的研究現(xiàn)狀，建立了一種新的航跡規(guī)劃模型，并基于此提出了一種無人機(jī)二維航跡規(guī)劃方法，最后進(jìn)行了仿真驗(yàn)證，并對(duì)仿真結(jié)果進(jìn)行了分析。

1 問題描述

1.1 民用無人機(jī)航跡規(guī)劃需求

民用無人機(jī)在使用時(shí)，為降低使用成本，首先，無人機(jī)執(zhí)行完任務(wù)后的要進(jìn)行回收，且一般起飛點(diǎn)與回收點(diǎn)為同一區(qū)域；其次，一個(gè)飛行架次一般包含多個(gè)任務(wù)，有多個(gè)任務(wù)航點(diǎn)。因此，除無人機(jī)轉(zhuǎn)場(chǎng)外，一般情況下，無人機(jī)的飛行航跡都是從起飛航點(diǎn)出發(fā)，到各個(gè)任務(wù)航點(diǎn)執(zhí)行任務(wù)，然后再返回著陸回收航點(diǎn)（即原起飛航點(diǎn)）的過程。同時(shí)，民用無人機(jī)在使用時(shí)還受任務(wù)區(qū)地理環(huán)境、氣象環(huán)境等威脅及無人機(jī)自身航時(shí)航程等限制。

一般情況下，民用無人機(jī)執(zhí)行任務(wù)前就已明確本次飛行的起飛航點(diǎn)、著陸回收航點(diǎn)、一個(gè)或多個(gè)任務(wù)航點(diǎn)以及航路上的威脅區(qū)域，航跡規(guī)劃問題轉(zhuǎn)化為從起飛航點(diǎn)出發(fā)，避開威脅區(qū)域，尋找一條歷經(jīng)所有任務(wù)航點(diǎn)的最優(yōu)路徑問題，如圖1所示，圖中橢圓區(qū)域?yàn)榈乩砘驓庀蟮韧{區(qū)域，無人機(jī)起飛航點(diǎn)和著陸（回收）航點(diǎn)為同一航點(diǎn)，共包含7個(gè)任務(wù)航點(diǎn)。因此，航跡規(guī)劃問題可以轉(zhuǎn)化為在一定的約束條件下求解TSP最優(yōu)路徑問題。

文獻(xiàn)[4]、文獻(xiàn)[5]、文獻(xiàn)[6]和文獻(xiàn)[7]都基于蟻群算法提出了不同的航跡規(guī)劃模型，并能有效規(guī)劃出從起飛點(diǎn)到目標(biāo)任務(wù)航點(diǎn)的折線最優(yōu)航跡，如圖2所示，。歸納起來，文獻(xiàn)中所提出的航跡規(guī)劃模型都未考慮無人機(jī)的回收問題和多任務(wù)航點(diǎn)問題，這并不符合無人機(jī)的使用模式，如圖2所示。

1.2無人機(jī)航跡規(guī)劃模型

在一般情況下，無人機(jī)執(zhí)行任務(wù)都是在固定高度定速飛行，只有在起飛和著陸階段才有高度和速度的變化，同時(shí)為了便于分析，可以忽略高度影響，本文在二維環(huán)境下研究無人機(jī)航跡規(guī)劃問題。

設(shè)定航點(diǎn)集合為

其中，為航點(diǎn)個(gè)數(shù)，為起飛和著陸回收航點(diǎn)，其它航點(diǎn)為任務(wù)航點(diǎn)。設(shè)無人機(jī)某一飛行架次的總航程為：

其中，為每段航跡的航程。航跡段受該段航路上約束條件控制，例如氣象威脅、地理等。設(shè)約束集合為，其中，為威脅區(qū)域的個(gè)數(shù)，可以等效為圓心為、半徑為的圓形區(qū)域。對(duì)于任意兩個(gè)航點(diǎn)和，形成的航段為，

因此，無人機(jī)的航跡規(guī)劃問題就是剔除威脅航段后，從起飛航點(diǎn)出發(fā)，尋求一條經(jīng)歷所有任務(wù)航點(diǎn)的最優(yōu)路徑問題，這與TSP問題的描述是一致的。

理論上，以下三種情況下當(dāng)所有航點(diǎn)之間的航段均屬于威脅航段時(shí)，或者某個(gè)航點(diǎn)僅與其他航點(diǎn)中的一個(gè)航點(diǎn)存在安全路徑時(shí)，在這種情況下，可能無法得到一條最優(yōu)化航跡，這不屬于本文討論的范圍。

2 基于蟻群算法的航跡規(guī)劃方法

2.1 蟻群算法基本原理

蟻群算法的定義及其基本原理由Dorigo給出了完整的描述。在解決TSP組合優(yōu)化問題領(lǐng)域有廣泛的應(yīng)用及研究。在基本蟻群算法中，螞蟻根據(jù)各個(gè)城市節(jié)點(diǎn)連接路徑上的信息素濃度決定其下一個(gè)訪問的城市，是選擇路徑時(shí)的轉(zhuǎn)移概率，其計(jì)算公式為：

是城市與之間的信息素濃度，是城市與之間的可見距離，是城市與之間的距離，是信息素系數(shù)，是絕對(duì)距離系數(shù)。

信息素更新公式可以用式（3）表示：

其中，表示信息素?fù)]發(fā)系數(shù)，其值介于0和1之間。是城市與之間的信息素，由式（5）表示。

是螞蟻信息素增加強(qiáng)度系數(shù)。

2.2 基于蟻群算法的航跡規(guī)劃方法

在無人機(jī)航跡規(guī)劃問題中，起飛航點(diǎn)是已知的，因此，在蟻群算法中螞蟻的出發(fā)城市不是隨機(jī)的，而是指定為起飛航點(diǎn)；同時(shí)由于存在威脅區(qū)域，導(dǎo)致某些航段屬于禁忌航段，應(yīng)該剔除。因此，基于蟻群算法的航路規(guī)劃步驟如下：

1）初始化信息素系數(shù)、絕對(duì)距離系數(shù)、信息素增加強(qiáng)度系數(shù)和信息素?fù)]發(fā)系數(shù)，螞蟻個(gè)數(shù)、航點(diǎn)個(gè)數(shù)，威脅區(qū)域；

2）判斷任意兩個(gè)航點(diǎn)構(gòu)建的航段是否屬于禁忌航段，若屬于禁忌航段，則被賦予為及大的值，同時(shí)，標(biāo)識(shí)該航段被剔除；否則是航點(diǎn)與航點(diǎn)之間的歐拉距離，標(biāo)識(shí)該航段為安全航段；

3）將螞蟻放置于起飛航點(diǎn)，并將起飛航點(diǎn)添加到螞蟻禁忌表中；

4）按照螞蟻轉(zhuǎn)移概率，選擇下一個(gè)轉(zhuǎn)移航點(diǎn)，直至遍歷完所有航點(diǎn)；

5）計(jì)算本次歷經(jīng)總航程，比較航跡路徑；

6）更新航段上的信息素；

7）輸出最優(yōu)航跡路徑。

3 仿真與分析

為了驗(yàn)證本文航跡規(guī)劃方法的有效性，分別用表1中的兩組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境硬件為Intel（R）Core（TM）i7-5820K @3.30GHz CPU，軟件環(huán)境為Win7操作系統(tǒng)、VS2010、MATLAB11.0。實(shí)驗(yàn)中首先在MATLAB11.0下繪制無人機(jī)飛行區(qū)域，包括任務(wù)航點(diǎn)及威脅區(qū)域；其次，在VS2010開發(fā)環(huán)境下建立無人機(jī)航跡規(guī)劃模型，計(jì)算出最優(yōu)的安全航跡路徑；最后，為了更明了地表述規(guī)劃出的跡路徑，手動(dòng)將路徑依次添加到無人機(jī)飛行區(qū)域，形成航跡路徑圖。仿真結(jié)果如圖3和圖4所示，結(jié)果表明，航跡規(guī)劃如表1所示條件下，本文的方法能夠規(guī)劃出滿足飛行要求的最優(yōu)航跡路徑。

理論上，當(dāng)所有航點(diǎn)之間的航段均屬于威脅航段時(shí)，或者某個(gè)航點(diǎn)僅與其他航點(diǎn)中的一個(gè)航點(diǎn)存在安全路徑時(shí)，在這種情況下，可能無法得到一條最優(yōu)化航跡，這不屬于本文討論的范圍。

4 結(jié)束語

本文首先研究了中小型民用無人機(jī)的應(yīng)用背景、模式、環(huán)境和約束條件，分析了民用無人機(jī)的航跡規(guī)劃模型需求和現(xiàn)有基于蟻群算法的無人機(jī)航跡規(guī)劃問題的研究現(xiàn)狀，建立了一種新的航跡規(guī)劃模型，并基于此提出了一種無人機(jī)二維航跡規(guī)劃方法，最后進(jìn)行了仿真驗(yàn)證。仿真結(jié)果表明，在給出的任務(wù)航點(diǎn)和威脅區(qū)域滿足一定要求的情況下，本文提出的方法可以有效規(guī)劃出滿足飛行要求的最優(yōu)航跡。

參考文獻(xiàn)：

[1] 繆永飛，鐘珞，陳艷恩，等.改進(jìn)免疫算法在無人機(jī)航線規(guī)劃中的應(yīng)用[J].武漢理工大學(xué)學(xué)報(bào)（信息與管理工程版）， 2015（2）.

[2] 牛治永，李錦軍，岳冬梅，等.無人機(jī)三維航跡規(guī)劃算法研究[J].自動(dòng)化技術(shù)與應(yīng)用， 2013， 32（11）.

[3] 房建卿，王和平.云模型蟻群算法在無人機(jī)航跡規(guī)劃中的應(yīng)用[J].科學(xué)技術(shù)與工程，2012（2）.

[4] 唐必偉，方群，朱占霞，等.基于改進(jìn)蟻群算法的無人飛行器二維航跡規(guī)劃[J].西北工業(yè)大學(xué)學(xué)報(bào)， 2013，31（5）.

[5] 唐必偉，朱占霞，方群，等.基于改進(jìn)蟻群算法的無人駕駛飛行器三維航跡規(guī)劃與重規(guī)劃[J].西北工業(yè)大學(xué)學(xué)報(bào)， 2013， 31（6）.

[6] 郭琦，潘廣員，楊江濤.基于Voronoi圖和動(dòng)態(tài)自適應(yīng)蟻群算法的UAV航跡規(guī)劃[J]. 計(jì)算機(jī)測(cè)量與控制， 2014， 22（9）.

[7] 高穎，陳旭，周士軍，等. 基于改進(jìn)蟻群算法的多批次協(xié)同三維航跡規(guī)劃. 西北工業(yè)大學(xué)學(xué)報(bào)[J]， 2016（1）.

[8] David B. KirK， Wen-mei W. Hwu. 大規(guī)模并行處理器編程實(shí)戰(zhàn)[M]. 北京： 清華大學(xué)出版社， 2013.