基于改進蟻群算法的無人機三維路徑規劃研究?

焦 陽

（北京新機場建設指揮部 北京 102602）

1 引言

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

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

2 問題描述

2.1 三維環境建模

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

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

圖1 規劃空間劃分示意圖

圖2 任意平面劃分示意圖

2.2 目標函數

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

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

3 路徑規劃算法

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

3.1 信息素更新規則

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

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

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

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

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

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

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

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

3.2 啟發式函數確定

啟發式函數設計的目的是利用啟發信息來引導無人機尋找從起點到終點的最優路徑［8］。根據蟻群算法的原理，當無人機從當前一個飛行節點飛向下一個飛行節點的時候，需要根據啟發式函數來計算無人機在當前飛行節點飛向空間中其他節點的概率。啟發式函數為

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

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

其中，xi，yi，zi表示當前節點的x，y，z三個方向的坐標，xi+1，yi+1，zi+1表示下一個節點x，y，z三個方向的坐標。

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

其中，nr表示在點（x，y，z）時無人機飛行空間內可通過的節點數量，nur表示在點（x，y，z）時無人機飛行空間內不可通過的節點數量。

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

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

3.3 路徑搜索

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

圖3 路徑搜索示意圖

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

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

3.4 蟻群算法描述

本文首先對無人機飛行環境進行建模，劃設飛行空間中的可通過區域以及不可通過區域，構建三維環境模型，然后確定信息素的選取方式，通過路徑點選擇，確定啟發式函數。本文的算法步驟如下：

1）通過2.1節中的三維環境模型構建無人機路徑規劃的三維飛行空間，根據飛行任務計劃以及環境模型，選取合適的點作為路徑規劃的起點和終點。

2）將蟻群中所有螞蟻放置在設定的路徑規劃的起點，將x軸作為螞蟻進行搜索的主運動方向。

3）初始化蟻群算法中各個模型的運行參數。

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

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

6）判斷規劃的路徑中的所有螞蟻是否全部到達終點，是，繼續執行，否，返回到步驟3）。

7）當螞蟻執行一次路徑搜索后，采用信息素全局更新模型對路徑上的信息素進行全局更新，并判斷算法是否滿足結束條件，是，則輸出最優解，否，返回到步驟3）繼續執行。

4 算例分析

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

首先，對三維環境進行建模，將環境空間等分為10×10×10的柵格，每個柵格大小相同，長度均為1，同時構建25個威脅區域。構建的三維環境模型如圖4所示。

圖4 三維環境模型

根據三維環境建模結果，結合威脅區的位置以及范圍，確定無人機路徑規劃的起始點坐標為（0.5，0.5，0.5），終點坐標為（8.5，8.5，5.5）。同時設置蟻群算法的各個參數的值，參數設置如表1所示。

表1 仿真參數設置

采用上述設置的參數，對無人機進行三維路徑規劃，得到的結果如圖5所示。

圖5 路徑規劃結果

將本文采用的蟻群算法進行路徑規劃的結果與采用傳統蟻群算法進行路徑規劃的結果進行比較，結果如表2所示。

表2 仿真參數設置

由表2可以看出，本文所采用的蟻群算法規劃出的路徑更短，運行時間更少，算法更加穩定，能在較短的時間內收斂。

5 結語

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