基于強(qiáng)化學(xué)習(xí)的多無人機(jī)WRSN充電路徑規(guī)劃方案

王 楊,單天樂,李迎春,趙傳信,陳 鵬,鄒榮譽(yù)

1(安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院,安徽 蕪湖 241002)

2(安徽建筑大學(xué) 智能建筑與建筑節(jié)能安徽省重點(diǎn)實(shí)驗(yàn)室,合肥 230022)

3(東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,南京 211189)

1 引 言

無線傳感器網(wǎng)絡(luò)通常是由一組無線傳感器節(jié)點(diǎn)構(gòu)造而成,傳感器節(jié)點(diǎn)會定期地從環(huán)境中收集信息,并通過數(shù)據(jù)匯聚等一些協(xié)議將數(shù)據(jù)傳送給基站.傳統(tǒng)無線傳感網(wǎng)的節(jié)點(diǎn)內(nèi)僅含一個(gè)能量有限的電池,為其工作提供能量,工作一定時(shí)間后節(jié)點(diǎn)的電量會用盡.小規(guī)模的無線傳感器網(wǎng)絡(luò)還能定期為節(jié)點(diǎn)更換電池來延長整個(gè)網(wǎng)絡(luò)的壽命.但隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大,為網(wǎng)絡(luò)中的所有節(jié)點(diǎn)定期地更換電池變得越來越困難,有限的單個(gè)傳感器電池能量最終會導(dǎo)致整個(gè)網(wǎng)絡(luò)壽命的有限問題.為了解決無線傳感網(wǎng)中的能量問題,國內(nèi)外研究員進(jìn)行了大量研究,其中最主要的方法有3種,分別是節(jié)點(diǎn)自我節(jié)能方式、自然能量獲取方式和無線充電方式.

節(jié)能方式主要通過對數(shù)據(jù)包壓縮傳輸、對網(wǎng)絡(luò)進(jìn)行聚類與選擇動態(tài)簇頭來降低傳感器節(jié)點(diǎn)單位時(shí)間內(nèi)的能耗.自然能量采集方式需要使用傳感器上的能量轉(zhuǎn)換器,通過該模塊從自然環(huán)境中收集能量(如太陽能、風(fēng)能等)以延長其壽命.但從自然環(huán)境中收集能源會帶來能量來源的不穩(wěn)定性(如晝夜影響、風(fēng)力強(qiáng)弱),能量轉(zhuǎn)換效率不高.無線充電方式是給網(wǎng)絡(luò)配備無線充電源(如充電站、充電車等).充電車沿著預(yù)先設(shè)定的路徑,在行駛的過程中WRSN中的各個(gè)節(jié)點(diǎn)進(jìn)行充電.如今,利用無線充電為傳感器節(jié)點(diǎn)或物聯(lián)網(wǎng)設(shè)備充電的方法已廣泛應(yīng)用于WRSN[1].

現(xiàn)有的無線充電技術(shù)主要基于3大原理:1) 電磁感應(yīng)技術(shù)[2],生活中很多設(shè)備都利用這一技術(shù)實(shí)現(xiàn)無線充電,例如手機(jī)、電動汽車等,它具有技術(shù)成熟且簡單、一對一式充電[3-5]、效率較低等特點(diǎn);2) 磁耦合諧振技術(shù)[6],相比電磁感應(yīng)充電技術(shù),它支持更大的空間范圍內(nèi)的能量傳輸,具有可以一對多式充電[7,8]、距離較短(10米左右)等特點(diǎn);3) 無線電波技術(shù)[9],它的充電范圍更廣(幾十公里),其具有技術(shù)要求較高、安全性不夠高等特點(diǎn).本文采用的是磁耦合諧振技術(shù)對網(wǎng)絡(luò)進(jìn)行充電,可以滿足中小范圍無線充電的要求.

對無線充電而言,小規(guī)模的無線可充電傳感網(wǎng)只需要單小車或單無人機(jī)為網(wǎng)絡(luò)充電,而在大規(guī)模的無線可充電傳感網(wǎng)中,因環(huán)境復(fù)雜、面積廣闊且單輛供電工具能量有限等原因,單小車或單無人機(jī)無法滿足供電需求,必須要多無人機(jī)協(xié)作才可以完成充電任務(wù).但是多余的無人機(jī)勢必會造成資源的浪費(fèi),這就要求在盡可能減少無人機(jī)個(gè)數(shù)的同時(shí)優(yōu)化多無人機(jī)的充電路徑.文獻(xiàn)[10]研究了將戶外山地場景中無人機(jī)群的路線設(shè)計(jì)問題建模成一個(gè)多旅行商問題,并提出了一種基于部分搜索方法的多無人機(jī)飛行路徑改進(jìn)算法,并且提出一個(gè)山火現(xiàn)場巡邏的具體例子,其采用了配有攝像頭的無人機(jī).這個(gè)例子雖然沒有地對空的通信鏈路,但是對于大型無人機(jī)群的飛行路徑規(guī)劃研究有一定的貢獻(xiàn).文獻(xiàn)[11]研究了怎樣規(guī)劃好多架無人機(jī)的運(yùn)動路徑,以便盡早完成群體感知相關(guān)的任務(wù).此文提出的基于雙向全變鄰域的搜索算法對于TSP問題的研究也具有非常重要的參考價(jià)值.

而文獻(xiàn)[12]又將無人機(jī)飛行軌跡問題的緯度提升至三維,文獻(xiàn)[13]所做工作的目的是將全部待充電傳感器節(jié)點(diǎn)的總接收能量最大化,以此來研究無線能量傳輸WRSN網(wǎng)絡(luò)中的無人機(jī)飛行路徑規(guī)劃方案.

現(xiàn)有研究中,全局路徑規(guī)劃的方法比較常用,如圖搜索法、RTT算法和人工勢場法等[14].但是由于全局路徑規(guī)劃方法都需要建立完整的模型,如果是復(fù)雜的環(huán)境計(jì)算開銷則會很大;現(xiàn)實(shí)情況下,無人機(jī)在復(fù)雜多變的環(huán)境中掌握全局信息十分困難,想要采用確定性的方案來實(shí)現(xiàn)最優(yōu)路徑規(guī)劃是不太可能的.由于近期人工智能[15]的發(fā)展,出現(xiàn)了許多基于人工智能的路徑規(guī)劃方法,其中比較典型的方法有神經(jīng)網(wǎng)絡(luò)方法、模糊邏輯方法[16]等,這些方法具有一定程度的智能性,在面對不同的場景時(shí),不論環(huán)境是否動態(tài)變化都有著出色的性能表現(xiàn),并且具有很強(qiáng)的泛化能力.

由于機(jī)器學(xué)習(xí)技術(shù)的快速發(fā)展,人們嘗試使用深度學(xué)習(xí)(Deep Learning,DL)與強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)方法來對路徑規(guī)劃等相關(guān)問題進(jìn)行解決[17].其中最為典型的是采用馬爾科夫決策模型的Q-Learning算法[18],它是一種監(jiān)督式的學(xué)習(xí)方法,可以通過學(xué)習(xí)并根據(jù)環(huán)境的變化為無人機(jī)規(guī)劃出一條更好的無碰撞路徑.許多現(xiàn)有的RL方法只關(guān)注單個(gè)無人機(jī)場景.文獻(xiàn)[19]中提出,在單個(gè)無人機(jī)基站服務(wù)的相關(guān)場景中使用RL與基于Q值表的Q學(xué)習(xí)相比更具優(yōu)勢,它不以長時(shí)間訓(xùn)練為代價(jià),且不對環(huán)境做出任何假設(shè).在文獻(xiàn)[20]中,作者只研究了基于表的無人機(jī)數(shù)據(jù)收集的Q學(xué)習(xí),解決了特定類別物聯(lián)網(wǎng)中的數(shù)據(jù)采集.文獻(xiàn)[21]中研究了為地面用戶服務(wù)的多無人機(jī)路徑規(guī)劃,采用基于表的Q學(xué)習(xí)算法,基于相對復(fù)雜的3步算法,包括使用遺傳算法對用戶進(jìn)行分組,然后在兩個(gè)獨(dú)立的實(shí)例中進(jìn)行部署和設(shè)計(jì)Q學(xué)習(xí)算法,證明了所研究的優(yōu)化問題為NP-hard,認(rèn)為Q學(xué)習(xí)是解決此類問題的有力工具.

針對現(xiàn)有研究沒有很好地解決多無人機(jī)飛行中存在的多約束和時(shí)空協(xié)同等帶來的問題,提出了基于強(qiáng)化學(xué)習(xí)的多無人機(jī)協(xié)同無線可充電傳感網(wǎng)充電路徑規(guī)劃方案(MC-CPP,Multi-UAV Collaborative Charging Path Planning),把多無人機(jī)充電路徑規(guī)劃問題的網(wǎng)絡(luò)模型映射到深度強(qiáng)化學(xué)習(xí)MDP中,解決了WRSN中多無人機(jī)充電路徑的設(shè)計(jì)問題.本方案首先利用Voronoi法將WRSN中的傳感器節(jié)點(diǎn)劃分至若干個(gè)充電單元中,由此可選擇合適的充電位置從而有助于無人機(jī)對其進(jìn)行一對多或一對一式充電;然后設(shè)計(jì)獎勵(lì)函數(shù)機(jī)制,將問題轉(zhuǎn)化為獎勵(lì)最大化問題并采用改進(jìn)的Q-learning對無人機(jī)進(jìn)行路徑規(guī)劃;最后采取改進(jìn)方法(如神經(jīng)網(wǎng)絡(luò)法、貪婪策略法等)使得路徑分配更為智能和高效.最終得到一個(gè)多無人機(jī)無線可充電傳感網(wǎng)充電的路徑規(guī)劃方案,仿真結(jié)果表明了該充電方案的有效性與優(yōu)越性.

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)系統(tǒng)模型

本網(wǎng)絡(luò)模型為一部署在三維空間內(nèi)的多無人機(jī)輔助的無線可充電系統(tǒng)模型,u個(gè)無人機(jī)U={U1,U2,…,Uu}被安排向網(wǎng)絡(luò)中n個(gè)物聯(lián)網(wǎng)設(shè)備節(jié)點(diǎn)N={N1,N2,…,Nn}提供充電服務(wù),網(wǎng)絡(luò)中物聯(lián)網(wǎng)設(shè)備節(jié)點(diǎn)Ni的坐標(biāo)是(Xi,Yi),無人機(jī)群從基站S=N0(設(shè)置在網(wǎng)絡(luò)中心處)出發(fā)后以一定的飛行高度H和飛行速度v沿著規(guī)劃路徑給網(wǎng)絡(luò)中的各待充電節(jié)點(diǎn)充能,最終返回基站.路徑規(guī)劃系統(tǒng)模型如圖1所示.

圖1 多無人機(jī)路徑規(guī)劃系統(tǒng)模型Fig.1 Multi UAV path planning system model

2.2 能量消耗模型

無人機(jī)的飛行功率與懸停功率[22]可分別表示為Pmov=Pprove,Phov=Ppro(vt=0)=P0+Pi,其中P0和Pi是常數(shù),P0代表UAV葉片輪廓功率,Pi代表UAV懸停時(shí)的感應(yīng)功率;Ppro是無人機(jī)的推進(jìn)功率;ve是飛行狀態(tài)下的平均轉(zhuǎn)子感應(yīng)速度;vt為無人機(jī)飛行速度.

2.3 無線能量傳輸模型

節(jié)點(diǎn)Si的能量接受功率Prec可以表示為:Prec=ηPtrahi,jt,這里0≤η≤1表示無線射頻能量傳輸?shù)男?無線充電中能量接收和充電時(shí)間關(guān)系如圖2所示.

圖2 接收能量和充電時(shí)間關(guān)系Fig.2 Relationship between received energy and charging time

2.4 碰撞避免策略

多無人機(jī)存在判斷碰撞及碰撞避免的問題:很多情況下,計(jì)算得到的路徑會有交點(diǎn).路徑相交并不代表無人機(jī)會產(chǎn)生碰撞,只有當(dāng)無人機(jī)同時(shí)到達(dá)一個(gè)交點(diǎn)時(shí)才會碰撞.當(dāng)兩架無人機(jī)一起向同一交點(diǎn)飛行時(shí),如果它們之間的距離小于ds,那么兩者的安全圓就會相交.滿足:

mini,k=1,…,n,j≠k[dik(j)]≥ds,j=1,2…m-1

(1)

時(shí),多無人機(jī)可以避免碰撞,其中ds為安全距離,dik(j)為第j個(gè)等分點(diǎn)時(shí),第i個(gè)UAV與第k個(gè)UAV之間的距離,表示為:

(2)

2.5 多無人機(jī)協(xié)同路徑規(guī)劃

Step 1.用Voronoi圖法進(jìn)行環(huán)境建模,選取合適的出發(fā)點(diǎn),并綜合考慮路徑長度、節(jié)點(diǎn)能量等因素對網(wǎng)絡(luò)使用深度強(qiáng)化學(xué)習(xí)獎懲函數(shù)法求解最優(yōu)路徑;

Step 2.采用神經(jīng)網(wǎng)絡(luò)方法對結(jié)果優(yōu)化,為每架無人機(jī)規(guī)劃出一條滿足時(shí)空協(xié)同約束條件的可飛行路徑;

Step 3.判斷每個(gè)無人機(jī)飛行路徑是否能夠滿足安全性約束條件,避免與其他無人機(jī)發(fā)生碰撞;

Step 4.如果所得路徑滿足不了要求,可以令任務(wù)時(shí)間短的無人機(jī)停止等待另一架通過后通行或者改變可能沖突的無人機(jī)對節(jié)點(diǎn)的充電順序.

多無人機(jī)充電路徑規(guī)劃流程圖如圖3所示.

圖3 充電流程圖Fig.3 Charging flow chart

其中Voronoi圖法用于選取充電停止點(diǎn),其具體方法如圖4所示.

圖4 Fig.4

Case 1.如圖4(a)所示:3個(gè)及多個(gè)節(jié)點(diǎn)的Voronoi交點(diǎn)處,當(dāng)節(jié)點(diǎn)在UAV最大可充電范圍內(nèi);

Case 2.如圖4(b)所示:兩個(gè)節(jié)點(diǎn)的垂直平分線上距離兩節(jié)點(diǎn)最近的點(diǎn),當(dāng)節(jié)點(diǎn)在UAV最大可充電范圍內(nèi);

Case 3.如圖4(c)所示:當(dāng)其它節(jié)點(diǎn)都不在UAV最大可充電范圍內(nèi),這時(shí)要單獨(dú)給此節(jié)點(diǎn)充電.

3 狀態(tài)獎勵(lì)函數(shù)

在無線可充電傳感網(wǎng)中,UAV在自身能量滿足充電需求的情況下既要給分配的節(jié)點(diǎn)進(jìn)行充電,又要盡快完成全部充電任務(wù)并且返回基地.所以本文所設(shè)計(jì)的狀態(tài)獎勵(lì)函數(shù)為兩個(gè)部分構(gòu)成,一個(gè)是充電項(xiàng),另一個(gè)是目標(biāo)引導(dǎo)項(xiàng),充電項(xiàng)負(fù)責(zé)提示UAV為每個(gè)節(jié)點(diǎn)充電,目標(biāo)引導(dǎo)項(xiàng)的目的是使UAV能夠選擇快捷的路徑到達(dá)目的地.

3.1 充電項(xiàng)設(shè)計(jì)

本文依據(jù)標(biāo)準(zhǔn)正態(tài)分布建模充電項(xiàng),用Ep表示節(jié)點(diǎn)消耗能量.Ep越小說明需求越小,會得到更大的懲罰獎勵(lì)值.充電項(xiàng)采用函數(shù)f(Ep)來表示,如公式(3)所示:

(3)

另外,由于一個(gè)充電周期內(nèi)同一節(jié)點(diǎn)只需完成一次充電,可以設(shè)置已完成充電的節(jié)點(diǎn)懲罰函數(shù)值無窮大.

3.2 碰撞避免項(xiàng)設(shè)計(jì)

當(dāng)多無人機(jī)發(fā)生碰撞時(shí),將獲得負(fù)獎勵(lì).當(dāng)兩個(gè)安全圓相互碰撞時(shí),稱之為偽碰撞.類似地,當(dāng)UAV與每個(gè)其他單位重疊,稱之為真正的碰撞.訓(xùn)練中,可以通過懲罰偽碰撞來減少實(shí)際碰撞的次數(shù).碰撞避免項(xiàng)用函數(shù)f(Cp)表示,如公式(4)所示:

(4)

3.3 目標(biāo)引導(dǎo)項(xiàng)設(shè)計(jì)

為了讓UAV既能給目標(biāo)節(jié)點(diǎn)充電又能快速靠近目標(biāo)地T,用Dus1表示UAV與下一待充電節(jié)點(diǎn)的距離(km),用Dus2表示UAV與下下個(gè)待充電節(jié)點(diǎn)的距離,目標(biāo)引導(dǎo)項(xiàng)如公式(5)所示:

(5)

α叫做間隔,是一個(gè)超參數(shù),它的值取決于所處環(huán)境與實(shí)驗(yàn)的要求.經(jīng)數(shù)次實(shí)驗(yàn)得到一個(gè)合適的α值為0.0475.

將充電項(xiàng)、碰撞避免項(xiàng)和目標(biāo)引導(dǎo)項(xiàng)結(jié)合起來,得到一個(gè)狀態(tài)獎勵(lì)函數(shù),其符合本文模型,如公式(6)所示:

Rstate(Dus1,Dus2)=fcharge(Ep)+fcollision(Cp)+
ftriplet(Dus1,Dus2)

(6)

4 Q-Learning算法

Q-Learning算法是一動態(tài)規(guī)劃的強(qiáng)化學(xué)習(xí)算法,Q是指在某一時(shí)刻的某一狀態(tài)下智能體(agent)采取某一動作所期望能夠得到的獎勵(lì)或懲罰.環(huán)境會根據(jù)agent的動作反饋相應(yīng)的回報(bào),因此Q-Learning算法的核心就是搜索并綜合所有可能的狀態(tài)與選擇的動作構(gòu)建出一張Q值表,然后根據(jù)Q值來選取可以獲得最大收益的動作.Q-Learning算法同時(shí)為馬爾科夫決策過程MDP(Markov Decision Process)的另一種表達(dá),其整體框架如圖5所示.

圖5 Q-Learning算法框圖Fig.5 Q-learning algorithm block diagram

本方案的第一步是把UAV充電路徑規(guī)劃問題用數(shù)組{S、A、R、P}建模為MDP,數(shù)組中的S是UAV的所處狀態(tài)空間,A為其動作空間,R為獎勵(lì)回報(bào)值(由狀態(tài)獎勵(lì)函數(shù)給出),P代表狀態(tài)轉(zhuǎn)移的概率.例如,系統(tǒng)在時(shí)間t選擇了動作at并飛至下一待充電節(jié)點(diǎn),環(huán)境信息由狀態(tài)st轉(zhuǎn)移至st+1,環(huán)境狀態(tài)st以如下概率轉(zhuǎn)移至st+1:

P[s=st+1|st,at]=P[st,at,st+1]

(7)

策略的集合由π表示,π(a|s)表示在某一狀態(tài)s所采取下一步可能發(fā)生的動作a的概率.

π(a|s)=P(At=a|st=s)

(8)

在策略π的作用下,累計(jì)獎賞值函數(shù)為:

Vπ(st)=Rst(a)+γ∑st+1P[st,at,st+1]Vπ(st+1)

(9)

式(9)中,Rst(a)表示當(dāng)前狀態(tài)下采取行動a可以立即獲得的獎勵(lì)回報(bào),Y∈[0,1]為衰減系數(shù),代表著下一步的回報(bào)對于當(dāng)前狀態(tài)回報(bào)的影響系數(shù).本算法的目的是找出狀態(tài)空間中最優(yōu)的解π*,可以讓每一st狀態(tài)的值都可以達(dá)到最優(yōu),如公式(10)所示:

π*=argmaxVπ(s),(?s)

(10)

式(10)是指所得最優(yōu)解π*可以令值函數(shù)Vπ(s)取到其可能取得的最大值.

設(shè)計(jì)動作值的Q函數(shù)如下:

(11)

其中,Q*(s,a)為在狀態(tài)s時(shí)采取動作a后所得的最佳獎勵(lì)值之和.目前的狀態(tài)s和目前動作a,在這之后會采取策略π,狀態(tài)s將以概率P(s,a,st)變化至下一可能狀態(tài)st+1,可以得到Q算法的基本形式如公式(12)所示:

Q*(s,a)=R(s,a)+γ∑P(s,a,st)maxQ*(st,at)

(12)

根據(jù)式(12)可得:

π*=argmaxQ*(s,a),(?s)

(13)

Learning的算法大致流程如下:UAV在狀態(tài)s時(shí)首先在所有可能采取的動作中選擇a動作,然后根據(jù)執(zhí)行了動作a到達(dá)下一節(jié)點(diǎn)后所獲立即獎勵(lì)以及接受了當(dāng)前狀態(tài)動作值的估計(jì)來評價(jià)動作a的好壞與對總獎賞值的影響程度.通過重復(fù)所有狀態(tài)下的所有動作,UAV便可通過判斷長期折扣回報(bào)來學(xué)習(xí)總體上的最佳行為,即節(jié)點(diǎn)充電順序及路徑規(guī)劃.Q函數(shù)的值會不斷迭代最終收斂至最優(yōu),表示為:

Q(s,a)←Q(s,a)+α[r+γmaxQπ(s′,a′)-Q(s,a)]

(14)

其中α為學(xué)習(xí)率;Q(s,a)表示在狀態(tài)s處采取動作a時(shí)獲得的總估值函數(shù),r代表“眼前利益”,即當(dāng)前狀態(tài)s下采取動作a后到達(dá)下一節(jié)點(diǎn)可以得到的收益.

在滿足了一定條件的情況下,隨機(jī)給定的狀態(tài)s以及動作a,在第k次(k趨近∞)時(shí)更新迭代的值函數(shù)終將收斂于函數(shù)Q(s,a).

通過多次強(qiáng)化學(xué)習(xí)的訓(xùn)練,系統(tǒng)能夠得到在確定的充電地點(diǎn)下應(yīng)該選擇哪一節(jié)點(diǎn)作為下一待充電地點(diǎn),從而獲得節(jié)點(diǎn)充電順序并由此構(gòu)成UAV最優(yōu)的充電軌跡,UAV采用這條路徑對節(jié)點(diǎn)充電可以將獲得的累計(jì)獎勵(lì)最大化.基于狀態(tài)獎勵(lì)函數(shù)的無人機(jī)路徑規(guī)劃方法如表1所示.

表1 基于狀態(tài)獎勵(lì)函數(shù)的無人機(jī)路徑規(guī)劃方法Table 1 UAV path planning method based on state reward function

5 基于改進(jìn)Q學(xué)習(xí)的路徑規(guī)劃

5.1 Q值近似

多無人機(jī)采用Q-Learning算法來訓(xùn)練并更新策略,標(biāo)準(zhǔn)的Q學(xué)習(xí)算法通常利用Q值表存儲不同狀態(tài)時(shí)選擇不同動作分別反饋的Q值,但是由于狀態(tài)空間與動作空間的不斷擴(kuò)大會致使儲存Q值所占內(nèi)存空間指數(shù)形增加.為避免此問題出現(xiàn),一般采取神經(jīng)網(wǎng)絡(luò)來近似地預(yù)測不同狀態(tài)組合下的Q值,從而把Q值表更新與保存轉(zhuǎn)化為函數(shù)的擬合問題,從而解決因儲存Q值表所造成的內(nèi)存開銷問題.

本文采用如圖6所示的“輸入層-隱藏層-輸出層”三層結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò),并且設(shè)置隱藏層的神經(jīng)元個(gè)數(shù)為2×n,其中n為無人機(jī)數(shù)量,此時(shí)可以讓算法達(dá)到不錯(cuò)的效果并且消耗相對低.這里的隱藏層是線性整流單元(ReLU),輸出層的激活函數(shù)是一個(gè)線性函數(shù)通過3層神經(jīng)網(wǎng)絡(luò)來擬合Q值,如公式(15)所示:

圖6 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.6 Neural network structure diagram

Q(s,a)=θ1S1+θ2S2+…+θnSn+β

(15)

其中θ={θ1,θ2,…,θn}表示神經(jīng)網(wǎng)絡(luò)中的參數(shù),β表示偏置,Si表示第i臺無人機(jī)的狀態(tài).本文的研究中,采用隨機(jī)梯度下降的方法來訓(xùn)練神經(jīng)網(wǎng)絡(luò).公式(16)表示為:

L(θ)=E[(TargetQ-Q(s,a,θ))2]

(16)

其中r表示在s狀態(tài)下執(zhí)行a動作所獲得獎勵(lì),TargetQ=r+γmaxQ(s′,a′,θ)是期望的Q值,Q(s,a,θ)是實(shí)際的Q值,通過兩者之間的誤差值可建立此損失函數(shù),目的是使當(dāng)前的Q值逼近期望Q值.

5.2 貪婪策略(ε-greedy)

在衡量繼續(xù)開發(fā)和探索擴(kuò)展二者之間權(quán)重時(shí),ε-greedy是常用的策略之一.這種貪婪策略在智能體做決策時(shí),會用一較小正數(shù)ε(<1)的概率來任意選取動作空間的一個(gè)動作,剩下1-ε的概率選取已有動作中回報(bào)最大的動作,這樣可以避免策略收斂于局部最優(yōu).本文采取此貪婪策略:為了得到最優(yōu)的學(xué)習(xí)策略,在任務(wù)剛開始時(shí)將探索的概率ε設(shè)置為0.5,隨著任務(wù)調(diào)度次數(shù)的增加逐步縮小ε,最終保持在0.06,這樣算法初期可以嘗試更多的策略,而后期減少探索偏向于使用優(yōu)化過的策略.

5.3 算法實(shí)現(xiàn)

多無人機(jī)協(xié)同充電路徑規(guī)劃(MC-CPP)如表2所示,MC-CPP算法的輸入為新的任務(wù)S(這里指待充電節(jié)點(diǎn)),輸出為At(最佳動作).算法的基本流程為:當(dāng)一個(gè)新的待充電節(jié)點(diǎn)進(jìn)入系統(tǒng),系統(tǒng)首先獲取無人機(jī)狀態(tài)信息,然后初始化經(jīng)驗(yàn)回放池,再使用ε-greedy策略來確定無人機(jī)下一步動作的選擇.即根據(jù)當(dāng)前的無人機(jī)狀態(tài)計(jì)算并保持所有下一步動作的Q值,再以ε的概率抽取無人機(jī)動作空間中的一隨機(jī)動作,以1-ε的概率采取可以使當(dāng)前Q值最大的動作,然后將動作分配給多無人機(jī)執(zhí)行,最后更新系統(tǒng)狀態(tài)、保存信息至經(jīng)驗(yàn)回放池中并更新神經(jīng)網(wǎng)絡(luò)中的參數(shù)θ值.

表2 MC-CPP算法Table 2 MC-CPP algorithm

6 仿真結(jié)果與分析

6.1 實(shí)驗(yàn)環(huán)境

本章設(shè)計(jì)了一個(gè)模擬程序來模擬數(shù)據(jù)傳輸過程中傳感器節(jié)點(diǎn)的能耗相關(guān)參數(shù).模擬器通過修改傳感器節(jié)點(diǎn)的初始能量、能量消耗速率等,可以模擬出本文中的WRSN場景.UAV的速度設(shè)置為6m/s,無線充電功率為30W,飛行成本為50J/m.負(fù)懲罰獎勵(lì)ε是-10,獎勵(lì)折扣Y等于0.9,在神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)中,使用的是具有兩個(gè)隱藏層的全連接前饋神經(jīng)網(wǎng)絡(luò).第1層和第2層各擁有256個(gè)神經(jīng)元.本節(jié)通過仿真實(shí)驗(yàn)來驗(yàn)證本文算法的性能,將環(huán)境建模為1000×1000區(qū)域并采用Voronoi圖的方法對區(qū)域進(jìn)行劃分.

在強(qiáng)化學(xué)習(xí)過程中,一個(gè)學(xué)習(xí)周期是多個(gè)學(xué)習(xí)步驟的序列,一個(gè)學(xué)習(xí)周期在如下3個(gè)事件中任意一個(gè)發(fā)生時(shí)結(jié)束:case1:完成充電任務(wù)并到達(dá)基站位置;case2:UAV發(fā)生碰撞;case3:已達(dá)到預(yù)先規(guī)定的最大學(xué)習(xí)步驟數(shù).

如圖7所示,4架無人機(jī)為區(qū)域內(nèi)100個(gè)傳感器節(jié)點(diǎn)進(jìn)行充電的路線示意圖,采用Voronoi法所以只需遍歷圖中47個(gè)停止點(diǎn)即可,利用強(qiáng)化學(xué)習(xí)及神經(jīng)網(wǎng)絡(luò)可獲得多無人機(jī)飛行路徑.其顯示了傳感器節(jié)點(diǎn)為100、基站個(gè)數(shù)為1時(shí)充電停止點(diǎn)分布情況以及充電路徑.可將100個(gè)傳感器節(jié)點(diǎn)全部覆蓋,且都滿足充電策略.

圖7 無人機(jī)飛行路徑Fig.7 UAV flight path

6.2 實(shí)驗(yàn)參數(shù)設(shè)置

Q-Learning算法中的學(xué)習(xí)過程及無人機(jī)設(shè)備的參數(shù)符號、含義與相關(guān)設(shè)置如表3所示.

表3 參數(shù)表Table 3 Parameter table

本文場景下的WRSN中有n輛UAV在充電中心處出發(fā),按照順序沿著各自路徑對路徑上待充電的節(jié)點(diǎn)補(bǔ)充能量,完成任務(wù)后返回基站補(bǔ)充無人機(jī)自身電能,這就是一輪次的充電調(diào)度.根據(jù)本文充電策略,UAV估計(jì)每次移動的回報(bào)值,隨著不斷地進(jìn)行訓(xùn)練與迭代,UAV的總飛行距離也隨之不斷下降,直到Q值收斂于極大值,便得到此環(huán)境下滿足要求的最佳飛行路徑.表4、表5為此環(huán)境下衰減系數(shù)Y和懲罰項(xiàng)ε對獎勵(lì)值、死亡節(jié)點(diǎn)、飛行距離的影響.

表4 γ的影響Table 4 Influence of γ

表5 ε的影響Table 5 Influence of ε

其中飛行距離的單位為km.

由此可以得到,收集到的充電獎勵(lì)隨著γ值的增加而增加,而當(dāng)γ=0.9時(shí),沒有傳感器節(jié)點(diǎn)耗盡能量.而引入懲罰值的目的是盡量減少網(wǎng)絡(luò)中死亡節(jié)點(diǎn)的數(shù)量,當(dāng)ε=0時(shí),死亡節(jié)點(diǎn)數(shù)為5,隨著ε的增加,死亡節(jié)點(diǎn)的數(shù)量逐漸減少,當(dāng)ε=-10時(shí),死亡節(jié)點(diǎn)數(shù)為0.

圖8為同一實(shí)驗(yàn)環(huán)境下無人機(jī)數(shù)量與充電覆蓋率之間的關(guān)系,可以得到改進(jìn)的Q-Learning算法比傳統(tǒng)Q學(xué)習(xí)算法的充電覆蓋率平均高出12.4%,改進(jìn)算法在無人機(jī)個(gè)數(shù)為4時(shí)對WRSN的充電覆蓋率高達(dá)97%,已滿足最小充電覆蓋率約束.然而同等數(shù)量無人機(jī)情況下,傳統(tǒng)算法充電覆蓋率為78%不能滿足90%充電覆蓋率要求,如需達(dá)到要求則至少需5架無人機(jī),此時(shí)會增加無人機(jī)個(gè)數(shù)導(dǎo)致資源浪費(fèi).

圖8 無人機(jī)數(shù)量與充電覆蓋率關(guān)系Fig.8 Relationship between the number of UAVs and charging coverage

對比算法的充電覆蓋率最高可以提升至92%,而MC-CPP的充電覆蓋率能夠提升至100%,而且對比算法所消耗的能量一直大于MC-CPP算法,這是由于MC-CPP算法具有更優(yōu)的全局計(jì)算能力及智慧高效的特點(diǎn),不僅滿足了節(jié)點(diǎn)覆蓋率與無人機(jī)飛行消耗的要求,還將無人機(jī)自身能量消耗降到最低,而對比算法則因智能性欠缺而無法達(dá)到這種效果.從圖中可以看出MC-CPP在無人機(jī)數(shù)量剛好滿足需求時(shí),算法的表現(xiàn)差異較大,由此可得MC-CPP算法在提高節(jié)點(diǎn)覆蓋率和減少無人機(jī)數(shù)量方面更為優(yōu)越.

圖9是由實(shí)驗(yàn)?zāi)M所得的多無人機(jī)產(chǎn)生碰撞的概率,從中可以看出隨著迭代次數(shù)的增加,多無人機(jī)碰撞概率從一開始的0.9%左右降低至0.4%左右.其中兩個(gè)無人機(jī)時(shí)產(chǎn)生碰撞的概率最小并保持在0.25%～0.81%之間,4個(gè)無人機(jī)時(shí)產(chǎn)生碰撞的概率最大并保持在0.39%～0.9%之間.由此可得,本方案的多無人機(jī)碰撞概率很低,可以滿足安全性約束條件.

圖9 多無人機(jī)碰撞概率Fig.9 Collision probability of multiple UAVs

訓(xùn)練損失值和時(shí)間的迭代關(guān)系圖如圖10所示,展示了訓(xùn)練損失函數(shù)的收斂速度,由此圖可得到損失函數(shù)的值在前1000次迭代內(nèi)迅速下降,在迭代2000次時(shí)基本穩(wěn)定下來.這是由于起初的動作對獎勵(lì)值的影響程度很大,損失函數(shù)值的下降會很迅猛,之后隨著迭代次數(shù)的增多,訓(xùn)練損失值會慢慢靠近最優(yōu)值,從而可得到合適的網(wǎng)絡(luò)參數(shù)值.

圖10 迭代關(guān)系圖Fig.10 Iterative graph

6.3 對比實(shí)驗(yàn)

本文算法與其他4種算法進(jìn)行對比實(shí)驗(yàn),分別為:

時(shí)空充電調(diào)度算法(TSCA):是一種按需充電算法,考慮時(shí)空信息的按需調(diào)度算法.其主要目標(biāo)是最小化死亡節(jié)點(diǎn)的數(shù)量,次要目標(biāo)是最小化UAV的移動距離,主要方案是由傳感器節(jié)點(diǎn)發(fā)送的這些充電請求首先根據(jù)它們的充電截止時(shí)間進(jìn)行排序,然后用最大努力重新排列.

最近工作優(yōu)先算法(NJNP):允許UAV選擇空間上最近的傳感器節(jié)點(diǎn)作為下一個(gè)傳感器來充電.

貪心充電算法(GC):一種使評估函數(shù)方程值最大化的移動設(shè)備充電算法.

隨機(jī)算法(RA):它隨機(jī)選擇下一個(gè)傳感器節(jié)點(diǎn)為充電節(jié)點(diǎn),UAV在每次完成充電任務(wù)后都會到達(dá).

圖11展示了4種對比算法與本文提出的MC-CPP算法獲得獎勵(lì)值和迭代時(shí)間的關(guān)系.由圖可知:1)隨著時(shí)間變化,所有算法的累積獎勵(lì)值都持續(xù)增大;2)起初計(jì)算量較小時(shí),4種對比算法和MC-CPP算法獎勵(lì)值相差不大,之后MC-CPP在25個(gè)訓(xùn)練周期處累計(jì)獎勵(lì)值迅速增加,這是由于在任務(wù)剛開始執(zhí)行時(shí),距離較遠(yuǎn)處的傳感器節(jié)點(diǎn)并沒有被覆蓋,有著提升獎勵(lì)值的空間;3)整體上,MC-CPP的獎勵(lì)值最高,TSCA其次,再者是NJNP和GC貪心算法,獎勵(lì)值最小的是RA隨機(jī)算法.本文提出的MC-CPP算法最先達(dá)到峰值,之后趨于一個(gè)穩(wěn)定值.

圖11 獎勵(lì)值對比Fig.11 Reward value comparison

UAV的能耗主要包括兩部分,即給節(jié)點(diǎn)傳輸?shù)哪芰亢妥陨盹w行懸停所消耗的能量.通過最小化移動距離,可以使能源利用效率最大化.如圖12所示,為傳感器節(jié)點(diǎn)個(gè)數(shù)和路徑長度的關(guān)系圖,展現(xiàn)了5種算法在路徑規(guī)劃及能量利用率方面的優(yōu)劣性.

圖12 路徑長度對比Fig.12 Path length comparison

從整體上看,TSCA算法的路徑長度最長,MC-CPP算法較短,NJNP算法得到的路徑長度最短,這是由于TSCA算法為按需充電,只要節(jié)點(diǎn)有充電需求就會按照順序執(zhí)行充電任務(wù)所以會使得路徑長度劇增,而NJNP算法會選擇空間上最近的節(jié)點(diǎn)進(jìn)行充電,所以當(dāng)無人機(jī)能量耗盡時(shí)其得到的充電路徑長度最短.當(dāng)網(wǎng)絡(luò)規(guī)模逐漸增大時(shí),NJNP算法會由于節(jié)點(diǎn)越來越密集,路徑長度變得越來越短;隨機(jī)算法由于采取隨機(jī)選擇節(jié)點(diǎn)進(jìn)行充電,其得到的路徑長度較不規(guī)律;其余3種算法得到的充電路徑長度都隨著節(jié)點(diǎn)數(shù)量的增加而逐漸增加.其中TSCA算法得到的平均充電路徑長度為7276m,貪心算法所得長度為6225m,MC-CPP得到的平均充電路徑長度為5691m.由此可得,本文的MC-CPP算法在平均充電路徑長度方面與TSCA算法和貪心算法相比分別縮短了21.7%、8.5%.

圖13為5種算法下產(chǎn)生死亡節(jié)點(diǎn)個(gè)數(shù)的對比.從整體上,可以直觀的看出隨機(jī)算法的死亡節(jié)點(diǎn)最多,其次是NJNP算法,貪心算法和TSCA的死亡節(jié)點(diǎn)相對較少,由MC-CPP算法所產(chǎn)生的死亡節(jié)點(diǎn)最少,且MC-CPP在節(jié)點(diǎn)總數(shù)超過30之前,沒有傳感器耗盡電池.MC-CPP確保UAV能夠及時(shí)地為所有需要充電的傳感器充電,而TSCA和隨機(jī)算法則不能保證UAV將達(dá)到同樣的結(jié)果.然而,當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量超過50個(gè)時(shí),即使是MC-CPP也不能再避免節(jié)點(diǎn)死亡,獎勵(lì)一般會下降.原因是隨著網(wǎng)絡(luò)中待充電節(jié)點(diǎn)越來越多,無人機(jī)個(gè)數(shù)也需要隨之增加,然而,無人機(jī)的增加需要滿足一定要求,在其節(jié)點(diǎn)覆蓋率可以達(dá)到95%以上時(shí)為了減少資源浪費(fèi)不會增加無人機(jī)個(gè)數(shù),此時(shí)會產(chǎn)生少數(shù)傳感器節(jié)點(diǎn)不能被覆蓋而導(dǎo)致節(jié)點(diǎn)餓死的情況發(fā)生.

圖13 死亡節(jié)點(diǎn)數(shù)對比Fig.13 Comparison of dead nodes

綜合以上的實(shí)驗(yàn)結(jié)果可得,本文所提出的MC-CPP算法在大規(guī)模無線可充電傳感網(wǎng)以及待充電節(jié)點(diǎn)數(shù)量變化的場景中都具有優(yōu)秀的魯棒性,其因環(huán)境動態(tài)變化而變化的可能性很小,能夠根據(jù)所處環(huán)境,盡可能得到最大獎勵(lì)值從而快速自適應(yīng)地做出最優(yōu)的充電決策,在滿足充電覆蓋率的同時(shí)使得無人機(jī)總飛行路徑最短、能量損耗值與死亡節(jié)點(diǎn)數(shù)最小.

7 結(jié)束語

本文提出了一種采用強(qiáng)化學(xué)習(xí)方法的多無人機(jī)無線可充電傳感網(wǎng)充電路徑規(guī)劃方案.本方案利用改進(jìn)的Q-Learning算法,通過結(jié)合神經(jīng)網(wǎng)絡(luò)、貪婪策略、經(jīng)驗(yàn)回放等來進(jìn)行算法優(yōu)化,由此可得最佳無人機(jī)數(shù)量并能夠迅速準(zhǔn)確地規(guī)劃出最佳飛行路徑,規(guī)劃出的路徑一定程度上降低了無人機(jī)在飛行路徑上的能量損耗.與基于傳統(tǒng)Q學(xué)習(xí)的方案相比,收斂速度更快,表現(xiàn)出了更好的路徑規(guī)劃性能.與TSCA等算法相比,基于獎勵(lì)機(jī)制的改進(jìn)Q學(xué)習(xí)算法在收斂性、獎勵(lì)值和節(jié)點(diǎn)餓死率上優(yōu)勢明顯.在未來的研究工作中,將對節(jié)點(diǎn)數(shù)量或地理位置變化情況以及環(huán)境因素(例如障礙物)等進(jìn)行考慮,從而得到一種更為通用的充電規(guī)劃方案.