文/陳樂(lè)珠 李鋼

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

1 Dijkstra算法和蟻群算法

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

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

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

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

算法流程圖如圖1所示。

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

圖1：算法流程圖

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

式中，信息素更新公式：

3 仿真與分析

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

表1：算法優(yōu)化前后運(yùn)行時(shí)間統(tǒng)計(jì)

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

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

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

4 結(jié)束語(yǔ)

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