基于最小二乘策略迭代的無人機航跡規劃方法

陳曉倩，劉瑞祥

北京聯合大學 智慧城市學院，北京100101

1 引言

與有人機相比，無人機具有體積小、成本低、生存能力強、機動性能好、使用方便等優點，業已在空中作戰、局勢偵察、精細農業、電力巡檢等領域得到廣泛應用。航跡規劃是無人機任務執行能力實現的核心技術之一，是指在綜合考慮飛行時間、燃料消耗、外界威脅等因素的前提下，為無人機規劃出一條符合任務需求和動態約束的最優航跡[1]。良好的航跡規劃能力是無人機飛行任務優化執行的重要保證。

已有的無人機航跡規劃算法包括A*算法[2]、遺傳算法[3]、蟻群算法[4]、粒子群算法[5]及人工勢場法[6]等。由于航跡規劃的規劃區域復雜多變，加之要考慮無人機的性能約束等條件，算法存在尋優能力差、計算量過大、效率不高等問題，在航跡規劃的最優性和實時性方面有待進一步提高。

近年來，強化學習算法在無人機領域的應用日益得到關注。李東華等人采用多智能體強化學習的方法，采用兩個功能不同的智能體，分別對應局部和全局路徑規劃[7]。郝釧釧等人利用無人機的航跡約束條件指導規劃空間離散化并在回報函數中引入回報成型技術[8]。上述文獻利用無人機的航跡約束條件指導規劃空間離散化，一定程度上降低了離散規劃問題的規模，提高了規劃獲得的航跡的可用性，但是航跡的精度直接與空間離散柵格尺度相關，在復雜應用場景中航跡精度無法保證。楊祖強等人采用Wire Fitting Neural Network Q（WFNNQ）學習方法實現了連續狀態連續動作的航跡規劃[9]。但連續的狀態和動作采用神經網絡逼近，訓練時間較長，收斂性較差，不適合在線應用。

為彌補已有方法的不足，本文采用最小二乘策略迭代算法開展無人機航跡規劃問題研究。該算法采用帶參線性函數逼近器近似表示值函數，避免進行空間離散化，提高了航跡精度。同時最小二乘方法利用采集的樣本數據求解值函數參數，直接對策略進行評價和改進。通過復雜城市場景中的飛行動力學仿真對算法的有效性進行了驗證，并與經典的Q 學習算法進行對比，仿真結果表明LSPI 算法規劃出的三維航跡更為平滑，規劃時間更短，有利于飛機實際飛行。

2 問題描述

本文針對城市反恐、智能物流、抗震救災等應用關注的無人機在復雜環境中的航跡規劃問題開展研究。所提出的算法能夠導引無人機安全無碰地從任一起始位置出發，到達目標位置，實現航跡長度、飛行高度、飛行安全性等指標的優化。

無人機航跡規劃功能結構如圖1 所示。任務規劃器提供航跡規劃的起始位置(X,Y,Z) 、目標位置(XT,YT,ZT)與速度(Vx,Vy,Vz)、航跡約束；基于算法的航跡規劃器利用以上任務信息及無人機提供的當前位置速度信息生成新的動作(Vx,Vy,Vz) 并提供給無人機；無人機飛控系統對飛行動作進行解析得到無人機控制指令作用于無人機；無人機將下一位置(X',Y',Z')反饋給航跡規劃和飛行控制模塊。

基于上述任務場景和功能結構，本文所述航跡規劃問題如式（1）所示。航跡優化的目標是使航跡費用J 最小，即找到一組具有最短航跡長度的可飛航跡。約束條件主要包括：航跡無碰和最大速度vmax。Co表示無人機與障礙物間的碰撞次數。

3 強化學習算法

3.1 MDP模型

強化學習是一種從環境狀態到行為映射的學習技術。學習過程如下：Agent 通過對感知到的環境狀態采取各種試探動作，獲得環境狀態的適合度評價值（通常是一個獎勵或懲罰信號），從而修改自身的動作策略以獲得較大的獎勵或較小的懲罰[10]。馬爾科夫決策過程（Markov Decision Process，MDP）常用來對強化學習問題進行建模[11]。MDP 問題通?？梢杂靡粋€五元組{S,A,P,R,γ}來描述[11]，其中S 是狀態空間，A 是動作空間，P 是狀態轉移概率，R 是立即回報（獎賞）函數，γ∈(0,1)是折扣因子。Agent 根據策略π 來選擇動作。強化學習的目標是對于一個MDP 模型，獲得最優策略π*滿足式（2）：

其中rt為單步回報，Jπ為策略π 的期望折扣總回報。

3.2 最小二乘策略迭代算法

最小二乘策略迭代（Least-Squares Policy Iteration，LSPI）是一種基于逼近方法的強化學習算法，在值函數空間進行逼近[12]。經典的Q 學習算法對狀態空間進行離散，采用查詢表的形式存儲動作值函數和策略，智能體能夠到達的狀態是有限的，不能遍歷所有狀態，離散尺度過大會降低系統精度。對于大規?；蛘哌B續空間問題，近似是一種有效的方法，可以遍歷狀態空間中所有的狀態，保證系統精度。

關于策略π 的狀態-動作值函數Qπ(s,a)定義為在狀態s 下采取動作a，且后續動作都按照策略進行選擇時獲得的期望總回報[13]。Q 值根據式（3）的貝爾曼公式計算[14]：

其中R(s,a)表示在狀態s 下執行動作a 后獲得的立即回報；P(s,a,s')∈[0,1]表示在狀態s 下選擇動作a 后使環境狀態轉移到狀態s' 的概率；π(a';s')表示策略在狀態s'選擇a'的概率。

圖1 無人機航跡規劃功能結構圖

在大規模或連續空間中，對Qπ(s,a)進行逼近。通常使用線性函數逼近器將值函數表示為一組基函數φ1,φ2,…,φn的線性組合[13]，如式（4）所示，其中ω 是一個n 維的參數向量。

LSPI是一類無模型、離策略的近似迭代算法，離線方法有更好的樣本利用率[15]。利用采樣方法，根據樣本數據來學習參數ω[16]。假設在任意策略π 下收集到N個樣本：

其中：

LSPI 的結構框圖如圖2 所示[17]。策略評估中采用線性函數逼近器逼近Q 值函數，逼近形式如式（2）所示，策略改進中通過式（7）所示的貪心策略逐步改善策略，直到前后兩次策略π[t]和π[t+1]沒有差別，得到最終的最優策略。

圖2 最小二乘策略迭代結構圖

基于LSPI的策略學習算法偽代碼如算法1所示。

算法1 基于LSPI的策略學習算法

輸入：D,ε,ω0

輸出：ω

1. 初始化：確定基函數φ，基函數個數k 和折扣因子γ

2. 計算ω：

while ‖ ω-ω' ‖＞ε do

ω ←ω'

for each (s,a,r,s')∈D do

end for

4 基于最小二乘策略迭代的無人機航跡規劃

4.1 無人機航跡規劃問題的MDP建模

由于LSPI 算法是針對MDP 模型逼近最優策略的一類有效方法，因此先將無人機航跡規劃問題建模為MDP 模型。由于無人機在航跡規劃過程中，下一時刻的位置只與當前位置和在當前位置采取的動作有關，而與其他信息無關，因此可直接建模為MDP模型。

狀態空間為無人機的三維位置集合，動作空間定義為無人機的三維速度集合?；貓蠛瘮档脑O計需要考慮各種航跡費用、飛行安全性、UAV的動態約束等航跡性能指標，具體如式（8）所示：

ωh、ωt和ωo分別為各項航跡性能指標的權重系數。在航跡規劃問題中所考慮的回報包括連續回報和離散回報兩類。

連續回報包括：UAV的飛行高度H= ||Z-Z0，其中Z0為無人機的最佳飛行高度；距離目標位置的距離差：

離散回報為碰撞懲罰；R 為狀態轉移過程中發生碰撞的懲罰項；C0為UAV與障礙發生碰撞的次數。

4.2 基于LSPI的無人機航跡規劃

采樣的樣本數據形式為(s,a,r,s')，表示在當前狀態s 選擇動作a 執行后獲得回報值r ，同時到達下一狀態s' 。當無人機到達目標位置或者發生碰撞時結束單次采樣過程。采樣階段結束后，采用LSPI 算法對采集的樣本數據進行學習得到最優策略。

基函數的選擇是LSPI 算法中一個基本的問題，高斯徑向基函數是一種常用的基函數，適用于逼近光滑且連續的函數[17]。函數形式如式（9）所示：

其中μ 表示函數中心，σ 表示函數寬度。

動作的表示是通過復制 ||A 次基函數實現的，基函數大小為 ||? × ||A 。計算選中動作對應的基函數值，其余動作的基函數值都為0，即

其中m 表示基函數個數，l 表示選中的動作a,na表示動作個數。

策略的學習根據算法1所示的偽碼進行，學習到策略后，根據策略進行航跡規劃，航跡規劃偽碼如算法2所示。根據學習到的策略估計Q 值，選擇Q 值最大的動作執行直到到達目標位置。

算法2 航跡規劃算法

輸入：s0,sT,ω

輸出：Path(s0,sT)

1. 初始化：Path(s0,sT)←{s0}

s ←s0

2. 航跡點計算：

while s ≠sTdo

π=arg max φT(s,a)ω

s′=nextstate(s,π)

s ←s'

Path(s0,sT)←s'

3. 輸出Path(s0,sT)

5 仿真結果與分析

通過無人機在復雜城市環境中的航線飛行仿真任務來驗證本文航跡算法的有效性。由于針對無人機航跡規劃問題暫無標準測試用例，本文設計了包含多種復雜形狀障礙的城市場景，如圖3所示。任務區域為100 m×100 m×60 m，設計無人機起始點為（15，25，0），目標點為（85，65，35）。航點的到達需要穿越復雜障礙環境，增加了任務的挑戰性。為了增加仿真的真實性，采用文獻[18]所述四旋翼動力學模型作為仿真中的無人機對象。仿真采用Matlab 軟件，由有2.5GHz Core i5-7200U CPU和4 GB RAM的計算機實現。

圖3 城市場景抽象圖

采用徑向基函數對狀態進行特征提取，狀態特征向量由8 個高斯基函數和1 個常量組成。位置X 分量取{25，65}兩個中心點，Y 分量中心點取{25，65}，Z 分量中心點取{15 35}，構成狀態空間共8 個高斯基中心點。探索因子γ=0.95。收集的樣本數據量為20 000。

由于目前采用與LSPI相關的強化學習方法進行無人機航跡規劃的研究較少，因此采用強化學習中應用相對廣泛的Q學習算法作為對比算法驗證LSPI算法在無人機航跡規劃中的有效性。圖4 為LSPI 算法與Q 學習算法的實驗結果對比圖，其中橫坐標為情節數，縱坐標表示每一情節對應的運行步數。從圖中可以看出，在收斂速度和收斂結果方面LSPI 算法都要優于Q 學習算法，且收斂更加穩定。圖5給出了Q學習算法與LSPI算法規劃的三維航跡對比圖，其中黑虛線為算法規劃出的航跡，紅實線表示的是將算法規劃結果用于UAV 氣動模型得到的仿真飛行曲線。具體統計數據見表1。由圖5及表1 可知，兩種算法都能實現避障，但LSPI 算法的規劃時間及航跡長度更短。雖然LSPI算法規劃的航跡轉彎與起伏動作次數較多，但總的轉彎角度和小，轉彎幅度小，更利于飛機實際飛行。Q學習算法中采用查詢表的形式存儲策略，對狀態空間進行離散化處理，狀態是離散有限的，無人機的位置只能是離散化后的狀態空間中的位置，若離散尺度偏大，計算出的航跡點間的距離就較長，無法保證無人機的平滑飛行。LSPI 算法中依據函數逼近器計算策略，函數是連續的，無人機可以到達狀態空間中的任意位置，只要動作設置合理，航跡點間的航跡長度就可以保證無人機平滑飛行。

圖4 不同算法在不同情節下到達目標所需的時間步

圖5 不同算法下的三維航跡對比圖

表1 Q-learning與LSPI算法規劃結果對比表

總的來說，LSPI算法獲得的三維航跡更為平滑，規劃時間及航跡長度更短，沒有過大的轉彎動作，可以節省燃料，提高跟蹤精度，更加適合無人機飛行。

6 結束語

本文針對傳統Q 學習算法無法有效解決連續狀態空間的問題，提出采用基于近似策略表示的最小二乘策略迭代算法進行無人機航跡規劃研究。采用線性函數逼近器近似表示動作值函數，利用最小二乘法進行參數更新，根據學習到的參數采用貪心策略進行動作選擇。仿真結果表明該算法能有效解決連續狀態空間問題，能夠為無人機在復雜城市場景中規劃出一條從起始位置到目標位置的無碰三維航跡且執行性能較優。

今后的工作將對算法展開進一步測試，并在算法充分訓練后在真實的無人機平臺實現。