楊雅寧+藺勇

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

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

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

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

1 問題描述

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

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

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

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

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

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

設(shè)定航點集合為

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

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

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

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

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

2.1 蟻群算法基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真與分析

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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