改進強化學習算法的UAV室內三維航跡規劃

張 俊，朱慶偉，嚴俊杰，溫 波

1.西安科技大學 測繪科學與技術學院，西安710054

2.西南大學 心理學部，重慶400715

無人機（Unmanned Aerial Vehicle，UAV）因其機動性能好、使用方便等特點，被廣泛應用在各個領域。將無人機用于災后室內環境搜索和救援時，可以降低對救援人員的傷害，提高任務效率，并能在救援團隊無法到達的區域執行搜索任務。航跡規劃是無人機自主導航技術的重要組成部分，其目的是找到一條安全且路徑長度盡可能短的路徑，供無人機從起始位置到達目標位置[1-2]。當發生災害時，室內空間中分布著大量的障礙物，嚴重威脅無人機的飛行安全。因此，安全高效的航跡規劃方法是無人機完成災后室內環境搜索救援任務的關鍵。

目前，許多文獻都提出了無人機航跡規劃算法。在基于網格的搜索方法中，網格的每個單元代表無人機的一個飛行節點，可根據適當的搜索算法（例如Dijkstra算法）建立基于網格的路徑規劃方法[3-4]。文獻[5]提出了一種解決加權連接定向網絡的多準則最短路徑問題的方法，將改良的粗Dijkstra標記算法用于確定最佳路徑。在基于人工勢場的方法中，根據接收來自目標和障礙物的吸引力和排斥力來改變機器人的路徑。文獻[6]根據分配給目標和障礙物的吸引力和排斥力，通過人工勢場的強度得出潛在勢場，提出了使用人工合成技術進行救援路徑規劃的方法。文獻[7]使用一種基于A*和人工勢場的混合路徑規劃算法，該算法對動態未知環境中的機器人進行路徑規劃。文獻[8]提出了一種基于遺傳算法和領航跟隨法相結合的編隊，在障礙物的環境下解決了收斂速度慢、路徑不平滑的問題。文獻[9]提出了一種結合模糊C均值（Fuzzy C-Means，FCM）算法的改進粒子群算法，用于三維環境中UAV的路徑規劃任務。文獻[10]提出了一種在環境中針對完全指定目標的在線路徑規劃算法，并假設目標的位置和障礙物的信息是已知的。文獻[11]提出了一種基于新興技術的綜合方法，通過無人飛行器和智能手機上的模擬信標的結合，就可獲取檢測到的失蹤人員的GPS位置。然而，無人機進行災后室內搜索和救援任務之前，障礙物的位置通常是未知的[12]，且目標位置和空間環境可能隨時變化。在先前的常規方法中缺少必要的學習階段，因此導致無人機的路徑規劃效率低。

針對上述航跡規劃中存在的問題，本文基于現有強化學習算法，提出了一種用于無人機室內環境的航跡規劃方法。在開始規劃前，首先對室內空間環境進行離散化處理，以降低無人機路徑規劃的難度；再通過起點和終點間連線與障礙物位置關系，以確立主要障礙物及其環繞節點，舍棄與路徑規劃中不相關的障礙物和節點。隨后，通過起終點坐標判斷出目標點所在的方向，使無人機在初始階段不再盲目選擇節點，而是朝著目標方向搜索。最后，通過仿真實驗驗證了該方法的可行性。

1 空間離散化處理

當發生災害時，室內空間環境中隨機分布著大量的障礙物，由于空間環境處于連續狀態，無人機在進行航跡規劃時，很難順利完成既定的搜索任務。因此，對室內環境進行空間離散化處理，從而在路徑規劃時可直接獲得空間節點集，即在空間節點集中找到組成路徑飛行的總成本代價最小的節點。

設每個節點knode代表無人機的一個三維坐標(xnode,ynode,znode)，令所有離散狀態空間節點的集合設置為k，如式（1）所示：

對于無人機由起點到目標點飛過的路徑節點構成的集合用G表示，如式（2）所示：

2 傳統強化學習算法及不足

Q-learning是由Watkins提出的一種強化學習方法，為給定的馬爾可夫決策過程提供最佳的動作選擇策略[13-14]。通常，強化學習是在agent與環境之間交互循環中進行，如圖1所示。在時間t中，agent觀察到一個狀態st∈S，執行一個動作at∈A，在這個過程中獲得獎勵rt∈R，隨后時間索引遞增，環境將agent傳播到新的狀態st+1，該狀態下重新開始循環。最佳路徑規劃中agent的目標是最大化獲得的總獎勵，考慮折扣系數，可以將收到的總獎勵定義如下：

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

其中，rt為時間t中獲得的獎勵。

通過不斷的訓練，agent可以自動感知未知的環境并最終獲得具有最大累積獎勵的狀態動作集，對Q函數進行迭代改進的Q學習更新規則：

其中，st和st+1是在時刻t和t+1處的觀測狀態s,rt是在時刻t的收益矩陣R，并且Qnew和Qold分別代表更新后的Q表和更新前的Q表；學習率?∈[0,1)決定將舊信息擴展到何種程度，折扣系數γ∈[0,1)平衡短期和長期獎勵的重要性。γ接近1將使主體專注于獲得長期獎勵，而選擇γ=0將使其僅考慮行為的立即獎勵，γ=1可能導致動作值發散。在遵循每個狀態-動作對被訪問無數次且學習參數?適當降低的假設下，無論遵循何種探索策略，Q學習都將收斂到最優策略。圖2描述了傳統Q學習的過程。

圖2 算法流程圖Fig.2 Algorithm flow chart

然而傳統Q-learning無法直接用于航徑規劃。在一個具有m個狀態和n個可能動作的環境中，構造出的Q表維數將為m×n。當從當前狀態轉換到下一個狀態時，agent必須從n個可能動作中選擇具有最高Q值的動作，這意味著需要n-1次比較。為了用n個狀態更新Q表，所需的比較次數為m(n-1)。因此，當環境的大小和復雜度增長，尤其是在現實世界中，隨著搜索空間的增加，完成路徑規劃的Q學習成倍增加[15]。

此外，在探索的初始階段，由于Q值初始化為0，無人機的動作完全隨機，導致不必要的計算，收斂速度慢且耗時，下一個狀態選擇的動作將由最高Q值確定[16-19]。

3 優化策略

為了克服上文中的局限性，對經典強化學習進行了優化，以滿足無人機災后室內環境的搜索和救援任務。首先，在算法學習之前，通過起點和終點間連線與障礙物碰撞確立關鍵的障礙物及包圍障礙物的節點，舍棄與路徑規劃中不相關的障礙物和節點；然后，用給定的起點和終點坐標求出目標點相對于無人機的方向，使無人機在初始階段不再隨機進行選擇，而是朝著目標方向搜索，從而降低了空間復雜性和提高了收斂速度。

3.1 空間優化策略

基于起點s和終點g的連線內與障礙物所處的位置關系，首先判斷出一組主要障礙物MO，并找到一組MO周圍的障礙物環繞點SP，以此達到限制MO的目的。然后，由起點和終點經SP上的網格點到達目標點，生成飛行路徑，如圖3所示，其中實心小球為選擇出的主要障礙物圍繞節點，空心小球為柵格節點。具體步驟為：基于與sg的碰撞，從一組危險因素中識別出一組主要障礙物MO和次要障礙物NMO，障礙物定義為O，其中MO?NMO=O且MO?NMO=?。然后令h作為基于兩個輸入之間存在交集和并集的判斷函數。若返回為1，則為MO，否則為NMO，可用以下方程式定義MO和NMO。

圖3 三維環境中MO-SOP過程Fig.3 MO-SOP process in a three-dimensional environment

確定了航跡規劃中的主要障礙物MO后，判斷出可行節點k的子集SP，以確定圍繞MO的一組節點。圍繞oi∈MO的一組點表示為spi，確定spi是基于某個參考點c，其相鄰點是距離參考點3d（d為柵格步長）長度的節點，由這些相鄰點可構成一個多維數據集。如果滿足式（8）的點定義為可行相鄰點，將其存入點集N()

c中，如式（8）所示：

N(c)是一個等待列表，其中包含選作為SP的參考點。若oi與參考點c的多維數據集ci相交，則返回1，否則返回0，表達式為由于spi中的所有點都是c的多維數據集與oi相交并從臨時列表中移除得到的，可得出spi?kh，當spi是一組圍繞oi的節點時，則spi=kh；而如果在進行SP進程找到周圍所有點前就結束了，表明spi≠kh，則c不會確定為spi的元素，因為它與oi的距離還不夠近，無法有效地圍繞障礙物。因此，c的相鄰點也將被忽略且不會輸入到該集中。重復此過程直到該集變為空集，即可獲得圍繞oi的網格點的子集。

初始參考點c可以通過s′獲得，即oi的SP過程的起點，這樣可以使參考點成為可行的節點，便于對oi啟動SP過程。定義s′之前，首先確定oi∈O和sg之間有n個相交點{ }jd1,jd2,…,jdn，距離s最近的相交點定義為j′,j′定義如式（9）所示：

然后根據j′來處理s′，從而開始進行針對oi的SP處理，如式（10）所示，表示在s和j′之間的所有節點中，距離j′最近的節點

找到MO中所有障礙物的周圍點集之后，即可規劃出從s到g的航跡，所規劃出的航跡是基于圖形T=(V,E)生成的，其中V是一組頂點，E是一組連接頂點對的邊。

除了提高無人機三維路徑規劃的效率外，本文所提的優化策略在降低路徑長度方面也具有優勢。在優化方法中，進行無人機三維路徑規劃時只考慮某幾個障礙物，其中每個頂點連接到一定數量的頂點或最近的相鄰節點，而不是整個圖形。因此，在將圖的密度定義為有限數量的連接點的情況下，空間中的點數量的減少有利于縮短路徑長度。

3.2 Q值初始化策略

Q-learning是一種“試錯”算法，收斂速度慢是Qlearning算法的一個重要缺陷。

無人機在三維環境中可向除自身外的26個方向之一運動，在路徑探索初期，由于Q值初始化為0，無人機將向其周圍的相鄰點隨機移動，收斂速度慢同時耗時較長。因此通過確定相對于起點位置的目標方向，對Q值進行初始化，使得學習初期即有一定的目標性。無人機飛行方向與起點和終點連線的夾角越小，構造的方向趨向函數值越大，就能獲得較高的獎勵，無人機將跳過向其他方向的移動，并且從開始位置到目標位置的整個移動過程都會重復這種狀態，此過程將引導無人機朝著目標方向搜索，減少計算路徑和到達目的地的時間。

通過以下關系確定當前無人機目標點的方向：將無人機起點坐標定義為s(sx,sy,sz),目標點定義為g(gx,gy,gz),下一個待選節點坐標定義為n(nx,ny,nz)。首先，通過待選節點坐標和終點坐標分別減去起點坐標，確定待選節點和終點與起點之間的差值，即：

然后如圖4所示，令θ為向量sg和向量sn之間的夾角，其余弦值為：

圖4 起點與待選節點直線和目標點直線之間的夾角Fig.4 Angle between starting point and straight line of selected node and straight line of target point

式（12）中兩個向量夾角值越小，余弦值越大，表明無人機動作方向靠近目標方向，能獲得更大的獎勵，于是構造方向趨向函數：

其中，q為方向趨向因子，D為當前待選節點到目標狀態的歐式距離在Q值初始化過程中，利用si處的方向函數值來初始化狀態價值函數V(si)，并通過式（14）行為價值函數和狀態價值函數之間的關系來實現Q值的初始化，即：

4 算法實現步驟與實驗

4.1 算法步驟

結合了目標方向和MO-SP策略的災后室內無人機強化學習航跡規劃策略的實施過程如下：

步驟1已知起點和終點坐標的條件下，根據起點和終點連線位置關系，確定所連直線經過的主要障礙物，判斷主要障礙物周圍的節點相對于障礙物的位置關系，當時，則為環繞主要障礙物的節點。

步驟2在初始狀態下，根據起點和終點的位置確定目標點所在方向，實現對環境先驗信息的初始化。

步驟3利用環境狀態值函數更新Q(s,a)。

步驟4無人機采取可變貪心法則，每移動一步就更新一組Q()s,a，直到搜索到目標點，再進行多次迭代達到穩定的收斂值。

4.2 實驗結果與分析

為了驗證本文優化的強化學習方法在路徑規劃中的有效性，在三維柵格地圖中對所優化的強化學習算法進行實驗。在本實驗中，考慮一架無人機、一個目標點，并且考慮無人機可向任意方向移動。本實驗柵格地圖尺度為90×60×50柵格，實驗搭建的三維模型如圖5所示，為了更接近真實室內環境，環境中隨機設置障礙物。無人機的起始位置為（6，54，0），目標點的位置為（78，30，18），將目標點設置在遠離邊界的位置，以防止某些實驗性事故的發生。

圖5 三維環境模型Fig.5 Three-dimensional environment model

算法中相關參數設置如下：算法最大迭代次數max_iteration=1 500,學習率?=0.1，折扣因子γ=0.96,貪婪度ε設置為0.8；設置回報函數Rt=100，對于即時獎勵r值的設置，可通過以下式子：

其中，δ、τ是參數，本實驗中設置δ為10，設置τ為40；dt為當前狀態與目標點之間的距離，dt+1為下一個無人機位置到目標點的距離，d0為無人機與障礙物之間的距離。

4.2.1算法有效性驗證

為了評估所提出算法的性能，評估了在每個情節中找到目標的收斂時間、路徑長度等評價因素，并對獲得的結果進行了比較和討論。在這項研究中，進行了三組實驗，分別是經典Q學習算法，記為C-Q算法，引入目標方向的Q學習算法，記為T-Q算法，以及基于目標方向和MO-SP的綜合改進Q學習算法，記為A-Q算法。為了消除隨機誤差對結果的影響，每種算法在實驗環境中多次運行后取切尾均值，然后將三種算法的結果進行比較以驗證算法的有效性。每種算法達到目標所規劃的路徑和算法的收斂情況分別顯示在圖6和圖7中，結果記錄在表1中。

圖6 三種Q-learning算法的路徑圖Fig.6 Path diagram of three Q-learning algorithms

圖7 三種Q-learning算法的收斂情況Fig.7 Convergence of three Q-learning algorithms

表1 三種Q-learning算法的性能比較Table 1 Performance comparison of three Q-learning algorithms

由圖7（a）可知，C-Q算法經過948次的迭代才收斂到目標點，但在學習初期，無人機需要超過4 000次的嘗試才能找到到達目標位置的路徑。這是因為算法的初始階段，Q值初始化為0，使得沒有經驗的無人機只能隨機選取動作，從而使算法的收斂速度很慢。圖7（b）是在C-Q算法基礎上計入了目標方向策略的T-Q算法，通過仿真結果可知，T-Q算法在經過547次迭代收斂于目標。在學習初期，找到目標位置的路徑所需要的嘗試次數為252次，遠低于C-Q算法；同時，算法從起始位置到目標方向的收斂時間相比于C-Q算法減少95.45%，這是因為Q值初始化時無人機就有一個朝著目標的方向，從而避免搜索與無人機終點方向無關的節點，減少了額外的時間開銷；由于減少了不必要方向的搜索，T-Q算法所得的路徑長度比C-Q算法降低了59.87%，且從圖6可知，T-Q算法的搜索路徑圖比C-Q算法更符合任務要求。上述分析表明引入方向目標策略能夠在學習初期引導無人機快速收斂，并縮短學習時間和路徑長度，從而提高收斂速度。由圖7（c）可知，在學習初始階段，無人機到達目標位置的嘗試次數較T-Q算法有略微的增加，但A-Q算法在經過307次的迭代后就能收斂于目標點。與圖7（b）仿真結果比較可知，在目標方向的基礎上，對環境進行MO-SP策略，使算法的收斂時間較T-Q算法減少了68.61%，空間搜索節點減少了55.49%，同時路徑長度也得到了進一步的減少。集成后的算法能更進一步提高算法初始階段的學習效率，改善無人機路徑規劃強化學習算法的性能。

4.2.2算法適應性驗證

為了確定本文優化算法的適應性，在不同的起始位置點和障礙物中進行了三組實驗，設置每組實驗的目標點坐標均為（84，30，18），每次實驗運行多次并取結果的切尾均值。圖8顯示了三組實驗的路徑規劃圖。其中地圖a與地圖b為相同起點和終點條件下不同障礙物環境，地圖a與地圖c障礙物位置相同而起點位置不同，結果比較見表2。根據表2結果可知，本文優化的Q-learning算法在不同場景中具有良好的適應性。

圖8 不同環境中優化Q-learning航跡規劃圖Fig.8 Optimized Q-learning trajectory planning diagram in different environments

表2 不同環境中優化Q-learning的性能比較Table 2 Performance comparison of optimized Q-learning in different environments

5 結束語

傳統強化學習Q-learning算法在初期，由于缺乏先驗知識，收斂速度慢，同時三維環境中空間復雜度高，對路徑規劃具有很大的影響，無法直接用于災后室內環境中的搜索和救援任務。本文提出了一種優化型強化學習Q-learning算法，通過起點和終點的位置關系確定出三維柵格地圖中路徑規劃的主要障礙物及障礙物包圍的點集，并且通過數學關系確定目標所在的方向來初始化Q值。仿真結果表明：相較于傳統Q-learning算法，在初始化Q值的過程中確定目標所在方向，能有效降低算法的收斂時間；目標方向和MO-SP策略整合后算法收斂時間降低了98.57%，搜索節點數量降低了55.49%；所規劃的路徑長度也得到了明顯的縮短。本文僅考慮靜態路徑規劃，因此將本文所提的優化型Q-learning應用于涉及動態移動障礙的路徑規劃是未來進一步研究的方向。