封 碩 舒 紅 謝步慶

1(長(zhǎng)安大學(xué)工程機(jī)械學(xué)院 陜西 西安 710064) 2(長(zhǎng)安大學(xué)理學(xué)院 陜西 西安 710064)

0 引 言

路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航的重要組成部分，目前大多研究成果顯示在二維環(huán)境下的路徑規(guī)劃比較成熟，但是在三維環(huán)境下的路徑規(guī)劃比較薄弱。在三維環(huán)境下，會(huì)更容易碰到不平坦、多峰谷、多阻礙的地理環(huán)境狀況，且不停地上下坡會(huì)帶來(lái)更多能量損耗，所以需要找尋一條在最短的基礎(chǔ)上，減少爬坡入坑(即減少耗能)的路徑[1]。

蟻群算法是一種典型的三維路徑規(guī)劃方法，其信息素具備一定記憶功能是顯著優(yōu)點(diǎn)，但其缺點(diǎn)也很明顯[2-3]。首先，它無(wú)法徹底解決三維環(huán)境路徑規(guī)劃問(wèn)題，最終找尋的路徑還會(huì)穿過(guò)山或者坑，不符合實(shí)際需求；其次，其算法收斂問(wèn)題并沒(méi)有得到很好的解決?；趯哟伟鼑信鲎矙z測(cè)的優(yōu)化算法[4]是一種針對(duì)三維場(chǎng)景的路徑規(guī)劃問(wèn)題的算法，雖然達(dá)到了路徑優(yōu)化的效果，且提高了時(shí)間效率，但沒(méi)有對(duì)障礙物進(jìn)行細(xì)化分析，對(duì)一些特定場(chǎng)景下的問(wèn)題解釋力有限。粒子群算法也是分析三維環(huán)境下的路徑規(guī)劃的傳統(tǒng)算法[5]，且解決其三維環(huán)境路徑規(guī)劃有良好的結(jié)果，但是仍然存在陷入極值和沒(méi)有較好的尋優(yōu)效率問(wèn)題。

深度Q學(xué)習(xí)算法(DQN)是結(jié)合了深度學(xué)習(xí)的感知能力和強(qiáng)化學(xué)習(xí)的決策能力的人工智能方法。感知能力和決策能力是衡量智能的大指標(biāo)，強(qiáng)化學(xué)習(xí)的弱感知能力致使機(jī)器人難以直接通過(guò)學(xué)習(xí)高維狀態(tài)輸入去控制輸出決策，而深度學(xué)習(xí)可用網(wǎng)絡(luò)結(jié)構(gòu)來(lái)映射Q表，從而解決Q-learning的維數(shù)災(zāi)難問(wèn)題。近年來(lái)，研究表明在未創(chuàng)建地圖情況下利用DQN實(shí)現(xiàn)移動(dòng)機(jī)器人的導(dǎo)航是完全可行的，且利用DQN在柵格化地圖中初步實(shí)現(xiàn)了路徑規(guī)劃，得到之前從未得到的較好結(jié)果[6]。但在該文獻(xiàn)中，DQN算法收斂性較弱，沒(méi)有對(duì)算法收斂性進(jìn)行提高。文獻(xiàn)[7]提出的改進(jìn)DQN算法不僅解決了DQN算法存在嚴(yán)重的過(guò)估計(jì)問(wèn)題，且將改進(jìn)DQN應(yīng)用于實(shí)際問(wèn)題，取得良好結(jié)果。但是沒(méi)有針對(duì)三維路徑規(guī)劃問(wèn)題進(jìn)行分析。最近，已經(jīng)有越來(lái)越多學(xué)者使用深度強(qiáng)化學(xué)習(xí)算法解決各個(gè)行業(yè)的問(wèn)題，且在路徑優(yōu)化問(wèn)題上已經(jīng)相對(duì)成熟[8-10]。理論上，將DQN應(yīng)用在路徑規(guī)劃中優(yōu)于其他算法，但需要解決三維環(huán)境的路徑規(guī)劃設(shè)計(jì)問(wèn)題，使得與最優(yōu)值差值較小的非最優(yōu)值得到較大的縮小，與最優(yōu)值差值較大的非最優(yōu)值得到較小的縮小。本文利用神經(jīng)網(wǎng)絡(luò)進(jìn)行建模，應(yīng)用到深度Q網(wǎng)絡(luò)中設(shè)計(jì)相應(yīng)的改進(jìn)算法，并將改進(jìn)算法應(yīng)用到三維路徑規(guī)劃的問(wèn)題中。

1 改進(jìn)深度強(qiáng)化學(xué)習(xí)算法

1.1 DQN深度強(qiáng)化學(xué)習(xí)

在機(jī)器學(xué)習(xí)方法中，深度神經(jīng)網(wǎng)絡(luò)具有感知復(fù)雜環(huán)境的能力，而強(qiáng)化學(xué)習(xí)是解決復(fù)雜決策問(wèn)題的有效手段，因此Mnih等[11]將兩者結(jié)合起來(lái)能夠解決復(fù)雜環(huán)境的感知決策問(wèn)題。本文針對(duì)三維路徑規(guī)劃的問(wèn)題，基于DQN模型中深度學(xué)習(xí)的感知能力，結(jié)合強(qiáng)化學(xué)習(xí)的決策能力，即使用深度神經(jīng)網(wǎng)絡(luò)框架來(lái)擬合強(qiáng)化學(xué)習(xí)中的Q值，可以使機(jī)器人實(shí)現(xiàn)真正自主學(xué)習(xí)且提高找尋最優(yōu)路徑的效率，獲得穩(wěn)定的獎(jiǎng)賞值。

DQN是一種結(jié)合了強(qiáng)化學(xué)習(xí)中的Q學(xué)習(xí)(Q-learning)和深度學(xué)習(xí)中的卷積神經(jīng)網(wǎng)絡(luò)(CNN)的算法。利用卷積神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了對(duì)Q表的建模，從而完整地表示所有的狀態(tài)-動(dòng)作值，Q-learning 通過(guò)馬爾可夫決策[12]建立模型，核心為四元組：目前狀態(tài)，動(dòng)作，獎(jiǎng)勵(lì)和下一步狀態(tài)。智能體根據(jù)當(dāng)前環(huán)境的狀態(tài)來(lái)采取動(dòng)作，在獲得相應(yīng)的獎(jiǎng)勵(lì)后，能通過(guò)試錯(cuò)的方法再去改變動(dòng)作，使得在接下來(lái)的環(huán)境下智能體能夠做出更優(yōu)的動(dòng)作，得到更高的獎(jiǎng)勵(lì)。

DQN采用神經(jīng)網(wǎng)絡(luò)作為函數(shù)近似的模型，其參數(shù)需通過(guò)強(qiáng)化學(xué)習(xí)反復(fù)調(diào)整，達(dá)到神經(jīng)網(wǎng)絡(luò)對(duì)Q表建模的目的。深度強(qiáng)化學(xué)習(xí)能夠?qū)?qiáng)化學(xué)習(xí)的決策能力和深度學(xué)習(xí)的感知能力相融合。首先通過(guò)深度學(xué)習(xí)對(duì)大規(guī)模原始輸入數(shù)據(jù)進(jìn)行簡(jiǎn)單但非線性的轉(zhuǎn)換，得到該原始數(shù)據(jù)更高層次的抽象表達(dá)，從而得到數(shù)據(jù)內(nèi)在的規(guī)律。然后結(jié)合強(qiáng)化學(xué)習(xí)，不斷調(diào)整神經(jīng)網(wǎng)絡(luò)參數(shù)，使得神經(jīng)網(wǎng)絡(luò)能夠更好地?cái)M合Q表。最后智能體依據(jù)神經(jīng)網(wǎng)絡(luò)能夠獲得一個(gè)更為理想的策略。

深度Q網(wǎng)絡(luò)依靠目標(biāo)值網(wǎng)絡(luò)Target Net(Q’)以及回放記憶單元D(Q空間)對(duì)神經(jīng)網(wǎng)絡(luò)的穩(wěn)定性進(jìn)行有效的提高，同時(shí)使用隨機(jī)梯度下降函數(shù)更新在線值網(wǎng)絡(luò)Main Net(Q)，使得深度Q網(wǎng)絡(luò)對(duì)較為復(fù)雜的控制問(wèn)題有一定的處理能力，而且深度Q網(wǎng)絡(luò)在訓(xùn)練的過(guò)程中無(wú)須添加額外的數(shù)據(jù)信息，將原始數(shù)據(jù)直接輸入一個(gè)卷積神經(jīng)網(wǎng)絡(luò)，從而使得智能體對(duì)數(shù)據(jù)的處理更接近人。然后使用強(qiáng)化學(xué)習(xí)中的Q-learning，通過(guò)與環(huán)境進(jìn)行交互，得到帶有獎(jiǎng)賞值的樣本數(shù)據(jù)，從而更新在線值網(wǎng)絡(luò)的參數(shù)，經(jīng)過(guò)固定的時(shí)間段，將在線值網(wǎng)絡(luò)的參數(shù)復(fù)制到目標(biāo)值網(wǎng)絡(luò)，利用目標(biāo)值網(wǎng)絡(luò)計(jì)算目標(biāo)值，在線值網(wǎng)絡(luò)以及目標(biāo)值網(wǎng)絡(luò)的更新如圖1所示。其中：s為智能體的當(dāng)前狀態(tài)；st+1為智能體的下一個(gè)狀態(tài)；r為獎(jiǎng)勵(lì)；a為機(jī)器人的當(dāng)前動(dòng)作；at+1為機(jī)器人的下一個(gè)動(dòng)作；γ為折扣因子；ω為主網(wǎng)絡(luò)權(quán)值；ω-是目標(biāo)網(wǎng)絡(luò)權(quán)值。

圖1 DQN算法流程

狀態(tài)值函數(shù)求取目標(biāo)值即目標(biāo)值函數(shù)為：

DQN通過(guò)誤差更新網(wǎng)絡(luò)的權(quán)值，誤差評(píng)價(jià)函數(shù)為輸出值和目標(biāo)值的差的平方求期望，即：

Lt=E[(yt-Q(s,a,ω))2]

采用梯度下降法更新網(wǎng)絡(luò)權(quán)值參數(shù)(▽為梯度符號(hào))：

ωt+1=ωt+E[yt-Q(s,a,ω)]▽Q(s,a,ω)

更新參數(shù)ω-：由參數(shù)ω延遲更新獲得，即在參數(shù)ω實(shí)時(shí)更新，經(jīng)過(guò)若干輪迭代后，將當(dāng)前Q網(wǎng)絡(luò)的參數(shù)賦值給Q-target網(wǎng)絡(luò)。

1.2 過(guò)估計(jì)問(wèn)題

估計(jì)值與真實(shí)值在狀態(tài)s下的誤差Bs為：

γmaxa′Qtarget(s′,a′))=

γ(maxa′Qestimation(s′,a′)-maxa′Qtarget(s′,a′))=

maxa′Qtarget(s′,a′))=

1.3 過(guò)估計(jì)問(wèn)題的改善策略

B(st,at,rt,st+1)=

計(jì)算目標(biāo)值：yt=V*(s)×B(s,a)

1.4 算法步驟

(1) 初始化經(jīng)驗(yàn)回放存儲(chǔ)區(qū)D、Q網(wǎng)絡(luò)ω、目標(biāo)Q′其權(quán)值ω、ω-為隨機(jī)值。

(2) 開(kāi)始新一輪，生成環(huán)境、高峰、低谷、目標(biāo)點(diǎn)。

(3) 通過(guò)神經(jīng)網(wǎng)絡(luò)(卷積神經(jīng)網(wǎng)絡(luò))f(s,a,ω)≈Q*(s,a)輸入目前狀態(tài)S，輸出當(dāng)前狀態(tài)S下動(dòng)作ai(其中i=1,2,…,n)的Q值得到Q值向量[Q(s,a1),Q(s,a2),…,Q(s,an)]。

(5) 執(zhí)行動(dòng)作at，得到當(dāng)前獎(jiǎng)勵(lì)rt，下一時(shí)刻狀態(tài)st+1，將(st,at,rt,st+1)存入D，獎(jiǎng)勵(lì)函數(shù)為：

(6) 從D中隨機(jī)采樣一批數(shù)據(jù)，即一批(st,at,rt,st+1)四元組，計(jì)算變更函數(shù)(b<1)：

B(st,at,rt,st+1)=

計(jì)算目標(biāo)值：yt=V*(s)×B(s,a)用Q-target網(wǎng)格計(jì)算目標(biāo)值V*(s)，sT為最終狀態(tài)：

(7) 損失函數(shù)：

式中：Q(s,a,ω)為當(dāng)前網(wǎng)絡(luò)的輸出，用來(lái)評(píng)估當(dāng)前狀態(tài)動(dòng)作對(duì)的值函數(shù)；Q(st+1,at+1,ω-)為Q-target的輸出，用來(lái)求得目標(biāo)值函數(shù)的Q值。然后更新參數(shù)ω和ω-。

2 實(shí) 驗(yàn)

2.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證NDQN的性能，本文在Python和MATLAB實(shí)驗(yàn)環(huán)境下對(duì)DQN和NDQN做對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)中的三維環(huán)境是積木型的，同時(shí)具有符合現(xiàn)實(shí)意義的高峰和低谷，與傳統(tǒng)二維環(huán)境相比，其障礙物具有一定的可通過(guò)性，比如在智能體允許通過(guò)的高峰和低谷范圍內(nèi)，三維環(huán)境中是可通過(guò)的，且可詳細(xì)計(jì)算需要消耗的能量與時(shí)間，三維環(huán)境更加符合現(xiàn)實(shí)意義的地理環(huán)境。

本文將初始化回憶記憶單位的大小設(shè)置為14 400，折扣因子初始化為0.9，更正函數(shù)的底數(shù)b初始化為0.9，以步長(zhǎng)0.1減少到0.4，貪心算法中進(jìn)行探索的概率ε隨著步長(zhǎng)的增長(zhǎng)由1逐漸減少為0.1。尋找最優(yōu)結(jié)果。雙網(wǎng)絡(luò)結(jié)構(gòu)，分別是在線值網(wǎng)絡(luò)和目標(biāo)值網(wǎng)絡(luò)。兩個(gè)網(wǎng)絡(luò)都是卷積神經(jīng)網(wǎng)絡(luò)，并且網(wǎng)絡(luò)的結(jié)構(gòu)都是一樣的，僅權(quán)值不同，目標(biāo)值網(wǎng)絡(luò)的權(quán)值來(lái)自在線值網(wǎng)絡(luò)的權(quán)值，周期設(shè)置為300步。

通過(guò)將MATLAB與Python緊密結(jié)合，運(yùn)用到三維路徑規(guī)劃中，能夠更加真實(shí)地反映現(xiàn)實(shí)環(huán)境中的路況，更好地詮釋三維環(huán)境中的路徑規(guī)劃。圖2為三維環(huán)境路徑規(guī)劃實(shí)現(xiàn)流程。

圖2 實(shí)現(xiàn)三維環(huán)境路徑規(guī)劃流程

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

本文將NDQN和DQN應(yīng)用在三維路徑規(guī)劃問(wèn)題中，分別從平均獎(jiǎng)勵(lì)值、從起點(diǎn)到終點(diǎn)所需步驟數(shù)、誤差分析圖三個(gè)方面的收斂圖對(duì)兩種算法進(jìn)行分析。平均獎(jiǎng)勵(lì)值越穩(wěn)定，從起點(diǎn)到終點(diǎn)所需的平均步驟數(shù)越少，誤差越小，說(shuō)明算法的性能越好。因?yàn)樯窠?jīng)網(wǎng)絡(luò)是Q表的泛化模型，使深度Q網(wǎng)絡(luò)存在不穩(wěn)定問(wèn)題，為了緩解不穩(wěn)定問(wèn)題，DQN采用雙網(wǎng)絡(luò)結(jié)構(gòu)和記憶回放機(jī)制提高了穩(wěn)定性。和之前相似，DQN和NDQN在三維環(huán)境下，在路徑、所需步數(shù)，以及獎(jiǎng)勵(lì)函數(shù)值的收斂圖上進(jìn)行對(duì)比。

圖3為將深度神經(jīng)網(wǎng)絡(luò)應(yīng)用于三維路徑規(guī)劃中所得的路線圖。兩種算法都得從起點(diǎn)至終點(diǎn)路徑完全避開(kāi)高峰或者低谷，取得滿(mǎn)足實(shí)際情況的較優(yōu)越的路線。說(shuō)明在復(fù)雜的三維環(huán)境中，深度神經(jīng)網(wǎng)絡(luò)沒(méi)有維數(shù)災(zāi)難的問(wèn)題，且能夠讓機(jī)器人得到良好的路徑規(guī)劃。黑色方塊為NDQN的實(shí)驗(yàn)路線，灰白色方塊為DQN的實(shí)驗(yàn)路線。經(jīng)過(guò)實(shí)驗(yàn)，NDQN與DQN所得的路線具有一定區(qū)別。雖然DQN也找到一條良好的路線，但其時(shí)而會(huì)經(jīng)過(guò)半坡的地方，且不是最優(yōu)路線，會(huì)陷入在低谷旁邊徘徊的情況。NDQN圖中的路線較DQN彎路少，且沒(méi)有爬坡情況出現(xiàn)。因此，上述針對(duì)過(guò)估計(jì)問(wèn)題的改善策略，NDQN得到的最優(yōu)路線優(yōu)于DQN。

圖3 DQN和NDQN的最優(yōu)路線圖

如圖4和圖5所示，通過(guò)平均獎(jiǎng)賞值分析算法的性能。以往的研究中平均獎(jiǎng)賞值越高，算法性能越優(yōu)越，而在此三維環(huán)境下的路徑規(guī)劃，由于給予沒(méi)有坡度、沒(méi)有坑的地方的獎(jiǎng)勵(lì)值為7，平均獎(jiǎng)勵(lì)值越高，并不一定是算法越優(yōu)越，而很大可能是選擇的路徑不是最優(yōu)路徑。所以在三維環(huán)境下的路徑規(guī)劃，應(yīng)分析平均獎(jiǎng)賞值的收斂性以及穩(wěn)定性。由圖4-圖5可以看出，NDQN在三維路徑規(guī)劃上取得了比DQN更穩(wěn)定的平均獎(jiǎng)賞值，且NDQN在1 000代左右就找到穩(wěn)定的較高的平均獎(jiǎng)賞值。在不同起終點(diǎn)變化的場(chǎng)景下，計(jì)算總共120次DQN和NDQN的平均獎(jiǎng)賞值再求平均之后得到：NDQN比DQN收斂速度快大約60%。這說(shuō)明上述針對(duì)過(guò)估計(jì)問(wèn)題的改善策略，NDQN得到的平均獎(jiǎng)賞值更穩(wěn)定。

圖4 DQN獎(jiǎng)賞值收斂圖

圖5 NDQN獎(jiǎng)賞值收斂圖

如圖6和圖7所示，通過(guò)誤差分析算法的性能。和以往分析相同，誤差越小，算法性能越優(yōu)越。可以很明顯看出，相對(duì)于DQN，NDQN的收斂速度變化不明顯。但是，NDQN收斂時(shí)損失函數(shù)的值比DQN低了21%左右。說(shuō)明上述針對(duì)過(guò)估計(jì)問(wèn)題的改善策略，在不同起終點(diǎn)變化的場(chǎng)景下，NDQN得到的損失函數(shù)值降低。同時(shí)計(jì)算總共120次DQN和NDQN的損失函數(shù)值再求平均之后得到：NDQN得到的損失函數(shù)值減少21%。

圖6 DQN損失函數(shù)值收斂圖

圖7 NDQN損失函數(shù)值收斂圖

如圖8和圖9所示，通過(guò)誤差分析算法的性能。和以往分析相同，從起點(diǎn)到終點(diǎn)所需的平均步驟數(shù)越低，算法性能越優(yōu)越?？梢院苊黠@看出，NDQN相比DQN有著更好的穩(wěn)定性，而且震蕩的幅度比較低，所需的平均步驟數(shù)降低了大約25%。這說(shuō)明上述針對(duì)過(guò)估計(jì)問(wèn)題的改善策略，在不同起終點(diǎn)變化的場(chǎng)景下，NDQN得到的平均步驟數(shù)量降低。同時(shí)計(jì)算總共120次DQN和NDQN的損失函數(shù)值再求平均之后得到：NDQN得到的平均步驟數(shù)量降低25%。

圖8 DQN所需步數(shù)收斂圖

圖9 NDQN所需步數(shù)收斂圖

3 結(jié) 語(yǔ)

本文針對(duì)三維環(huán)境的路徑規(guī)劃問(wèn)題，提出改進(jìn)深度強(qiáng)化學(xué)習(xí)算法。算法中加入了差值增長(zhǎng)概念，使得與最優(yōu)值相差越近的非最優(yōu)值變化得較大，反之，與最優(yōu)值相差越遠(yuǎn)的非最優(yōu)值變化得較小。實(shí)驗(yàn)結(jié)果顯示：

(1) 改進(jìn)的算法 NDQN在三維環(huán)境中得到的路徑明顯優(yōu)于DQN得到的路徑，且在平均獎(jiǎng)賞值、算法的穩(wěn)定性、收斂性上都比DQN有一定程度的提高。

(2) 本文提出的更正函數(shù)應(yīng)用在深度Q網(wǎng)絡(luò)中可以有效地緩解深度Q網(wǎng)絡(luò)存在的過(guò)估計(jì)問(wèn)題。

總之，NDQN方法可以在更少迭代次數(shù)內(nèi)得到更穩(wěn)定的累積獎(jiǎng)賞值，從而使得智能體可以在最短時(shí)間內(nèi)獲得最優(yōu)路徑。