基于混合蟻群算法的無人機航跡規劃

郝昱 陳強

摘要：由于傳統方法在無人機航跡規劃實際應用中規劃的航跡長度較長，文章提出基于混合蟻群算法的無人機航跡規劃。由山峰模型和天氣模型組建無人機航跡環境數學模型，描述無人機飛行航跡環境情況，以無人機航跡代價最小建立目標函數，并對無人機航跡長度、高度、速度、轉彎角度進行約束，采用混合蟻群算法對目標函數求解，求出最優航跡規劃策略。實驗證明，文章設計方法規劃的航跡長度最短為1 032.58 m，規劃航跡長度較短，在無人機航跡規劃方面具有良好的應用前景。

關鍵詞：混合蟻群算法；無人機；航跡規劃；航跡代價；約束條件

中圖分類號：TP391? 文獻標志碼：A

0 引言

航跡規劃是無人機完成飛行任務的關鍵，無人機自主飛行主要依靠航跡規劃，一條合格的無人機航跡規劃路線需要滿足線路短、達到時間短、能源消耗少、代價小、無障礙等多個條件，由于多數情況下無人機飛行環境比較惡劣，障礙物較多，地形比較復雜，導致無人機航跡規劃難度較高［1］。隨著無人機生產數量和需求量的不斷提高，無人機航跡規劃問題受到學者和專家們的重視和關注［2-3］。

1 無人機航跡規劃方法設計

1.1 無人機飛行環境建模

無人機航跡規劃是在一個特定的環境中，首先需要建立無人機飛行環境數學模型，此次采用指數函數模擬出山峰環境，其用公式表示為：

h（x，y）=∑i=1Hiexp-x-xix*2-y-yiy*2（1）

式中，h（x，y）表示無人機飛行地圖在（x，y）點的高程值；i表示無人機飛行地圖中山峰數量；Hi表示無人機飛行地圖中第i個山峰的高度；xi，yi分別表示無人機飛行地圖中第i個山峰的中心點橫坐標和縱坐標；x*表示第i個山峰在水平方向的衰減量；y*表示第i個山峰在垂直方向的衰減量。無人機在飛行過程中會受到天氣條件威脅，這種強對流天氣很容易使無人機飛行中機身發生嚴重的顛簸，采用圓柱形表示無人機航跡規劃受天氣威脅影響區域，具體如圖1所示。R表示無人機航跡距離天氣飛行中心半徑，其用數學模型表示為：

P=1π（R2-R1），R≤r≤R1（2）

式中，P表示無人機飛行時受天氣環境影響的概率；R1表示距離天氣威脅中心半徑范圍外的安全區域半徑；r表示無人機與天氣威脅中心點的距離。

1.2 建立航跡規劃目標函數

代價是無人機航跡規劃需要考慮的重點因素，其關系到航跡規劃精度，規劃的航跡盡可能將無人機飛行代價控制到最小［4-5］。無人機航跡是由n段長度不同的航路組成，則其飛行代價用公式表示為：

E=c×∑n=1dn（3）

式中，E表示無人機航跡飛行代價；c表示常數系數，通常情況下該系數取值范圍為0～1；dn表示無人機航跡中第n個航路的長度。除了受自身性能影響付出的飛行代價外，假設無人機飛行環境中的威脅為M，將無人機航跡劃航路分成相等的路段，其受到的威脅代價如圖2所示。

如圖2所示，將無人機每個航路劃分成m個路段，路段用k表示，威脅點M到每個路段的距離為h，假設當無人機飛行到某個路段k時，威脅點M對其正常飛行影響存在一定概率，則其航跡代價為：

E*=Phm/m（4）

式中，E*表示無人機飛行受環境中威脅影響付出的代價。此次以無人機航跡代價最小為目標，建立無人機航跡規劃目標函數，根據上述分析，目標函數用公式表示為：

minE*=min∫L（αE+（1-α）E*）（5）

式中，minE*表示無人機航跡規劃目標函數；L表示無人機航跡長度；α表示無人機航跡代價指標的權重系數。

1.3 約束條件設定

無人機飛行距離存在一定的限制，在執行飛行任務時無人機航跡要小于其最大航行距離，保證無人機可以正常返航到初始點，因此對無人機航跡航行距離約束如下：

∑n=1Ln≤Lmax（6）

式中，Ln表示在規劃的無人機航跡下無人機航行距離；Lmax表示無人機最大航行距離。無人機從當前航段進入下一段航路，因此在無人機航跡規劃時，當考慮無人機航向發生改變時調整轉彎角度，要保證無人機轉彎角度在安全范圍內，因此對無人機轉彎角度約束如下：

aiaj|ai|×|aj|≥cosβ（7）

式中，ai，aj分別表示無人機當前航路和下一段航路的飛行方向向量；β表示無人機由當前航路到下一段航路的最大轉彎角度。無人機在執行飛行任務時，要將無人機飛行高度和飛行速度設定在安全范圍內，因此對無人機飛行速度和飛行高度約束如下：

Vmin≤Vi≤Vmax

Dmin≤Di≤Dmax（8）

式中，Vmin，Vmax分別表示按照規劃的無人機航跡最小和最大飛行速度；Vi表示無人機航跡飛行速度；Dmin，Dmax分別表示按照規劃的無人機航跡最小和最大飛行高度；Di表示無人機航跡飛行高度。

1.4 基于混合蟻群算法的最優航跡求解

根據實際需求此次選擇混合蟻群算法對最優航跡求解，將從解集中選擇最優解問題模擬為螞蟻搜索食物問題，假設每一個解為螞蟻搜索食物中需要路經的城市，最優解為螞蟻搜索食物的目標點，其計算流程如圖3所示。

如圖3所示，首先根據無人機航跡規劃的實際情況，對算法參數進行初始化，蟻群數量設定范圍為100～300，最大迭代次數設定范圍為100～200，信息素揮發系數設定范圍為0.3～0.7，啟發因子重要程度設定范圍為3～7，信息素增加濃度設定范圍為1～10，信息素重要程度設定范圍為3～7，信息素初始濃度設定范圍為10～100。計算出螞蟻個體的適應度，適應度是螞蟻種群的屬性，表示螞蟻的優劣程度，其計算公式為：

v=wzi+cε（pi+si）（9）

式中，v表示螞蟻種群個體適應度；w表示慣性權重，通常情況下該慣性權重取值范圍為2～7；zi表示第i個螞蟻位置；c表示螞蟻個體學習因子；ε表示在區間0～1內均勻分布的隨機數；pi表示第i個螞蟻個體極限第d維分量；si表示第i個螞蟻速度的第d維分量。螞蟻按照設定的迭代次數進行迭代全局搜索，每進行一次食物搜索，就完成一次迭代計算，螞蟻在食物搜索過程中會留下信息素，因此完成一次迭代后要對搜索路徑上的信息素進行更新，其更新公式為：

δ（t+1）=（1-ρ）+△δ（10）

式中，δ（t+1）表示螞蟻食物搜索過程中遺留在路徑上的信息；ρ表示啟發因子重要程度；表示信息素更新系數；△δ表示和收斂次數成正比的函數。由于防止在迭代過程中過早進入局部最優，將信息素最大值進行限定，其用公式表示為：

δmax=QρLmin（11）

式中，δmax表示信息素最大值；Q表示混沌變量。將每個搜索路徑上的信息素濃度進行限制，使搜索空間內所有的路徑都有可能被選擇，利用上述公式對蟻群位置和信息素更新，并判斷當前蟻群位置是否為個體極值，如果是則判斷當前位置是否優于全局極值，如果不是，則返回上一步驟重新計算。當達到迭代要求后，停止計算，輸出信息素濃度最高的解作為最優解，其對應的無人機航跡規劃策略為最優策略。

2 仿真實驗

為了驗證本次提出的無人機航跡規劃思路的可行性與可靠性，筆者在Matlab平臺上進行一組仿真實驗，實驗中所使用的計算機配置為：Windows2010操作系統，1.16 GHz頻率CPU，16 GB運行內存。實驗在多種場景下，使用設計方法與傳統方法進行無人機航跡規劃仿真。基于混合蟻群算法的無人機航跡規劃步驟如下。

Step1：建立無人機飛行環境建模。通過公式（1）公式（2）計算飛行環境中每個山峰的坐標和受天氣環境影響的概率，根據計算結果得到無人機飛行環境模型。

Step2： 混合蟻群算法參數設定。根據飛行環境情況對混合蟻群算法參數設定如下：初始信息素濃度為56.26，信息素重要程度因子設定為5.64，信息素揮發系數設定為0.56，信息素增加濃度因子設定為6.35，啟發因子重要程度設定為6.48，蟻群數量設定為100，最大迭代次數設定為200。

Step3：最優無人機航跡規劃方案求解。通過公式（9）～公式（11），對蟻群個體適應度計算及對蟻群迭代更新，輸出全局最優，得到無人機航跡規劃最優方案。

將本文設計方法與傳統方法進行仿真對比，場景設計：在模擬的無人機飛行環境中設定6個威脅點。選擇7個坐標點作為無人機飛行目標點，從出發點出發飛行達到8個目標點，對8次飛行航跡進行規劃，以第一個飛行航跡規劃為例，其仿真結果如圖4所示。

從圖4可以看出，設計方法規劃的無人機航跡避開了所有障礙物，而傳統方法規劃的無人機航跡僅避開了兩個障礙物，與其中4個障礙物重合，說明設計方法規劃精度優于傳統方法。

為了進一步驗證設計方法適用性，以航跡長度為兩種方法評價指標，使用電子表格記錄每條飛行航跡長度，對比兩種方法規劃的航跡長度長短，具體數據如表1所示。

通過對表1中數據分析可以得出以下結論：采用設計方法規劃的無人機航跡長度比較短，同一目標點設計方法規劃的無人機航跡長度比傳統方法短近894.62 m，這是因為此次采用了混合蟻群算法，保證了無人機航跡規劃精度。此外，此次設計方法中對無?? 人機航跡三維環境進行了建模，綜合無人機飛行地形環境和天氣環境兩個環境因素，描述出無人機航跡規劃環境需求。因此實驗結果證明在航跡長度方面設計方法優于傳統方法，設計方法對無人機航跡目標點的目的性更強，規劃的航跡長度更短。

3 結語

本文提出了一個新的規劃思路，并通過實驗論證了該思路的可行性與可靠性，有效縮短了無人機航跡長度，此次研究對豐富無人機航跡規劃理論，具有良好的現實意義。

參考文獻

［1］謝新連，何平，何傲，等.復雜水域船舶避碰路徑規劃研究［J］..重慶交通大學學報（自然科學版），2019（12）：1-7.

［2］楊玉，金敏，魯華祥.融合簡化稀疏A*算法與模擬退火算法的無人機航跡規劃［J］.計算機系統應用，2019（4）：25-31.

［3］陳俠，艾宇迪，梁紅利.基于改進蟻群算法的無人機三維航跡規劃研究［J］.戰術導彈技術，2019（2）：59-66，105.

［4］趙江，張巖，馬澤文，等.對AGV路徑規劃A星算法的改進與驗證［J］.計算機工程與應用，2018（21）：217-223.

［5］宋雪倩，胡士強.基于Dubins路徑的A*算法的多無人機路徑規劃［J］.電光與控制，2018（11）：25-29.

（編輯 王雪芬）

UAV path planning based on hybrid ant colony algorithm

Hao? Yu， Chen? Qiang

（Jiangxi University of Science and Technology，Ganzhou 341400， China）

Abstract：? Due to the long flight path length planned by traditional methods in the practical application of UAV flight path planning， this paper proposes a UAV flight path planning method based on hybrid ant colony algorithm. A mathematical model of UAVs flight path environment was established by mountain peak model and weather model to describe the environment of UAVs flight path. The objective function was established with the minimum cost of UAVs flight path， and constraints were set according to the actual requirements to constrain the length， height， speed and turning Angle of UAVs flight path. The mixed ant colony algorithm was used to solve the objective function， and the optimal flight path planning strategy was obtained. The experimental results show that the shortest length of the planned flight path is 1 032.58 m， and the planned flight path length is relatively short， which has a good application prospect in UAV flight path planning.

Key words： hybrid ant colony algorithm; drones; track planning; track cost; constraint condition