基于深度強(qiáng)化學(xué)習(xí)的三維路徑規(guī)劃算法

黃東晉 ，蔣晨鳳 ，韓凱麗

1.上海大學(xué) 上海電影學(xué)院，上海 200072

2.上海電影特效工程技術(shù)研究中心，上海 200072

1 引言

三維路徑規(guī)劃算法是人工智能領(lǐng)域的一個(gè)極其重要的研究內(nèi)容，該算法被應(yīng)用到許多領(lǐng)域，包括：移動(dòng)機(jī)器人導(dǎo)航、車輛導(dǎo)航以及3D游戲。三維路徑規(guī)劃是指智能體在具有障礙物的虛擬環(huán)境中，按照預(yù)定義的評價(jià)指標(biāo)，找到一條從起點(diǎn)到目標(biāo)點(diǎn)無碰撞的較優(yōu)路線。在虛擬環(huán)境中進(jìn)行路徑規(guī)劃是十分必要的，對于機(jī)器人導(dǎo)航及車輛導(dǎo)航領(lǐng)域，可以降低后期真正投入使用的風(fēng)險(xiǎn)；對于3D游戲開發(fā)領(lǐng)域，可以進(jìn)一步提高智能體模擬人類的決策行為從而增加可玩性。

現(xiàn)有的路徑規(guī)劃方法有基于采樣的算法、基于節(jié)點(diǎn)的算法、基于數(shù)學(xué)模型的算法、基于生物啟發(fā)式的算法等。這些算法在已知的靜態(tài)環(huán)境中都具有較強(qiáng)的搜索能力，但不能很好地適應(yīng)復(fù)雜未知的三維環(huán)境。針對這一問題，研究人員將深度學(xué)習(xí)（DL）與強(qiáng)化學(xué)習(xí)（RL）進(jìn)行融合，提出了深度強(qiáng)化學(xué)習(xí)（DRL）[1-3]。其中，深度學(xué)習(xí)主要通過損失函數(shù)增強(qiáng)對環(huán)境狀態(tài)的感知，強(qiáng)化學(xué)習(xí)主要通過獎(jiǎng)勵(lì)函數(shù)完成決策實(shí)現(xiàn)狀態(tài)到動(dòng)作的映射，從而實(shí)現(xiàn)智能體在復(fù)雜環(huán)境中不依賴地圖信息進(jìn)行運(yùn)動(dòng)的需求。

本文針對三維環(huán)境的復(fù)雜特點(diǎn)和深度強(qiáng)化學(xué)習(xí)算法的優(yōu)勢，將長短時(shí)記憶網(wǎng)絡(luò)（Long Short-Term Memory，LSTM）引入近端策略優(yōu)化算法（Proximal Policy Optimization algorithm，PPO）[4-5]并應(yīng)用于三維路徑規(guī)劃中。為了評估本文方法的有效性，搭建了包含靜態(tài)和動(dòng)態(tài)的多類型障礙物的三維仿真環(huán)境進(jìn)行實(shí)驗(yàn)，通過與傳統(tǒng)算法對比進(jìn)一步驗(yàn)證了本文方法在路線選擇上更智能更合理。

2 相關(guān)工作

2.1 傳統(tǒng)的三維路徑規(guī)劃算法

近些年，由于各領(lǐng)域?qū)θS路徑規(guī)劃的虛擬仿真測試需求迫切，越來越多的研究人員開始研究三維路徑規(guī)劃算法。A*算法[6]被認(rèn)為是二維路徑規(guī)劃技術(shù)中最高效的一種算法，但它不能很好地適用于三維場景，因?yàn)槠溆?jì)算量非常大，效率較低。

目前主流的路徑規(guī)劃研究方法有：D*算法[7]、人工勢場法[8]、遺傳算法[9]、RRT 算法[10]、蟻群算法[11]等，也有研究人員從圖形學(xué)的角度[12]更改空間搜索的方法來完成三維路徑規(guī)劃。但是，這些方法都有一定的局限性，例如D*算法是一種適合動(dòng)態(tài)求解最短路徑的方法，但是在場景大距離遠(yuǎn)的環(huán)境下效果較差；人工勢場法計(jì)算量較小且路徑平滑，但是存在易于陷入局部最優(yōu)解或震蕩導(dǎo)致智能體不能到達(dá)目標(biāo)點(diǎn)的問題；遺傳算法的單一編碼不能完整地表達(dá)環(huán)境約束，不適宜規(guī)模較大的三維路徑規(guī)劃問題；RRT算法的復(fù)雜度與空間維數(shù)和環(huán)境大小基本無關(guān)比較適合高維空間，但是它存在狹長處難采樣，軌跡曲折等缺點(diǎn)；蟻群算法雖然提高了全局搜索的能力但是存在收斂速度慢的缺點(diǎn)。

2.2 基于深度強(qiáng)化學(xué)習(xí)的路徑規(guī)劃算法

強(qiáng)化學(xué)習(xí)是一種通過獎(jiǎng)懲來學(xué)習(xí)正確行為的機(jī)制，不需要環(huán)境和智能體自身的先驗(yàn)知識(shí)，按照學(xué)習(xí)方法可以分成兩類：基于價(jià)值和基于策略。傳統(tǒng)的基于價(jià)值的強(qiáng)化學(xué)習(xí)算法有：Q-Learning和Sarsa，這兩個(gè)算法都局限于離散的較小的動(dòng)作和樣本空間，不適合連續(xù)控制任務(wù)。將傳統(tǒng)的Q-Learning結(jié)合深度學(xué)習(xí)產(chǎn)生Deep Q Network（DQN），通過經(jīng)驗(yàn)回放池與目標(biāo)網(wǎng)絡(luò)成功將深度學(xué)習(xí)算法與強(qiáng)化學(xué)習(xí)算法相結(jié)合，改進(jìn)了Q-Learning依靠表格存儲(chǔ)狀態(tài)導(dǎo)致內(nèi)存不夠及不適宜在連續(xù)空間學(xué)習(xí)的問題。除了DQN算法，具有代表性的深度強(qiáng)化學(xué)習(xí)方法還有Policy Gradient。研究人員又結(jié)合DQN和Policy Gradient各自的優(yōu)勢提出了經(jīng)典的Actor-Critic算法。之后，通過不斷改進(jìn)Actor-Critic算法不能很好地預(yù)測連續(xù)動(dòng)作的問題，提出了DDPG、A3C、TRPO以及PPO等算法。其中PPO算法是現(xiàn)在OpenAI默認(rèn)的方法，效果較優(yōu)。

目前深度強(qiáng)化學(xué)習(xí)受到國內(nèi)外廣泛的關(guān)注，出現(xiàn)大量與之相關(guān)的路徑規(guī)劃的研究成果：

在機(jī)器人導(dǎo)航領(lǐng)域，Tai等人[13]通過訓(xùn)練DQN，讓移動(dòng)機(jī)器人在虛擬環(huán)境中不斷試錯(cuò)，最終能夠在未知環(huán)境下獲得較好的路徑結(jié)果；Zhu等人[14]通過Actor-Critic模型解決了DRL缺乏對新目標(biāo)的泛化能力并且提出AI2-THOR框架，改善了DRL無法從模擬環(huán)境轉(zhuǎn)移到真實(shí)世界的問題，實(shí)現(xiàn)了移動(dòng)機(jī)器人在房間中自行找到指定物品；王珂等人[15]提出基于最小深度信息有選擇的訓(xùn)練模式，并結(jié)合A3C算法對機(jī)器人進(jìn)行訓(xùn)練，提高了機(jī)器人在未知復(fù)雜環(huán)境下的尋路能力。

在車輛導(dǎo)航領(lǐng)域，Wulfmeier等人[16]提出一個(gè)基于最大熵的非線性逆強(qiáng)化學(xué)習(xí)（IRL）框架，更準(zhǔn)確地處理環(huán)境中的拐角情況，如樓梯、斜坡和地下通道；徐國艷等人[17]提出了一種基于改進(jìn)DDPG算法的無人車智能避障方法，實(shí)現(xiàn)轉(zhuǎn)向盤轉(zhuǎn)角和加速度的連續(xù)輸出，最終在TORCS平臺(tái)進(jìn)行駕駛模擬。

在3D游戲領(lǐng)域，Mnih等人[3]首次提出了端到端的深度學(xué)習(xí)模型，訓(xùn)練智能體玩Atari2600游戲，算法有效且智能體玩游戲的能力甚至超越人類。Zambaldi等人[18]使用自注意力來推斷環(huán)境中各實(shí)體間的關(guān)系，最終成功運(yùn)用深度強(qiáng)化學(xué)習(xí)方法完成了“方塊世界”的路線探索任務(wù)。

但是目前基于深度強(qiáng)化學(xué)習(xí)的三維路徑規(guī)劃的研究主要集中在避障策略，對于各類障礙物均采用相同的方式進(jìn)行避讓，與實(shí)際路線選擇仍有偏差。

3 近端策略優(yōu)化算法

近端策略優(yōu)化算法[4]是2017年由OpenAI提出的一種較好的深度強(qiáng)化學(xué)習(xí)算法。同年，Deepmind通過訓(xùn)練PPO實(shí)現(xiàn)了智能體在沒有特殊指示的情況下探索出復(fù)雜技能[5]，進(jìn)一步證明PPO算法可以較好地應(yīng)用于連續(xù)控制及連續(xù)性情節(jié)的任務(wù)上。

PPO是一種新型的策略梯度算法（Policy Gradient，PG）。PG算法的主要思想是使用梯度提升的方法更新策略π從而最大化期望獎(jiǎng)勵(lì)。在PG算法中，網(wǎng)絡(luò)參數(shù)θ更新的目標(biāo)函數(shù)為：

PG算法的最大優(yōu)勢是可以在連續(xù)空間中選擇動(dòng)作，缺點(diǎn)是它對步長敏感卻很難選擇合適的步長。為了改進(jìn)該缺點(diǎn)，首先采用當(dāng)前策略下的行動(dòng)概率πθ(a|s)與上一個(gè)策略的行動(dòng)概率πθold(a|s)比來觀察智能體行動(dòng)的效果，即新舊策略的比值記為：

若獎(jiǎng)勵(lì)函數(shù)rt(θ)>1，表明在該策略下動(dòng)作發(fā)生的概率高于先前策略，若0

其次，為了避免在參數(shù)更新的過程中出現(xiàn)策略突變的情況，則需對目標(biāo)函數(shù)（公式（3））進(jìn)行約束。PPO算法通過將策略更新約束在小范圍內(nèi)來提高訓(xùn)練智能體行為時(shí)的穩(wěn)定性。PPO算法采用的約束方式有兩種：限制KL散度或截?cái)?。在?shí)際應(yīng)用中，研究人員發(fā)現(xiàn)使用截?cái)嗟姆椒ㄐЧ?，則PPO的目標(biāo)函數(shù)優(yōu)化為：

其中，ε為截?cái)喑?shù)用來輔助設(shè)定策略更新的范圍，通常設(shè)置為0.1或0.2；clip函數(shù)為截?cái)嗪瘮?shù)，將新舊策略參數(shù)rt(θ)的值限定在[ ]1-ε,1+ε區(qū)間，如圖1所示。目標(biāo)函數(shù)使用min函數(shù)表示選取新舊策略概率比與截?cái)嗪瘮?shù)中較小的值。

當(dāng)優(yōu)勢函數(shù)A為正時(shí)，表示當(dāng)前行動(dòng)對優(yōu)化目標(biāo)有積極效果，則應(yīng)增加其出現(xiàn)的概率，但同時(shí)要限制其更新范圍在1+ε以下。當(dāng)A為負(fù)時(shí)，表示當(dāng)前行為是消極的，則應(yīng)被阻止同時(shí)降低其概率到1-ε。

PPO算法的核心思想是避免采用大的策略更新，解決PG算法中步長難以確定和數(shù)據(jù)效率低的問題，并且大大降低研究人員調(diào)試的難度。

4 本文算法

本文主要目標(biāo)是：智能體在規(guī)定步長內(nèi)找到到達(dá)目標(biāo)位置的合理路徑。所謂合理是指區(qū)別處理不同高度的障礙物，使得智能體行為路徑趨近現(xiàn)實(shí)。對于高度小于閾值的障礙物（即低矮障礙）視為可通行的并采用跳躍的形式通過，對于高度大于閾值的障礙視為需避開并采用繞行的方式通過。

本文將PPO算法用于多障礙未知環(huán)境下的三維路徑規(guī)劃任務(wù)。訓(xùn)練過程由初始化、執(zhí)行動(dòng)作、獲取獎(jiǎng)勵(lì)和訓(xùn)練決策四個(gè)階段構(gòu)成，如圖2所示。

圖2 智能體訓(xùn)練過程示意圖

首先，設(shè)計(jì)了合理的環(huán)境狀態(tài)及動(dòng)作狀態(tài)，智能體利用激光探測環(huán)境信息并收集數(shù)據(jù)，然后將這些數(shù)據(jù)作為特征向量結(jié)合獎(jiǎng)勵(lì)函數(shù)輸入至神經(jīng)網(wǎng)絡(luò)中進(jìn)行訓(xùn)練，最后根據(jù)探索策略選擇最優(yōu)動(dòng)作并輸出到達(dá)下一個(gè)可視的觀察。不斷循環(huán)迭代執(zhí)行動(dòng)作、獲取獎(jiǎng)勵(lì)和訓(xùn)練決策三個(gè)階段直到訓(xùn)練完成。

4.1 狀態(tài)空間與動(dòng)作空間

智能體的環(huán)境模型要考慮目標(biāo)位置、邊界信息還要考慮障礙物的高度和所在位置才能采取合理的行為避免碰撞。本文仿真環(huán)境中設(shè)置了多種障礙物且高度在一定范圍內(nèi)隨機(jī)變化。由于連續(xù)高維空間的狀態(tài)及動(dòng)作數(shù)量巨大使得算法較難收斂，因而將智能體周圍障礙物等信息離散成有限個(gè)狀態(tài)，合理地制定狀態(tài)空間。訓(xùn)練中，需要觀測的環(huán)境信息包括：目標(biāo)點(diǎn)和智能體相對預(yù)設(shè)地面的空間位置，以及當(dāng)前智能體是否在地面上。其次，智能體擁有n條3D測距射線，每條射線的最遠(yuǎn)測距dmax相同，通過射線感知收集障礙物信息(di,aθ,ftype,ho)，其中di和aθ分別表示射線被障礙物阻擋時(shí)的長度與夾角，ftype表示射線所觸障礙的類型，ho表示該障礙的高度。總的來說，環(huán)境狀態(tài)應(yīng)該包括智能體瞬時(shí)速度(vsx,vsy,vsz)、所在位置(psx,psy,psz)、目標(biāo)點(diǎn)所在位置(pgx,pgy,pgz)、障礙物所在位置(pox,poy,poz)以及射線信息，則狀態(tài)可以定義為：

由于智能體在仿真環(huán)境中觀測的障礙物數(shù)量是未知的、非固定的，因而本文在PPO算法的基礎(chǔ)上，向環(huán)境感知端引入長短時(shí)記憶網(wǎng)絡(luò)，如圖3所示，其中虛線框內(nèi)為LSTM網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)。LSTM是一種循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，可處理的連續(xù)數(shù)據(jù)信息。首先，智能體將每個(gè)狀態(tài)向量si（公式（5））依次輸入到LSTM網(wǎng)絡(luò)，通過遺忘門選擇要記憶的先前信息的數(shù)量。其次，通過輸入門存儲(chǔ)當(dāng)前信息中的有效信息。然后，通過輸出門輸出有效信息并存儲(chǔ)到隱藏狀態(tài)中。最后，通過最終隱藏狀態(tài)將智能體的整個(gè)狀態(tài)編碼成固定長度的向量輸入至PPO網(wǎng)絡(luò)中。

圖3 環(huán)境感知模型結(jié)構(gòu)

本文采用離散矢量動(dòng)作空間定義了四個(gè)動(dòng)作，分別是前向運(yùn)動(dòng)、側(cè)向運(yùn)動(dòng)、旋轉(zhuǎn)以及跳躍。其中，前向運(yùn)動(dòng)包含三種可能行為：前進(jìn)、后退、無動(dòng)作；側(cè)向運(yùn)動(dòng)包括三種可能行為：左移、右移、無動(dòng)作；旋轉(zhuǎn)也包含三種可能的行為：左轉(zhuǎn)、右轉(zhuǎn)、無動(dòng)作；跳躍則包含兩種可能行為：跳躍、無動(dòng)作。每次智能體決定是否跳躍時(shí)需要滿足以下兩個(gè)條件：

（1）智能體必須靠近障礙物的前部，且障礙物的高度不得高于智能體高度的2倍。

（2）智能體在地面上或在障礙物頂面。

4.2 獎(jiǎng)懲函數(shù)

深度強(qiáng)化學(xué)習(xí)算法中，所有目標(biāo)都可以通過預(yù)期累積獎(jiǎng)勵(lì)的最大化來描述。智能體可以通過與環(huán)境互動(dòng)得到的反饋信號(hào)來學(xué)習(xí)正確的策略。每次實(shí)驗(yàn)都包含許多學(xué)習(xí)回合，當(dāng)智能體出界或者在規(guī)定步長內(nèi)未到達(dá)目的地時(shí)結(jié)束該回合的學(xué)習(xí)。為了避免由于稀疏獎(jiǎng)勵(lì)導(dǎo)致學(xué)習(xí)效率低的問題，本文在主線獎(jiǎng)勵(lì)基礎(chǔ)上進(jìn)行獎(jiǎng)勵(lì)重塑，增加外部獎(jiǎng)勵(lì)機(jī)制以及好奇心驅(qū)動(dòng)[19]來提高訓(xùn)練效率和最終性能。

本文懲罰值在?1至0之間，獎(jiǎng)勵(lì)值在0至1之間。當(dāng)智能體與障礙物發(fā)生碰撞或出界時(shí)給予懲罰，當(dāng)智能體到低矮障礙前選擇跳躍動(dòng)作時(shí)給予獎(jiǎng)勵(lì)。本文將目標(biāo)劃分為三個(gè)子目標(biāo)：第一、找到一條始于起點(diǎn)止于目標(biāo)點(diǎn)的路線。第二、不碰撞環(huán)境中高于閾值的障礙物。第三、判斷障礙物類型，會(huì)跳躍通過低矮障礙。由此，外部獎(jiǎng)懲函數(shù)設(shè)計(jì)如公式（6）所示，第1行針對主線獎(jiǎng)勵(lì)，第2、3行針對子目標(biāo)1，第4行針對子目標(biāo)2，最后以后針對子目標(biāo)3。除此之外，為了加快智能體訓(xùn)練速度則給智能體每一步的移動(dòng)一個(gè)負(fù)獎(jiǎng)勵(lì)，本文設(shè)置為?0.000 2。

內(nèi)在獎(jiǎng)勵(lì)機(jī)制則是促進(jìn)智能體更加積極地探索環(huán)境以尋找下一個(gè)外在獎(jiǎng)勵(lì)，從而降低因稀疏獎(jiǎng)勵(lì)帶來的學(xué)習(xí)效率低下的問題。

4.3 網(wǎng)絡(luò)結(jié)構(gòu)

訓(xùn)練決策階段主要由策略網(wǎng)絡(luò)和評價(jià)網(wǎng)絡(luò)組成。圖4展示了PPO的網(wǎng)絡(luò)結(jié)構(gòu)，策略網(wǎng)絡(luò)主要作用是決定策略πθ，它包含新舊神經(jīng)網(wǎng)絡(luò)并周期性地更改舊神經(jīng)網(wǎng)絡(luò)，本文策略網(wǎng)絡(luò)設(shè)計(jì)了3個(gè)隱層，每個(gè)隱層的神經(jīng)元是128個(gè)，狀態(tài)s輸入到網(wǎng)絡(luò)中，通過不同的激活函數(shù)預(yù)測合適的均值和方差，確定正態(tài)分布，通過該分布選擇智能體即將采取的動(dòng)作。評價(jià)網(wǎng)絡(luò)根據(jù)以往數(shù)據(jù)評價(jià)策略網(wǎng)絡(luò)的性能指導(dǎo)策略網(wǎng)絡(luò)更新參數(shù)，本文評價(jià)網(wǎng)絡(luò)同樣設(shè)計(jì)了3個(gè)隱層，每個(gè)隱層有128個(gè)節(jié)點(diǎn)，狀態(tài)s輸入到網(wǎng)絡(luò)中后輸出狀態(tài)值函數(shù)v，其中狀態(tài)值函數(shù)表示在當(dāng)前狀態(tài)下執(zhí)行該策略獲得的累計(jì)獎(jiǎng)勵(lì)。

圖4 PPO網(wǎng)絡(luò)結(jié)構(gòu)

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

本文在Unity3D引擎上進(jìn)行仿真實(shí)驗(yàn)。進(jìn)行智能體訓(xùn)練的電腦配置如下：硬件環(huán)境為Intel?Xeon?CPU E5-2620 v4@2.10 GHz的處理器，內(nèi)存64 GB，顯卡NVIDIA TITAN Xp，軟件環(huán)境為Unity 2018.3.1f1。

本文設(shè)計(jì)了兩個(gè)實(shí)驗(yàn)來驗(yàn)證算法的有效性：

實(shí)驗(yàn)1基于LSTM-PPO算法的三維路徑規(guī)劃仿真實(shí)驗(yàn)。

實(shí)驗(yàn)2本文算法與傳統(tǒng)算法的對比實(shí)驗(yàn)。

5.1 仿真實(shí)驗(yàn)

5.1.1 環(huán)境模型與訓(xùn)練參數(shù)

本文設(shè)計(jì)的基礎(chǔ)訓(xùn)練仿真環(huán)境具有一定的代表性，如圖5所示。整體實(shí)驗(yàn)環(huán)境為2.5 m×6.0 m，其中障礙物類型 ftype包括2種：低矮障礙以及可移動(dòng)墻體，4個(gè)低矮障礙高度在（0 m，0.25 m）內(nèi)隨機(jī)產(chǎn)生，可移動(dòng)墻體高度為1.2 m，訓(xùn)練中隨機(jī)進(jìn)行前后左右移動(dòng)，移動(dòng)距離不超過0.15 m。實(shí)驗(yàn)將地面中心定為原點(diǎn)（0，0，0），智能體相對地面的起點(diǎn)坐標(biāo)（?8.2，1，?20.1），目標(biāo)點(diǎn)為（0.7，1，20）。本實(shí)驗(yàn)中智能體是邊長0.1 m的立方體，質(zhì)量25 kg，跳躍阻力3 N，初始移動(dòng)速度為1.5 m/s，每次跳躍狀態(tài)持續(xù)時(shí)間為0.2 s，最大跳躍高度為0.375 m。

圖5 單個(gè)智能體的基礎(chǔ)訓(xùn)練環(huán)境

實(shí)驗(yàn)采用連續(xù)觀察向量空間，利用特征向量表示智能體在每一步的觀察結(jié)果。訓(xùn)練中，需要觀察目標(biāo)點(diǎn)和智能體相對地面的位置。設(shè)置射線角度為{0，20，45，70，90，110，135，160，180}，射線的最遠(yuǎn)測距 dmax=1.5 m ，通過兩組射線收集障礙信息，獲取附近障礙相對智能體的距離、夾角以及該障礙的種類和高度。本文實(shí)驗(yàn)觀測記錄的空間大小為112個(gè)。

每個(gè)智能體都按照本文所提出的方法不斷地學(xué)習(xí)探索，訓(xùn)練過程中，始終遵循公式（6）進(jìn)行一定的獎(jiǎng)懲。在每一回合規(guī)定的最大步長內(nèi)未到達(dá)目的地則?0.5，到達(dá)目的地則+1.0。每一回合結(jié)束或出現(xiàn)出界的情況則整個(gè)場景復(fù)位。為了加快訓(xùn)練速度提高訓(xùn)練效果采用多智能體并行訓(xùn)練，雖然10個(gè)智能體是獨(dú)立的個(gè)體，但是它們具有相似的觀測和動(dòng)作。本實(shí)驗(yàn)總訓(xùn)練次數(shù)為1.5×106次，PPO參數(shù)設(shè)置如表1所示。

表1 PPO算法參數(shù)

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

經(jīng)過8.36 h的訓(xùn)練后，智能體成功從起點(diǎn)出發(fā)運(yùn)動(dòng)到目標(biāo)點(diǎn)。圖5展示了訓(xùn)練過程中智能體的路線圖。圖6展示了訓(xùn)練過程中獎(jiǎng)勵(lì)變化情況。

圖6（a）～（d）分別為訓(xùn)練第2 000、22 000、60 000與240 000次的結(jié)果。圖6（a）為訓(xùn)練初期，智能體還沒有充分地學(xué)習(xí)，隨機(jī)概率較大，此時(shí)累計(jì)獎(jiǎng)勵(lì)值很低，僅?0.636。圖6（b）依舊處于探索階段，智能體經(jīng)常碰撞低矮障礙物而不會(huì)跳躍通過，到達(dá)目標(biāo)點(diǎn)的次數(shù)極少，該階段的累計(jì)獎(jiǎng)勵(lì)值僅?0.169。圖6（c）中智能體成功越過第一個(gè)低矮障礙但碰撞第二個(gè)低矮障礙，該階段的累計(jì)獎(jiǎng)勵(lì)值為0.322。隨著訓(xùn)練次數(shù)的增加，經(jīng)過大量“試錯(cuò)”后，智能體逐漸由探索環(huán)境的狀態(tài)變?yōu)槔弥R(shí)的狀態(tài)，成功率迅速提高。圖6（d）為訓(xùn)練中后期，智能體已經(jīng)能夠成功到達(dá)目的地，但軌跡選擇不穩(wěn)定，此階段的獎(jiǎng)勵(lì)值為0.548。隨著時(shí)間的增加，路徑軌跡不斷優(yōu)化，長度縮小。

圖7中淺色線條表示獎(jiǎng)勵(lì)值，深色線條表示平均獎(jiǎng)勵(lì)值。圖7所示隨著訓(xùn)練次數(shù)不斷增大，智能體所獲獎(jiǎng)勵(lì)值也不斷增加且逐漸趨近1.0。實(shí)驗(yàn)結(jié)果表明智能體已經(jīng)能夠根據(jù)前方障礙物類型采取不同策略，成功到達(dá)終點(diǎn)，完成三維路徑規(guī)劃任務(wù)。

圖6 本文算法訓(xùn)練過程中的智能體路線圖

圖7 訓(xùn)練過程中的獎(jiǎng)勵(lì)值

在相同實(shí)驗(yàn)環(huán)境中，本文將獎(jiǎng)勵(lì)函數(shù)分為三種情況進(jìn)行對比：第一、僅有主線獎(jiǎng)勵(lì)，第二、主線獎(jiǎng)勵(lì)結(jié)合外部獎(jiǎng)勵(lì)，第三、在第二種基礎(chǔ)上增加內(nèi)在獎(jiǎng)勵(lì)。僅有主線獎(jiǎng)勵(lì)時(shí)，實(shí)驗(yàn)失敗，智能體未能在規(guī)定步長內(nèi)到達(dá)終點(diǎn)。

圖8中藍(lán)色線表示第二種僅有外部獎(jiǎng)勵(lì)的訓(xùn)練情況，橙色線表示第三種情況。圖中可直觀地看到橙色線條在更少的迭代次數(shù)達(dá)到較優(yōu)的累計(jì)獎(jiǎng)勵(lì)值，在訓(xùn)練130 000次時(shí)累計(jì)獎(jiǎng)勵(lì)就已達(dá)到0.945，而僅有外部獎(jiǎng)勵(lì)的情況下，智能體在訓(xùn)練200 000次時(shí)獎(jiǎng)勵(lì)值達(dá)到0.94。實(shí)驗(yàn)結(jié)果表明增加內(nèi)在獎(jiǎng)勵(lì)對智能體訓(xùn)練更有效率，加快智能體對環(huán)境的探索。

圖8 基于不同獎(jiǎng)勵(lì)函數(shù)的訓(xùn)練情況對比

本文進(jìn)一步在兩類復(fù)雜環(huán)境中進(jìn)行訓(xùn)練來驗(yàn)證算法的有效性，第一類由眾多基本幾何體組合而成，第二類仿真環(huán)境則是山地地形。障礙物包括墻壁、高度隨機(jī)的低矮障礙、平滑的球體障礙、帶棱角的不規(guī)則障礙及樹木等。圖9（a）可見智能體能夠躲避大型的障礙物，越過低于閾值的障礙物。圖9（b）中的樹木均不可碰撞，實(shí)驗(yàn)結(jié)果可見對于路面崎嶇不平的地形，智能體也能夠成功找到目標(biāo)點(diǎn)且整體路徑較合理但是跳躍軌跡不夠優(yōu)化。

圖9 本文方法應(yīng)用于復(fù)雜環(huán)境

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

為了驗(yàn)證本文方法的合理性，將其與三維游戲引擎中最常用的NavMesh方法和二維搜索中較優(yōu)的A*方法進(jìn)行比較，如圖10所示。三個(gè)實(shí)驗(yàn)環(huán)境相同，四個(gè)低矮障礙物的高度分別是：0.05 m，0.2 m，0.1 m，0.05 m，圓球半徑為0.15 m。將從路線選擇及路線長度這兩方面進(jìn)行對比。

圖10 三種路徑規(guī)劃方案路線選擇對比

圖10 （a）中黑色線條表示A*算法的路線圖，A*根據(jù)障礙物分布情況全局規(guī)劃了一條最短路徑，避開了場景中所有的障礙物。圖10（b）所示為Navmesh導(dǎo)航路線圖。Navmesh其實(shí)是使用導(dǎo)航網(wǎng)格將3D搜索空間轉(zhuǎn)換為虛擬2D平面進(jìn)行路線的規(guī)劃。本實(shí)驗(yàn)將所有區(qū)域定為可行走區(qū)域并參與導(dǎo)航烘焙，設(shè)置具有代表性的物體高度為0.2 m，最大可進(jìn)行斜坡度為15°。圖10（b）中智能體直接穿過第一個(gè)和第四個(gè)低矮障礙物，避開其余障礙物，缺陷是速度固定，避障行為單一。圖10（c）所示為本文算法結(jié)果。相比前兩種算法的完全性避障及速度固定，本文算法的避障行為更加智能，對于不同高度障礙采用不同避障策略，路線更加合理。圖11為本次實(shí)驗(yàn)中三種方法的運(yùn)動(dòng)路徑及長度的對比圖，直線線條是A*算法的路徑，總長度為97.85 m，虛線線條是Navmesh算法的路徑總長度為46.42 m，本文算法路徑長度為44.34 m。

圖11 三種路徑規(guī)劃方案路線及長度對比

本文使用新的思路來解決避障問題，對于模擬場景中的不同類型的障礙物，針對性地采用不同的策略進(jìn)行避障。由于智能體采用跳躍行為，本文算法最終計(jì)算得出的路線并不是在任意環(huán)境中都絕對最短，但始終是較為合理的路線選擇。

6 結(jié)論

本文提出了一種基于深度強(qiáng)化學(xué)習(xí)的三維路徑規(guī)劃算法，實(shí)現(xiàn)更合理地選擇路線及避障方法。將改進(jìn)的近端策略優(yōu)化算法用于具有多類型障礙的三維未知環(huán)境中，無需任何先驗(yàn)知識(shí)，智能體經(jīng)過反復(fù)試錯(cuò)找到較優(yōu)的路徑。本文首先采用虛擬射線獲取仿真環(huán)境信息，將連續(xù)狀態(tài)空間離散化輸入至長短時(shí)記憶網(wǎng)絡(luò)，其次，提供了智能體動(dòng)作狀態(tài)，然后，設(shè)置外部獎(jiǎng)懲函數(shù)同時(shí)結(jié)合好奇心驅(qū)動(dòng)促使智能體學(xué)會(huì)處理不同的障礙物。最后，利用PPO截?cái)囗?xiàng)機(jī)制優(yōu)化策略更新的幅度。實(shí)驗(yàn)結(jié)果表明本文算法能夠有效地應(yīng)用在包含復(fù)雜障礙的未知環(huán)境中，學(xué)會(huì)對于不同障礙采用不同的處理方式，且路線更加符合實(shí)際情況。

下一步，將進(jìn)一步完善本文算法，優(yōu)化智能體跳躍軌跡減少跳躍抖動(dòng)，并嘗試用于類人形智能體的三維路徑規(guī)劃中。