針對特殊威脅的改進人工勢場法航跡規劃

李 昱，李紅燁

(中國艦船研究院，北京 100083)

0 引言

無人機(UAV)全稱為“無人駕駛飛機”或“無人自主飛行器”，是一種依靠無線電遙控或者機載程序自動控制的不載人飛行器。無人機廣泛應用于民用領域與軍事領域，可執行航拍、測繪、通信中繼、目標偵察打擊等多種任務。與載人飛機相比，其優勢在于更高的全天候工作能力，更低的資源消耗，其更適用于簡單重復性任務以及高風險任務。無人機執行任務的回報率更高，任務失敗的代價損失更小。目前各國都將裝備發展的核心轉移到無人裝備領域中，其中，無人航行器是無人裝備的重點研究對象[1-2]。

無人機在執行任務前或執行任務過程中需要對其航行路線進行規劃。航跡規劃主要是指使用相關算法實現無人機自動導航的功能，是人工智能及導航與制導領域中的重要研究方向之一。對于一般的無人機，在執行任務前，會根據戰場已知信息(如目的地、任務區域、威脅區域等)對無人機的飛行路線進行設置，實現無人機獨立自主工作；對于功能更加復雜的無人機，其可以使用機載傳感器等自主判別風險事態并執行自主規避、創建新航跡等動作。無人機航跡規劃的基本原則是在保證自身安全的前提下實現路徑最短、效率最大化，即“最優路線規劃原則”。航跡規劃對于無人機執行任務有著至關重要的作用，其重點討論的問題在于航跡規劃算法的構建與優化，使無人機利用最少的資源計算得出最優的路徑[3-4]。

目前已有多種成熟的航跡規劃算法，傳統的確定性方法包括智能搜索算法、最速下降法、可視圖方法、人工勢場法、單元分解法、最優控制方法、模擬退火算法等。現代智能航跡規劃算法有隨機化航跡搜索方法以及結合遺傳算法、蟻群算法、神經網絡算法發展而來的子算法等。

本文所研究的人工勢場法為傳統算法中的經典算法之一，其優勢在于算法的理論簡潔易懂，算法的建模方案以及計算過程相對簡單，計算開銷相對較小。但是傳統的人工勢場算法適用范圍較小，在不加以優化的前提下，只能對單一威脅源執行規避。在實際戰場應用中，飛行器的航線上很可能存在多個敵方威脅需要規避，甚至存在一整個區域需要規避的情況；同時傳統APF算法由于其理論、方法本身固有的缺陷存在區域極值的問題，導致規劃出的航跡存在尖點以及振蕩等問題。因此，傳統APF算法必須加以改進才能得以適用[5-7]。

在對傳統算法的改進過程中，主要以無人機的特殊威脅作為任務背景，綜合考慮了障礙物建模、引力斥力的產生方式和飛行器的最大轉角等問題，建立改進后的人工勢場法數學模式，并在Matlab軟件中進行仿真計算，再通過與傳統算法生成的路徑相比較驗證算法的改進效果。

1 傳統人工勢場法

1.1 算法的概念及原理

傳統人工勢場法的基本思想是在空間中人為構造出一個虛擬的勢場。這個虛擬的勢場由兩部分組成：第一部分是一個由目標點產生的引力場引導物體向其運動；第二部分是一個由障礙物產生的斥力場，避免航行器與障礙物發生碰撞。通過查找勢場函數下降的方位來得到最優的路徑，物體在路徑上每一點所受的合力等于這一點所受到的斥力和引力的矢量總和。這里的關鍵是如何構建引力場和斥力場[8-9]。我們將引力場寫作Uatt，斥力場寫作Urep，兩個勢場的總勢場即為矢量相加：

U=Uatt+Urep。

(1)

總勢場如圖1所示。

圖1 總勢場Fig.1 Total potential field

定義引力Fatt為引力場的負梯度，斥力Frep為斥力場的負梯度，無人機受到的合力即為引力與斥力的矢量和，如圖2所示。

Fatt=-?Uatt，

(2)

Frep=-?Urep，

(3)

Ftotal=Fatt+Frep=-?Utotal=-?(Uatt+Urep)。

(4)

圖2 機器人受力圖示Fig.2 Force diagram

引力場與引力：設X是當前無人機的位置，Xg是目標點的位置，X-Xg為目標點與無人機之間的距離，Katt為引力場的增益系數。則無人機與目標點之間的引力場

(3)

無人機在該力場中所受的引力為該力場函數的負梯度，即

Fatt(X)=-?Uatt(X)=-Katt|X-Xg|。

(4)

該引力的特點是在起始點處無人機受引力最大，且隨著無人機與目標點距離的減小而線性趨近于0[10-11]。

斥力場與斥力：設X是當前無人機的位置，Xobs是障礙物的位置，X-Xobs為障礙物與無人機之間的距離，ρ0是無人機受障礙物的影響距離，krep是斥力的增益系數。則無人機與障礙物之間的斥力場

。

(5)

該力場函數的特點是其產生的勢能與無人機和障礙物之間的距離有關，勢能隨著無人機和障礙物之間的距離增加而減小，與距離成反比。該力場函數為分段函數，在障礙物的影響距離之外可以認為不受障礙物的作用，在障礙物的點上可以認為其值無窮大。

無人機在該力場中所受的斥力為該力場函數的負梯度，即

(6)

對于多個障礙物所形成的勢場可以利用勢場的疊加原理將多個勢場矢量相加以得到總勢場

Utotal=Uatt+∑iUrepi。

(7)

所受合力為總勢場的負梯度[12-13]

Ftotal=Fatt+∑iFrepi。

(8)

1.2 算法的Matlab實現

傳統APF算法的Matlab程序主要包含四個部分：分別是程序主體，用于定義初始變量；調用函數，進行循環計算路徑點以及畫圖；三個子函數，分別是引力計算、斥力計算以及引力與斥力的角度計算函數。

在程序中需定義如下變量：起點終點障礙物位置坐標、引力增益系數、斥力增益系數、障礙影響距離、障礙個數、障礙半徑、步長、循環次數等初始值。初值設定完成后進入循環階段，每次循環通過計算引力、斥力的合力方向來確定無人機的下一步運動方向，再根據步長來決定無人機下一步的位置，即為一次循環。通過增加循環次數來確保無人機能夠到達目標點。

角度計算函數的輸入有無人機的坐標、目標和障礙物的坐標以及障礙物的個數。其目的是計算出無人機與目標點以及各障礙物之間的夾角以便于在計算引力和斥力的函數中使用來計算引力和斥力的各個分量。

引力計算函數的輸入有無人機的坐標、目標和障礙物的坐標、障礙物的個數、引力增益系數和引力與X軸正方向夾角。其目的是得到引力的X方向和Y方向的兩個分量以便于主體函數中矢量相加求得合力[14]。

斥力計算函數的輸入有無人機的坐標、目標和障礙物的坐標、障礙物的個數、斥力增益系數、斥力與X軸正方向夾角和障礙物的影響范圍。其目的是計算出各個障礙物對無人機的斥力的分量

子函數輸出值最后通過導入主程序進行循環計算并繪制出航跡的實際路線[15-16]。

2 特殊威脅的人工勢場算法建模過程

2.1 特殊威脅的定義

對于傳統的APF算法來說，其對傳統威脅的定義為從A至B航線上的一個威脅點，當所需要避開的威脅不能簡化為單一點坐標時，傳統的APF算法將無法適用[17]。

我們將除傳統APF算法適用的單一威脅源以外的其他形式威脅稱作特殊威脅，其包括航跡路線上需要規避的多個簡化后的點威脅、平面區域威脅以及空間區域威脅等。

本文研究的重點在平面上的面區域威脅，多點威脅可直接使用該研究算法進行簡化，空間立體區域可做相關拓展得出更進一步的結論。在面區域威脅的研究上，我們更關注障礙物的形狀、頂點以及其邊緣輪廓等特征。對于無人機的一條最優航跡來說，既要避開障礙物所占區域，又要盡可能貼近其邊緣，實現安全性與效率最大化[18]。

本文研究的“特殊威脅”背景如下：我方無人機執行任務需從起點A飛往終點B，原計劃按照最短路線，即AB連接直線飛行；同時在飛行器起飛前由戰場偵察反饋信息發現在原計劃飛行區域上可能存在敵方的防空火力覆蓋，進而須重新計算航跡路線避免被敵方擊落；重新計算航跡的過程可在地面進行計算并將新的航跡路線上傳至飛行器導航系統中或直接將測得的關鍵數據上傳給飛行器，由機載計算機中的算法直接計算得出新的航跡。所需的關鍵數據有：起點與目標終點位置信息，威脅區域的邊界信息等。改進算法將自動計算航路是否重疊，是否需要規避，如何有效規避等任務，并自動設計出一條安全有效的新航路進行導航[19]。

2.2 特殊威脅區域的擬合優化

通常威脅區域為不規則圖形，對不規則圖形進行合理的擬合化為規則的多邊形區域以方便算法的設計與計算。當輸入為已知某一威脅區域的邊界點坐標時(如圖3中多個點坐標)，改進算法可以自動判斷出距離起點最近的坐標并且由此連接相鄰點坐標，進而繪制出威脅多邊形區域。如圖3所示，當已知邊界點坐標A、B、C、D時，算法可以自動計算并擬合出簡化后的威脅區域，進而執行下一步的處理工作。

圖3 威脅區域的擬合優化Fig.3 The optimization of threat aera

當威脅區域邊界點坐標組成的威脅區域為凹多邊形時，算法在計算多邊形區域時會出現多種凹多邊形的情況無法確認，進而導致算法中止。

圖4 多種凹多邊形區域情況Fig.4 Multiple cases of threat regions

如圖4所示，當凸多邊形內部存在威脅點坐標進而組成凹多邊形時，會出現多種多邊形威脅區域的情況，算法無法自主確認具體威脅區域，進而需要對該種情況進行分類討論。最簡單的辦法即忽略掉該內部的邊界點，將威脅區域擴大為凸多邊形。雖對原始威脅區域有一定的擴大，但可減少多個判斷識別的步驟，節約大量的計算。

如圖5，將內部威脅點忽略進而組成優化后的凸多邊形區域。原始航跡如圖短虛線，目標的規避航跡如圖長虛線。如增加威脅區域邊界條件至更多點或線的集合，亦可根據上述思路得到相應的凸多邊形作為優化后的規避區域[20-21]。

圖5 去除內部威脅點的擬合優化Fig.5 The optimization of threat aera after removing internal threat point

2.3 改進算法設計原理

傳統人工勢場算法認為無人機航行中每一個時間點所受到的合力是根據目標點產生的引力和障礙點產生的斥力共同決定的。在本文中，目標點依然為單一的坐標點未發生變化，因此引力模型可以沿用傳統人工勢場法中已有的結論。對于斥力來說，原有的障礙點變為障礙區域，模型將有所變化，這也是改進算法的重點研究部分。

平面上的凸多邊形的每條邊的延長線可以將整個平面分割成多個部分，如圖6為四個威脅點的平面化分情況。

假如起點設為左下角(0，0)點附近，終點設為右上角(100， 100)點附近，可以發現若無人機以直線路線從起點向終點飛行的話將經過威脅區域正上方，因此需要采取手段從兩側規避；在無人機經過區域2，4，6，8(即威脅區域多邊形的邊對應區域)以及區域9，10(延長線相交后的區域)時，我們認為可讓無人機貼近區域邊界并與邊界保持一定距離前進效率最高；在無人機經過區域1，3，5，7(即威脅區域多邊形的頂點對應區域)時，我們認為此時無人機需要進行平滑的轉向遠離區域11(威脅區域)。

綜上我們將平面中所有被劃分的區域分為三大類：1) 頂點對應區域需要平滑轉向；2) 邊對應區域可貼近前進；3) 威脅區域不可跨越。

如圖7所示，根據兩種非威脅區域的類型制定兩種對應的障礙點選取規則。當無人機經過頂點對應區域時，我們將算法中的威脅點設置為其對應的頂點,例如經過區域1時將D點視做單一威脅點，經過區域3時將B點視做單一威脅點以此類推。此時無人機受單一引力源與單一斥力源共同作用，與傳統APF算法中的情況相同，當無人機飛行至此區域時可以使用傳統算法進行下一步路徑點的求解。當無人機經過邊對應區域時，我們將算法中的威脅點設置為此時無人機位置到威脅區域對應邊界垂線的垂足點，該點在該時刻對無人機的斥力方向垂直于該點所在邊向外，且無人機距離威脅區域邊越近該斥力越大，當無人機無限靠近邊緣時，斥力達到無窮大，保證無人機不會進入威脅區域。與第一種情況相同的是此時的目標點及威脅點同樣只有一個，亦可以使用傳統APF算法進行計算。

在該算法的執行過程上我們可以認為算法在每次計算下一步的路徑點時先進行分類討論，對自身位置進行判斷，進而選取相應規則的坐標點作為障礙物。在每一次的下一步航路計算中均只存在一個威脅點，進而可直接使用傳統APF算法進行計算，與傳統APF算法不同的是每一步的威脅點雖然數量相同，但卻不一定是同一個坐標點。威脅點的總數與算法中設置的計算步長有直接的關系，步長設置越大，計算量越小，精度相應更低；步長設置越小，計算量增加，精度相應更高。

2.4 航跡的優化

在仿真的過程中我們發現在某些輸入條件下和一些特殊位置(例如區域交接處)，規劃出的航跡會發生角度較大的偏轉。為了使規劃的航跡符合飛行器的轉彎性能，在程序中需加入控制轉角的條件，從而限制每個路徑點之間的最大角度改變量以符合飛行器性能。尖點通常出現在飛行器進入一個新區域時，振蕩更多出現在飛行器沿邊界飛行時。

改進程序主要是在每次循環計算下一個路徑點的方向時，利用判斷語句判斷前后兩次方向角度的差值是否大于設定值，如不大于則保持該值不變，若大于則令其等于最大值。如圖8所示，例如令最大轉角α=30°，不加限制時轉角為θ，可以將下次的路徑規劃點進行修正[22]。

圖6 平面區域的劃分Fig.6 The division of plane areas

圖7 障礙點的選取Fig.7 The selection of obstacle points

圖8 最大轉角限制Fig.8 Maximum angle limit

改進的算法流程圖如圖9所示。

3 仿真驗證與結果分析

依據上述建模思路以及現有的傳統APF仿真程序在Matlab中設計出改進APF算法。算法主要包含引力計算函數、斥力計算函數、角度計算函數以及算法主體部分共四個文件。

引力計算函數、斥力計算函數可以直接延用傳統APF算法中的函數；角度計算函數中加入了航跡角度最大值的限制；主程序中加入了輸入邊界值的預處理部分、平面劃分部分以及多重判斷與循環，使無人機明確自身位置進而執行下一步路徑點的計算。

對所編寫的程序進行多種情況下的輸入測試得到多組航跡規劃的結果，重點對影響航跡較大的初始變量進行討論，以及對優化算法的優化效果進行分析。

圖9 改進算法流程圖Fig.9 Flow chart of improved algorithm

以下仿真內容在各幅圖像分辨率均設定為 100×100 像素時進行。通過控制區域圖像的像素密度與算法計算步長控制總計算量。

首先改變增益系數以及距離影響參數這兩個對航跡形狀影響較大的參數并對比結果，如圖10所示。

圖10 不同斥力增益系數、距離影響參數下的仿真航跡對比Fig.10 Simulation route under different repulsive gain coefficients and distance influence parameters

從仿真結果可見，增大斥力增益系數與障礙影響范圍可以使規劃出的航跡更加遠離威脅區域。斥力的增益系數直接影響了障礙點產生的斥力大小，增大斥力增益系數使無人機受到的合力方向偏離目標點；增大障礙影響距離使無人機更早地受到斥力作用，更早進行偏轉規避動作。經過驗證，該算法可以通過調節上述兩項參數進而根據需求對新航跡路線進行適應性調整。

我們對引入的航跡路徑點的最大轉角優化部分進行對比分析其效果，如圖11所示，左右兩圖分別為未加入路徑點優化與加入了優化程序的航跡結果對比。

圖11 有無最大轉角限制的仿真航跡對比Fig.11 Simulation route with and without maximum angle limitation

從仿真結果可見，在未添加角度限制條件時，無人機接近威脅區域時可能會產生尖點，同時在無人機沿威脅區域邊界飛行時可能會發生振蕩問題。添加角度限制條件可以有效改善航跡規劃生成路徑中的尖點和振蕩點，使路徑更為平滑。

最后我們對改進算法與傳統算法進行對比，由于傳統APF算法并不能針對區域威脅進行計算，這里簡單地將威脅區域的重心視為單一威脅點輸入給傳統APF算法進行計算，如圖12(b)。

圖12 改進APF算法與傳統APF算法對比Fig.12 Comparison of the improved APF algorithm with the traditional APF algorithm

通過對比發現，傳統人工勢場法所規劃的路徑距離威脅區域的邊界過遠，無法有效地利用威脅區域周邊的安全區域。改進人工勢場算法能夠更有效地利用特殊威脅區域以外的空間，能使無人機在不穿越威脅區域的前提下更加貼近威脅區域邊界飛行。

同時通過對比Matlab程序中的迭代次數，即路徑點個數n可對比出使用兩種方法得到的航跡的總長度與總計算量上的區別。在將步長設定為0.5時，使用改進APF算法的迭代次數n為382，使用傳統APF算法的迭代次數n為507。因此可以得出結論，改進的APF算法相比傳統算法，在保證無人機避開威脅的前提下，實現了更低的路徑計算量、更短的規劃航線以及更短的航行時間。可見改進算法相對傳統算法規劃出的路徑具有更高的效率，實現了“最優航跡規劃”原則。

4 結論

本文針對傳統人工勢場法在避障階段的障礙物建模方面做出了進一步研究，一定程度上解決了傳統APF算法籠統地將障礙物視作點坐標并忽略其具體形狀而帶來對于航跡規劃上的影響。

本文通過利用傳統APF思想，部分傳統APF函數以及建模方案，加入無人機區域判斷與障礙點選取機制，使無人機可以根據不同形狀邊界的威脅區域自主計算出一條安全且高效的飛行路線。

本文主要以平面空間以及四點坐標的威脅區域體現改進APF算法相對傳統APF算法在航跡規劃上的準確性與高效性。對形狀更加復雜、邊界更多、特征更不明顯甚至三維空間的立體避障區域的研究亦可參考本文的建模思路進行設計與完善。