閆皎潔，張鍥石，胡希平

（1.中國科學(xué)院深圳先進(jìn)技術(shù)研究院，廣東 深圳 518055；2.中國科學(xué)院大學(xué) 深圳先進(jìn)技術(shù)學(xué)院，廣東 深圳 518055）

0 概述

隨著計(jì)算機(jī)技術(shù)、人工智能技術(shù)及自動(dòng)化控制技術(shù)的發(fā)展，移動(dòng)機(jī)器人的智能化程度不斷提高，路徑規(guī)劃作為實(shí)現(xiàn)機(jī)器人自主導(dǎo)航的核心技術(shù)受到廣泛關(guān)注［1-2］。路徑規(guī)劃就是使目標(biāo)對(duì)象在最小的時(shí)間或距離代價(jià)下，在規(guī)定區(qū)域范圍內(nèi)找到一條從起點(diǎn)到終點(diǎn)的安全無碰撞路徑。目前，路徑規(guī)劃的核心方法［3-4］按其特點(diǎn)及關(guān)鍵技術(shù)可分為常規(guī)方法與強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）方法兩類。常規(guī)方法可分為傳統(tǒng)方法、圖形學(xué)方法及智能仿生學(xué)方法。近年來，又由強(qiáng)化學(xué)習(xí)方法衍生出深度強(qiáng)化學(xué)習(xí)方法，深入研究強(qiáng)化學(xué)習(xí)方法及其衍生方法對(duì)路徑規(guī)劃技術(shù)的發(fā)展有重要的意義。本文簡述基于常規(guī)方法的路徑規(guī)劃技術(shù)，重點(diǎn)分析基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃技術(shù)并將其分為基于值和基于策略兩類，再由強(qiáng)化學(xué)習(xí)引出基于深度強(qiáng)化學(xué)習(xí)的路徑規(guī)劃技術(shù)，同時(shí)對(duì)強(qiáng)化學(xué)習(xí)代表方法的原理、特點(diǎn)、優(yōu)缺點(diǎn)、適用場(chǎng)合及改進(jìn)策略進(jìn)行深入探討。

1 基于常規(guī)方法的路徑規(guī)劃技術(shù)

常規(guī)方法分為傳統(tǒng)方法、圖形學(xué)方法、智能仿生學(xué)方法等3 類：

1）傳統(tǒng)方法主要包括模擬退火法［5］、人工勢(shì)場(chǎng)法［6］和模糊邏輯法［7］。這類方法最早應(yīng)用于路徑規(guī)劃技術(shù)，具有描述簡單、易于實(shí)現(xiàn)的特點(diǎn)，但不能充分利用先驗(yàn)知識(shí)和全局信息，求解時(shí)容易陷入局部最優(yōu)解或遇到目標(biāo)不可達(dá)的問題。

2）圖形學(xué)方法主要包括A*算法［8］、柵格法［9］等。這類方法可提供建模方法，解決了傳統(tǒng)方法建模難的問題，但由于搜索效率低下，導(dǎo)致其難以應(yīng)用在實(shí)際系統(tǒng)中。

3）智能仿生學(xué)方法主要包括遺傳算法［10］、人工神經(jīng)網(wǎng)絡(luò)算法［11］、蟻群算法［12］、粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［13］等。這類方法的原理與自然生物的性質(zhì)或生態(tài)機(jī)制非常接近，如模仿生物遺傳進(jìn)化、人體神經(jīng)網(wǎng)絡(luò)系統(tǒng)、螞蟻覓食等行為，故統(tǒng)稱為智能仿生學(xué)方法。由于仿生特點(diǎn)，這類方法更加智能、效率更高，但在路徑規(guī)劃應(yīng)用中存在容易陷入局部最優(yōu)解、收斂速度慢等問題。

為更加清晰直觀地對(duì)比各類各種常規(guī)方法，表1給出了各種常規(guī)方法的優(yōu)劣勢(shì)對(duì)比結(jié)果。

表1 應(yīng)用于路徑規(guī)劃技術(shù)的常規(guī)方法優(yōu)劣勢(shì)對(duì)比Table 1 Comparison of advantages and disadvantages of conventional approaches applied to path planning techniques

2 基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃技術(shù)

2.1 強(qiáng)化學(xué)習(xí)基本原理與研究歷程

強(qiáng)化學(xué)習(xí)［14-15］的基本原理為智能體在環(huán)境反饋獎(jiǎng)勵(lì)或懲罰的刺激下持續(xù)學(xué)習(xí)，根據(jù)反饋不斷調(diào)整策略，最終達(dá)成獎(jiǎng)勵(lì)最大化或?qū)崿F(xiàn)特定目標(biāo)。強(qiáng)化學(xué)習(xí)方法主要包括狀態(tài)、策略、行動(dòng)、獎(jiǎng)勵(lì)等4 個(gè)要素。智能體在狀態(tài)st下，根據(jù)策略π選擇動(dòng)作at，并從狀態(tài)st轉(zhuǎn)移到新的狀態(tài)st+1，同時(shí)獲得環(huán)境反饋的獎(jiǎng)勵(lì)r，根據(jù)獲得的獎(jiǎng)勵(lì)r獲得最優(yōu)策略π*。

其中：γ?(0，1)為折扣率。

強(qiáng)化學(xué)習(xí)思想最早可追溯到行為心理學(xué)研究。1911年THORNDIKE 提出效果律（Law of Effect）：一定情景下讓動(dòng)物感到舒服的行為，就會(huì)與此情景增強(qiáng)聯(lián)系（強(qiáng)化），當(dāng)此情景再現(xiàn)時(shí)，動(dòng)物的這種行為也更易再現(xiàn)；反之則相反。20 世紀(jì)50 年代中期，最優(yōu)控制理論被提出，基本原理為從控制方案中尋找最佳方案。1956 年BELLMAN［16］提出動(dòng)態(tài)規(guī)劃方法，1977 年WERBOS［17］提出自適應(yīng)動(dòng)態(tài)規(guī)劃方法。直到20世紀(jì)80年代末90年代初，人工智能、機(jī)器學(xué)習(xí)等技術(shù)開始得到廣泛應(yīng)用，強(qiáng)化學(xué)習(xí)開始受到關(guān)注。1988 年SUTTON 等［14］提出時(shí)序差分（Temporal Difference，TD）算法，1992 年WATKINS 等［18］提 出Q-Learning 算 法，1994 年RUMMERY等［19］提出SARAS算法，1995年BERSEKAS等［20］提出解決隨機(jī)過程中優(yōu)化控制的神經(jīng)動(dòng)態(tài)規(guī)劃方法，2006 年KOCSIS 等［21］提出置信上限樹算法，2009 年LEWIS等［22］提出反饋控制自適應(yīng)動(dòng)態(tài)規(guī)劃算法，2014年SILVER 等［23］提出確定性策略梯度（Deterministic Policy Gradient，DPG）算法，2016 年Google DeepMind［24］提出A3C 方法。

2.2 強(qiáng)化學(xué)習(xí)方法分類

求解強(qiáng)化學(xué)習(xí)問題的方法分為基于值、基于策略以及基于值與基于策略相結(jié)合的方法?；谥档姆椒ǘx了值函數(shù)，根據(jù)值函數(shù)的大小選擇動(dòng)作；基于策略的方法將策略進(jìn)行參數(shù)化，通過優(yōu)化參數(shù)使策略的累計(jì)回報(bào)最大。

當(dāng)移動(dòng)機(jī)器人在復(fù)雜未知環(huán)境下進(jìn)行路徑規(guī)劃時(shí)，由于初期探索策略存在盲目性，導(dǎo)致強(qiáng)化學(xué)習(xí)存在收斂速度慢的問題，在機(jī)器人訓(xùn)練過程中需要花費(fèi)大量時(shí)間。此外，隨著環(huán)境復(fù)雜度和系統(tǒng)狀態(tài)維度的增加，需要訓(xùn)練的參數(shù)呈指數(shù)級(jí)增長，因此會(huì)消耗大量訓(xùn)練時(shí)間和存儲(chǔ)空間，最終導(dǎo)致維數(shù)災(zāi)難［25］。此外，強(qiáng)化學(xué)習(xí)的可移植性和通用性差，訓(xùn)練過的機(jī)器人無法直接在新的環(huán)境中按照期望規(guī)劃移動(dòng)。

2.2.1 基于值的強(qiáng)化學(xué)習(xí)方法

基于值的方法主要適用于離散動(dòng)作空間，目標(biāo)是通過最大化每個(gè)狀態(tài)的值函數(shù)來得到最優(yōu)策略。值函數(shù)用來衡量當(dāng)前狀態(tài)下機(jī)器人選擇策略的優(yōu)劣程度。根據(jù)自變量的不同，值函數(shù)可以分為狀態(tài)值函數(shù)V(s)和狀態(tài)-動(dòng)作對(duì)值函數(shù)Q(s，a)，如式（2）和式（3）所示：

從式（2）和式（3）可知：狀態(tài)值函數(shù)是某狀態(tài)下的獎(jiǎng)勵(lì)反饋值，狀態(tài)-動(dòng)作對(duì)值函數(shù)是狀態(tài)-動(dòng)作對(duì)下的獎(jiǎng)勵(lì)反饋值，因此只需最大化值函數(shù)就可達(dá)成最終獎(jiǎng)勵(lì)最大化。基于值的方法主要包括TD［14］、Q-Learning［18］、SARSA［19］、Dyna［26］等方法。

1）TD 算法

TD 算法是一類無模型的強(qiáng)化學(xué)習(xí)算法，從環(huán)境中取樣并學(xué)習(xí)當(dāng)前值函數(shù)的估計(jì)過程，原理為通過借助時(shí)間的差分誤差來更新值函數(shù)，誤差計(jì)算公式和值函數(shù)更新公式分別如式（4）和式（5）所示：

其中：α為學(xué)習(xí)率。

TD 算法基于蒙特卡羅思想和動(dòng)態(tài)規(guī)劃思想，可直接學(xué)習(xí)初始體驗(yàn)，無需環(huán)境動(dòng)態(tài)模型，同時(shí)基于學(xué)習(xí)更新，需等待最終學(xué)習(xí)結(jié)果。NAIR 等［27］提出一種針對(duì)靜態(tài)障礙物路徑規(guī)劃和避障的修正時(shí)序差分算法，降低了TD 算法的計(jì)算復(fù)雜度。MARTIN 等［28］將時(shí)序差分算法的更新過程簡化為高斯回歸過程，提高了機(jī)器人在海洋環(huán)境的路徑規(guī)劃中的數(shù)據(jù)處理效率。

2）Q-Learning 算法

在TD 算法的基礎(chǔ)上，WATKINS 等［18］提 出QLearning 算法。Q-Learning 算法是強(qiáng)化學(xué)習(xí)發(fā)展的里程碑，是基于值的強(qiáng)化學(xué)習(xí)算法中應(yīng)用最廣泛的算法，也是目前應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃最有效的算法之一。Q-Learning 算法屬于在線強(qiáng)化學(xué)習(xí)算法，基本思想為定義一個(gè)狀態(tài)-動(dòng)作對(duì)值函數(shù)Q(s，a)，將某時(shí)刻的數(shù)據(jù)代入式（6）和式（7）中更新值函數(shù)Q(s，a)。

其中：at為學(xué)習(xí)率；δt為誤差；a′為狀態(tài)st+1執(zhí)行的動(dòng)作。

Q-Learning 算法采用離線策略（off-policy）來產(chǎn)生動(dòng)作，根據(jù)該動(dòng)作與環(huán)境的交互得到的下一個(gè)狀態(tài)及獎(jiǎng)勵(lì)來學(xué)習(xí)得到另一個(gè)最優(yōu)的Q(s，a)。目前，關(guān)于Q-Learning 算法的改進(jìn)是學(xué)者們研究的重點(diǎn)方向，主要包括以下4 個(gè)方面：

（1）引入啟發(fā)式思想。啟發(fā)式思想通常是對(duì)某一訓(xùn)練環(huán)節(jié)進(jìn)行趨勢(shì)性啟發(fā)以提高學(xué)習(xí)效率。啟發(fā)式搜索策略具有較強(qiáng)的搜索能力，LI 等［29］在改進(jìn)的Q-Learning 算法中引入了啟發(fā)式搜索策略來加快學(xué)習(xí)過程，通過限制方向角的變化范圍，縮小搜索空間。劉智斌等［30］利用shaping 函數(shù)參與Q 表的更新，對(duì)Q-Learning 的趨勢(shì)性進(jìn)行啟發(fā)，大幅提高收斂效率。JIANG 等［31］提出一種基于經(jīng)驗(yàn)重放和啟發(fā)式知識(shí)的深度Q-Learning 算法來實(shí)現(xiàn)智能機(jī)器人的路徑規(guī)劃。一方面，啟發(fā)式知識(shí)可以指導(dǎo)機(jī)器人的動(dòng)作選擇，減少智能機(jī)器人系統(tǒng)中的隨機(jī)性；另一方面，啟發(fā)式知識(shí)提高了神經(jīng)網(wǎng)絡(luò)的訓(xùn)練效率，使其可以更快地收斂到最優(yōu)的行動(dòng)策略。

（2）引入分層思想。分層強(qiáng)化學(xué)習(xí)［32］致力于將一個(gè)大規(guī)模問題分解為若干個(gè)子問題，以分而治之的思想逐個(gè)解決，分層思想可以很好地解決傳統(tǒng)強(qiáng)化學(xué)習(xí)中的維數(shù)災(zāi)難問題。劉智斌等［30］提出的基于BP 神經(jīng)網(wǎng)絡(luò)的雙層啟發(fā)式強(qiáng)化學(xué)習(xí)算法，引入了雙層強(qiáng)化學(xué)習(xí)模型：第一層為定量層，通過Q-Learning算法訓(xùn)練得到精確結(jié)果；第二層為定性層，具有較好的泛化能力，提供大方向上的預(yù)見。BUITRAGOMARTINEZ 等［33］提出一種基于選擇的雙層QLearning 學(xué)習(xí)方法：第一層用來訓(xùn)練機(jī)器人的基本行為且每一種行為在訓(xùn)練階段相互獨(dú)立；第二層通過訓(xùn)練機(jī)器人并協(xié)調(diào)這些基本行為來解決路徑規(guī)劃問題。劉志榮等［34］建立雙層網(wǎng)絡(luò)結(jié)構(gòu)，使用Q-target神經(jīng)網(wǎng)絡(luò)來計(jì)算目標(biāo)Q 值，減少了目標(biāo)狀態(tài)對(duì)當(dāng)前狀態(tài)的依賴，大幅提高了收斂效率。

（3）引入模糊邏輯思想［35］。在生活中的許多概念都具有模糊性，如遠(yuǎn)和近、快和慢等，模糊邏輯用隸屬度取代布爾數(shù)值來標(biāo)識(shí)程度，在人工智能領(lǐng)域起到了重要的作用。LUVIANO 等［36］將模糊邏輯應(yīng)用于連續(xù)時(shí)間的多智能機(jī)器人路徑規(guī)劃中進(jìn)行以下改進(jìn)：①模糊量化狀態(tài)空間；②將模糊邏輯與WoLFPHC［37］算法結(jié)合，使Q 函數(shù)通過模糊狀態(tài)空間進(jìn)行分離；③將模糊Q-Iteration 模型用于智能體的次優(yōu)策略，解決了傳統(tǒng)Q-Learning 算法的維數(shù)災(zāi)難問題。WEN 等［38］在優(yōu)化的Q-Learning 算法基礎(chǔ)上提出模糊Q-Learning（Fuzzy Q-Learning，F(xiàn)QL）算法并將其應(yīng)用于路徑規(guī)劃的避障問題，進(jìn)一步提高了訓(xùn)練的收斂速度。葛媛等［39］提出一種基于模糊RBF 網(wǎng)絡(luò)的Q-Learning 算法，使模糊神經(jīng)系統(tǒng)具有自適應(yīng)性，對(duì)未知?jiǎng)討B(tài)環(huán)境中移動(dòng)機(jī)器人的自主路徑規(guī)劃具有一定的應(yīng)用價(jià)值。

（4）多算法結(jié)合思想。一個(gè)單獨(dú)的路徑規(guī)劃算法在實(shí)際應(yīng)用中或多或少都存在一定的缺陷，設(shè)計(jì)新的算法難度大，因此可通過多種算法的結(jié)合來解決問題。除上述三大類的改進(jìn)思路外，學(xué)者們還將Q-Learning與其他類型的算法相結(jié)合進(jìn)行優(yōu)化。樸松昊等［40］用遺傳算法初步規(guī)劃出全局最優(yōu)路徑，并結(jié)合Q-Learning算法實(shí)現(xiàn)機(jī)器人的避障行為，兩種算法取長補(bǔ)短，滿足了路徑規(guī)劃的高實(shí)時(shí)性要求。MEERZA 等［41］提出一種基于Q-Learning 和粒子群優(yōu)化的路徑規(guī)劃算法，利用PSO 改進(jìn)Q 表的迭代，在速度和精度上相比單獨(dú)使用這兩種算法性能更優(yōu)。SHI 等［42］將Q-Learning 算法與蟻群算法中的信息素機(jī)制進(jìn)行融合，機(jī)器人之間通過信息素進(jìn)行信息交換，解決了多智能體路徑規(guī)劃中的信息共享問題，并且在Q 值的作用下，機(jī)器人做出狀態(tài)更新和決策選擇。YAO 等［43］在Q-Learning 算法的基礎(chǔ)上，結(jié)合人工勢(shì)場(chǎng)法，以黑洞勢(shì)場(chǎng)為環(huán)境，使機(jī)器人在沒有先驗(yàn)知識(shí)的情況下可跳出局部最優(yōu)解。LIU等［44］將RRT 與Q-Learning 算法進(jìn)行結(jié)合，提出一種基于Q-Learning的分區(qū)啟發(fā)式RRT算法，利用Q-Learning改進(jìn)獎(jiǎng)勵(lì)函數(shù)，獲得全局最優(yōu)路徑，此算法可以獲得更平滑的結(jié)果，并且提高了搜索和避障的能力。為解決Q-Learning 獎(jiǎng)勵(lì)函數(shù)定義寬泛導(dǎo)致學(xué)習(xí)效率低下的問題，王子強(qiáng)等［45］提出一種基于詳細(xì)回報(bào)分類的Q-Learning算法，根據(jù)移動(dòng)機(jī)器人與障礙物間的距離，對(duì)每個(gè)時(shí)刻機(jī)器人獲得的獎(jiǎng)勵(lì)值分配安全等級(jí)，使機(jī)器人學(xué)習(xí)過程的安全等級(jí)更高，選擇的路徑更合理。

3）SARSA 算法

SARSA 算法與Q-Learning 算法相似，也是一種在線強(qiáng)化學(xué)習(xí)算法。區(qū)別在于SARSA 算法采用在線策略（on-policy），迭代的是Q(s，a)的實(shí)際值，誤差計(jì)算公式如下：

由式（8）可知：SARSA 值函數(shù)Q(s，a)的更新涉及到(s，a，r，st+1，at+1)這5 個(gè)部分，它們構(gòu)成了該算法的名字SARSA。

在機(jī)器學(xué)習(xí)中，若智能體在線學(xué)習(xí)且注重學(xué)習(xí)期間所獲獎(jiǎng)勵(lì)，則SARSA 算法的適用性會(huì)更強(qiáng)。SARSA 算法是單步更新算法，即SARSA（0）。在獲得獎(jiǎng)勵(lì)后，僅更新上一步狀態(tài)和動(dòng)作對(duì)應(yīng)的Q 值，但每一步得到的獎(jiǎng)勵(lì)都會(huì)影響最終得到的獎(jiǎng)勵(lì)，因此將此算法優(yōu)化為多步更新的SARSA 算法，即SARSA（λ）。ZOU 等［46］針對(duì)復(fù)雜動(dòng)態(tài)環(huán)境提出一種基于SARSA（λ）優(yōu)化的RRT 路徑規(guī)劃算法，通過該優(yōu)化可增加擴(kuò)展點(diǎn)時(shí)的選擇并減少無效節(jié)點(diǎn)數(shù)，從而提高算法性能。XU 等［47］通過SOM 神經(jīng)網(wǎng)絡(luò)獲得位置信息并產(chǎn)生R 值，再使用SARSA（λ）并基于產(chǎn)生的R 值來更新Q 值，從而使路徑規(guī)劃更加精準(zhǔn)高效。FATHINEZHAD 等［48］提出監(jiān)督模糊SARSA 學(xué)習(xí)算法，將監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的優(yōu)點(diǎn)相結(jié)合，訓(xùn)練找出每個(gè)模糊規(guī)則的最佳動(dòng)作，通過模糊SARSA 學(xué)習(xí)在線微調(diào)模糊控制結(jié)論部分的參數(shù)，減少了學(xué)習(xí)時(shí)間和訓(xùn)練失敗次數(shù)。

SARSA 算法與Q-Learning 算法有相同點(diǎn)但又有所區(qū)別，這兩種算法的相同點(diǎn)包括：（1）在TD 算法的基礎(chǔ)上改進(jìn)；（2）使用ε-greedy 選擇新的動(dòng)作；（3）均為在線強(qiáng)化學(xué)習(xí)算法。這兩種算法的區(qū)別包括：（1）Q-Learning 算法使用off-policy，迭代內(nèi)容為Q(s，a)的最大值；（2）SARSA 算法使用on-policy，迭代內(nèi)容為Q(s，a)的實(shí)際值。

4）Dyna 算法

Dyna 算法并不是一個(gè)具體的強(qiáng)化學(xué)習(xí)算法，而是一類算法框架的總稱。將基于模型的強(qiáng)化學(xué)習(xí)和與模型無關(guān)的強(qiáng)化學(xué)習(xí)相結(jié)合，既從模型中學(xué)習(xí)，也從與環(huán)境交互的經(jīng)驗(yàn)中學(xué)習(xí)，從而進(jìn)行函數(shù)更新。DABOONI 等［49］利用直接啟發(fā)式動(dòng)態(tài)規(guī)劃（Heuristic Dynamic Programming，HDP）改 進(jìn)Dyna 算法，采用HDP 策略學(xué)習(xí)構(gòu)造Dyna-agent，并提出一種新的在線規(guī)劃學(xué)習(xí)算法Dyna-HDP，可以更快得到近似最優(yōu)路徑，并具有一定的穩(wěn)定性。VIET 等［50］將移動(dòng)機(jī)器人的學(xué)習(xí)過程分為兩階段：第一階段通過Dyna-Q 算法加速獲取最優(yōu)策略，并訓(xùn)練機(jī)器人躲避障礙物；第二階段訓(xùn)練機(jī)器人獲得平滑的路徑。該方法能夠有效解決障礙物密集的未知環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃問題。HWANG 等［51］將一種基于樹的自適應(yīng)模型學(xué)習(xí)方法與Dyna-Q 算法相結(jié)合，利用模型訓(xùn)練產(chǎn)生的經(jīng)驗(yàn)加速迭代，訓(xùn)練效率得到明顯提升。

2.2.2 基于策略的強(qiáng)化學(xué)習(xí)方法

基于策略的方法通過直接優(yōu)化策略得到最優(yōu)策略?；诓呗缘姆椒ㄖ饕ú呗蕴荻龋≒olicy Gradient，PG）［52］、模仿學(xué)習(xí)（Imitation Learning，IL）［53］等方法。

1）策略梯度法

策略梯度法是基于策略的算法中最基礎(chǔ)的一種算法［52］，基本思路為通過逼近策略來得到最優(yōu)策略。策略梯度法分為確定性策略梯度法和隨機(jī)性策略梯度法（Stochastic Policy Gradient，SPG）。在確定性策略梯度法中，動(dòng)作被執(zhí)行的概率為1，而在隨機(jī)性策略梯度法中，動(dòng)作以某概率被執(zhí)行。與隨機(jī)性策略梯度法相比，確定性策略梯度法在連續(xù)動(dòng)作空間求解問題中性能更好。假設(shè)需要逼近的策略是π(s，a；θ)，策略π對(duì)參數(shù)θ可導(dǎo)，定義目標(biāo)函數(shù)和值函數(shù)如式（9）和式（10）所示。從初始狀態(tài)s0開始，依據(jù)策略πθ選取動(dòng)作的分布狀態(tài)如式（11）所示。根據(jù)式（9）～式（11）得到的策略梯度公式如式（12）所示。

LIU 等［54］以學(xué)習(xí)曲線理論為基礎(chǔ)，構(gòu)造經(jīng)驗(yàn)池容量變化函數(shù)，在傳統(tǒng)深度確定性策略梯度法（Deep Deterministic Policy Gradient，DDPG）中加入學(xué)習(xí)曲線，從而實(shí)時(shí)調(diào)整回放緩沖容量，改進(jìn)后的算法獎(jiǎng)勵(lì)值更高，學(xué)習(xí)能力更強(qiáng)。PAUL 等［55］將DDPG算法應(yīng)用于機(jī)械臂的路徑規(guī)劃中，即應(yīng)用于連續(xù)動(dòng)作空間，使用該方法進(jìn)行訓(xùn)練，簡化了學(xué)習(xí)步驟并提高了成功率。ZHENG 等［56］提出一種改進(jìn)的多智能體深度確定性策略梯度法（Improved Multi-Agent Deep Deterministic Policy Gradient，IMADDPG），通過增加平均場(chǎng)網(wǎng)絡(luò)（Mean Field Network，MFN）最大化智能體的返回值，使所有的智能體在訓(xùn)練時(shí)能最大限度地提高協(xié)作性，最終可求解全局最優(yōu)路徑。

2）模仿學(xué)習(xí)法

與策略梯度法相同，模仿學(xué)習(xí)也是一種直接策略搜索方法。模仿學(xué)習(xí)的基本原理是從示范者提供的范例中進(jìn)行學(xué)習(xí)，示范者一般提供人類專家的決策數(shù)據(jù)，通過模仿專家行為得到與專家近似的策略。

在線性假設(shè)下，反饋信號(hào)可由一組確定基函數(shù)φ1，φ2，…，φk線性組合而成，因此策略的價(jià)值可表示如下：

若有策略π的特征期望滿足[μ(π)-ωt μE]2≤ε時(shí)式（14）成立，則該策略π是模仿學(xué)習(xí)法的一個(gè)解。

以上求解過程與通過計(jì)算積累獎(jiǎng)勵(lì)值獲得最優(yōu)策略的直接學(xué)習(xí)方法有本質(zhì)區(qū)別。在多步?jīng)Q策中，基于積累獎(jiǎng)勵(lì)值的學(xué)習(xí)方法存在搜索空間過大、計(jì)算成本過高的問題，模仿學(xué)習(xí)法能夠很好地解決多步?jīng)Q策中的這些問題。PFEIFFER 等［57］將模仿學(xué)習(xí)與強(qiáng)化學(xué)習(xí)結(jié)合起來進(jìn)行模型訓(xùn)練，通過模仿學(xué)習(xí)的目標(biāo)驅(qū)動(dòng)演示，可以顯著提高強(qiáng)化學(xué)習(xí)過程中的探索能力，同時(shí)在避障方面也顯現(xiàn)出較好的性能。HUSSEIN 等［58］提出一種深度模仿學(xué)習(xí)方法來學(xué)習(xí)三維環(huán)境中的路徑規(guī)劃任務(wù)，利用主動(dòng)學(xué)習(xí)對(duì)監(jiān)督策略進(jìn)行改進(jìn)，以便將其推廣到未知的動(dòng)態(tài)環(huán)境中。傳統(tǒng)的模仿學(xué)習(xí)不支持一個(gè)模型學(xué)習(xí)多個(gè)任務(wù)，XU 等［59］提出共享多頭模仿學(xué)習(xí)（Shared Multi-headed Imitation Learning，SMIL），使移動(dòng)機(jī)器人在不同模型切換的情況中，使用一個(gè)模型學(xué)習(xí)多個(gè)任務(wù)。該方法將每個(gè)任務(wù)建模為子策略，并設(shè)計(jì)一個(gè)多頭策略激活所有的子策略，以學(xué)習(xí)相關(guān)任務(wù)的共享信息。

2.2.3 基于值和策略相結(jié)合的強(qiáng)化學(xué)習(xí)方法

Actor-Critic 算法［60］將基于值的算法和基于策略的算法的優(yōu)點(diǎn)相融合，相比傳統(tǒng)策略梯度法效率更高，是一種性能較好的強(qiáng)化學(xué)習(xí)算法。Actor-Critic算法分為Actor 和Critic 兩個(gè)部分，其中，Actor 由策略梯度法衍生而來，Critic 由基于值的算法衍生而來。該算法的原理為：Actor 根據(jù)概率選擇行動(dòng)，Critic 為選擇的行動(dòng)反饋獎(jiǎng)勵(lì)，Actor 再根據(jù)Critic 的反饋修改選擇行動(dòng)的概率。Actor 策略函數(shù)的參數(shù)更新公式如下：

使用均方差損失函數(shù)來更新Critic 的網(wǎng)絡(luò)參數(shù)ω：

MUSE 等［61］將Actor-Critic 框架用于與平臺(tái)無關(guān)的移動(dòng)機(jī)器人路徑規(guī)劃任務(wù)中，使不同機(jī)器人平臺(tái)的功能具有一定的可移植性，并用于新型機(jī)器人平臺(tái)的快速原型設(shè)計(jì)。LACHEKHAB 等［62］提出一種模糊Actor-Critic 學(xué)習(xí)算法（Fuzzy Actor-Critic Learning Algorithm，F(xiàn)ACL），使用基于模糊邏輯的控制器控制機(jī)器人從起點(diǎn)到終點(diǎn)的路徑規(guī)劃，并在模糊規(guī)則中基于概率選擇機(jī)器人的下一行動(dòng)，因此可在已知環(huán)境下較好地完成路徑規(guī)劃任務(wù)。SHAO 等［63］提出一種基于廣義優(yōu)勢(shì)估計(jì)（Generalized Advantage Estimator，GAE）的Actor-Critic 算法，使智能體可以從多個(gè)過程中進(jìn)行學(xué)習(xí)以節(jié)約訓(xùn)練時(shí)間，并利用GAE 估計(jì)優(yōu)勢(shì)函數(shù)減少方差，從而提高了策略梯度的估計(jì)精度。

2.3 強(qiáng)化學(xué)習(xí)方法的局限性

雖然基于值的強(qiáng)化學(xué)習(xí)方法收斂速度快、學(xué)習(xí)效率高，但存在以下局限性：

1）當(dāng)動(dòng)作空間是連續(xù)動(dòng)作空間時(shí)，如果采用基于值的方法，需要對(duì)動(dòng)作空間離散化，進(jìn)而會(huì)導(dǎo)致連續(xù)空間到離散空間指數(shù)級(jí)的映射，從而產(chǎn)生維數(shù)災(zāi)難問題。

2）由基于值的方法最終得到的是一個(gè)確定性的策略，而最優(yōu)策略可能是隨機(jī)的，此時(shí)值函數(shù)法不適用。

3）值函數(shù)的一個(gè)微小的變動(dòng)通常會(huì)導(dǎo)致一個(gè)原本被選擇的動(dòng)作反而不能被選擇，這種變化會(huì)影響算法的收斂性。

與基于值的方法不同，基于策略的方法適用于高維或連續(xù)動(dòng)作空間，并具有更好的收斂性，但也存在以下局限性：

1）需要完全序列樣本才可以做算法迭代，訓(xùn)練慢、方差高，在多數(shù)情況下沒有基于值的方法有效。

2）優(yōu)化的梯度方向可能不是策略梯度的最優(yōu)方向，因此易收斂到局部最優(yōu)解，而非最優(yōu)策略。

3）移動(dòng)機(jī)器人的路徑規(guī)劃通常應(yīng)用在離散動(dòng)作空間中，基于策略的算法優(yōu)勢(shì)并不能顯現(xiàn)出來，因此目前基于策略的算法在移動(dòng)機(jī)器人路徑規(guī)劃上的應(yīng)用較少。

表2 給出了強(qiáng)化學(xué)習(xí)方法的代表方法、特點(diǎn)和優(yōu)劣勢(shì)對(duì)比結(jié)果。

表2 強(qiáng)化學(xué)習(xí)方法的代表方法、特點(diǎn)和優(yōu)劣勢(shì)對(duì)比Table 2 Comparison of representative methods，characteristics and advantages and disadvantages of reinforcement learning methods

3 基于深度強(qiáng)化學(xué)習(xí)的路徑規(guī)劃技術(shù)

3.1 深度強(qiáng)化學(xué)習(xí)與路徑規(guī)劃

強(qiáng)化學(xué)習(xí)的最終目的是通過最大化獎(jiǎng)勵(lì)值來獲得最優(yōu)策略，具有較強(qiáng)的決策能力。在越來越復(fù)雜的現(xiàn)實(shí)場(chǎng)景應(yīng)用中，需要利用深度學(xué)習(xí)從原始大規(guī)模數(shù)據(jù)中提取高級(jí)特征，深度學(xué)習(xí)具有較強(qiáng)的感知能力，但缺乏一定的決策能力。深度強(qiáng)化學(xué)習(xí)［64］（Deep Reinforcement Learning，DRL）將強(qiáng)化學(xué)習(xí)的決策能力與深度學(xué)習(xí)的感知能力相結(jié)合，可以直接根據(jù)輸入的信息進(jìn)行控制，是一種更加接近人類思維的人工智能方法。

2013 年，谷歌的人工智能研究團(tuán)隊(duì)DeepMind［65］將Q-Learning 算法與卷積神經(jīng)網(wǎng)絡(luò)相結(jié)合，創(chuàng)新性地提出深度Q 網(wǎng)絡(luò)（Deep Q-Network，DQN）。DQN基礎(chǔ)模型為一個(gè)卷積神經(jīng)網(wǎng)絡(luò)，并使用Q-Learning的變體進(jìn)行訓(xùn)練。DQN 對(duì)Q-Learning 主要做了以下改進(jìn)：

1）用卷積神經(jīng)網(wǎng)絡(luò)替代狀態(tài)-動(dòng)作對(duì)值函數(shù)Q(s，a)。具體地，使用參數(shù)為θi的值函數(shù)Q(s，a；θi)，迭代i次后的損失函數(shù)表示如下：

其中：Yi近似表示值函數(shù)的優(yōu)化目標(biāo)。Yi的計(jì)算公式如下：

在學(xué)習(xí)過程中通過θi更新θ-，具體學(xué)習(xí)過程為對(duì)θi求偏導(dǎo)得到梯度：

2）使用經(jīng)驗(yàn)回放技術(shù)。在每個(gè)時(shí)間步t時(shí)，存儲(chǔ)智能體的經(jīng)驗(yàn)樣本et=（st，at，rt，st+1）到回放記憶單元D=｛e1，e2，…，et｝中，通過重復(fù)采樣歷史數(shù)據(jù)增加樣本使用率，可有效避免學(xué)習(xí)時(shí)參數(shù)震蕩。

3）隨機(jī)小批量從記憶單元D中取樣。由于樣本之間相關(guān)性高，因此直接從連續(xù)樣本中學(xué)習(xí)是低效的，隨機(jī)小批量取樣降低了樣本間的關(guān)聯(lián)性，從而提升了算法的穩(wěn)定性。

為更有效地將深度強(qiáng)化學(xué)習(xí)方法應(yīng)用于路徑規(guī)劃，學(xué)者們嘗試了許多改進(jìn)思路。TAI 等［66］針對(duì)沒有障礙物地圖和距離信息稀疏的情況，提出一個(gè)基于學(xué)習(xí)的無地圖運(yùn)動(dòng)規(guī)劃器，以稀疏的10 維測(cè)距結(jié)果和目標(biāo)相對(duì)于移動(dòng)機(jī)器人坐標(biāo)系的位置作為輸入，連續(xù)轉(zhuǎn)向命令作為輸出，通過異步深度強(qiáng)化學(xué)習(xí)方法訓(xùn)練規(guī)劃器，使訓(xùn)練和樣本收集可以并行執(zhí)行。該方法在極端復(fù)雜的環(huán)境中具有更好的穩(wěn)定性。王珂等［67］基于深度強(qiáng)化學(xué)習(xí)提出一種基于最小深度信息選擇的訓(xùn)練模式，通過運(yùn)動(dòng)學(xué)方程約束，優(yōu)化狀態(tài)空間的搜索與采集，提高了訓(xùn)練速率。李輝等［68］將深度卷積神經(jīng)網(wǎng)絡(luò)的特征提取能力與強(qiáng)化學(xué)習(xí)的決策能力相結(jié)合，提出一種基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)算法，該算法用近似值函數(shù)代替Q-Learning 中的動(dòng)作值函數(shù)，設(shè)計(jì)包含4 層結(jié)構(gòu)的深度卷積神經(jīng)網(wǎng)絡(luò)，以網(wǎng)絡(luò)的輸出代替?zhèn)鹘y(tǒng)的Q 值表，解決了Q-Learning 在狀態(tài)空間較大時(shí)產(chǎn)生的維數(shù)災(zāi)難問題。

3.2 深度強(qiáng)化學(xué)習(xí)方法的局限性

目前，深度強(qiáng)化學(xué)習(xí)方法存在以下3 個(gè)方面的局限性：

1）深度強(qiáng)化學(xué)習(xí)理論支撐不夠。谷歌的DeepMind 團(tuán)隊(duì)于2015 年在《自然》雜志上發(fā)表的文章［69］雖然取得了較好的應(yīng)用效果，但沒有證明DQN的收斂性，并且到目前為止在DQN 或其他深度強(qiáng)化學(xué)習(xí)方法的基礎(chǔ)上的改進(jìn)工作也沒有很好地解決該問題。

2）樣本采樣率低。樣本采樣率低使得深度強(qiáng)化學(xué)習(xí)方法有時(shí)在實(shí)際應(yīng)用中效果不佳。導(dǎo)致該問題的主要原因有兩個(gè)：一是完成任務(wù)需要收集大量數(shù)據(jù)；二是訓(xùn)練過程中利用當(dāng)前數(shù)據(jù)的有用信息效率低。

3）在連續(xù)動(dòng)作空間中應(yīng)用有限。目前主流的深度強(qiáng)化學(xué)習(xí)方法大多適用于離散動(dòng)作空間，對(duì)于機(jī)器人的機(jī)械臂路徑規(guī)劃等連續(xù)動(dòng)作空間［70］的任務(wù)還處于初步研究階段，理論支撐不夠，因此應(yīng)用十分有限。

3.3 強(qiáng)化學(xué)習(xí)與深度強(qiáng)化學(xué)習(xí)的異同

強(qiáng)化學(xué)習(xí)通常使用馬爾可夫決策過程進(jìn)行描述，具體而言：機(jī)器處在一個(gè)環(huán)境中，每個(gè)狀態(tài)為機(jī)器對(duì)當(dāng)前環(huán)境的感知；機(jī)器只能通過動(dòng)作來影響環(huán)境，在機(jī)器執(zhí)行一個(gè)動(dòng)作后，會(huì)使當(dāng)前環(huán)境按某種概率轉(zhuǎn)移到另一個(gè)狀態(tài)；當(dāng)前環(huán)境會(huì)根據(jù)潛在的獎(jiǎng)賞函數(shù)反饋給機(jī)器一個(gè)獎(jiǎng)賞。

深度強(qiáng)化學(xué)習(xí)是深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)的結(jié)合，具體而言是結(jié)合了深度學(xué)習(xí)的結(jié)構(gòu)和強(qiáng)化學(xué)習(xí)的思想，但它的側(cè)重點(diǎn)更多在強(qiáng)化學(xué)習(xí)上，解決的仍是決策問題，只是借助神經(jīng)網(wǎng)絡(luò)強(qiáng)大的表征能力擬合Q表或直接擬合策略以解決狀態(tài)-動(dòng)作空間過大或連續(xù)狀態(tài)-動(dòng)作空間問題。

4 基于強(qiáng)化學(xué)習(xí)的路徑規(guī)劃技術(shù)展望

雖然移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)已取得了大量的科研成果，并廣泛地應(yīng)用于實(shí)際場(chǎng)景中，但隨著移動(dòng)機(jī)器人應(yīng)用領(lǐng)域的擴(kuò)大和應(yīng)用場(chǎng)景的復(fù)雜化，從目前的發(fā)展現(xiàn)狀和未來的發(fā)展需求來看，基于強(qiáng)化學(xué)習(xí)方法的路徑規(guī)劃技術(shù)的下一步研究方向主要包括以下4 個(gè)方面：

1）設(shè)計(jì)有效的獎(jiǎng)勵(lì)函數(shù)。強(qiáng)化學(xué)習(xí)通過最大化獎(jiǎng)勵(lì)值來獲得最優(yōu)策略，那么策略是否最優(yōu)取決于獎(jiǎng)勵(lì)函數(shù)。現(xiàn)階段獎(jiǎng)勵(lì)函數(shù)由專家學(xué)者憑借專業(yè)知識(shí)設(shè)計(jì)，面對(duì)路徑規(guī)劃領(lǐng)域日益復(fù)雜多變的應(yīng)用環(huán)境，不合理的獎(jiǎng)勵(lì)函數(shù)也會(huì)使得到的最優(yōu)策略不合理。有學(xué)者提出元學(xué)習(xí)（Meta Learning，ML）等方式，讓智能體嘗試在面對(duì)環(huán)境或任務(wù)變換的情況下，從合理的策略中不斷完善獎(jiǎng)勵(lì)函數(shù)。因此，設(shè)計(jì)有效的獎(jiǎng)勵(lì)函數(shù)是未來發(fā)展的熱點(diǎn)之一。

2）解決強(qiáng)化學(xué)習(xí)的探索-利用困境。一方面，探索的目的是通過不斷探索新的環(huán)境信息來獲得更高的獎(jiǎng)勵(lì)值，以此避免陷入局部最優(yōu)解。另一方面，利用探索是指用已學(xué)習(xí)到的信息來選擇獎(jiǎng)勵(lì)值最高的動(dòng)作。探索-利用的困境即使得探索信息與利用信息兩者之間得到平衡，目前常用的解決方法為ε-greedy 算法［69］。該算法的基本原理是使智能體以ε為概率隨機(jī)探索信息，并以1?ε為概率利用信息，通過不斷的學(xué)習(xí)，ε會(huì)不斷衰減以保證后期的學(xué)習(xí)效率。ε-greedy 算法簡單易實(shí)現(xiàn)，但隨機(jī)探索效率低，因此如何解決強(qiáng)化學(xué)習(xí)的探索-利用困境有待進(jìn)一步研究。

3）研究強(qiáng)化學(xué)習(xí)方法與常規(guī)方法的結(jié)合方法。每種強(qiáng)化學(xué)習(xí)方法在路徑規(guī)劃應(yīng)用中都存在自身局限性，為了彌補(bǔ)單一方法的不足，通過不同方法之間相互結(jié)合的優(yōu)勢(shì)互補(bǔ)可以得到一些性能更好的方法，如傳統(tǒng)路徑規(guī)劃算法、圖形學(xué)算法、智能仿生學(xué)算法以及強(qiáng)化學(xué)習(xí)算法之間的有效結(jié)合，相互取長補(bǔ)短后均具有一定的發(fā)展前景。

4）將強(qiáng)化學(xué)習(xí)算法應(yīng)用于多智能體協(xié)作的路徑規(guī)劃研究。多智能體協(xié)作路徑規(guī)劃技術(shù)具有高靈活性、易部署、高協(xié)調(diào)性等優(yōu)點(diǎn)，被廣泛應(yīng)用于機(jī)器人雙臂協(xié)作路徑規(guī)劃、機(jī)器人足球賽、多無人機(jī)競(jìng)速賽等實(shí)際場(chǎng)景中。目前，對(duì)于單機(jī)器人路徑規(guī)劃研究的成果較多，而多機(jī)器人協(xié)作路徑規(guī)劃的成果相對(duì)較少，對(duì)應(yīng)用中出現(xiàn)的碰撞、路徑死鎖、協(xié)調(diào)配合、花費(fèi)代價(jià)大等一系列問題有待進(jìn)一步解決。

5 結(jié)束語

本文闡述基于常規(guī)方法、強(qiáng)化學(xué)習(xí)方法及深度強(qiáng)化學(xué)習(xí)方法的路徑規(guī)劃技術(shù)，分類并對(duì)比強(qiáng)化學(xué)習(xí)方法的特點(diǎn)、優(yōu)劣性及適用場(chǎng)合。針對(duì)強(qiáng)化學(xué)習(xí)方法應(yīng)用于路徑規(guī)劃技術(shù)時(shí)存在的局限性，重點(diǎn)研究了將啟發(fā)式思想、分層思想、模糊邏輯思想及多算法結(jié)合思想融入強(qiáng)化學(xué)習(xí)算法的改進(jìn)思路。面對(duì)未來更加復(fù)雜的應(yīng)用環(huán)境，下一步將從設(shè)計(jì)有效的獎(jiǎng)勵(lì)函數(shù)、解決強(qiáng)化學(xué)習(xí)的探索-利用困境等方面入手，對(duì)強(qiáng)化學(xué)習(xí)在路徑規(guī)劃技術(shù)中的應(yīng)用進(jìn)行更深入的研究。