周盛世,單 梁,常 路,陳 佳,劉成林,李 軍

(1.南京理工大學(xué) 自動化學(xué)院,江蘇 南京 210094;2.江南大學(xué) 輕工過程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室,江蘇 無錫 214122)

在移動機(jī)器人自主導(dǎo)航中,路徑規(guī)劃問題是一個(gè)基礎(chǔ)又重要的部分,其目標(biāo)可以描述為在一定的約束條件下,尋找1條從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑。常見的路徑規(guī)劃算法有A*[1]、蟻群算法[2-4]、遺傳算法[5]、粒子群算法[6]等,但是這些算法存在運(yùn)算時(shí)間長、迭代次數(shù)過多以及在未知環(huán)境下實(shí)時(shí)性差的問題。而人工勢場法[7,8]可以根據(jù)機(jī)器人當(dāng)前狀態(tài)和環(huán)境確定下一步的運(yùn)動狀態(tài),算法實(shí)時(shí)性高,但是存在容易陷入局部最小點(diǎn)的問題。近年來,深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)成為機(jī)器學(xué)習(xí)領(lǐng)域重要的研究熱點(diǎn)。神經(jīng)網(wǎng)絡(luò)強(qiáng)大的特征提取和函數(shù)擬合能力使得強(qiáng)化學(xué)習(xí)可以應(yīng)用到非常復(fù)雜的決策問題上[9,10],深度強(qiáng)化學(xué)習(xí)(Deep reinforcement learning,DRL)可以充分發(fā)揮深度學(xué)習(xí)的感知優(yōu)勢和強(qiáng)化學(xué)習(xí)的決策優(yōu)勢。

Google DeepMind通過結(jié)合Q學(xué)習(xí)(Q-learning)和深度神經(jīng)網(wǎng)絡(luò)提出了深度Q網(wǎng)絡(luò)[11,12](Deep Q network,DQN),解決了高維輸入引發(fā)的維度災(zāi)難問題,允許連續(xù)狀態(tài)輸入。隨后以Actor-Critic算法為基礎(chǔ),將DQN和確定性策略梯度[13]相結(jié)合,提出了深度確定性策略梯度(Deep deterministic policy gradient,DDPG)算法[14,15],解決了動作空間離散的問題。文獻(xiàn)[16]提出了一種根據(jù)優(yōu)先級回放經(jīng)驗(yàn)池的改進(jìn)策略。文獻(xiàn)[17]使用強(qiáng)化學(xué)習(xí)進(jìn)行路徑規(guī)劃,但是狀態(tài)和動作空間都是離散的,不符合實(shí)際機(jī)器人的運(yùn)動模型。文獻(xiàn)[18]通過分離經(jīng)驗(yàn)緩存池,提出基于失敗經(jīng)驗(yàn)糾錯(cuò)的改進(jìn)算法。文獻(xiàn)[19]在訓(xùn)練后期增大了經(jīng)驗(yàn)池,沒有從根本上篩選訓(xùn)練樣本,訓(xùn)練提升空間有限。

本文在現(xiàn)有研究[20-22]的基礎(chǔ)上,提出了一種基于改進(jìn)DDPG的路徑規(guī)劃算法,根據(jù)機(jī)器人周圍環(huán)境和目標(biāo)點(diǎn)的狀態(tài),利用人工勢場法實(shí)時(shí)性避障的優(yōu)點(diǎn),引入其作為前期訓(xùn)練的輔助策略,并研究連續(xù)的回報(bào)函數(shù),加快訓(xùn)練速度,最后進(jìn)行實(shí)驗(yàn)仿真,驗(yàn)證了算法的有效性。

1 DDPG算法

1.1 基本原理

DDPG采用了異策略的演員-評論家(Actor-Critic)算法框架,使用類似雙深度Q學(xué)習(xí)網(wǎng)絡(luò)(Double deep Q-learning network,DDQN)的雙網(wǎng)絡(luò)結(jié)構(gòu)用于解決收斂慢的問題。在DDPG算法中,智能體與環(huán)境交互得到狀態(tài),通過神經(jīng)網(wǎng)絡(luò)得到動作策略,智能體執(zhí)行策略后,得到環(huán)境的反饋,再通過強(qiáng)化學(xué)習(xí)的決策能力對各個(gè)策略進(jìn)行評價(jià),之后對神經(jīng)網(wǎng)絡(luò)進(jìn)行更新。DDPG算法網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示[14]。

圖1 DDPG算法網(wǎng)絡(luò)框架圖

在Actor-Critic中,Actor和Critic都包含2個(gè)神經(jīng)網(wǎng)絡(luò):Eval網(wǎng)絡(luò)和Target網(wǎng)絡(luò)。在Actor中,Eval網(wǎng)絡(luò)根據(jù)當(dāng)前狀態(tài)st選擇動作at,并負(fù)責(zé)更新策略網(wǎng)絡(luò)參數(shù)θ;Target網(wǎng)絡(luò)根據(jù)經(jīng)驗(yàn)池采樣的下一個(gè)狀態(tài)st+1選擇下一個(gè)最優(yōu)動作at+1,網(wǎng)絡(luò)參數(shù)θ′從θ中更新。使用對狀態(tài)和行為的評價(jià)均值作為損失函數(shù)

Loss=-mean(Q(st,at,θ))

(1)

在Critic中,Eval網(wǎng)絡(luò)根據(jù)狀態(tài)st和動作at計(jì)算當(dāng)前Q值Q(st,at),并負(fù)責(zé)價(jià)值網(wǎng)絡(luò)參數(shù)ω的更新;Target網(wǎng)絡(luò)根據(jù)st+1和at+1計(jì)算下一個(gè)狀態(tài)的實(shí)際Q值Q(st+1,at+1),網(wǎng)絡(luò)參數(shù)ω′通過ω更新。

QTarget=rt+1+γ·Q′(st+1,at+1,ω′)

(2)

式中:γ為折扣因子,表示時(shí)間的遠(yuǎn)近對獎勵的影響程度,越小表示更看重當(dāng)前獎勵。

采用均方差構(gòu)建網(wǎng)絡(luò)可優(yōu)化的損失函數(shù)

Loss=E[(QTarget-Q(st,at,ω))2]

(3)

1.2 環(huán)境探索

在訓(xùn)練過程中,網(wǎng)絡(luò)模型需要權(quán)衡探索和利用功能。探索是為了尋找潛在的更優(yōu)策略,所以在訓(xùn)練過程中引入隨機(jī)噪聲,將決策從確定性過程變?yōu)殡S機(jī)過程。

ε貪婪(ε-greedy)策略實(shí)現(xiàn)簡單,但是探索效率低下,因?yàn)槭请S機(jī)選擇,所以也沒有記憶,會造成重復(fù)探索。在DDPG中引入了Ornstein-Uhlenbeck(OU)過程,OU過程是1個(gè)時(shí)間相關(guān)的過程,在慣性系統(tǒng)中探索效率更高,如圖2所示。其連續(xù)形式如下

圖2 OU噪聲

dxt=θ(μ-xt)dt+σdWt

(4)

其離散形式為

xt-xt-1=θ(μ-xt)+σWt

(5)

式中:μ是均值,θ表示變化速率[14],σ表示噪聲的范圍,xt是狀態(tài),Wt是維納過程。

2 改進(jìn)DDPG算法

目前DDPG算法在機(jī)器人路徑規(guī)劃上的研究場景相對簡單,狀態(tài)和動作空間不連續(xù),且存在訓(xùn)練時(shí)間長、不穩(wěn)定等缺點(diǎn)。本文采用連續(xù)的狀態(tài)空間和動作空間設(shè)計(jì),更符合機(jī)器人實(shí)際運(yùn)動學(xué)模型,并在回報(bào)函數(shù)中引入人工勢場法來加快訓(xùn)練速度。

2.1 連續(xù)狀態(tài)空間設(shè)計(jì)

狀態(tài)空間是整個(gè)環(huán)境的反饋,是智能體選擇動作空間的依據(jù)。狀態(tài)包括2部分。

(1)激光雷達(dá)數(shù)據(jù)。機(jī)器人上裝有激光雷達(dá),探測距離為10 m,掃描范圍是360°。考慮到精度和計(jì)算問題,只考慮機(jī)器人正前方180°,取9個(gè)方向的雷達(dá)數(shù)據(jù),如圖3所示。

圖3 環(huán)境狀態(tài)空間圖

用dio表示雷達(dá)各個(gè)方位探測到障礙物的距離,使用雷達(dá)量程將dio進(jìn)行歸一化處理,最終方位狀態(tài)信息為[D1o,D2o,D3o,D4o,D5o,D6o,D7oD8o,D9o]。

(6)

式中:D為激光雷達(dá)最大量程。

(2)為了使機(jī)器人能夠朝向目標(biāo)點(diǎn)運(yùn)動,將機(jī)器人當(dāng)前朝向與目標(biāo)點(diǎn)的夾角β作為1個(gè)輸入狀態(tài),如圖4所示。目標(biāo)點(diǎn)在機(jī)器人左側(cè)時(shí),β取值范圍是[0,180°];目標(biāo)點(diǎn)在機(jī)器人右側(cè)時(shí),β取值范圍是(-180°,0)。

圖4 目標(biāo)夾角

2.2 連續(xù)動作空間設(shè)計(jì)

在機(jī)器人運(yùn)動模型中,控制量包含線速度和角速度2部分,上限分別為vmax和ωmax,并且有最大加速度a和最大角加速度α。定義動作空間為線速度比值v和角速度比值ω,其中,線速度取值范圍是[0,1],角速度取值范圍是[-1,1],兩者均為連續(xù)值,相對于低維離散動作更接近真實(shí)機(jī)器人運(yùn)動模型。位置更新公式為

(7)

式中:dt表示位置更新周期,γ表示機(jī)器人朝向與x軸正方向的夾角,Px和Py表示機(jī)器人的位置[23]。

2.3 與人工勢場法相結(jié)合的獎勵函數(shù)設(shè)計(jì)

獎勵函數(shù)用于評價(jià)深度學(xué)習(xí)框架決策的好壞,對每步?jīng)Q策給出1個(gè)獎勵值,它對整個(gè)學(xué)習(xí)過程起著導(dǎo)向作用。神經(jīng)網(wǎng)絡(luò)根據(jù)狀態(tài)做出具體的決策,環(huán)境根據(jù)決策執(zhí)行更新,并計(jì)算出獎勵值,神經(jīng)網(wǎng)絡(luò)根據(jù)反饋出來的獎勵值更新網(wǎng)絡(luò)參數(shù),使網(wǎng)絡(luò)下次計(jì)算時(shí)能夠做出更優(yōu)決策。獎勵函數(shù)的好壞直接影響整個(gè)強(qiáng)化學(xué)習(xí)框架的有效性和收斂性。獎勵函數(shù)設(shè)計(jì)如下

(8)

R=rate*norm(P0-P1)+(1-rate)*R

(9)

式中:d(t)表示當(dāng)前時(shí)刻機(jī)器人距離目標(biāo)點(diǎn)的距離;d(t-1)表示上一個(gè)時(shí)刻機(jī)器人距離目標(biāo)點(diǎn)的距離;do表示障礙物的安全距離,小于該值即表示碰到障礙物;dg表示距離目標(biāo)點(diǎn)的閾值,小于該值即認(rèn)為到達(dá)目標(biāo)點(diǎn);dn表示靠近目標(biāo)點(diǎn)的距離,到達(dá)該范圍內(nèi)給予1個(gè)正向獎勵,可以促使機(jī)器人更快到達(dá)目標(biāo)點(diǎn)。當(dāng)機(jī)器人所處位置是障礙時(shí),獲得負(fù)獎勵;當(dāng)機(jī)器人到達(dá)終點(diǎn),獲得較大的正獎勵;當(dāng)機(jī)器人靠近目標(biāo)點(diǎn)時(shí),獲得1作為獎勵;當(dāng)機(jī)器人原地不動時(shí),獲得-1作為獎勵;其他情況獲得-2作為獎勵,這個(gè)獎勵比1小是因?yàn)檫@樣可以避免機(jī)器人出現(xiàn)來回運(yùn)動去獲得正獎勵的情況,可以促使機(jī)器人尋找最短路徑?？傮w來說,機(jī)器人只有靠近目標(biāo)點(diǎn)以及到達(dá)目標(biāo)點(diǎn)才會獲得正獎勵。

強(qiáng)化學(xué)習(xí)最大的缺點(diǎn)是訓(xùn)練的時(shí)間長且不穩(wěn)定,如果前期能夠很快到達(dá)目標(biāo)點(diǎn),訓(xùn)練的速度會很快,否則會探索很大的空間。為了解決傳統(tǒng)算法盲目選擇動作的問題,引入人工勢場法作為前期訓(xùn)練的輔助,使系統(tǒng)能夠更快訓(xùn)練出模型。在選擇出動作空間后,先根據(jù)人工勢場法計(jì)算機(jī)器人下一步的位置P0,然后再進(jìn)行環(huán)境的更新得到機(jī)器人實(shí)際的位置P1。在原獎勵函數(shù)的基礎(chǔ)上,加上P0和P1的距離。式(9)中,norm(P0-P1)為計(jì)算2個(gè)位置的距離,rate是1個(gè)權(quán)重值,代表人工勢場法的權(quán)重,在前期比重較大,引導(dǎo)機(jī)器人更快走向終點(diǎn),隨著訓(xùn)練次數(shù)的增加,權(quán)重逐漸下降。

2.4 優(yōu)先級經(jīng)驗(yàn)回放機(jī)制

DDPG使用經(jīng)驗(yàn)回放池來消除輸入樣本間的相關(guān)性,每次從中隨機(jī)選取小批量的樣本來更新神經(jīng)網(wǎng)絡(luò)。這種方式將新老樣本進(jìn)行混合來更新網(wǎng)絡(luò),認(rèn)為經(jīng)驗(yàn)池中的所有樣本的重要性都是一致的,但是會減弱樣本之間的時(shí)序相關(guān)性。

在經(jīng)驗(yàn)回放池中的樣本中時(shí)序差分(Temporal-difference,TD)誤差越大,對反向傳播的作用也越大,算法的收斂速度會更快,同時(shí)也會提高訓(xùn)練過程的穩(wěn)定性。因此引入經(jīng)驗(yàn)回放的優(yōu)先級,根據(jù)TD誤差

Error=rt+γ·Q′(st+1,at+1,ω′)-Q(st,at,ω)

(10)

來衡量每個(gè)樣本的學(xué)習(xí)價(jià)值,優(yōu)先級高的樣本更容易被選取。

3 算法流程

使用DDPG算法對機(jī)器人路徑規(guī)劃進(jìn)行訓(xùn)練,程序流程如圖5所示。

圖5 DDPG算法流程圖

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

為了驗(yàn)證改進(jìn)的DDPG算法在機(jī)器人路徑規(guī)劃中的有效性和收斂性,本文采用Python語言,在不同地圖下分別使用人工勢場法、原始DDPG和改進(jìn)的DDPG算法進(jìn)行仿真對比實(shí)驗(yàn)。構(gòu)建100×100的二維柵格地圖,設(shè)置雷達(dá)量程為20,起點(diǎn)為(2,2),終點(diǎn)為(30,82),訓(xùn)練回合為500次,每回合訓(xùn)練次數(shù)最多為200次。機(jī)器人在地圖內(nèi)不斷學(xué)習(xí)探索,如果成功到達(dá)目標(biāo)點(diǎn)、碰到障礙物或者每回合訓(xùn)練次數(shù)超過200次,那么就會場景復(fù)位,開始下一回合訓(xùn)練。模型部分參數(shù)設(shè)置如表1所示。

表1 模型參數(shù)表

圖6(a)、圖6(b)分別是原始DDPG算法和本文提出的改進(jìn)DDPG算法訓(xùn)練1000回合后的路徑圖。

圖6 算法路徑圖

原始DDPG算法訓(xùn)練初期沒有樣本池,隨機(jī)性較大,需要大量的樣本才能夠訓(xùn)練出模型。改進(jìn)的DDPG算法通過結(jié)合人工勢場法,在訓(xùn)練中能夠給予模型一定的指引,減少訓(xùn)練的盲目性和隨機(jī)性,從而大大加快訓(xùn)練時(shí)間,能夠更早得到優(yōu)化模型。

為了驗(yàn)證改進(jìn)的DDPG算法在不同地圖下的有效性,選取多個(gè)地圖進(jìn)行測試驗(yàn)證。圖7是不同地圖路徑規(guī)劃圖。圖8是原始DDPG算法和改進(jìn)的DDPG算法訓(xùn)練成功率的對比圖。原始DDPG算法在開始訓(xùn)練時(shí)隨機(jī)性較大,訓(xùn)練結(jié)果不穩(wěn)定,隨著樣本量增大逐步穩(wěn)定,成功率最終為70%。改進(jìn)的DDPG算法在40回合后成功率穩(wěn)定上升,說明算法已經(jīng)開始收斂,明顯快于原始DDPG收斂速度。隨著訓(xùn)練次數(shù)的增加,人工勢場法作用逐步減小,成功率開始緩慢增加,訓(xùn)練1000回合的收斂成功率為92%。

圖7 不同地圖路徑規(guī)劃圖

圖8 算法改進(jìn)前后的訓(xùn)練成功率曲線圖

5 結(jié)束語

本文主要考慮了移動機(jī)器人在未知環(huán)境下的路徑規(guī)劃問題。在建模過程中考慮機(jī)器人的實(shí)際運(yùn)動模型,提出了一種在未知環(huán)境下基于深度強(qiáng)化學(xué)習(xí)的路徑規(guī)劃算法。分析了DDPG算法的問題,引入人工勢場法解決算法訓(xùn)練量大、隨機(jī)性強(qiáng)和不穩(wěn)定的缺點(diǎn),增強(qiáng)了算法的魯棒性,并且避免了人工勢場法本身易陷入局部最小值的缺點(diǎn),驗(yàn)證了算法的有效性。后續(xù)將研究多機(jī)器人協(xié)同編隊(duì)的路徑規(guī)劃算法。