融合Q 學習算法和人工勢場算法的無人機航跡規劃方法

劉 冬，余文泉，霍文健，李 瑞，姜偉月

（北方自動控制技術研究所，太原 030006）

0 引言

作為重要的無人裝備，軍用無人機已在現代戰爭中嶄露頭角。從敘利亞戰爭到納卡沖突，軍用無人機都表現出色，它們對地面坦克、步戰車、自行火炮等裝甲高價值目標形成巨大的威脅。戰爭形態的持續變化不斷呼喚新裝備新技術，自主執行任務是軍用無人機發展的趨勢。無人機航跡規劃是在綜合考慮無人機到達時間、油耗、威脅以及飛行區域等因素的前提下，為無人機規劃出最優或滿意的飛行航跡［1］。戰場環境下無人機需要深入敵區進行偵察和對抗，因此，如何快速準確地規劃出一條安全、便捷的路徑，成為了無人機自主完成任務的關鍵。

現有航跡規劃算法可分為經典算法和智能算法。其中，應用于航跡規劃的經典算法主要有A*算法、人工勢場法、快速搜索隨機樹、Voronoi 圖法等；用于航跡規劃的智能算法主要包括蟻群算法、粒子群算法、遺傳算法等［2-9］。上述方法在一定條件下擁有各自的優勢，但在環境信息無法完全獲取或模型過于復雜的情況下，表現的效果并不理想［10］。

隨著機器學習的迅速發展，人們試圖用基于強化學習的算法來解決無人機航跡規劃問題。Q 學習算法作為一種經典的強化學習方法，它能夠在環境信息未完全獲取的情況下，通過學習機制為無人機規劃出一條避開所有危險區域的最優路徑?，F有基于強化學習的航跡規劃方法大多基于Q 學習及其改進算法，見文獻［11-13］。

基于強化學習的航跡規劃算法生成的航跡，是由搜索到的航跡點直線連接而成，若無人機沿規劃的航跡飛行時，可能與障礙物發生碰撞［14］。針對該問題，本文提出了一種融合Q 學習算法和人工勢場算法的無人機航跡規劃方法，可以有效、快速地構建出最短航線，并避免基于Q 學習算法規劃的航跡中發生與障礙物碰撞的危險。

1 融合Q 學習算法和人工勢場算法的航跡規劃方法

1.1 基于Q 學習算法的航跡規劃方法

強化學習是機器學習的范式和方法論之一，它把學習看成試探的過程，具體模型如圖1 所示。每次試探時，智能體先是感知環境，獲得當前在環境中所處狀態St；然后依據一定的策略，從動作集中選擇一個動作At作用于環境；環境在動作At的作用下，變更到了新的狀態St+1，并根據動作給予智能體獎懲Rt+1；智能體通過獎懲判斷執行動作的好壞反饋，并且不斷地調整動作的選擇策略，以期望獲得最大的回報。在基于強化學習的航跡規劃系統中，無人機可以看作智能體，飛行環境可以看作智能體作用的環境，位置可以看作智能體所處的狀態，飛行的方向可以看作智能體能夠采取的動作，如果飛到障礙區給予懲罰，或者飛到安全區給予獎勵，尋求最佳路徑的過程即求取最佳決策的過程。

圖1 強化學習基本模型Fig.1 Basic model of reinforcement learning

下面給出基于強化學習的航跡規劃方法的實現方法。

1.1.1 環境建模

本文假設無人機在相同高度飛行，并采用柵格法對飛行環境進行建模，具體如圖2 所示。

圖2 基于柵格法的飛行環境Fig.2 Flight environment based on grid method

在該圖中，飛行區域被劃分成了多個連續但不重合的網格，其中，黑色網格表示障礙物（山峰、攻擊區），白色網格表示可以通行的區域，實心圓圈分別表示起始點和目標點。為了計算無人機的飛行軌跡，需要對柵格地圖中網格的位置進行標記。網格的位置有兩種表示方法：序列法和坐標法［15］。假設每個網格都有如圖2 所示的一個序列化的編號，每個網格的中心點坐標為網格的直角坐標，則網格編號與其直角坐標的對應關系如式（1）所示。

式中：x，y 分別為網格的直角坐標；N 表示每個網格對應的編號；n 表示網格的行（列）數；Mod 表示取余函數，ceil 表示向右取整運算。

1.1.2 動作建模

在柵格地圖中，無人機位于某一柵格時有8 種可能前進方向，本文用0，1…7 來表示無人機可能執行的8 種動作，即向正北、東北、正東、東南、正南，西南、正西，西北飛行，具體如圖3 所示。

圖3 飛行動作Fig.3 Flight movements

1.1.3 獎懲函數

在基于強化學習的規劃航跡算法中，智能體每次與環境進行一次交互（即飛行器在柵格中每移動一步）就會獲得一次獎懲。學習的目標就是到達終點時，得到的回報最多，因此，構建合理的獎勵函數直接關系到航跡規劃的好壞。本文設計的獎勵函數如表1 所示。

表1 無人機飛行獎懲函數表Table 1 Flight reward and punishment function table of UAV

1.1.4 Q 學習算法

Q 學習算法是最基本的強化學習算法之一，它采用Q 值迭代方式來獲取到最優策略。Q 學習算法中的迭代方程如式（2）所示：

式中，Q（st，at）表示在狀態s 下采取動作a 能夠獲得的回報，α∈［0，1］為學習率，用于調節學習過程中的可能誤差；γ 為折扣因子，r 為狀態下執行動作a得到的即時獎勵。

算法1 給出了Q 學習算法的偽碼描述，利用該算法可以求得所需的路徑。

算法1 Q 學習算法1 Initialize Q（s，a）arbitrarily 2 Repeat（for each episode）:3 Initialize s4 Repeat（for each step of episode）:5 Choose a from s using policy derived 6 from Q（e.g.ξ-greedy）7 Take action a，observe r，s'8 Q（s，a）=Q（s，a）+α［r+ymaxa'（s'，a'）-Q（s，a）］9 s=s'10 until s is terminal

1.2 人工勢場算法

人工勢場算法是一種對運動物體進行路徑規劃的常用方法。該算法將假設無人機周圍存在一個虛擬的力場，并由引力場和斥力場所構成。其中，目標點會對物體產生引力場，障礙物對物體產生斥力場，無人機在這兩種勢場力的控制下不斷朝目標點前進，最終形成要規劃的軌跡。圖4 展示了無人機在人工勢場環境下的受力模型，其中，Fatt表示引力，Frep示排斥力，Ftotal是引力和斥力的合力。

圖4 人工勢場環境下的無人機受力模型Fig.4 Force model of UAV under the artificial potential field environment

下面給出傳統人工勢場法相關函數的定義。

假設無人機當前的位置為X=（x，y），目標的位置為Xg=（x，y），則引力勢場函數表示為：

由于引力是引力場產生的負梯度，則引力函數表示為：

式（3）和式（4）中Katt表示引力增益系數，表示無人機從當前位置到目標位置的距離。

障礙物產生的斥力勢場函數公式如下：

同理，由斥力場的負梯度可以得到斥力函數：

式中，Krep表示斥力增益系數，ρ 表示障礙物能夠對無人機產生影響的最大半徑，同時也是無人機和障礙物之間的最小安全距離，表示無人機與障礙物之間的距離。

無人機在運動空間中受到的勢場和合力分別為：

1.3 基于融合算法的航跡規劃方法

由上節可知，在基于Q 學習算法無人機航跡規劃方法中，無人機可以沿正南、正北、正東、正西、東南、東北、西南、西北8 個方向飛行。根據獎懲函數，斜線飛行的價值大于水平飛行，所以系統在為無人機規劃航線時會優先選擇斜線飛行方向。沿著斜線飛行會縮短飛行距離，但這也會導致如圖5 所示與障礙物碰撞的情形。

圖5 飛行器沿斜線飛行時的情形Fig.5 The status of UAV flying along oblique line

為了避免該問題的發生，本文提出了融合Q 學習算法和人工勢場算法的航跡規劃方法。該方法首先采用Q 學習算法獲得一條飛行路徑，其次針對該路徑每段斜線軌跡統計其范圍內所包含的障礙物，再次判斷每段斜線軌跡是否包含障礙物，如果包含采用改進的人工勢場法對該段軌跡進行重新規劃，否則仍采用原有軌跡。障礙物的統計方法如圖6 所示：以p1和p2的連線為直徑畫圓，如果障礙物落在圓內則進行記錄，否則將將其丟棄。其中，p1是無人飛行器移動的當前位置，p2是通過Q 學習算法產生的當前節點的下一位置，圖中的圓是障礙物，r 是半徑。

圖6 局部路徑規劃中障礙物、目標點示意圖Fig.6 Schematic diagram of obstacles and target points in local route planning

傳統人工勢場法的局限性在于，當目標點對無人機的吸引力和障礙物對無人機的排斥力合力為零時，無人機永遠無法到達目標點。針對該問題，本文通過引入式（9）所示的斥力場函數來解決。

該函數在原有斥力場的基礎上增加了目標和物體距離的影響。無人機靠近目標時，雖然斥力場會增加，但是距離卻在減少，因此，在一定程度上能夠起到對斥力場增大減緩的作用。

相應的斥力變成式（10）

其中，

為了進一步解決該問題，本文還對排斥力在坐標軸上的分量進行改進，具體如式（13）和式（14）所示。當無人機因受力平衡陷入僵局時，通過此法改變排斥力的方向，從而使無人機繞開障礙物繼續向目標靠近。

下頁算法2 給出了融合算法的偽代碼描述，首先通過Q 學習算法得到全局路徑點集golobpath（步驟2），接下來對全局路徑的每段軌跡進行遍歷（步驟3～步驟26）。每次遍歷時首先判斷該段軌跡p1-p2是否為斜邊（步驟5～步驟25）。如果p1-p2是斜邊，則需要進一步判段是否需要對斜邊p1-p2進行局部航跡規劃（步驟6～步驟22），否則直接將該軌跡段的起始點p1加入到最終路徑path 中（步驟24）。判段是否需要對該斜邊p1-p2進行局部路徑規劃，主要看該段軌跡內是否存在障礙物，也即判讀obj2集合是否為空，如果不為空基于人工勢場法求出局部路徑localpath（步驟18），將其加入最終路徑path（步驟19），如果為空則將該路段的起始點p1加入到最終路徑path 中。其中obj2集的構建方法如下：1）求出該段軌跡范圍的半徑r 和圓心o（步驟6～步驟7）。2）遍歷障礙物集obj1（步驟9～步驟15）。每次遍歷時判段該次遍歷到的障礙物obj1［i］到圓心o 的距離是否小于半徑r，如果小于等于r，將其加入obj2中（步驟10～步驟11），否則加入到障礙物點集obj3中（步驟12～步驟13）。

算法2 Q-learning and artificial potential field fusion algorithm Intput:start，goal，map，obstacle Output:path 1 Initialize：obj1=obstacle，J=200 2 golobpath=Q 學習（star，goal，map，obstacle）3 for i=1：len（golobpath）-1 4 p1=golobpath［i］：p2=golobpath［i+1］5 If（‖p2［2］-p1［2］‖=‖p2［1］-p1［1］‖）6 r=1/2‖p1-p2‖7 o［1］=1/2（p2［1］-p1［1］）；o［2］=1/2（p2［2］-p1［2］）8 obj2=［］；obj3=［］9 for j=1:len(obj1)-1 10 if（‖obj1［j］-o‖≤r）then 11 obj2=obj2.append（obj1［j］）12 else 13 obj3=obj3.append（obj1［j］）14 end 15 end 16 obj1=obj3 17 If（len（obj2）>0 18 localpath=artificialpotentialfield（p1，p2，obj2）19 path.append（localpath）20 else21.path.append（p1）22 end23.else 24 path.append（p1）25 end 26 end 27 path.append（goal）

算法2 中主要用到的符號及其含義見表2。

表2 符號意義Table 2 The meaning of symbols

2 實驗評價

為了驗證融合算法的有效性，本文基于MATLAB2015a、在Intel（R）Core（TM）i5-10210U 主頻為1.6 GHz 的計算機上進行仿真實驗。選取的地圖起始點設為（0.5，0.5），目標點設為（19.5，19.5），每個網格的單位長度為200 m。本文主要進行了兩組實驗。實驗1 基于Q 學習算法，設定折扣因子，學習率，迭代次數為80 次，獎懲函數參數見表2，動作集元素如圖3 所示。實驗2 基于融合算法，設定引力增益系數，斥力增益系數，最小安全距離0.5*單元格長度，參數n=2。

圖7 展示了實驗1 的運行結果，可以看出盡管利用該方法得到的路徑長度最短，但當無人機沿著該路線飛行時會與障礙物發生碰撞。下頁圖8 展示了實驗2 的運行結果，雖然路徑長度有所增加，但當無人機沿著該修正路線進行飛行時，可以避免障礙物發生碰撞。

圖7 基于Q 學習算法規劃出的路線Fig.7 The planned route based on Q-learning algorithm

圖8 基于融合算法規劃出的路線Fig.8 The planned rtoute based on fusion algorithm

下頁表3 列出了兩種算法的性能指標對比。從表3 可以看出，融合算法較Q 學習算法規劃出的路徑長度增加了3.9%，規劃時間增加了19%，但碰撞點卻減少了100%。

表3 兩種算法性能指標對比Table 3 Performance index comparison of two kinds of algorithms

綜合來看，雖然融合算法在路徑長度和規劃時間上略有犧牲，卻避免了與障礙物碰撞的風險，這樣的路徑也更加適合無人機的飛行。

3 結論

針對基于Q 學習算法規劃出的航線存在與障礙物發生碰撞危險的問題，本文提出了一種融合Q學習算法和人工勢場算法的航跡規劃方法，并與基于Q 學習算法的航跡規劃算法進行了實驗比較。實驗結果顯示，融合算法可以在給出最短軌跡航線的情況下，有效避免障礙物發生碰撞。

本文的航跡規劃方法僅僅考慮了靜態障礙物，而無人機的飛行環境是復雜多變的，往往會出現運動軌跡未知的隨機障礙物。若要使用本文方法避開動態運行的障礙物，則需要結合飛機的飛行速度，這將作為本文下一步的研究重點。