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

郝昱 陳強

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

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

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

0 引言

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

1 無人機航跡規(guī)劃方法設(shè)計

1.1 無人機飛行環(huán)境建模

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

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

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

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

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

1.2 建立航跡規(guī)劃目標函數(shù)

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

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

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

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

E*=Phm/m（4）

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

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

式中，minE*表示無人機航跡規(guī)劃目標函數(shù)；L表示無人機航跡長度；α表示無人機航跡代價指標的權(quán)重系數(shù)。

1.3 約束條件設(shè)定

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

∑n=1Ln≤Lmax（6）

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

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

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

Vmin≤Vi≤Vmax

Dmin≤Di≤Dmax（8）

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

1.4 基于混合蟻群算法的最優(yōu)航跡求解

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

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

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

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

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

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

δmax=QρLmin（11）

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

2 仿真實驗

為了驗證本次提出的無人機航跡規(guī)劃思路的可行性與可靠性，筆者在Matlab平臺上進行一組仿真實驗，實驗中所使用的計算機配置為：Windows2010操作系統(tǒng)，1.16 GHz頻率CPU，16 GB運行內(nèi)存。實驗在多種場景下，使用設(shè)計方法與傳統(tǒng)方法進行無人機航跡規(guī)劃仿真?；诨旌舷伻核惴ǖ臒o人機航跡規(guī)劃步驟如下。

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

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

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

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

從圖4可以看出，設(shè)計方法規(guī)劃的無人機航跡避開了所有障礙物，而傳統(tǒng)方法規(guī)劃的無人機航跡僅避開了兩個障礙物，與其中4個障礙物重合，說明設(shè)計方法規(guī)劃精度優(yōu)于傳統(tǒng)方法。

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

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

3 結(jié)語

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

參考文獻

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

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

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

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

［5］宋雪倩，胡士強.基于Dubins路徑的A*算法的多無人機路徑規(guī)劃［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