基于優(yōu)化蟻群算法的無人機(jī)海島監(jiān)測航跡規(guī)劃

文/陳樂珠 李鋼

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

1 Dijkstra算法和蟻群算法

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

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

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

2 優(yōu)化蟻群算法的實現(xiàn)

算法流程圖如圖1所示。

利用Dijkstra 算法在MAKLINK 圖上產(chǎn)生依次通過路徑節(jié)點 的一條次最優(yōu)路徑。節(jié)點對應(yīng)的自由鏈接線依次為。設(shè) 和 為Li的兩個端點，鏈路上的其他點表示方法為：

圖1：算法流程圖

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

式中，信息素更新公式：

3 仿真與分析

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

表1：算法優(yōu)化前后運行時間統(tǒng)計

圖2：航跡規(guī)劃圖

圖3：航跡規(guī)劃迭代變化

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

4 結(jié)束語

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