司鵬搏 吳 兵 楊睿哲 李 萌 孫艷華

(北京工業(yè)大學信息學部信息與通信工程學院 北京 100124)

0 引言

無人機(unmanned aerial vehicle,UAV)由于其體積小、成本低、環(huán)境適應力強等優(yōu)點,獲得了廣泛關注,已被應用在目標追蹤[1]、通信[2]、監(jiān)測[3]、農業(yè)[4]、災難管理[5]等方面。無人機在完成任務時,自主導航是實現(xiàn)對無人機控制的關鍵部分,因此,無人機路徑規(guī)劃是實現(xiàn)無人機自主飛行的重要因素。路徑規(guī)劃是確定無人機從起始點到目標點的路徑,其目的不僅在于尋找最佳和最短的路徑,而且還為無人機提供無碰撞的環(huán)境,并在運動動力學約束下優(yōu)化給定的成本函數[6]。

近年來,對無人機路徑規(guī)劃的研究越來越多。無人機飛行路徑規(guī)劃是一個復雜的優(yōu)化問題,需要考慮路徑長度、時間消耗、能量消耗、障礙規(guī)避、魯棒性等多個問題,文獻[7]提出一種基于多宇宙優(yōu)化器(multi-verse optimizer,MVO)的2D 無人機路徑規(guī)劃方案,將服務質量(quality of service,QoS)作為衡量路徑優(yōu)劣的指標,考慮多個無人機的協(xié)同工作與碰撞,同時也將最短路徑與最短時間作為約束條件。文獻[8]研究一種城市環(huán)境中無人機導航覆蓋路徑規(guī)劃算法,考慮障礙物環(huán)境下無人機無障礙最短路徑的路徑規(guī)劃,并探索不同障礙物形狀對路徑的影響。在實現(xiàn)無人機路徑規(guī)劃優(yōu)化問題的探索中,研究學者提出了很多無人機路徑規(guī)劃算法,如A*算法[9]、人工勢場[10]、線性規(guī)劃[11]、隨機樹[12]等算法,但是,當無人機路徑規(guī)劃具有多個約束條件時,這些方法中的大多數都具有較高的時間復雜度和局部極小陷阱[13],且如果在大范圍的環(huán)境下,計算壓力也會急劇增加。

為了解決這些問題,將深度強化學習(deep reinforcement learning,DRL)算法引入無人機路徑規(guī)劃研究中。深度強化學習是將具有感知能力的深度學習與具有決策能力的強化學習相結合,所形成的一種端對端的感知與控制系統(tǒng),使用函數擬合的方法對Q 表逼近,使其在高維環(huán)境下也有很好的效果,具有很強的通用性[14]。文獻[15]研究搜索和救援場景中的無人機導航,提出擴展雙深度Q 網絡(double deep Q-network,DDQN)算法用于基于無人機捕獲的圖像來提高無人機對環(huán)境的理解,大幅減少了每個任務期間處理的數據量。文獻[13]將環(huán)境建模為有障礙的三維環(huán)境,提出將強化學習算法與灰狼優(yōu)化算法(grey wolf optimizer,GWO)結合的算法,并將路徑規(guī)劃分為搜索、幾何調整和最佳調整三部分,解決局部優(yōu)化中陷入困局和無人機路徑規(guī)劃不平穩(wěn)的問題。文獻[16]提出了一種快速態(tài)勢評估模型,能夠將全球環(huán)境狀況轉換為順序的態(tài)勢圖,采用了決斗雙深度Q 網絡(dueling double deep Q-network,D3QN)算法,并將ε 貪心策略與啟發(fā)式搜索規(guī)則結合選擇動作,使用網格方法將動作劃分為8 個離散的值。文獻[17]用Q 學習算法,并將Q值基于表的近似和神經網絡(neural network,NN)近似進行對比,而對于無人機的動作值同樣需要離散化。以上深度強化學習算法的應用雖然都取得了良好的效果,但大多數算法都需要將動作空間離散化,這樣就限定了無人機只能在特定幾個方向進行轉角與飛行,而在實際中無人機的飛行方向需是全方位的,且由于需不斷躲避障礙物,其高度也不斷變化,此時,再將動作值離散化會大幅增加計算負擔。

本文研究復雜環(huán)境、連續(xù)空間狀態(tài)下,無人機無碰撞的路徑規(guī)劃問題。首先,建立一種復雜3D 場景模型,將無人機任務過程劃分為飛行、等待、通信3 個階段;其次,提出一種無人機高度避障方法,引入偏離度δ 表示無人機與障礙物及目標用戶的相對位置;最后,采用深度確定性策略梯度算法[18](deep deterministic policy gradient,DDPG)實現(xiàn)無人機路徑規(guī)劃,并與現(xiàn)有算法比較以驗證提出方法的有效性。

1 系統(tǒng)模型

假設在一定區(qū)域的城市空間中,分布著如手機、電腦等智能用戶,由于自然災害、距離等原因,用戶不能直接與基站通信,為保障災后救援,滿足用戶需求,使用體積小、對環(huán)境要求低的無人機作為中繼通信。無人機的飛行任務需滿足以下約束。

(1) 用戶(UEs)隨機分布,且UEs 之間互聯(lián)互通,每個UE 都能接收來自鄰近UEs 的消息。

(2) UAV 從結束收集UE 數據到結束收集下一個UE 數據為一個飛行任務。

(3) UAV 在一個任務中能量充足,不考慮由于能量耗盡導致任務終止。

如圖l 所示,包括1 個UAV 以及隨機分布的N個UEs 和M個障礙物OBs 。當UE 有數據傳輸請求時,會向全網廣播其位置信息。而位于UAV 通信范圍內的UE 則會將其獲得的具有數據傳輸請求的UE 位置信息傳遞給UAV 。UAV 獲得數據請求信息后,利用深度確定性算法規(guī)劃路徑、規(guī)避障礙,向目標UE 移動并為其提供服務。UAV 服務完畢后,若無新的UE 數據上傳請求,UAV 將懸停在此處,等待新的目標UE。實際情況中,UAV 由于體積小,搭載能量有限,UAV 需要在有限的能量限制下服務更多UE;同時,為滿足用戶的服務質量,需要在最短時間內完成飛行任務,并且避免與障礙物的碰撞。

圖1 無人機路徑規(guī)劃系統(tǒng)模型

2 無人機任務建模與分析

假設UAV 已完成UEs 中Pn-1的數據收集,正在等待或直接前往Pn收集數據,則無人機從Pn-1飛往Pn。

2.1 任務建模

2.1.1 飛行距離

t時刻UAV 到UE 的位移dUP為

則,UAV 飛行的最短距離dmin為

實際情況中,UAV 需躲避障礙,避免碰撞,UAV實際飛行距離dU滿足:dU≥dmin。

2.1.2 俯仰角α 與偏航角β

UAV 的速度v與z軸的夾角為俯仰角α;UAV與Pn投影在xoy平面,UAV 的速度v與x軸的夾角為偏航角β,則:

αt、βt分別為t時刻的俯仰角和偏航角。

UAV 在飛行中,α 與β 隨UAV 速度的變化而不斷變化,則α 與β 的變化有以下規(guī)律:

2.2 成本函數

2.2.1 障礙規(guī)避與目標抵達

UAV 在接收到Pn的位置信息后,在向Pn飛行的過程中,需要避開障礙,盡可能到達Pn上方接收數據,因此,引入偏離向量集Φ=,其中,輔助判斷UAV 與障礙物是否碰撞,其中:

對于UAV 懸停位置的判斷,引入目標偏離向量σP=(σPx,σPy),其中:

當UAV 到達目標UE 附近,為提高數據傳輸效率,則存在極小值?(0 ＜? ＜1),使得UAV 懸停位置滿足以下約束條件:

2.2.2 任務時間

UAV 完成一個任務過程所需時間包括3 部分:飛行時間Tf、等待時間Tw、通信時間Tcom。

飛行時間Tf:UAV 從Pn-1出發(fā)至到達Pn耗費的時間,當UAV 以最大速度飛行最小距離時,耗費最短飛行時間為

UAV 在飛行中,為躲避障礙,需不斷改變飛行方向及飛行高度,則飛行時間Tf滿足:

等待時間Tw: UAV 等待下一個具有數據傳輸請求UE 出現(xiàn)的時間。

通信時間Tcom:UE 將數據傳輸到UAV 耗費的時間,在該過程中,數據接收率為R,則傳輸Dn數據量耗時為

綜上,UAV 完成從Pn-1到Pn的數據收集任務耗費的總時間為

2.2.3 能量消耗

在一個數據收集過程中,耗能分為3 種,分別為飛行、等待、通信,各階段耗能情況如下。

飛行能耗:每時隙耗能ef,耗時Tf,則總耗能為

等待能耗:UAV 懸停在UE 上方每時隙耗能ew,耗時Tw,則懸?？偤哪転?/p>

通信能耗:每時隙耗能ecom,耗時Tcom,則通信總耗能為

綜上,UAV 在一個任務中總耗能為

3 基于DDPG 的無人機路徑規(guī)劃

3.1 深度確定性策略梯度算法

深度確定性策略梯度算法適用于連續(xù)動作空間,包括Actor 網絡和Critic 網絡兩部分,二者利用深度神經網絡分別實現(xiàn)對策略和Q函數的逼近[20-21]。DDPG 的訓練過程如下。

(1) Actor 網絡在狀態(tài)st下給出動作at=π(st),為了增加樣本的隨機性,會對Actor 網絡給出的動作at=π(st) 增加一個隨機噪聲(使用Uhlenbeck-Ornstein 隨機過程,作為引入的隨機噪聲)A,即行為動作φt=π(st)+A。

(2)動作φt作用于環(huán)境,DDPG 得到獎賞rt和下一個狀態(tài)st+1,DDPG 將集合(st,φt,rt,st+1) 存儲到經驗緩沖區(qū)H。

(3)DDPG 從經驗緩沖區(qū)隨機選取大小為K的小批量數據集作為Actor 網絡和Critic 網絡的輸入。

(4)在Critic 網絡,目標Critic 網絡利用式(20)根據小批量數據集計算累計獎賞更新:

在線Critic 網絡利用動作φt逼近目標Q值Qw(st,φt),并使用最小化損失函數式(21)進行在線Critic 網絡的更新。

其中,ω 為在線Critic 網絡的參數,ω' 為目標Critic網絡的參數,πθ'(st+1) 為目標Actor 網絡根據小批量數據集得出的下一狀態(tài)的動作。

(5)在Actor 網絡中,使用式(22):

對網絡進行更新,其中,θ 為在線Actor 網絡的參數,θ'為目標Actor 網絡的參數。

(6)通過步驟(4)、(5)分別對在線Critic 網絡及Actor 網絡參數更新,而目標網絡的參數以一定的頻率從在線網絡復制更新,更新規(guī)則分別為式(23a)與(23b)。

3.2 基于DDPG 的無人機路徑規(guī)劃設計

本文針對連續(xù)空間內無人機路徑規(guī)劃,將適用于連續(xù)空間問題的DDPG 算法引入,以尋求滿足優(yōu)化目標的最優(yōu)路徑。

動作空間:t時刻分別在x軸、y軸、z軸方向的加速度,則t時刻的動作值為

獎賞:合理的獎賞設置能夠更加快速地訓練出最優(yōu)的策略。為使UAV 用最短時間、最小能量消耗到達目的點,同時避開障礙,以及更加接近目的點,則將獎賞劃分以下幾個部分。

障礙物獎賞robs:如果UAV 與障礙物的位置關系滿足式(7)、(8)、(9),則robs=0,否則robs=,并且結束游戲。

路徑獎賞rTE: 主要包括對路徑中的時間及能耗的衡量。

目的點獎賞rdes:衡量UAV 是否到達目的點完成任務,rdes=。

區(qū)域獎賞rb: 將UAV 限定在一定區(qū)域內,當UAV 飛出該區(qū)域,rb=。

綜上,則t時刻總獎賞為式(24)。

則基于DDPG 無人機路徑規(guī)劃算法(deep deterministic policy gradient algorithm UAV path planning,DDPG-UPP)具體內容如算法1 所示。

4 仿真分析

本部分將通過仿真評估算法DDPG-UPP 的性能,仿真環(huán)境使用Python 3.6、TensorFlow 1.12。本實驗將模擬500 m×500 m×500 m 區(qū)域內無人機使用DDPG-UPP 算法從起點到目標點的路徑規(guī)劃情況,其中障礙物隨機分布在該區(qū)域內。本文測試DDPG-UPP 算法的性能通過不同學習率性能比較、不同算法及不同維度路徑規(guī)劃的性能比較,從而獲得最優(yōu)學習率并驗證DDPG-UPP 算法的最優(yōu)性。仿真使用的各參數設置如表1 所示。

表1 仿真參數

算法1[22]采用演員評論家(Actor-Critic,AC)算法,并融合指針網絡(pointer network-A*,Ptr-A*)進行無人機路徑規(guī)劃探索,將Ptr-A*的參數在小規(guī)模聚類問題實例上進行訓練,以便在Actor-Critic 算法中進行更快的訓練。

算法2[16]采用決斗雙深度Q 網絡D3QN 算法,同時使用ε-greedy 策略與啟發(fā)式搜索結合選擇動作,實現(xiàn)離散環(huán)境下無人機自主路徑規(guī)劃。

算法3 采用了策略梯度(policy gradient,PG),將策略表示為連續(xù)函數,并用梯度上升等連續(xù)函數優(yōu)化方法尋找最優(yōu)策略,有效彌補了基于值函數算法(DQN 等)適用場景的不足。

圖2、圖3 分別為在二維與三維環(huán)境下對無人機路徑規(guī)劃的效果采樣圖。圖3 對三維環(huán)境無人機路徑規(guī)劃仿真實驗中設置無人機與目標點的閾值為20,即當無人機在以目標點為中心、20 為半徑的球形區(qū)域內時,可認為無人機到達目標位置。通過對比,在將環(huán)境從二維拓展到三維并不斷增加障礙物數量的過程中,使用本文算法訓練的無人機都能準確到達目標點,同時精準避開障礙物。

圖2 二維場景路徑仿真圖

圖3 三維場景路徑仿真圖

圖4 展示了算法DDPG-UPP 在不同學習率下的性能評估。學習率決定著目標函數能否收斂到局部最小值以及何時收斂到最小值,合適的學習率能夠使目標函數在合適的時間內收斂到局部最小值。從圖4 可以看出,當Actor 網絡學習率為0.005、0.001,Critic 網絡學習率為0.01、0.002 時,隨著訓練次數的增多,UAV 在不斷試錯過程中獲得的獎賞會逐漸穩(wěn)定,這表明UAV 學會到達目標點并滿足約束條件的最優(yōu)路徑。同時,如圖5 所示,UAV 到達相同的目標點所需要的步數也逐漸減小,并穩(wěn)定到固定值,UAV 隨著學習次數的增多,能夠更加準確地到達目標點。而對于Actor 網絡學習率為0.0005、0.0001,Critic 網絡學習率為0.001、0.0002 時,獎賞值及到達相同目標所需的步數雖然也收斂到定值,但相較于a=0.005、c=0.01 與a=0.001、c=0.002 的學習率,此時算法的性能并未達到最優(yōu),無人機學習到的路徑并不是最優(yōu)路徑。另外,當學習率為Actor=0.01、Critic=0.02 時,算法不收斂,無人機并不能學會到達目標的最優(yōu)路徑。因此,學習率的大小對算法DDPG-UPP 的性能至關重要,能指導UAV 在合適的時間找到最優(yōu)路徑。

圖4 不同學習率下算法DDPG-UPP 的性能對比圖(Reward)

圖5 不同學習率下算法DDPG-UPP 的性能對比圖(Step)

圖6、圖7 分別為不同算法下無人機路徑規(guī)劃獎賞以及到達相同目標所需步數的對比圖。將本文提出的DDPG-UPP 算法與算法1、算法2、算法3 的性能比較,如圖6 所示,DDPG-UPP 算法用于UAV路徑規(guī)劃相較于算法1、算法2、算法3 收斂較快且獲得的獎賞值也明顯高于其他3 種算法,表明使用DDPG-UPP 算法獲得的路徑在能耗及時間都是最少的。這是因為算法2、算法3 適用于離散動作空間,UAV 在進行訓練前需將動作空間離散化,而對于UAV 路徑規(guī)劃的動作空間,要想實現(xiàn)UAV 更加自主、高效動作,其離散動作空間復雜化,且在每一次訓練中,無人機只能在特定的幾個方向中選擇,大幅降低了無人機的靈活性;其次,對于算法1,雖然Actor-Critic 算法可用于連續(xù)動作空間,但由于Actor 的行為取決于Critic 的值,Critic 難收斂導致Actor-Critic 算法很難收斂,盡管算法1 融入了指針網絡Ptr-A*以加快Actor-Critic 算法的收斂,但相較于本文算法仍有很大差距。本文算法也采用Actor-Critic結構,但融入了深度Q 網絡(deep Q-network,DQN)的優(yōu)勢,既解決了算法2 的空間離散問題,又區(qū)別于算法1、算法3 中Actor的概率分布輸出,而是以確定性的策略輸出加快了算法的收斂。因此,如圖6、圖7 所示,本文算法不僅能夠使UAV 更快獲得到達目標的最優(yōu)路徑,而且使得無人機能耗及時間都是最小的,同時能在到達相同目標時使用更少步數。

圖6 不同算法下無人機路徑規(guī)劃性能對比圖(Reward)

圖7 不同算法下無人機路徑規(guī)劃性能對比圖(Step)

圖8 為二維環(huán)境與三維環(huán)境下分別使用DDPGUPP 算法與算法2 的性能對比圖。首先,圖8 顯示無論是二維環(huán)境還是三維環(huán)境,使用DDPG-UPP 算法的性能都要優(yōu)于使用算法2。這是由于算法2 雖然改變了DQN 的模型結構,但仍需將動作空間離散化,而針對本文無人機飛行環(huán)境,則至少需要將動作空間離散為6 個維度,在每一次試錯中,相較于本文算法,算法2 都增加了試錯成本,同時也增加了計算復雜度,從而增加了無人機探索最佳路徑的難度;其次,DDPG-UPP 算法在無障礙環(huán)境中的獎賞值要高于有障礙環(huán)境,且較有障礙環(huán)境更快收斂,這是因為環(huán)境中的障礙會在一定程度上阻礙無人機的探索,無人機需進行更多次嘗試才能學習到最優(yōu)路徑;此外,對于本文算法,在同時考慮障礙物的環(huán)境下,在三維環(huán)境中的性能也要明顯優(yōu)于二維環(huán)境。綜上,本文算法在三維環(huán)境避障路徑選擇中相較于其他算法具有更優(yōu)的性能。

圖8 不同維度下無人機路徑規(guī)劃性能對比圖(2D 與3D)

5 結論

本文研究了一種三維復雜環(huán)境下無人機路徑規(guī)劃方法,提出一種無人機高度避障方法,引入偏度δ表示無人機與障礙物及目標用戶的相對位置,使UAV 能夠更加自主、靈活地避開障礙,更加適應UAV 實際工作環(huán)境。另外,考慮UAV 動作空間的連續(xù)性,采用深度確定性策略梯度算法進行無人機路徑規(guī)劃。實驗結果表明,本文算法能夠克服傳統(tǒng)算法需將動作離散化的弊端,增加了環(huán)境適應性。