基于優化蟻群算法的無人機海島監測航跡規劃

文/陳樂珠 李鋼

無人機作為一種新的遙感監測平臺起著非常重要的作用。在粵東地域的四個城市中特別是汕尾市，五個縣區中有四個縣區瀕臨南海，利用無人機進行近海海島監測，可大大減少人力物力的浪費。然而，無人機在進行海島監測時會遇到氣流不穩定等因素而影響無人行飛行，因此對無人機進行航跡規劃非常有意義。目前，國內外的航跡規劃控制算法主要分為兩大類，傳統經典與人工智能算法。傳統經典包括動態規劃法，導數相關法，最優控制法，動態規劃算法在解決多級決策最優化問題中比較常見的算法之一，該算法受狀態空間限制，對于無人機的航跡規劃大范圍的搜索，比較有局限性；導數相關法中，常見的有牛頓法和最小二乘法等，要求導函數有連續性，迭代運算量大，容易陷入局部最優解。最優控制比較廣泛應用于火箭、衛星軌道等。智能算法中包括遺傳算法，例如文獻，對于遺傳算法，在進行規劃路徑時比較費時，另外一種常見的蟻群算法，例如文獻，該方法收斂速度較慢。以上國內外所提到的各種路徑算法都有各自的局限性，適應于完成特定的路徑規劃等任務。然而，對于本課題的研究來說，因為本課題有一種的空間及環境因素，所以，本文結合以上的研究基本上，通過MAKLINK 圖論建立二維路徑規劃空間模型 ，利用Dijkstra 算法規劃無人機初始航跡，融合蟻群算法優化路徑，根據螞蟻搜索到更短、更準的航跡規劃。

1 Dijkstra算法和蟻群算法

在二十世紀50年代，荷蘭計算機科學家狄克斯特拉提出了一種典型的單源最短路徑算法，命名為Dijkstra 算法，用于計算非負權值圖中一個節點到其他所有節點的最短路徑。

蟻群算法是由Dorigo.M 等人提出來的，啟發于螞蟻在尋找食物的過程中，螞蟻所經過的地方會釋放一種分泌物，該分泌物叫信息素，只要在一定范圍內，其它螞蟻就能通過該信息素獲取路徑信息，后繼螞蟻也會選擇信息素濃度較高的路徑，同時把自己的信息素留下，從而使該路徑信息素不斷增加，螞蟻們選擇的路徑概率大的就是蟻群算法尋找的最優路徑。

以上兩種算法都能找到最短路徑，蟻群算法通過信息素更新得到最優路徑，然而信息素更新速度較慢，嚴重地會影響無人機的航行任務，Dijkstra 算法規劃速度快，但是迭代次數多的情況下誤差率較高。通過研究設想，如果先由Dijkstra 算法規劃初始航跡，再與蟻群算法融合，這樣即提高無人機航跡規劃效率又提高航跡規劃最優率。

2 優化蟻群算法的實現

算法流程圖如圖1所示。

利用Dijkstra 算法在MAKLINK 圖上產生依次通過路徑節點 的一條次最優路徑。節點對應的自由鏈接線依次為。設 和 為Li的兩個端點，鏈路上的其他點表示方法為：

圖1：算法流程圖

其中，i 為鏈接線上所有點的集合；q 為[0,1]區間的隨機數；q0為[0,1]區間的可調參數；為啟發值；為信息素。j 的計算方法為：首先依次計算當前鏈接線節點i 到下條鏈接錢節點j 的選擇概率，然后根據選擇概率采用輪盤賭法找出下一個節點j，的計算公式為：

式中，信息素更新公式：

3 仿真與分析

為了驗證優化算法的有效性，使用Matlab 軟件編程實現優化蟻群算法的仿真，在200×200 的二維空間，設置四個二維障礙物仿真為海島群，海島1 頂點坐標分別為（40 140；60 160；80 140；60 120），海島2頂點坐標分別為（50 30；30 40；80 80；100 40），海島3 頂點坐標分別為（120 160；140 100；180 170；165 180），海島4 頂點坐標分別為（120 40；170 40；140 80），S（20，180）作為起點，T（160，90）作為終點。蟻群算法種群數量m=10，循環次數N=500，信息素初始值 =2。

表1：算法優化前后運行時間統計

圖2：航跡規劃圖

圖3：航跡規劃迭代變化

仿真結果如圖2所示；圖2中，黃色虛線為改進前算法得到的航跡，紅色實線為算法優化后的航跡，后者航跡總距離更短，大大提高無人機完成航行飛行任務。圖3為航跡規劃迭代變化曲線。為了驗證優化后的蟻群算在運算過程中消耗的時間更短，對系統運行十次，把測試的結果記錄下來，如表1所示。從表1可看出，優化后算法運行時間比未優化的算法運行時間平均快30%，前者效率較高。

4 結束語

本文通過融合蟻群算法仿真得到優化航跡規劃路徑，仿真結果表明，該融合得到的優化算法，比改進前的蟻群算法求解時間快、規劃路徑準確、迭代過程中系統穩定的特點，從而保證無人機在復雜的海島監測中飛行航跡規劃零失誤。通過該算法應用于海島監測，具有一定的應用價值。然而該算法模型局限于二維空間，為了使模型更真實，規劃路徑更準確，可在此基礎上對三維空間進行建模改進研究。