基于多智能體強化學習的無人機群室內(nèi)輔助救援①

郭天昊,張 鋼,岳文淵,王 倩,郭大波

(山西大學 物理電子工程學院,太原 030006)

無人機具有易于部署,靈活性高以及制造成本低等優(yōu)勢,常被用來部署在各種民用場景中,其中包括精準農(nóng)業(yè),清理海洋廢棄物,包裹投遞,自然災害后恢復網(wǎng)絡(luò)服務(wù)以及搜索與搜救[1–5].基于無人機的災后搜救也由之前的單機式搜救逐漸發(fā)展到小型的多機群式搜救[6],大幅度提高了搜救效率.

在早期,無人機輔助搜救的目標多是針對目標位置已知的情況[7–9],無人機只需要規(guī)劃飛行路線抵達目標所在位置即可.實際搜救過程中在搜索目標之前對于任務(wù)區(qū)域的信息知之甚少,復雜的室內(nèi)環(huán)境對于無人機的避障能力提出了巨大的挑戰(zhàn).如何使無人機群對環(huán)境無任何先驗知識的前提下進行自主決策是個值得研究的問題.為此,文獻[10]將基于模型的強化學習算法應(yīng)用到無人機的自主導航領(lǐng)域,極大提高了無人機自主決策能力.在無人機最佳路徑規(guī)劃方向,文獻[11]考慮了獎勵與懲罰機制,使得無人機在不斷地嘗試飛行中選擇最佳路徑從而到達目標位置.考慮到無人機在復雜環(huán)境中狀態(tài)值爆炸式的增多,為解決大容量的狀態(tài)值問題,文獻[12]提出了基于神經(jīng)網(wǎng)絡(luò)的分布式DQN算法,以控制無人機在未知環(huán)境中進行目標搜索與目標跟蹤.針對大規(guī)模的搜索環(huán)境,需要多臺無人機設(shè)備進行協(xié)作完成搜索任務(wù),文獻[13]提出一種異構(gòu)多智能體算法,以控制多臺無人機在復雜的環(huán)境中以協(xié)作的方式最大程度上完成搜索任務(wù).

為組織合作的、智能的、適應(yīng)復雜環(huán)境下的無人機群,本文提出了一種基于多智能體強化學習的控制策略.首先將多無人機搜救任務(wù)進行建模處理,將其轉(zhuǎn)化為具有完全回報函數(shù)的分散的部分可觀的馬爾可夫決策過程;其次提出了基于集中學習分散執(zhí)行的多智能體強化學習方法,利用了Double-DQN 算法對Dec-POMDP 進行了求解;最后利用蒙特卡洛方法對本方案進行通用性測試.結(jié)果表明本文方案在搜救成功率方面所具備的優(yōu)勢,能夠在大型的救援環(huán)境中出色的完成搜救任務(wù).

1 問題概述與系統(tǒng)模型

1.1 問題概述

本文考慮了這樣一個場景,某大型圖書館發(fā)生火災,無人機群進入圖書館以協(xié)作的方式迅速對館內(nèi)受害人員進行搜索.具體地,無人機群的搜索任務(wù)環(huán)境如圖1所示.該圖模擬了復雜的室內(nèi)環(huán)境,為簡化訓練模型,假設(shè)無人機飛行過程中高度恒定為h(不包括起飛與降落操作),飛行速度恒定為V.受害者的手機可作為其位置信息傳感器隨時發(fā)出其位置信息,其通信模式為:無人機通過發(fā)射一種激活信號,受害者持有的終端設(shè)備接受此信號后通過反向散射(back scatter)方式向無人機發(fā)送位置數(shù)據(jù)[14],由于每個手機設(shè)備反射功率的不同會導致無人機只有在一定范圍內(nèi)才能采集位置信息.

圖1 無人機室內(nèi)搜救模型

任務(wù)區(qū)域內(nèi)隨機布置了3 臺無人機與7 名位置隨機的受害者.無人機從停機坪(充電站位置)出發(fā)后,分別對受害者位置信息進行采集,受限于電池容量的影響,無人機群須在電量耗盡之前返航到充電站位置進行充電操作,對于沒能在電量耗盡之前安全返航進行充電操作的所提方案將其作為懲罰加入獎勵函數(shù)中.

為將地圖進行合理的建模,本方案將地圖分割為N×N的網(wǎng)格模型,定義整個室內(nèi)區(qū)域為M:M×M∈N2,將M區(qū)域分割為尺寸大小為n的32×32 網(wǎng)格.定義無人充電位置區(qū)域Z ∈{[xZi,yZi]T,i=1,···,N},將所有窗戶位置定義為禁飛區(qū)域 C ∈{[xCi,yCi],i=1,···,N},避免由于窗戶處于打開狀態(tài)而導致無人機從窗戶飛到室外無形中將搜索區(qū)域擴展為無限大.將墻體與門所在位置定義為障礙物區(qū)域 N={[xNi,yNi],i=1,···,N},無人機在飛行過程中要絕對避免的區(qū)域.

1.2 信道模型

在本文中,所提方案考慮到現(xiàn)實場景,將無人機與受害者之間的通信鏈路建模為視距(line of sight,LOS)與非視距(none-line of sight,NLOS)的點對點信道模型[15],在該信道模型下本文定義在時間為n,第j位受害者能夠達到的信息速率為:

其中,Pj為發(fā)射功率,σ2為接受機處的高斯白噪聲的功率,αe與 ηe為信號在無人機與受害者之間的傳播路徑損耗指數(shù),其中e∈{LOS,NLOS},具體與環(huán)境有關(guān),主要來自視距損耗或者非視距損耗.dj(n)為無人機距離受害者的直線距離.

1.3 系統(tǒng)模型

本系統(tǒng)模型的主要研究目標是使得無人機團隊在一定約束條件下能夠最大化的從搜救區(qū)域中搜集受害者的位置信息.這些約束條件主要分為兩部分,一部分來自無人機設(shè)備自身的條件約束,例如電池容量.另一部分來自環(huán)境對無人機設(shè)備的約束.例如室內(nèi)門墻等障礙物、無人機與無人機之間避免碰撞以及無人機的起落位置(充電位置).

對無人機群進行建模,定義第i臺無人機的位置為pi(t)=[xi(t),yi(t),zi(t)]T,為簡化模型假設(shè)無人機的飛行高度為zi(t)∈{0,h}即無人機的高度位置只能為地面0 或者以h的高度恒定飛行.在本模型中無人機的動作空間受限于其所處環(huán)境的位置,無人機只有在充電區(qū)域時才能執(zhí)行著陸充電動作.動作空間定義為:

第i臺無人機在t時刻的動作為ai(t),其中,ai(t)∈A(pi(t)).

無人機t時刻的飛行狀態(tài)為λi(t)∈{0,1},0 表示無人機處于靜止狀態(tài),1 表示無人機處于運動狀態(tài).值得注意的是當無人機處于充電狀態(tài)時,運動狀態(tài)變?yōu)榉沁\動狀態(tài).定義無人機的下一狀態(tài)為:

對于本模型中的無人機剩余電量,第i臺無人機在t時刻剩余電量為Ei(t).假設(shè)無人機運動時消耗的電量始終恒定,此時可以直接將剩余電量等價于此無人機的剩余飛行時間.由于耗電量主要由運行狀態(tài)決定,為此無人機的下一時刻的剩余電量可離散化為:

對于無人機的動作策略的優(yōu)化本質(zhì)上是對無人機的接收信息的吞吐量最大化,無人機群與受害者持有的設(shè)備之間通信時遵循標準的時分多址模型(TDMA),在任務(wù)時間T內(nèi),整個團隊I臺無人機設(shè)備在聯(lián)合策略xiai(t)下的最大化吞吐量模型為:

其中,n∈[βt,β(t+1)?1]表示在任務(wù)時間T內(nèi)的通信時間,β為通信時隙,λi(t)為無人機的在t時刻的運行狀態(tài),qi,j(n)∈{0,1}為TDMA 模式下的調(diào)度變量.

2 多智能體強化學習

強化學習作為機器學習的一個重要分支,其核心是智能體與特定環(huán)境的重復交互,學習如何在未知環(huán)境中執(zhí)行最優(yōu)策略[16].在當前狀態(tài)S下,智能體執(zhí)行動作A,環(huán)境接收到此動作后反饋于智能體下一狀態(tài)St+1和回報值R,智能體依據(jù)環(huán)境反饋的回報值來優(yōu)化策略并且進行再學習,就這樣通過不斷地迭代最后生成最優(yōu)策略.

本文針對多無人機協(xié)作問題定義了同質(zhì)的、非通信的、簡單合作的無人機群.同質(zhì)性是指每臺無人機設(shè)備具有相同的構(gòu)造結(jié)構(gòu),相同的動作空間以及任務(wù)領(lǐng)域;非通信是指無人機之間沒有直接的通信,即無人機不能協(xié)調(diào)它們的動作以及進行有關(guān)的通信,但都能感知與其他無人機之間位置信息,并可利用這種感知到的位置信息對無人機進行監(jiān)管維護;簡單合作是指無人機團隊共同收集的位置數(shù)據(jù)可添加到每一臺無人機的回報函數(shù)中,這就使得他們有一個共同的目標.在多智能體訓練階段,每臺無人機與環(huán)境不斷地交互進行自身的策略優(yōu)化,之后將它們的經(jīng)驗數(shù)據(jù)集中起來,通過組建神經(jīng)網(wǎng)絡(luò)數(shù)據(jù)庫來訓練控制系統(tǒng),最后將訓練好的控制系統(tǒng)部署到每臺無人機設(shè)備上.

2.1 部分可觀的馬爾可夫決策過程

本節(jié)將無人機團隊與環(huán)境交互的問題轉(zhuǎn)換為部分可觀的馬爾可夫決策過程.一個Dec-MDP 通常是由一個七元組組成(S,Ax,P,R,?x,O,γ),其中S代表一組空間狀態(tài)值,Ax表示智能體的動作空間,P:S×A→?(S)為狀態(tài)轉(zhuǎn)移概率矩陣,R:S×A×S→R為即時的獎勵函數(shù),?x=?I為一組觀測結(jié)果,即無人機傳感器獲得的環(huán)境數(shù)據(jù).O為條件觀測概率.γ ∈[0,1]為貼現(xiàn)因子,表示長期回報與短期回報的重要程度.

狀態(tài)(S):本模型狀態(tài)空間由3 部分組成.分別為環(huán)境信息、無人機狀態(tài)、受害者狀態(tài).定義狀態(tài)空間為S(t)=(M,{pi(t)},{Ei(t)},λi(t),{Lj},{Dj(t)}),其中,M表示環(huán)境中的一系列位置信息集合,包括室內(nèi)門窗以及墻體等障礙物的位置、無人機的起落位置以及危險區(qū)域的位置信息.{pi(t)} 表示第i臺無人機的位置信息,{Ei(t)}表示第i臺 無人機的剩余電量,λi(t)表示第i臺無人機的運行狀態(tài),{Lj} 表示第j位受害者的位置信息,{Dj(t)} 表示第j位受害者的位置信息量.

動作(Ax):考慮到模型的復雜性,為避免無人機發(fā)生碰撞,引入符合本模型的動作狀態(tài)空間,在之前的無人機動作空間模型中引入一種安全控制機制,無人機通過判斷所處的環(huán)境位置來執(zhí)行相應(yīng)的動作,當無人機位于區(qū)域 R時,該區(qū)域包括無人機的下個位置位于障礙物區(qū)域以及兩臺無人機同時出現(xiàn)在同一種位置且處于運動狀態(tài),此時安全機制執(zhí)行懸停動作.本方案定義安全動作空間如下:

在區(qū)域 R,有:

即時獎勵(R):本模型總即時獎勵Ri(t)由所有無人機任務(wù)時間內(nèi)搜救受害者數(shù)量的獎勵、路徑規(guī)劃獎勵、即時充電獎勵3 部分組成,其中搜集所有受害者位置信息量獎勵是每臺無人機共享獎勵的唯一部分.

t時間內(nèi)收集的所有受害者的位置信息量作為集體獎勵,τ為收集乘數(shù)將數(shù)據(jù)收集參數(shù)化,方法如下:

路徑規(guī)劃獎勵主要用于懲罰無人機在飛行過程中不執(zhí)行安全動作空間,為誘導無人機優(yōu)化最短飛行路徑來搜集受害者的位置信息,定義方法如下:

其中,當無人機的動作空間不符合安全動作空間時,給出懲罰θ,δ為持續(xù)飛行的路徑懲罰,使無人機減少飛行時間優(yōu)化其搜救路徑.

即時充電獎勵強迫無人機在電量耗盡之前返航進行充電,對于沒有即時返航的無人機給予值為ω的處罰,為此定義即時充電的獎勵計算如下:

綜上3 部分,總即時獎勵為以上3 部分獎勵之和,即:

觀測結(jié)果(?x):本模型無人機的觀測空間由室內(nèi)環(huán)境M、無人機的飛行狀態(tài)Oλi(t)、無人機的剩余電量OEi(t)、受害者位置信息量ODj(t)四部分組成.為簡化模型,將無人機的位置與受害者位置進行2D 投影,投影函數(shù)定義如下:

式(15)與式(16)分別將受害者與無人機的位置經(jīng)過投影函數(shù)f2D(x)后所得2D 位置信息為:

帶有位置信息Plocation與該位置所對應(yīng)的某一類值Qinformation映射到相對應(yīng)的圖層O,定義如下映射:

式(18),式(19),式(20)分別將無人機的位置信息與該位置對應(yīng)的運動狀態(tài)和剩余電量在映射函數(shù)fobservation下,得到其對應(yīng)得圖層O.

將上述所有的圖層作為無人機的觀測結(jié)果輸入到本文神經(jīng)網(wǎng)絡(luò)架構(gòu)中,式(21)為無人機的觀測結(jié)果:

2.2 DQN 算法:

本文的無人機群在大型室內(nèi)空間中執(zhí)行任務(wù),如將Q值表示為數(shù)值表格是不可取的,文獻[17]應(yīng)用了經(jīng)驗回放等方面的技術(shù),將Q-Learning 與神經(jīng)網(wǎng)絡(luò)結(jié)合起來,完美的解決了大狀態(tài)空間問題.經(jīng)驗池的主要功能是解決相關(guān)性與非靜態(tài)分布問題,具體方法是通過將每個時刻智能體與環(huán)境交互的樣本 (st,at,rt,st+1)存儲于回放記憶單元,訓練時在經(jīng)驗池中隨機抽取一批數(shù)據(jù)進行訓練.

DQN 算法的主要目標是保證估計值網(wǎng)絡(luò)輸出的值Q(s,a;θ)無 限接近于目標值網(wǎng)絡(luò)輸出的目標值TargetQ,其中,θ為網(wǎng)絡(luò)參數(shù),目標值計算方法為:

基于上述的目標值,定義DQN的損失函數(shù)公式,求L(θ) 關(guān)于θ的梯度,使用隨機梯度下降算法更新網(wǎng)絡(luò)參數(shù)θ:

具體地,DQN 算法的流程如圖2所示.

圖2 DQN 算法流程圖

3 無人機團隊路徑規(guī)劃算法

3.1 Double DQN (DDQN)算法

本文利用DDQN 算法對無人機團隊路徑規(guī)劃進行訓練,不同于DQN 算法,DDQN 算法克服了QLearning 算法固有的缺陷即過估計問題,而在DQN 算法中此問題也沒有得到有效解決,為解決過估計問題Double DQN 算法將動作的選擇和動作的評估分別用不同的值函數(shù)來實現(xiàn)如圖3所示,具體如下:

圖3 DDQN 損失函數(shù)構(gòu)造流程

通過網(wǎng)絡(luò)(main-net)獲得最大值函數(shù)的動作a,然后通過目標網(wǎng)絡(luò)(target-net)獲得上述動作a所對應(yīng)的TargetQ值:

基于目標網(wǎng)絡(luò)TargetQ值,定義DDQN的損失函數(shù)為:

3.2 Double DQN 神經(jīng)網(wǎng)絡(luò)

如圖4所示,本文構(gòu)建了該神經(jīng)網(wǎng)絡(luò)架構(gòu).將上述處理的4 幅信息圖層堆疊起來組成狀態(tài)信息圖作為觀測值傳入卷積核為5×5的卷積層1和2,然后通過激活函數(shù)R eLU (線性整流函數(shù))將輸出傳入展平層,該層的目的是將多維的數(shù)據(jù)一維化.最后將平坦后的數(shù)據(jù)與無人機剩余飛行時間的標量連接起來經(jīng)過3 個隱藏層后通過激活函數(shù) ReLU將數(shù)據(jù)傳入到一個動作空間大小為6的全連接層,最后得到在給定觀測空間狀態(tài)下的每個動作所對應(yīng)的Q值.

圖4 神經(jīng)網(wǎng)絡(luò)架構(gòu)

利用 Softmax激活函數(shù)對每個動作的Q值處理轉(zhuǎn)換為相對概率P(ai|s),其中通過調(diào)節(jié)參數(shù) β來平衡無人機的探索與利用.

通過貪婪策略得到P(ai|s)中最大值的索引,其中,a∈A.

4 仿真分析

本節(jié)對所提方案進行仿真與分析,且與傳統(tǒng)算進行對照,最后驗證了本文所提方案所具備的優(yōu)勢.本文考慮了320 m×320 m的無人機搜索區(qū)域,無人機團隊在所提方案的訓練后在室內(nèi)搜救路徑規(guī)劃如圖5所示.

圖5 無人機團隊搜救路徑

在該室內(nèi)區(qū)域隨機分布了9 位受害者,為達到較好搜救效果,本方案為其配備由3 臺無人機設(shè)備組成的搜救機群.無人機的起落位置,充電站都在圖5中藍色區(qū)域.將不同的受害者用不同顏色的小圓圈表示.所飛行的路徑軌跡由圖5中帶箭頭的線段表示,不同路徑顏色則代表此時的無人機正在搜集與本顏色所對應(yīng)受害者的位置信息.固定其飛行高度為10 m,飛行速度為1 m/s,考慮到飛行區(qū)域為室內(nèi)區(qū)域,設(shè)定路徑損耗參數(shù)αLOS=2.27,αNLOS=3.64.訓練仿真參數(shù)由表1給出.

表1 仿真參數(shù)設(shè)置

相比于傳統(tǒng)方案,所提方案優(yōu)勢在于加入充電操作、引入多智能體、適用大狀態(tài)搜救場景3 方面,為驗證3 方面所具備的優(yōu)勢,分別使用所提方案與傳統(tǒng)的算法對本文場景進行了無人機群的路徑規(guī)劃訓練.經(jīng)過3 000 000 次的訓練迭代,所提方案使得累計回報值得到顯著提升.

本文方案加入充電模塊,相比于未加入此模塊的傳統(tǒng)方案訓練所得的累計回報對比如圖6所示.

圖6 兩種方案的訓練回報對比

在圖6中,所提方案累計回報值增長較快,最終達到收斂.可以明顯看出加入充電模塊的回報值明顯高于傳統(tǒng)方案.這種比較說明了本文方案能夠快速的適應(yīng)搜救場景,且能高效的進行輔助搜救,因此本文方案更加有效.

為說明所提方案在大狀態(tài)環(huán)境的適用性,將本文室內(nèi)搜救場景下的受害者的數(shù)量以及部署的無人機集群規(guī)模進行逐步增大,觀測其對于搜救率的影響.如圖7所示,隨著受害者人數(shù)的增加對同一規(guī)模集群其搜救率并沒有出現(xiàn)明顯的驟降,之所以出現(xiàn)下降趨勢是由于在整個搜救場景中受害者的位置被隨機的放置,受害者人數(shù)的增加導致無人機的碰撞概率增大最終導致無人機集群更加復雜的路徑規(guī)劃,因此使得搜救成功率有所下降.

圖7 所提方案對于大狀態(tài)環(huán)境下的搜救率

在圖7中,由2 臺無人機組成的集群搜救成功率明顯低于其他集群,主要原因是在大范圍與復雜的搜救場景中,2 臺無人集群缺乏搜索覆蓋能力,存在搜索盲區(qū)導致搜救率下降.如果采取由4 臺無人機組成的集群進行搜救任務(wù),當環(huán)境中存在4 位以下受害者時能達到最佳搜救效果,然而隨著受害者人數(shù)增加到5 位以上時,搜救成功率明顯低于由3 臺無人機組成的搜救集群.這是因為環(huán)境中存在4 位以下受害者時,由4 臺無人機組成的搜救集群具有較強的搜救覆蓋能力且不需要執(zhí)行復雜的路徑規(guī)劃,受害者人數(shù)增加到5 人以上時,4 臺無人機集群雖具有較強的覆蓋能力,但在一定范圍的搜索環(huán)境下,無人機設(shè)備數(shù)量的增多以及受害者人數(shù)的上升勢必會導致復雜的路徑規(guī)劃,對于無人機之間的避免碰撞以及單程電池容量提出了巨大挑戰(zhàn).考慮到本文實際的模擬場景以及設(shè)備成本,最終選擇3 臺無人機作為搜救集群,并達到了最優(yōu)的搜救效果.

本文對隨機場景進行了1 000 次蒙特卡洛迭代,所得性能指標用于評估多智能體在搜救任務(wù)中的優(yōu)勢,圖8可以明顯看出,在搜救場景中部署多臺無人機設(shè)備使得搜救成功率得到了顯著提高,傳統(tǒng)的單智能體方案在搜救區(qū)域增大時缺乏搜救覆蓋能力,如其經(jīng)常在某一個固定區(qū)域搜救然后直接返回著陸位置,造成其他區(qū)域位置的受害者無法得到救援,最終導致搜救能力下降.

圖8 多智能體與單智能體搜救率對比

5 總結(jié)

本文研究了無人機群協(xié)作進行輔助搜救的問題,搜救的區(qū)域是發(fā)生火災的大型室內(nèi)場景.為提高無人機群的搜救能力本文引入了一種多智能體強化學習方案,該方案基于DDQN 算法來優(yōu)化無人機團隊的飛行路徑,解決了無人機群在不確定環(huán)境下的搜救問題,在搜救過程中無人機群受限于電池容量,所提方案又引入了充電模塊,從而最大程度的完成對受害者位置信息的搜集.除此之外,本文還詳細描述了將搜救的模型轉(zhuǎn)化為部分可觀的馬爾可夫決策的過程.對于未來的工作,無人機速度控制以及飛行高度的擴展是重要的探索方向,這種擴展可以使無人機團隊適應(yīng)更為復雜的搜救場景.