基于改進(jìn)蟻群算法的無人機(jī)三維路徑規(guī)劃研究?

焦 陽

（北京新機(jī)場建設(shè)指揮部 北京 102602）

1 引言

近些年來，無人機(jī)在農(nóng)業(yè)灌溉、安全報警、氣象預(yù)報、地理測繪以及軍事作戰(zhàn)等多個領(lǐng)域有著廣泛的應(yīng)用。無人機(jī)高度的自治性和靈活性，在現(xiàn)實生活中扮演著重要的角色［6］，無人機(jī)未來的發(fā)展方向也更加趨于智能化、自動化。尤其是在軍事領(lǐng)域方面，無人機(jī)參與指揮作戰(zhàn)能有效地減少目標(biāo)被發(fā)現(xiàn)的概率，增加指揮作戰(zhàn)時移動的靈活性，減少作戰(zhàn)人員傷亡［1］。因此，隨著無人機(jī)的快速發(fā)展，研究無人機(jī)路徑規(guī)劃技術(shù)，統(tǒng)籌考慮無人機(jī)的生存概率、航程代價和時間代價等多種因素，為其找到一條從起點到終點的最優(yōu)飛行路徑，能有效保障無人機(jī)的飛行安全，提高任務(wù)的執(zhí)行效率，減少不必要的損失。

路徑規(guī)劃是無人機(jī)相關(guān)研究中最重要的內(nèi)容之一，也是無人機(jī)能夠安全可靠地執(zhí)行各項任務(wù)的基本保障。近年來國內(nèi)外學(xué)者提出了許多路徑規(guī)劃的方法，主要包括有Voronoi圖法、遺傳算法、蟻群算法［9］、粒子群優(yōu)化算法、人工勢場法［12］、A*算法［6］等。上述算法在進(jìn)行三維路徑規(guī)劃中，均有一定的局限性，在規(guī)模較大的三維環(huán)境中，很難規(guī)劃出一條最優(yōu)的路徑。由于蟻群算法具有分布式計算、群體智能、正反饋等優(yōu)點［8］，本文針對其容易陷入局部最優(yōu)、收斂速度慢的缺點，對該算法進(jìn)行改進(jìn)并將改進(jìn)的算法應(yīng)用到無人機(jī)三維路徑規(guī)劃中，最后通過仿真驗證算法的可行性。

2 問題描述

2.1 三維環(huán)境建模

環(huán)境建模是無人機(jī)進(jìn)行路徑規(guī)劃的一個重要環(huán)節(jié)，也是需要完成的第一步，環(huán)境建模的好壞直接影響著路徑規(guī)劃的結(jié)果與質(zhì)量［11］。本文借鑒柵格化的方法對無人機(jī)飛行的三維空間進(jìn)行環(huán)境建模，主要思想是首先把三維立體空間等分成平面空間，然后再把平面空間劃分成平面柵格［2］。

如圖1所示，首先建立三維直角坐標(biāo)系O-XYZ，其中O為無人機(jī)進(jìn)行路徑規(guī)劃的起始點［10］。在直角坐標(biāo)系中，構(gòu)造一個三維立方體空間ABCD-EFGH，其中平面ABCD位于XOZ平面上，AB邊平行于X軸，CD邊平行于Z軸，原點O位于平面ABCD的中點。然后將無人機(jī)的飛行空間置于該三維立體區(qū)域內(nèi)，AB、AE分別等于無人機(jī)飛行空間的長度和寬度。之后對規(guī)劃空間進(jìn)行進(jìn)一步的劃分。首先，沿Y軸方向?qū)臻g進(jìn)行n等分，其次過每個等分點做平行于ABCD的平面，得到n+1個平面。同理，對任意平面沿Z軸進(jìn)行l(wèi)等分，沿X軸進(jìn)行m等分，如圖2所示，這樣規(guī)劃空間就被劃分成n×m×l個柵格。在實際應(yīng)用中，以無人機(jī)能在單位柵格內(nèi)進(jìn)行自由運(yùn)動為提前，對柵格的大小進(jìn)行劃分，即首先為無人機(jī)飛行設(shè)定路徑規(guī)劃的空間，然后進(jìn)一步根據(jù)無人的爬坡能力設(shè)定n，m，l的大小。

圖1 規(guī)劃空間劃分示意圖

圖2 任意平面劃分示意圖

2.2 目標(biāo)函數(shù)

無人機(jī)路徑規(guī)劃的本質(zhì)是在一定的約束條件下找出從起點到終點能有序地避開威脅區(qū)域的最優(yōu)路徑［6］。采用2.1節(jié)中的柵格法對無人機(jī)的運(yùn)動空間進(jìn)行三維建模，并把禁飛區(qū)、障礙區(qū)、威脅區(qū)等對無人機(jī)飛行造成威脅的區(qū)域，簡化成無人機(jī)無法通過的柵格，則無人機(jī)路徑規(guī)劃就變成在可通過的柵格集合中尋找有序的子集，從而使無人機(jī)的飛行距離之和最短的問題。無人機(jī)路徑規(guī)劃的目標(biāo)函數(shù)如下所示：

其中，(xi，yi，zi)表示柵格中心點坐標(biāo)，n表示路徑點的個數(shù)，L表示規(guī)劃的路徑總距離。

3 路徑規(guī)劃算法

蟻群算法是由M.Dorigo等在1991年提出的通過模擬螞蟻集體覓食行為的啟發(fā)式優(yōu)化算法［3］。在自然界中，螞蟻覓食過程由每個螞蟻不斷釋放信息素所決定，通過引導(dǎo)其他螞蟻選擇信息素濃度較高的路徑，幫助蟻群最終找到覓食的最優(yōu)路徑［4］。這種整個群體形成的正反饋機(jī)制，使得該算法的搜索機(jī)制具有隨機(jī)性，以及正反饋的特點，這個特點能有效地在無人機(jī)三維路徑規(guī)劃中，找到全局最優(yōu)的路徑。

3.1 信息素更新規(guī)則

根據(jù)蟻群算法原理，信息素是蟻群在覓食過程中對螞蟻產(chǎn)生吸引作用的信息載體，在一定程度上對算法的收斂速度和路徑規(guī)劃效果有著十分重要的影響［5］。信息素主要留在路徑上，與尋找路徑構(gòu)造圖的邊相對應(yīng)，在三維空間內(nèi)進(jìn)行路徑規(guī)劃時，會造成龐大的計算量［7］。因此本文采用環(huán)境模型中的離散點作為載體，將信息素存儲到各個離散點上，在節(jié)省存儲空間的同時，降低計算的復(fù)雜度。

在對無人機(jī)進(jìn)行路徑規(guī)劃的過程中，需要對信息素進(jìn)行更新，信息素更新分為局部信息素更新和全局信息素更新。局部信息素更新是指當(dāng)無人機(jī)每經(jīng)過一個路徑點時，該路徑點上的信息素濃度會相對減少，其目的是為了減少其他無人機(jī)選擇該點的可能性，增加無人機(jī)發(fā)現(xiàn)更多路徑的機(jī)會，避免算法陷入局部最優(yōu)。局部信息素更新公式如下：

其 中 ，τxyz表示點(x，y，z)上的信息素的值，ξ(0＜ξ＜1)表示信息素衰減系數(shù)。

全局信息素更新就是當(dāng)無人機(jī)從起點飛到終點規(guī)劃一條飛行路徑時，以無人機(jī)規(guī)劃的路徑長度作為評價來判斷信息素的多少，然后從路徑集合中選擇最優(yōu)路徑，對該路徑上各點的信息素進(jìn)行更新。其更新規(guī)則如下：

其中，Δτxyz表示信息素增量，length(α)表示第α個螞蟻完成路徑時的路徑長度，ρ表示信息素更新系數(shù)，k表示常數(shù)。

在上述公式中，由于信息素增量Δτxyz中的k為常數(shù)，在無人機(jī)尋找最優(yōu)路徑過程的前期，最優(yōu)路徑中的離散點所對應(yīng)的信息素增加不快，而在進(jìn)行無人機(jī)尋找最優(yōu)路徑過程的后期，搜索到的最優(yōu)路徑與其他路徑相比在距離上有很大的優(yōu)勢，導(dǎo)致最優(yōu)路徑上的信息素增加非常迅速，這將造成最優(yōu)路徑信息素的濃度過高，而其他路徑上的離散點信息素濃度偏低，算法容易陷入局部最優(yōu)的困境［5］。因此，本文提出一種全局信息素更新改進(jìn)方法，在保留對已經(jīng)搜索到的最優(yōu)飛行路徑上的信息素進(jìn)行更新的同時，在出現(xiàn)當(dāng)前搜索過程中的最優(yōu)路徑和已經(jīng)搜索到的最優(yōu)路徑長度不相等的狀況下，采取同步對當(dāng)前搜索最優(yōu)路徑上的信息素進(jìn)行更新的策略，來避免算法陷入局部最優(yōu)的困境。此外，算法在循環(huán)搜索過程中，當(dāng)處于停滯狀態(tài)的次數(shù)達(dá)到一定時，算法停止更新已經(jīng)搜索到的最優(yōu)路徑上的信息素，使蟻群中的螞蟻從有序狀態(tài)變?yōu)闊o序，以達(dá)到增大算法發(fā)現(xiàn)更優(yōu)解能力的目的。

具體方法為改變信息素增量表達(dá)式，具體如下：

上述公式中，Imax表示算法進(jìn)行路徑搜索的最大迭代次數(shù)，I表示算法當(dāng)前迭代次數(shù)，λ和J為常數(shù)。J由預(yù)估的理想搜索路徑長度決定，λ值由J和Imax共同決定，保證λImax+J的值與第一次進(jìn)行無人機(jī)路徑規(guī)劃的長度接近。該方法能有效保證在無人機(jī)進(jìn)行路徑搜索前期，最優(yōu)路徑上的信息素能有效增加，在路徑搜索后期，最優(yōu)路徑上的信息素不會快速增加，有效地避免了陷入局部最優(yōu)的困境。

3.2 啟發(fā)式函數(shù)確定

啟發(fā)式函數(shù)設(shè)計的目的是利用啟發(fā)信息來引導(dǎo)無人機(jī)尋找從起點到終點的最優(yōu)路徑［8］。根據(jù)蟻群算法的原理，當(dāng)無人機(jī)從當(dāng)前一個飛行節(jié)點飛向下一個飛行節(jié)點的時候，需要根據(jù)啟發(fā)式函數(shù)來計算無人機(jī)在當(dāng)前飛行節(jié)點飛向空間中其他節(jié)點的概率。啟發(fā)式函數(shù)為

其中，D1(x，y，z)表示當(dāng)前點飛行節(jié)點到下一個飛行節(jié)點的距離，主要用來引導(dǎo)無人機(jī)飛向距離當(dāng)前節(jié)點較近的下一個節(jié)點；T(x，y，z)表示威脅代價函數(shù)，主要用來引導(dǎo)無人機(jī)飛向安全的區(qū)域；D2(x，y，z)表示無人機(jī)從下個飛行節(jié)點飛向終點的距離，主要用來引導(dǎo)無人機(jī)飛向路徑規(guī)劃的終點。

上式中，D1(x，y，z)的表達(dá)式如下：

其中，xi，yi，zi表示當(dāng)前節(jié)點的x，y，z三個方向的坐標(biāo)，xi+1，yi+1，zi+1表示下一個節(jié)點x，y，z三個方向的坐標(biāo)。

T(x，y，z)的表達(dá)式如下：

其中，nr表示在點（x，y，z）時無人機(jī)飛行空間內(nèi)可通過的節(jié)點數(shù)量，nur表示在點（x，y，z）時無人機(jī)飛行空間內(nèi)不可通過的節(jié)點數(shù)量。

D2(x，y，z)的表達(dá)式如下：

其中xd，yd，zd表示終點x，y，z三個方向的坐標(biāo)。

3.3 路徑搜索

在進(jìn)行路徑規(guī)劃時，本文將X軸方向作為無人機(jī)移動的主要方向。假設(shè)無人機(jī)飛行的起點為Ps，終點為Pc，并規(guī)定無人機(jī)的運(yùn)動方向分為前進(jìn)、橫向和縱向運(yùn)行。若無人機(jī)以X軸為主方向前進(jìn)，則無人機(jī)在點（xi，yi，zi）沿 X軸方向運(yùn)動的情況下，無人機(jī)最大橫向運(yùn)動距離為Lymax，最大縱向運(yùn)動距離為Lzmax。因此，無人機(jī)下一步飛行空間可按上述方法定義，無人機(jī)下一步飛行可到達(dá)的點就在這個飛行空間之中。采用蟻群算法構(gòu)建路徑的過程如圖3所示。

圖3 路徑搜索示意圖

根據(jù)上述路徑搜索方法，無人機(jī)在目前所在節(jié)點i選擇下一個節(jié)點i+1時，首先利用無人機(jī)當(dāng)前所在節(jié)點的位置信息，計算當(dāng)前路徑搜索空間內(nèi)所有可通過的節(jié)點信息，然后根據(jù)所有可通過節(jié)點的信息，通過啟發(fā)式函數(shù)進(jìn)行計算，最后得到其他可通過節(jié)點的啟發(fā)函數(shù)的值［5］。根據(jù)啟發(fā)函數(shù)的值計算所有可通過節(jié)點的選擇概率p(x+1，y，z)，p(x+1，y，z)的表達(dá)式如下所示：

其中，τ(x+1)yz表示點p(x+1，y，z)對應(yīng)的信息素的值；node∈reachable表示當(dāng)前節(jié)點可通過；node∈unreachable表示當(dāng)前節(jié)點不可通過。

3.4 蟻群算法描述

本文首先對無人機(jī)飛行環(huán)境進(jìn)行建模，劃設(shè)飛行空間中的可通過區(qū)域以及不可通過區(qū)域，構(gòu)建三維環(huán)境模型，然后確定信息素的選取方式，通過路徑點選擇，確定啟發(fā)式函數(shù)。本文的算法步驟如下：

1）通過2.1節(jié)中的三維環(huán)境模型構(gòu)建無人機(jī)路徑規(guī)劃的三維飛行空間，根據(jù)飛行任務(wù)計劃以及環(huán)境模型，選取合適的點作為路徑規(guī)劃的起點和終點。

2）將蟻群中所有螞蟻放置在設(shè)定的路徑規(guī)劃的起點，將x軸作為螞蟻進(jìn)行搜索的主運(yùn)動方向。

3）初始化蟻群算法中各個模型的運(yùn)行參數(shù)。

4）開始對三維路徑進(jìn)行搜索，更新路徑點上的信息素濃度，對可通過區(qū)域采用啟發(fā)函數(shù)進(jìn)行計算，同時根據(jù)計算結(jié)果選擇下一個需要通過的路徑節(jié)點。

5）放置所有螞蟻到計算的下一個路徑節(jié)點，對該點的信息素濃度進(jìn)行局部更新，并對更新的結(jié)果結(jié)果存儲到內(nèi)存中。

6）判斷規(guī)劃的路徑中的所有螞蟻是否全部到達(dá)終點，是，繼續(xù)執(zhí)行，否，返回到步驟3）。

7）當(dāng)螞蟻執(zhí)行一次路徑搜索后，采用信息素全局更新模型對路徑上的信息素進(jìn)行全局更新，并判斷算法是否滿足結(jié)束條件，是，則輸出最優(yōu)解，否，返回到步驟3）繼續(xù)執(zhí)行。

4 算例分析

本文采用仿真的方式對無人機(jī)飛行空間進(jìn)行模擬，用Matlab軟件編程工具，對基于蟻群算法的無人機(jī)路徑規(guī)劃進(jìn)行仿真，來驗證該算法進(jìn)行路徑規(guī)劃的效果以及可行性。

首先，對三維環(huán)境進(jìn)行建模，將環(huán)境空間等分為10×10×10的柵格，每個柵格大小相同，長度均為1，同時構(gòu)建25個威脅區(qū)域。構(gòu)建的三維環(huán)境模型如圖4所示。

圖4 三維環(huán)境模型

根據(jù)三維環(huán)境建模結(jié)果，結(jié)合威脅區(qū)的位置以及范圍，確定無人機(jī)路徑規(guī)劃的起始點坐標(biāo)為（0.5，0.5，0.5），終點坐標(biāo)為（8.5，8.5，5.5）。同時設(shè)置蟻群算法的各個參數(shù)的值，參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)設(shè)置

采用上述設(shè)置的參數(shù)，對無人機(jī)進(jìn)行三維路徑規(guī)劃，得到的結(jié)果如圖5所示。

圖5 路徑規(guī)劃結(jié)果

將本文采用的蟻群算法進(jìn)行路徑規(guī)劃的結(jié)果與采用傳統(tǒng)蟻群算法進(jìn)行路徑規(guī)劃的結(jié)果進(jìn)行比較，結(jié)果如表2所示。

表2 仿真參數(shù)設(shè)置

由表2可以看出，本文所采用的蟻群算法規(guī)劃出的路徑更短，運(yùn)行時間更少，算法更加穩(wěn)定，能在較短的時間內(nèi)收斂。

5 結(jié)語

本文采用蟻群算法對無人機(jī)進(jìn)行路徑規(guī)劃問題進(jìn)行研究，首先采用柵格化的方法對無人機(jī)的飛行進(jìn)行抽象建模，并在建模空間中，以最短路徑為目標(biāo)函數(shù)，提出一種改進(jìn)的信息素更新規(guī)則的蟻群算法，為無人機(jī)在三維空間中規(guī)劃出一條安全、最優(yōu)的飛行路徑，最后，采用仿真的方式進(jìn)行驗證，實驗結(jié)果表明，本文所采用的蟻群算法規(guī)劃出的路徑更短，運(yùn)行時間更少，算法更加穩(wěn)定，能在較短的時間內(nèi)收斂。