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

楊雅寧+藺勇

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

關鍵詞：無人機；航跡規劃；蟻群算法

中圖分類號：TP301 文獻標識碼：A 文章編號：1009-3044（2016）28-0189-03

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

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

1 問題描述

1.1 民用無人機航跡規劃需求

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

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

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

1.2無人機航跡規劃模型

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

設定航點集合為

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

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

因此，無人機的航跡規劃問題就是剔除威脅航段后，從起飛航點出發，尋求一條經歷所有任務航點的最優路徑問題，這與TSP問題的描述是一致的。

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

2 基于蟻群算法的航跡規劃方法

2.1 蟻群算法基本原理

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

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

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

其中，表示信息素揮發系數，其值介于0和1之間。是城市與之間的信息素，由式（5）表示。

是螞蟻信息素增加強度系數。

2.2 基于蟻群算法的航跡規劃方法

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

1）初始化信息素系數、絕對距離系數、信息素增加強度系數和信息素揮發系數，螞蟻個數、航點個數，威脅區域；

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

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

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

5）計算本次歷經總航程，比較航跡路徑；

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

7）輸出最優航跡路徑。

3 仿真與分析

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

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

4 結束語

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

參考文獻：

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

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

[3] 房建卿，王和平.云模型蟻群算法在無人機航跡規劃中的應用[J].科學技術與工程，2012（2）.

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

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

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

[7] 高穎，陳旭，周士軍，等. 基于改進蟻群算法的多批次協同三維航跡規劃. 西北工業大學學報[J]， 2016（1）.

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