改進(jìn)強(qiáng)化學(xué)習(xí)算法的UAV室內(nèi)三維航跡規(guī)劃

張 俊，朱慶偉，嚴(yán)俊杰，溫 波

1.西安科技大學(xué) 測繪科學(xué)與技術(shù)學(xué)院，西安710054

2.西南大學(xué) 心理學(xué)部，重慶400715

無人機(jī)（Unmanned Aerial Vehicle，UAV）因其機(jī)動(dòng)性能好、使用方便等特點(diǎn)，被廣泛應(yīng)用在各個(gè)領(lǐng)域。將無人機(jī)用于災(zāi)后室內(nèi)環(huán)境搜索和救援時(shí)，可以降低對(duì)救援人員的傷害，提高任務(wù)效率，并能在救援團(tuán)隊(duì)無法到達(dá)的區(qū)域執(zhí)行搜索任務(wù)。航跡規(guī)劃是無人機(jī)自主導(dǎo)航技術(shù)的重要組成部分，其目的是找到一條安全且路徑長度盡可能短的路徑，供無人機(jī)從起始位置到達(dá)目標(biāo)位置[1-2]。當(dāng)發(fā)生災(zāi)害時(shí)，室內(nèi)空間中分布著大量的障礙物，嚴(yán)重威脅無人機(jī)的飛行安全。因此，安全高效的航跡規(guī)劃方法是無人機(jī)完成災(zāi)后室內(nèi)環(huán)境搜索救援任務(wù)的關(guān)鍵。

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

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

1 空間離散化處理

當(dāng)發(fā)生災(zāi)害時(shí)，室內(nèi)空間環(huán)境中隨機(jī)分布著大量的障礙物，由于空間環(huán)境處于連續(xù)狀態(tài)，無人機(jī)在進(jìn)行航跡規(guī)劃時(shí)，很難順利完成既定的搜索任務(wù)。因此，對(duì)室內(nèi)環(huán)境進(jìn)行空間離散化處理，從而在路徑規(guī)劃時(shí)可直接獲得空間節(jié)點(diǎn)集，即在空間節(jié)點(diǎn)集中找到組成路徑飛行的總成本代價(jià)最小的節(jié)點(diǎn)。

設(shè)每個(gè)節(jié)點(diǎn)knode代表無人機(jī)的一個(gè)三維坐標(biāo)(xnode,ynode,znode)，令所有離散狀態(tài)空間節(jié)點(diǎn)的集合設(shè)置為k，如式（1）所示：

對(duì)于無人機(jī)由起點(diǎn)到目標(biāo)點(diǎn)飛過的路徑節(jié)點(diǎn)構(gòu)成的集合用G表示，如式（2）所示：

2 傳統(tǒng)強(qiáng)化學(xué)習(xí)算法及不足

Q-learning是由Watkins提出的一種強(qiáng)化學(xué)習(xí)方法，為給定的馬爾可夫決策過程提供最佳的動(dòng)作選擇策略[13-14]。通常，強(qiáng)化學(xué)習(xí)是在agent與環(huán)境之間交互循環(huán)中進(jìn)行，如圖1所示。在時(shí)間t中，agent觀察到一個(gè)狀態(tài)st∈S，執(zhí)行一個(gè)動(dòng)作at∈A，在這個(gè)過程中獲得獎(jiǎng)勵(lì)rt∈R，隨后時(shí)間索引遞增，環(huán)境將agent傳播到新的狀態(tài)st+1，該狀態(tài)下重新開始循環(huán)。最佳路徑規(guī)劃中agent的目標(biāo)是最大化獲得的總獎(jiǎng)勵(lì)，考慮折扣系數(shù)，可以將收到的總獎(jiǎng)勵(lì)定義如下：

圖1 強(qiáng)化學(xué)習(xí)的基本模型Fig.1 Basic model of reinforcement learning

其中，rt為時(shí)間t中獲得的獎(jiǎng)勵(lì)。

通過不斷的訓(xùn)練，agent可以自動(dòng)感知未知的環(huán)境并最終獲得具有最大累積獎(jiǎng)勵(lì)的狀態(tài)動(dòng)作集，對(duì)Q函數(shù)進(jìn)行迭代改進(jìn)的Q學(xué)習(xí)更新規(guī)則：

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

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

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

此外，在探索的初始階段，由于Q值初始化為0，無人機(jī)的動(dòng)作完全隨機(jī)，導(dǎo)致不必要的計(jì)算，收斂速度慢且耗時(shí)，下一個(gè)狀態(tài)選擇的動(dòng)作將由最高Q值確定[16-19]。

3 優(yōu)化策略

為了克服上文中的局限性，對(duì)經(jīng)典強(qiáng)化學(xué)習(xí)進(jìn)行了優(yōu)化，以滿足無人機(jī)災(zāi)后室內(nèi)環(huán)境的搜索和救援任務(wù)。首先，在算法學(xué)習(xí)之前，通過起點(diǎn)和終點(diǎn)間連線與障礙物碰撞確立關(guān)鍵的障礙物及包圍障礙物的節(jié)點(diǎn)，舍棄與路徑規(guī)劃中不相關(guān)的障礙物和節(jié)點(diǎn)；然后，用給定的起點(diǎn)和終點(diǎn)坐標(biāo)求出目標(biāo)點(diǎn)相對(duì)于無人機(jī)的方向，使無人機(jī)在初始階段不再隨機(jī)進(jìn)行選擇，而是朝著目標(biāo)方向搜索，從而降低了空間復(fù)雜性和提高了收斂速度。

3.1 空間優(yōu)化策略

基于起點(diǎn)s和終點(diǎn)g的連線內(nèi)與障礙物所處的位置關(guān)系，首先判斷出一組主要障礙物MO，并找到一組MO周圍的障礙物環(huán)繞點(diǎn)SP，以此達(dá)到限制MO的目的。然后，由起點(diǎn)和終點(diǎn)經(jīng)SP上的網(wǎng)格點(diǎn)到達(dá)目標(biāo)點(diǎn)，生成飛行路徑，如圖3所示，其中實(shí)心小球?yàn)檫x擇出的主要障礙物圍繞節(jié)點(diǎn)，空心小球?yàn)闁鸥窆?jié)點(diǎn)。具體步驟為：基于與sg的碰撞，從一組危險(xiǎn)因素中識(shí)別出一組主要障礙物MO和次要障礙物NMO，障礙物定義為O，其中MO?NMO=O且MO?NMO=?。然后令h作為基于兩個(gè)輸入之間存在交集和并集的判斷函數(shù)。若返回為1，則為MO，否則為NMO，可用以下方程式定義MO和NMO。

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

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

c中，如式（8）所示：

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

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

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

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

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

3.2 Q值初始化策略

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

無人機(jī)在三維環(huán)境中可向除自身外的26個(gè)方向之一運(yùn)動(dòng)，在路徑探索初期，由于Q值初始化為0，無人機(jī)將向其周圍的相鄰點(diǎn)隨機(jī)移動(dòng)，收斂速度慢同時(shí)耗時(shí)較長。因此通過確定相對(duì)于起點(diǎn)位置的目標(biāo)方向，對(duì)Q值進(jìn)行初始化，使得學(xué)習(xí)初期即有一定的目標(biāo)性。無人機(jī)飛行方向與起點(diǎn)和終點(diǎn)連線的夾角越小，構(gòu)造的方向趨向函數(shù)值越大，就能獲得較高的獎(jiǎng)勵(lì)，無人機(jī)將跳過向其他方向的移動(dòng)，并且從開始位置到目標(biāo)位置的整個(gè)移動(dòng)過程都會(huì)重復(fù)這種狀態(tài)，此過程將引導(dǎo)無人機(jī)朝著目標(biāo)方向搜索，減少計(jì)算路徑和到達(dá)目的地的時(shí)間。

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

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

圖4 起點(diǎn)與待選節(jié)點(diǎn)直線和目標(biāo)點(diǎn)直線之間的夾角Fig.4 Angle between starting point and straight line of selected node and straight line of target point

式（12）中兩個(gè)向量夾角值越小，余弦值越大，表明無人機(jī)動(dòng)作方向靠近目標(biāo)方向，能獲得更大的獎(jiǎng)勵(lì)，于是構(gòu)造方向趨向函數(shù)：

其中，q為方向趨向因子，D為當(dāng)前待選節(jié)點(diǎn)到目標(biāo)狀態(tài)的歐式距離在Q值初始化過程中，利用si處的方向函數(shù)值來初始化狀態(tài)價(jià)值函數(shù)V(si)，并通過式（14）行為價(jià)值函數(shù)和狀態(tài)價(jià)值函數(shù)之間的關(guān)系來實(shí)現(xiàn)Q值的初始化，即：

4 算法實(shí)現(xiàn)步驟與實(shí)驗(yàn)

4.1 算法步驟

結(jié)合了目標(biāo)方向和MO-SP策略的災(zāi)后室內(nèi)無人機(jī)強(qiáng)化學(xué)習(xí)航跡規(guī)劃策略的實(shí)施過程如下：

步驟1已知起點(diǎn)和終點(diǎn)坐標(biāo)的條件下，根據(jù)起點(diǎn)和終點(diǎn)連線位置關(guān)系，確定所連直線經(jīng)過的主要障礙物，判斷主要障礙物周圍的節(jié)點(diǎn)相對(duì)于障礙物的位置關(guān)系，當(dāng)時(shí)，則為環(huán)繞主要障礙物的節(jié)點(diǎn)。

步驟2在初始狀態(tài)下，根據(jù)起點(diǎn)和終點(diǎn)的位置確定目標(biāo)點(diǎn)所在方向，實(shí)現(xiàn)對(duì)環(huán)境先驗(yàn)信息的初始化。

步驟3利用環(huán)境狀態(tài)值函數(shù)更新Q(s,a)。

步驟4無人機(jī)采取可變貪心法則，每移動(dòng)一步就更新一組Q()s,a，直到搜索到目標(biāo)點(diǎn)，再進(jìn)行多次迭代達(dá)到穩(wěn)定的收斂值。

4.2 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文優(yōu)化的強(qiáng)化學(xué)習(xí)方法在路徑規(guī)劃中的有效性，在三維柵格地圖中對(duì)所優(yōu)化的強(qiáng)化學(xué)習(xí)算法進(jìn)行實(shí)驗(yàn)。在本實(shí)驗(yàn)中，考慮一架無人機(jī)、一個(gè)目標(biāo)點(diǎn)，并且考慮無人機(jī)可向任意方向移動(dòng)。本實(shí)驗(yàn)柵格地圖尺度為90×60×50柵格，實(shí)驗(yàn)搭建的三維模型如圖5所示，為了更接近真實(shí)室內(nèi)環(huán)境，環(huán)境中隨機(jī)設(shè)置障礙物。無人機(jī)的起始位置為（6，54，0），目標(biāo)點(diǎn)的位置為（78，30，18），將目標(biāo)點(diǎn)設(shè)置在遠(yuǎn)離邊界的位置，以防止某些實(shí)驗(yàn)性事故的發(fā)生。

圖5 三維環(huán)境模型Fig.5 Three-dimensional environment model

算法中相關(guān)參數(shù)設(shè)置如下：算法最大迭代次數(shù)max_iteration=1 500,學(xué)習(xí)率?=0.1，折扣因子γ=0.96,貪婪度ε設(shè)置為0.8；設(shè)置回報(bào)函數(shù)Rt=100，對(duì)于即時(shí)獎(jiǎng)勵(lì)r值的設(shè)置，可通過以下式子：

其中，δ、τ是參數(shù)，本實(shí)驗(yàn)中設(shè)置δ為10，設(shè)置τ為40；dt為當(dāng)前狀態(tài)與目標(biāo)點(diǎn)之間的距離，dt+1為下一個(gè)無人機(jī)位置到目標(biāo)點(diǎn)的距離，d0為無人機(jī)與障礙物之間的距離。

4.2.1算法有效性驗(yàn)證

為了評(píng)估所提出算法的性能，評(píng)估了在每個(gè)情節(jié)中找到目標(biāo)的收斂時(shí)間、路徑長度等評(píng)價(jià)因素，并對(duì)獲得的結(jié)果進(jìn)行了比較和討論。在這項(xiàng)研究中，進(jìn)行了三組實(shí)驗(yàn)，分別是經(jīng)典Q學(xué)習(xí)算法，記為C-Q算法，引入目標(biāo)方向的Q學(xué)習(xí)算法，記為T-Q算法，以及基于目標(biāo)方向和MO-SP的綜合改進(jìn)Q學(xué)習(xí)算法，記為A-Q算法。為了消除隨機(jī)誤差對(duì)結(jié)果的影響，每種算法在實(shí)驗(yàn)環(huán)境中多次運(yùn)行后取切尾均值，然后將三種算法的結(jié)果進(jìn)行比較以驗(yàn)證算法的有效性。每種算法達(dá)到目標(biāo)所規(guī)劃的路徑和算法的收斂情況分別顯示在圖6和圖7中，結(jié)果記錄在表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算法經(jīng)過948次的迭代才收斂到目標(biāo)點(diǎn)，但在學(xué)習(xí)初期，無人機(jī)需要超過4 000次的嘗試才能找到到達(dá)目標(biāo)位置的路徑。這是因?yàn)樗惴ǖ某跏茧A段，Q值初始化為0，使得沒有經(jīng)驗(yàn)的無人機(jī)只能隨機(jī)選取動(dòng)作，從而使算法的收斂速度很慢。圖7（b）是在C-Q算法基礎(chǔ)上計(jì)入了目標(biāo)方向策略的T-Q算法，通過仿真結(jié)果可知，T-Q算法在經(jīng)過547次迭代收斂于目標(biāo)。在學(xué)習(xí)初期，找到目標(biāo)位置的路徑所需要的嘗試次數(shù)為252次，遠(yuǎn)低于C-Q算法；同時(shí)，算法從起始位置到目標(biāo)方向的收斂時(shí)間相比于C-Q算法減少95.45%，這是因?yàn)镼值初始化時(shí)無人機(jī)就有一個(gè)朝著目標(biāo)的方向，從而避免搜索與無人機(jī)終點(diǎn)方向無關(guān)的節(jié)點(diǎn)，減少了額外的時(shí)間開銷；由于減少了不必要方向的搜索，T-Q算法所得的路徑長度比C-Q算法降低了59.87%，且從圖6可知，T-Q算法的搜索路徑圖比C-Q算法更符合任務(wù)要求。上述分析表明引入方向目標(biāo)策略能夠在學(xué)習(xí)初期引導(dǎo)無人機(jī)快速收斂，并縮短學(xué)習(xí)時(shí)間和路徑長度，從而提高收斂速度。由圖7（c）可知，在學(xué)習(xí)初始階段，無人機(jī)到達(dá)目標(biāo)位置的嘗試次數(shù)較T-Q算法有略微的增加，但A-Q算法在經(jīng)過307次的迭代后就能收斂于目標(biāo)點(diǎn)。與圖7（b）仿真結(jié)果比較可知，在目標(biāo)方向的基礎(chǔ)上，對(duì)環(huán)境進(jìn)行MO-SP策略，使算法的收斂時(shí)間較T-Q算法減少了68.61%，空間搜索節(jié)點(diǎn)減少了55.49%，同時(shí)路徑長度也得到了進(jìn)一步的減少。集成后的算法能更進(jìn)一步提高算法初始階段的學(xué)習(xí)效率，改善無人機(jī)路徑規(guī)劃強(qiáng)化學(xué)習(xí)算法的性能。

4.2.2算法適應(yīng)性驗(yàn)證

為了確定本文優(yōu)化算法的適應(yīng)性，在不同的起始位置點(diǎn)和障礙物中進(jìn)行了三組實(shí)驗(yàn)，設(shè)置每組實(shí)驗(yàn)的目標(biāo)點(diǎn)坐標(biāo)均為（84，30，18），每次實(shí)驗(yàn)運(yùn)行多次并取結(jié)果的切尾均值。圖8顯示了三組實(shí)驗(yàn)的路徑規(guī)劃圖。其中地圖a與地圖b為相同起點(diǎn)和終點(diǎn)條件下不同障礙物環(huán)境，地圖a與地圖c障礙物位置相同而起點(diǎn)位置不同，結(jié)果比較見表2。根據(jù)表2結(jié)果可知，本文優(yōu)化的Q-learning算法在不同場景中具有良好的適應(yīng)性。

圖8 不同環(huán)境中優(yōu)化Q-learning航跡規(guī)劃圖Fig.8 Optimized Q-learning trajectory planning diagram in different environments

表2 不同環(huán)境中優(yōu)化Q-learning的性能比較Table 2 Performance comparison of optimized Q-learning in different environments

5 結(jié)束語

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