RVO-DDPG算法在多UAV集結航路規劃的應用

楊秀霞，高恒杰，劉 偉，張 毅

1.海軍航空大學 岸防兵學院，山東 煙臺 264001

2.海軍航空大學 作戰勤務學院，山東 煙臺 264001

在軍事應用領域，單無人機往往很難實現任務預期，多無人機編隊、有人/無人協同編隊等編隊形式逐漸引起人們的重視，隨著UAV技術的不斷發展，無人機自主編隊控制技術已經引起了國內外學者的廣泛關注[1]。

無人機編隊航路規劃的重難點在于不確定環境下的動態避障航路規劃和多機協同規劃，而多無人機編隊集結路徑規劃不僅需要考慮不確定環境、無人機性能約束，還需要滿足各UAV之間的時間協同和空間協同約束，是一個約束眾多、復雜且相互耦合的多目標優化問題[2]。文獻[3]提出了具有合作機制的分布式協同粒子群算法，該方法使每架UAV規劃出一條滿足機間協同約束的最優安全可飛行路徑。文獻[4]提出了一種新的路徑規劃和位置分配方法，通過矩陣迭代得到一組較優的目標點分配方案。文獻[5]設計了一種新的快速共識方法，實現了多UAV能夠同時到達目標區域。文獻[6]提出了GRC-SAS算法將多UAV合作問題分解為連續的單UAV計劃問題，滿足了多UAV動態規劃的需要。文獻[7]提出了基于Dubins路徑的分層規劃方法，該方法相對于多UAV非線性方法提供更優的路徑。文獻[8]采用粒子群優化算法為UAV設計dubins曲線參數，使得多UAV能夠同時到達集結點。文獻[9]采用模型預測控制實時調整各UAV航路以實現多UAV集結航路規劃。文獻[10]提出基于A*算法規劃UAV集結航路，并采用B樣條曲線對航路進行平滑。文獻[11]提出了一種分區集結的控制策略，將集結點分為多個分區，不同分區的UAV按一定規則向分配的集結點航行。文獻[12]提出基于定向A*算法的多UAV同時集結分步策略，通過調整各UAV的航路實現多UAV的同時集結。文獻[13]將UAV集群集結航路規劃問題轉化為最優控制問題，并采用Radau偽譜法進行求解。文獻[14]提出基于虛擬導引點的三階段UAV制導律，將UAV與虛擬導引點的距離分為三個階段并分別設計UAV制導律。文獻[15]根據編隊集結的要求為各UAV設計Dubins集結路徑，并通過一致性控制協議完成多UAV集結航路規劃。

盡管上述方法在其各自的環境中都實現了規劃的目標，但是仍然存在一些不足，主要表現在以下幾點：一是大多算法僅在靜態環境中進行多UAV編隊集結路徑規劃，缺乏處理動態障礙的能力，很難應用于不確定環境中。二是上述方法過于依賴環境動態模型和UAV模型，這些模型的準確性很大程度上影響其方法的性能。尤其在不確定環境中，上述方法時刻計算多UAV和障礙的狀態并為UAV尋找安全的航路，不但大量浪費計算資源，而且計算時間長不易滿足多UAV應用于不確定環境中的需求。因此，設計一種算法能夠使多UAV在集結過程中快速避障并安全達到集結點是十分必要的。

針對以上問題，在傳統DDPG算法基礎上引入互惠速度障礙法，本文提出了一種基于RVO-DDPG的多UAV集結路徑規劃算法，根據此算法對多UAV在集結過程中的航路進行規劃。首先，提出了基于DDPG的多UAV集結航路規劃算法，基于馬爾可夫決策過程設計了集結航路規劃模型。其次，引入互惠速度障礙法指導UAV在避碰過程中有效地選擇動作，提高了算法的收斂速度。再次，將多UAV編隊中多目標優化問題轉化為獎勵函數設計問題，設計了一種基于綜合代價的獎勵函數，有效解決了傳統DDPG算法應用于集結航路規劃時易產生局部最優路徑的問題。最后基于PyCharm軟件通過仿真實驗驗證了該算法的性能并與其他算法進行對比分析。仿真實驗結果表明，本文提出的基于RVO-DDPG算法不僅能夠為多UAV編隊集結任務快速規劃出最優航路，而且具有良好的收斂性和實用性。

1 問題描述

1.1 任務描述

假設有N架UAV從起始點出發，在不確定環境中的目標點完成集結。環境內存在多個動態障礙和靜態障礙。其中靜態障礙主要為禁飛區域、雷達威脅區域，動態障礙主要為非合作飛行器。為簡化問題，將不規則靜態障礙用其外接圓表示。任務環境如圖1所示，圖中黑色圓形區域表示靜態障礙，紅色圓形區域表示移動的非合作飛行器，統一視為動態障礙，三角形區域為UAV的集結點。

圖1 飛行任務環境示意圖Fig.1 Schematic diagram of mission environment

本文的研究對象為裝備有機載探測器的UAV，UAV的探測能力用以下約束條件表示：

其中，d表示從UAV當前位置到障礙的距離，dsensor為機載探測器的最大探測距離。為研究方便給出以下假設：

（1）研究問題在二維平面內，不考慮無人機的高度。

（2）UAV能夠實時探測并獲得該范圍內的障礙信息，并且獲知障礙信息時沒有延遲。

（3）UAV和動態障礙的運動方式為勻速直線運動。

綜上所述，各UAV在不確定環境中的任務為從起始點出發，在飛行過程中使得總代價J最小的前提下，避免我方UAV和動、靜態障礙物并達到集結區域形成編隊隊形。

1.2 UAV運動學模型

根據前文描述，將航路規劃問題中的UAV看作質點運動模型，使用航向角的角速度來控制UAV的運動過程。UAV的運動方程可表示為：

式中，vu表示UAV在XOY平面內的速度，α為航向角，ω為航向角速度。

1.3 多UAV飛行代價約束

1.3.1 UAV運動學約束

在飛行過程中，UAV的航向角、航向角速度都必須在一定范圍內變化，以滿足UAV的飛行性能約束JUAV。其約束條件為：

1.3.2 航程代價約束

UAV航程代價可以表示為：

式中，c1為比例系數；Li表示第i架UAV的航路長度；JL,i為第i架UAV的航路代價函數。

1.3.3 碰撞代價約束

碰撞代價Jobs,i分為靜態障礙碰撞代價Js_obs,i、動態障礙碰撞代價Jd_obs,i以及UAV之間的碰撞代價JUAV,i，即：

在前文中已經說明將各不規則障礙用其外接圓表示，在此設定其安全距離。動態、靜態障礙物的安全距離為其外接圓的半徑。而對于UAV之間，設定其安全距離為400 m。

其中：

1.3.4 時間協同代價約束

編隊成員間的時間協同代價可表示為：

式中，Li為第i架UAV達到集結點的航行路程，Lc為N架UAV達到集結點的航行路程平均值，N為UAV的數量，Jt為時間協同代價函數。

1.3.5 綜合航行代價

多UAV的綜合航行代價描述為：

式中，W1、W2、W3分別為航程代價、碰撞代價、時間協同代價的權重，JL,i為航程代價，Jobs,i為碰撞代價，Jt為時間協同代價。多UAV航路規劃的目的就是使無人機綜合代價最小化。

2 DDPG集結航路規劃算法

2.1 算法原理

深度確定性策略梯度算法（DDPG）是一種以確定性策略梯度算法（DPG）為基礎、加入深度神經網絡的基于actor-critic架構的確定性策略算法。DDPG網絡架構由在線actor網絡、目標actor網絡、在線Q網絡、目標Q網絡四個網絡組成，其四個神經網絡更新的方式如下所示。

在線actor網絡更新策略梯度為：

在線critic網絡通過最小化損失函數進行更新，其損失函數為：

其中：

DDPG算法采取了軟更新的方式更新目標網路參數，其目標actor網絡、目標critic網絡更新方式分別為：

其中，τ?1。

對于DDPG算法而言，其存在的主要缺陷是探索能力不足。為解決此缺陷，DDPG算法引入了Behavior策略，即在線actor網絡輸出動作時加入隨機噪聲ηt，將智能體執行的確定值動作變為隨機值動作at。

2.2 馬爾可夫模型設計

通過DDPG算法將不確定環境中多UAV路徑規劃問題建模為馬爾可夫決策過程。下面依次對該模型的三個元素，即狀態空間、動作空間、獎勵函數進行設計。

2.2.1 狀態空間設計

狀態空間s的設計與多UAV飛行任務密切相關，要對各UAV飛行時的狀態變化有所反應。在不確定環境下的多UAV集結路徑規劃問題中，UAV狀態空間設計主要考慮UAV的位置和航向信息以及集結點的位置。結合UAV運動學模型，狀態空間s如式（15）：

其中，( ux,uy)i為各UAV的位置；(α )i為各UAV的航向；( t arx,tary)i為各UAV的集結點。具體為：

2.2.2 動作空間設計

如前文所述，UAV的飛行通過改變航向角α實現。控制策略每隔一次采樣時間δt更新一次航向角速度。考慮到無人機最大航向角速度，并避免航向角的劇烈變化影響無人機的安全飛行，定義航向角速度動作空間a∈A為：

若t時刻無人機航向角為αt，則下一時刻無人機狀態為：

2.2.3 獎勵函數設計

DDPG集結航路規劃算法中，獎勵函數是在各UAV做出動作并與環境進行交互后由環境反饋的獎懲信號。針對航路規劃中UAV的安全和達到集結點的問題對獎勵函數設計如下：

2.3 算法流程

DDPG集結航路規劃算法通過對多UAV航向角速度的學習進行航路規劃。在進行航路規劃時，UAV傳感器將獲取的環境數據輸入在線actor網絡，在線actor網絡根據環境數據使用策略梯度進行策略學習選擇各UAV航向角速度，在線critic網絡則根據UAV所處環境狀態以及所做動作對價值函數進行評估，根據產生的評估信號評價各UAV航向角速度。

算法與環境交互獲得樣本數據(s,a,r,s′)，并將其存入經驗池中。在樣本數據中，s為某一時刻各UAV從環境中觀測到的狀態信息，a為各UAV根據觀測到的狀態信息s執行的動作，s′為各UAV在執行動作a后從環境中觀測到的狀態信息，r為各UAV在狀態s的情況下執行動作a后獲得的獎勵值，各UAV根據獎勵值的大小選擇最優動作策略。DDPG路徑規劃算法進行更新迭代時，首先對經驗池進行樣本數據積累直至達到最小批次所規定的數量，然后隨機從經驗池中采樣batch_size個樣本數據進行訓練并更新其神經網絡。最后訓練好的神經網絡為各UAV規劃出集結航路。

2.4 傳統DDPG集結航路規劃算法不足之處

首先是避障過程中動作調整具有隨機性導致算法收斂時間長。在采用DDPG算法的多UAV系統中，在線actor網絡由動作空間中每個動作的選擇概率和隨機噪聲的共同作用選擇動作。在當前狀態下選擇此動作的獎勵值少，則會降低該動作的選擇概率，反之則提高該動作的選擇概率。由于算法初期網絡訓練不充分，UAV在面對障礙時會選擇錯誤航向角速度以降低該動作的選擇概率。在很多次試錯之后在線actor網絡才會在面對障礙時選擇正確的航向角速度，此時算法才開始收斂。所以傳統DDPG算法應用于多UAV集結航路規劃時存在訓練時間長、算法收斂速度慢的缺點。

其次是航路集結問題中獎勵函數設計不合理，易產生局部最優解。傳統DDPG算法通過最大化獎勵r計算目標的最優解。在多UAV編隊集結問題中，獎勵函數R對各UAV的動作決策進行量化評估，為各UAV學習航向決策提供有效的指導。但是多UAV集結航路規劃問題的本質為多目標優化問題，而經過RVO-DDPG算法學習后的航路有可能只是使多UAV安全達到集結點的航路，只滿足了UAV能夠安全避障然后到達集結點，并不滿足航路綜合代價最小。此時規劃出的集結航路為局部最優航路，而非全局最優航路。

3 RVO-DDPG航路規劃算法

針對上述問題，本文將互惠速度障礙法與DDPG算法相結合，提出基于RVO-DDPG的多UAV集結航路規劃算法，通過互惠速度障礙法指導各UAV在避障過程中的動作選擇以加快算法收斂速度。同時設計了一種基于引導和約束的綜合型獎勵函數，避免產生局部最優航路。

3.1 改進動作選擇策略

3.1.1 互惠速度障礙法的引入

假設UAV2突然探測到動態障礙Po( )xo,yo，如圖2所示。只要調整α2使v2偏離速度障礙錐VO，即可完成避障。

圖2 速度障礙法示意圖Fig.2 Schematic diagram of speed obstacle method

假設UAV2突然探測到友方UAV1，在UAV2避免碰撞過程中，考慮到UAV1也會進行機動，為了避免路徑發生抖動，設定UAV2在避障過程中承擔一半的避障任務，即將v2偏轉出互惠速度障礙錐RVO即可[18]。如圖3所示，互惠速度障礙錐RVO可由碰撞錐CC平移得到。

圖3 互惠速度障礙法示意圖Fig.3 Diagram of reciprocal speed obstacle method

3.1.2 改進動作選擇策略原理

當UAV突然探測到友方UAV或動態障礙時，改進動作選擇策略通過互惠速度障礙法和速度障礙法指導其對友方UAV和動態障礙進行避碰。首先UAV在探測范圍內獲取友方UAV或動態障礙的信息，然后根據碰撞錐判斷是否產生碰撞。如果在未來某個時間點發生碰撞，則根據互惠速度障礙法或速度障礙法計算需要避碰的航向角，進而計算此時需要調整的航向角速度范圍。如果在線actor網絡選擇的航向角速度在此范圍內，則給予獎勵，否則給予懲罰并重新選擇航向角。互惠速度障礙法指導流程圖如圖4所示。

圖4 改進動作選擇策略原理圖Fig.4 Schematic diagram of improved action selection strategy

3.2 改進獎勵函數

針對傳統DDPG算法獎勵函數設計不合理易產生局部最優解的問題，本文提出一種基于UAV綜合航行代價的獎勵函數設計方法，將多UAV綜合航行代價約束轉化為獎勵函數設計問題。根據UAV不同飛行狀態和各種代價約束賦予不同的獎勵值：

式中，ki(i=1,2,…,5)對應為相應獎勵r的權重，rtar、rl、robs、rt、rother分別為UAV到達集結點、航行距離、碰撞、時間協同、其他飛行狀態時的獎勵。分別為：

其中，α為UAV調整后的航向角，αRVO為互惠速度障礙法計算后需要調整的航向角。需要注意的是，rtar、rl、rt為每一回合結束后計算的獎勵，robs、rother為UAV每次選擇動作與環境進行交互后計算的獎勵。

3.3 RVO-DDPG算法偽代碼

使用RVO-DDPG算法對多UAV在不確定環境中的編隊集結任務進行訓練，算法偽代碼如下所示。

RVO-DDPG算法：

1.隨機初始化在線actor網絡Q(s,a|θQ)和在線critic網絡μ(s|θμ)的網絡參數θμ和θQ

2.初始化目標網絡μ′和θQ′及其權重，θμ′←θμ，θQ′←θQ

3.初始化經驗池

4.forepisode=1,max_episodedo

5.為行為探索初始化隨機噪聲ηt

6.收到初始觀測狀態s1

7.fort=1,Tdo

8. 各UAV根據式（14）選擇動作at

9. 根據動作at、互惠速度障礙法與環境進行交互

10. 產生獎勵值R，新的狀態st+1

11.將元組數據(st,at,rt,st+1)存放至經驗池中

12. 從經驗池中隨機采樣N個元組數據(st,at,rt,st+1)

13. 根據式（11）更新當前critic網絡

14. 根據式（10）更新當前actor網絡

15. 根據式（13）更新目標網絡

16.end for

17.end for

4 仿真分析

為驗證本文提出的RVO-DDPG算法在多UAV編隊集結路徑規劃問題的實用性和有效性，本文將以3架UAV從不同起始點出發集結生成V型編隊的路徑規劃為例進行仿真實驗。仿真軟件為Pycharm2020.1.3，采用Open AI的Gym建立訓練環境。

操作系統環境為Windows10 x64，使用軟件工具包版本為Python3.6、Torch1.70，硬件信息為Intel i7-9750H，DDR4 16 GB和1.86 TB SSD。算法仿真參數如表1所示。

表1 算法訓練參數設置Table 1 Algorithm training parameters setting

各UAV初始狀態與性能如表2所示。本文將UAV、障礙物的速度和環境距離同比例縮小，在實際應用的過程中將其按比例放大即可。

表2 各UAV初始狀態與性能參數Table 2 Initial state and performance parameters of each UAV

4.1 不確定復雜環境實驗仿真

為驗證RVO-DDPG算法的可行性，在不確定復雜環境中驗證和分析算法的有效性。不確定復雜環境包含多個靜態、動態障礙且障礙信息均未知，其參數如表3、表4所示；UAV初始位置為（100，100）、（250，118）、（550，80），集結點位置、航向為（370，550，90°）、（400，580，90°）、（430，550，90°）。

表3 動態障礙物參數Table 3 Dynamic obstacle parameters

表4 靜態障礙物參數Table 4 Static obstacle parameters

如圖5為3架UAV在不確定復雜環境中進行航路規劃的情況。從圖中可以看出，各UAV在未知環境中各障礙信息的情況下，能夠利用互惠速度障礙法調整自身航向角進行避障，還能夠得到平滑且安全的規劃航路。

圖6、圖7為各UAV在規劃航路中的航向角、航向角速度速度變化圖。由圖6可知，各UAV到達集結點時航向角速度一致，達到了預期的效果。從圖7中可以看出，各UAV的航向角速度變化范圍均在[-2（°）/s，2（°）/s]之間，能夠滿足UAV航向角的約束。結合圖5中平滑路徑可知，改進DDPG算法能夠為各UAV規劃出安全的集結航路。同時，其航路平滑、所需航向角速度變化范圍小的優點能夠更有利于UAV飛行。

圖5 UAV編隊協同集結路徑Fig.5 UAV formation collaborative assembly path

圖6 各UAV航向角變化Fig.6 Change in heading angle of each UAV

圖7 各UAV航向角速度變化Fig.7 Changes in heading angular velocity of each UAV

如表5為集結航路中各UAV與障礙的最小距離。當UAV在探測范圍內獲取到動態障礙運動信息并判斷可能發生碰撞后，通過速度障礙法快速調整其航向角進行避碰。由表5可知，航路中各UAV與動態障礙的最小距離均大于動態障礙的安全距離，說明UAV能夠安全避開動態障礙。同理，當UAV探測到靜態障礙的位置時，通過障礙錐判斷是否會發生碰撞，當可能發生碰撞時，UAV立刻調整其航向角進行避碰。同時，在航程獎勵函數的作用下，各UAV選擇最小機動方式調整航向角，即UAV與靜態障礙的距離稍大于靜態障礙安全距離。此時，得到的集結航程獎勵最高，航程代價最小。

表5 各UAV與障礙最小距離Table 5 Minimum distance between UAV and obstacle

如圖8為改進DDPG算法在訓練回合下的平均獎勵值變化情況。從圖8中不難發現，隨著訓練的不斷進行，RVO-DDPG算法給出的航路使得獎勵值不斷提高，最終趨于平穩，說明多UAV集結航路綜合代價獎勵值收斂到最優值，即多UAV集結航路綜合代價最小、規劃的航路最優。

圖8 獎勵值變化圖Fig.8 Change graph of reward value

4.2 對比仿真實驗

為驗證RVO-DDPG算法的實用性和有效性，將在3.1節環境下，分別采用改進DDPG算法和傳統DDPG算法以及合作粒子群（CPSO）算法[9]進行航路規劃實驗仿真，其仿真結果如圖9、圖10和表6所示。

圖9 傳統DDPG算法規劃航路Fig.9 Traditional DDPG algorithm for route planning

圖10 CPSO算法規劃航路Fig.10 CPSO algorithm for route planning

由表6可知，在3.1節環境下，采用RVO-DDPG算法對多UAV進行編隊集結航路規劃后，相比于DDPG算法和CPSO算法，航程代價減少了8.38%、3.12%，時間協同代價減少了47.65%、12.01%，綜合代價減少了23.15%、4.08%，航路規劃時間減少了13.89%、86.75%。由此分析可知，在相同條件下，RVO-DDPG算法在為多UAV集結規劃出合理、安全航路的同時，也能夠使航程代價、時間協同代價、綜合代價大大減少，提高了多UAV在不確定復雜環境下執行任務的效率，保證了多UAV在不確定復雜環境下的安全。

表6 三種算法的航路規劃數據Table 6 Route planning data of three algorithms

如圖11為3.1節環境中改進DDPG算法前后獎勵值對比圖，獎勵值越高，表示UAV能夠在當前狀態下選擇更優的航向角。從圖中可以看出，改進獎勵函數后DDPG算法獎勵收斂值明顯提升，這是因為將航路綜合代價設計為獎勵函數后，算法規劃的航路更優。同時，改進動作選擇策略后的DDPG算法獎勵值收斂速度明顯優于傳統DDPG算法，說明引入速度障礙法、互惠速度障礙法后的DDPG算法避障效率更高。

圖11 改進DDPG算法獎勵值對比Fig.11 Comparison of improved DDPG algorithm reward values

如表7為改進DDPG算法獎勵值收斂時的迭代次數。由表7可知，改進動作選擇策略的DDPG算法和RVO-DDPG算法在第3 654、4 352次迭代時開始收斂，相比于傳統DDPG算法在第6 528次開始收斂的迭代次數分別提高了44.03%、33.33%，說明改進動作選擇策略能夠提高算法的訓練效率，加快網絡的學習效率。同時，由收斂時的獎勵均值可以看出，改進獎勵函數的DDPG算法和RVO-DDPG算法的獎勵均值遠遠大于傳統DDPG算法，說明RVO-DDPG算法能夠使多UAV避免陷入局部最優航路，更能滿足不確定復雜環境下多UAV集結航路規劃的任務需求。

表7 改進DDPG算法收斂迭代次數Table 7 Improved DDPG algorithm convergence iteration times

5 結論

針對傳統智能算法難以處理不確定復雜環境下多UAV集結航路規劃的問題，本文將傳統DDPG算法與互惠速度障礙法相結合設計了RVO-DDPG算法。為提高傳統DDPG算法的收斂速度，采用互惠速度障礙法調整UAV航向，使多UAV成功躲避不確定復雜環境中的動態、靜態障礙物。設計了一種基于綜合代價約束的獎勵函數，將多UAV航路規劃中的多約束問題轉化為獎勵函數設計問題，使算法規劃出的集結航路綜合代價最小。最后通過仿真實驗驗證了該算法的實用性和有效性，并與傳統DDPG算法和CPSO算法進行對比用于驗證RVO-DDPG算法的先進性，實驗結果表明RVODDPG算法能夠快速為各UAV在不確定環境中規劃出安全有效的航路。