一、無人機簡介
0 引言
随着現代技術的發展，飛行器種類不斷變多，應用也日趨專一化、完善化，如專門用作植保的大疆PS-X625無人機，用作街景拍攝與監控巡察的寶雞行翼航空科技的X8無人機，以及用作水下救援的白鲨MIX水下無人機等，決定飛行器性能主要是内部的飛控系統和外部的路徑規劃問題。就路徑問題而言，在具體實施任務時僅靠操作員手中的遙控器控制無人飛行器執行相應的工作，可能會對操作員心理以及技術提出極高的要求，為了避免個人操作失誤，進而造成飛行器損壞的危險，一種解決問題的方法就是對飛行器進行航迹規劃。
飛行器的測量精度，航迹路徑的合理規劃，飛行器工作時的穩定性、安全性等這些變化對飛行器的綜合控制系統要求越來越高。無人機航路規劃是為了保證無人機完成特定的飛行任務，并且能夠在完成任務的過程中躲避各種障礙、威脅區域而設計出最優航迹路線的問題。
1 常見的航迹規劃算法
圖1 常見路徑規劃算法
文中主要對無人機巡航階段的航迹規劃進行研究，假設無人機在飛行中維持高度與速度不變，那麼航迹規劃成為一個二維平面的規劃問題。在航迹規劃算法中,A算法計算簡單，容易實作。在改進A算法基礎上，提出一種新的、易于了解的改進A算法的無人機航迹規劃方法。傳統A算法将規劃區域栅格化，節點擴充隻限于栅格線的交叉點，在栅格線的交叉點與交叉點之間往往存在一定角度的兩個運動方向。将存在角度的兩段路徑無限放大、細化，然後分别用兩段上的相應路徑規劃點作為切點，找到相對應的組成内切圓的圓心，然後作弧，并求出相對應的兩切點之間的弧所對應的圓心角，根據下式計算出弧線的長度
式中：R———内切圓的半徑；
α———切點之間弧線對應的圓心角。
二、蟻群算法簡介
1 蟻群算法(ant colony algorithm,ACA)起源和發展曆程
Marco Dorigo等人在研究新型算法的過程中，發現蟻群在尋找食物時，通過分泌一種稱為資訊素的生物激素交流覓食資訊進而能快速的找到目标，于是在1991年在其博士論文中首次系統地提出一種基于螞蟻種群的新型智能優化算法“螞蟻系統（Ant system,簡稱AS）”，後來，提出者及許多研究者對該算法作了各種改進，将其應用于更為廣泛的領域，如圖着色問題、二次配置設定問題、工件排序問題、車輛路徑問題、工廠中的房間作業排程問題、網絡路由問題、大規模內建電路設計等。近些年來，M.Dorigo等人把螞蟻算法進一步發展成一種通用的優化技術“蟻群優化（Ant Colony Optimization,簡稱ACO）”，并将所有符合ACO架構的算法稱為“蟻群優化算法（ACO algorithm）”。
具體來說，各個螞蟻在沒有事先告知食物在什麼地方的前提下開始尋找食物。當一隻找到食物以後，它會向環境釋放一種揮發性分泌物pheromone (稱為資訊素,該物質随着時間的推移會逐漸揮發消失，資訊素濃度的大小表征路徑的遠近)資訊素能夠讓其他螞蟻感覺進而起到一個引導的作用。通常多個路徑上均有資訊素時，螞蟻會優先選擇資訊素濃度高的路徑，進而使濃度高的路徑資訊素濃度更高，形成一個正回報。有些螞蟻并沒有像其它螞蟻一樣總重複同樣的路，他們會另辟蹊徑，如果另開辟的道路比原來的其他道路更短，那麼，漸漸地，更多的螞蟻被吸引到這條較短的路上來。最後，經過一段時間運作，可能會出現一條最短的路徑被大多數螞蟻重複着。最終，資訊素濃度最高的路徑即是最終被螞蟻選中的最優路徑。
與其他算法相比，蟻群算法是一種比較年輕的算法，具有分布式計算、無中心控制、個體之間異步間接通信等特點，并且易于與其他優化算法相結合，經過不少仁人志士的不斷探索，到今天已經發展出了各式各樣的改進蟻群算法，不過蟻群算法的原理仍是主幹。
2 蟻群算法的求解原理
基于上述對蟻群覓食行為的描述，該算法主要對覓食行為進行以下幾個方面模拟：
（1）模拟的圖場景中包含了兩種資訊素，一種表示家，一種表示食物的地點，并且這兩種資訊素都在以一定的速率進行揮發。
（2）每個螞蟻隻能感覺它周圍的小部分地方的資訊。螞蟻在尋找食物的時候，如果在感覺範圍内，就可以直接過去，如果不在感覺範圍内，就要朝着資訊素多的地方走，螞蟻可以有一個小機率不往資訊素多的地方走，而另辟蹊徑，這個小機率事件很重要，代表了一種找路的創新，對于找到更優的解很重要。
（3）螞蟻回窩的規則與找食物的規則相同。
（4）螞蟻在移動時候首先會根據資訊素的指引，如果沒有資訊素的指引，會按照自己的移動方向慣性走下去，但也有一定的機率改變方向，螞蟻還可以記住已經走過的路，避免重複走一個地方。
（5）螞蟻在找到食物時留下的資訊素最多，然後距離食物越遠的地方留下的資訊素越少。找到窩的資訊素留下的量的規則跟食物相同。蟻群算法有以下幾個特點:正回報算法、并發性算法、較強的魯棒性、機率型全局搜尋、不依賴嚴格的數學性質、搜尋時間長，易出現停止現象。
螞蟻轉移機率公式：
公式中：是螞蟻k從城市i轉移到j的機率；α，β分别為資訊素和啟發式因子的相對重要程度；為邊（i，j）上的資訊素量；為啟發式因子；為螞蟻k下步允許選擇的城市。上述公式即為螞蟻系統中的資訊素更新公式，是邊（i,j)上的資訊素量；ρ是資訊素蒸發系數，0<ρ<1;為第k隻螞蟻在本次疊代中留在邊（i,j）上的資訊素量；Q為一正常系數；為第k隻螞蟻在本次周遊中的路徑長度。
在螞蟻系統中，資訊素更新公式為：
3 蟻群算法的求解步驟：
（1）初始化參數在計算之初，需要對相關參數進行初始化，如蟻群規模（螞蟻數量）m、資訊素重要程度因子α、啟發函數重要程度因子β、資訊素會發銀子ρ、資訊素釋放總量Q、最大疊代次數iter_max、疊代次數初值iter=1。
（2）建構解空間将各個螞蟻随機地置于不同的出發點，對每個螞蟻k（k=1,2,3…m），按照（2-1）計算其下一個待通路城市，直到所有螞蟻通路完所有城市。
（3）更新資訊蘇計算每個螞蟻經過路徑長度Lk(k=1,2,…，m），記錄目前疊代次數中的最優解（最短路徑）。同時，根據式（2-2）和（2-3）對各個城市連接配接路徑上資訊素濃度進行更新。
（4） 判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經過路徑的記錄表，并傳回步驟2；否則，終止計算，輸出最優解。
（5）判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經過路徑的記錄表，并傳回步驟2；否則，終止計算，輸出最優解。3. 判斷是否終止若iter<iter_max，則令iter=iter+1,清空螞蟻經過路徑的記錄表，并傳回步驟2；否則，終止計算，輸出最優解。
三、部分源代碼
%% 該函數用于示範基于蟻群算法的三維路徑規劃算法
%% 清空環境
clc
clear
%% 資料初始化
%下載下傳資料
load HeightData HeightData
%網格劃分
LevelGrid=10;
PortGrid=21;
%起點終點網格點
starty=10;starth=4;
endy=8;endh=5;
m=1;
%算法參數
PopNumber=10; %種群個數
BestFitness=[]; %最佳個體
%初始資訊素
pheromone=ones(21,21,21);
%% 初始搜尋路徑
[path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone, ...
HeightData,starty,starth,endy,endh);
fitness=CacuFit(path); %适應度計算
[bestfitness,bestindex]=min(fitness); %最佳适應度
bestpath=path(bestindex,:); %最佳路徑
BestFitness=[BestFitness;bestfitness]; %适應度值記錄
%% 資訊素更新
rou=0.2;
cfit=100/bestfitness;
for i=2:PortGrid-1
pheromone(i,bestpath(i*2-1),bestpath(i*2))= ...
(1-rou)*pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit;
end
%% 循環尋找最優路徑
for kk=1:100
%% 路徑搜尋
[path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,...
pheromone,HeightData,starty,starth,endy,endh);
%% 适應度值計算更新
fitness=CacuFit(path);
[newbestfitness,newbestindex]=min(fitness);
if newbestfitness<bestfitness
bestfitness=newbestfitness;
bestpath=path(newbestindex,:);
end
BestFitness=[BestFitness;bestfitness];
%% 更新資訊素
cfit=100/bestfitness;
for i=2:PortGrid-1
pheromone(i,bestpath(i*2-1),bestpath(i*2))=(1-rou)* ...
pheromone(i,bestpath(i*2-1),bestpath(i*2))+rou*cfit;
end
end