基于改進(jìn)DQN算法的NPC行進(jìn)路線規(guī)劃研究

劉 森，李 璽，黃 運(yùn)

(1.河北遠(yuǎn)東通信系統(tǒng)工程有限公司， 河北 石家莊 050200；2.陸軍工程大學(xué)石家莊校區(qū)，河北 石家莊 050000;3.中國人民解放軍32620部隊(duì)，青海 西寧 810007)

0 引言

在軍事游戲或仿真訓(xùn)練系統(tǒng)中，非玩家角色(No-player Character,NPC)的智能化水平在很大程度上決定了模擬訓(xùn)練的效果。構(gòu)建NPC的核心是進(jìn)行行為建模。行為建模分為認(rèn)知行為建模和物理行為建模，行進(jìn)路線的規(guī)劃則是NPC物理行為建模的重要組成部分。傳統(tǒng)的NPC行進(jìn)路線規(guī)劃主要采用固定路線或利用有限狀態(tài)機(jī)、行為樹構(gòu)建腳本等方式。前者相對(duì)比較原始，很難有效提升模擬訓(xùn)練的效果，后者具有一定的智能性，但是面對(duì)復(fù)雜多變的戰(zhàn)場(chǎng)環(huán)境往往不能靈活應(yīng)對(duì)。本文針對(duì)上述問題開展研究，利用強(qiáng)化學(xué)習(xí)(Reinforcement Learning,RL)的方法設(shè)計(jì)NPC行進(jìn)路線規(guī)劃算法，實(shí)現(xiàn)NPC行進(jìn)路線的智能化選擇。

近年來，深度學(xué)習(xí)(Deep Learning,DL)和RL相結(jié)合產(chǎn)生的深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)，使傳統(tǒng)的RL擴(kuò)展到高維度狀態(tài)空間和高維度動(dòng)作空間等以前無法解決的領(lǐng)域[1]。特別是Mnih等人[2]提出的深度Q網(wǎng)絡(luò)(Deep Q-Network,DQN)將DRL的研究推向新的高度。目前，各國學(xué)者利用DRL在機(jī)器人控制[3-4]、游戲[5]和無人駕駛[6-7]等領(lǐng)域開展了廣泛而深入的研究。其中,基于DRL的路線規(guī)劃研究[8-14]也是熱點(diǎn)之一，同時(shí)也是多領(lǐng)域的基礎(chǔ)應(yīng)用研究內(nèi)容。

上述研究多關(guān)注于如何進(jìn)行避障，而在此基礎(chǔ)上如何實(shí)現(xiàn)最優(yōu)路線的選擇研究較少。另外，由于DQN算法在經(jīng)驗(yàn)回放時(shí)采用均勻的采樣方法，不利于算法的收斂。本文針對(duì)DQN算法收斂性差和最優(yōu)路線選取問題進(jìn)行改進(jìn)，提出PRDQN算法。該算法利用基于SumTree的優(yōu)先經(jīng)驗(yàn)回放方法取代了DQN算法的均勻采樣回放機(jī)制，并重新設(shè)計(jì)了獎(jiǎng)勵(lì)函數(shù)。實(shí)驗(yàn)證明，該算法相對(duì)于DQN算法不僅提高了收斂速度，而且實(shí)現(xiàn)了路線的優(yōu)化。

1 PRDQN算法

1.1 Q-learning算法

Q-learning是RL的經(jīng)典算法，核心是智能體通過與環(huán)境的不斷交互學(xué)習(xí)，更新和完善Q-table，以達(dá)到智能決策的目的。Q-table的行代表狀態(tài)，列代表行動(dòng)，表格的數(shù)值即Q-value是在不同狀態(tài)下采取相應(yīng)行動(dòng)時(shí)能夠獲得的最大的未來期望獎(jiǎng)勵(lì)。Q-learning算法利用式(1)來計(jì)算Q-value:

Q(st,at)=Q(st,at)+

α[rt+γmaxQ(st+1,at+1)-Q(st,at)]。

(1)

式(1)展開可得：

Q(st,at)=(1-α)Q(st,at)+

α[rt+γmaxQ(st+1,at+1)]。

(2)

將式(2)進(jìn)行迭代，得：

Q(st,at)=(1-α)Q(st,at)+α[rt+γmaxQ(st+1,at+1)]=

(1-α){(1-α)Q(st,at)+

α[rt+γmaxQ(st+1,at+1)]}+

α[rt+γmaxQ(st+1,at+1)]=

(1-α)2Q(st,at)+

[1-(1-α)2][rt+γmaxQ(st+1,at+1)]=

…=

(1-α)nQ(st,at)+

[1-(1-α)n][rt+γmaxQ(st+1,at+1)],

(3)

式中，st為t時(shí)刻的狀態(tài)；at為t時(shí)刻采取的行動(dòng)；st+1為t+1時(shí)刻的狀態(tài)；at+1為t+1時(shí)刻采取的動(dòng)作；Q(st,at)為st狀態(tài)下采用行動(dòng)at的值函數(shù)；α為學(xué)習(xí)率；rt為t時(shí)刻已經(jīng)獲得的獎(jiǎng)勵(lì)；γ為衰減因子。由于α∈(0,1)，因此0<α-1<1，當(dāng)n→∞時(shí)，(1-α)n→0，則式(3)可變?yōu)椋?/p>

Q(st,at)=rt+γmaxQ(st+1,at+1)。

(4)

式(4)即是在各類程序中，計(jì)算st狀態(tài)下采用行動(dòng)at的Q值公式。

利用Q-learning算法實(shí)現(xiàn)RL簡單明了，并且不存在收斂性的問題。但是，當(dāng)狀態(tài)空間S和行動(dòng)空間A足夠大時(shí)，Q-table會(huì)變得非常大，從而導(dǎo)致維數(shù)災(zāi)難。因此，純粹的Q-learning算法很少用于解決現(xiàn)實(shí)中的各類應(yīng)用問題。

1.2 DQN算法

針對(duì)Q-learning算法存在的維數(shù)災(zāi)難問題，DeepMind團(tuán)隊(duì)的Mnih等人將深度卷積神經(jīng)網(wǎng)絡(luò)和Q-learning結(jié)合，利用卷積神經(jīng)網(wǎng)絡(luò)動(dòng)態(tài)生成Q-table，不僅避免了復(fù)雜空間的維數(shù)災(zāi)難，而且在一定程度上解決了非線性函數(shù)近似表示值函數(shù)的不穩(wěn)定問題。

DQN算法示意如圖1所示，算法定義了2個(gè)相對(duì)獨(dú)立且結(jié)構(gòu)相同的網(wǎng)絡(luò)，分別是訓(xùn)練網(wǎng)絡(luò)(TrainingNet)和目標(biāo)網(wǎng)絡(luò)(TargetNet)。利用Q-learning算法，智能體通過與環(huán)境的交互，實(shí)現(xiàn)訓(xùn)練網(wǎng)絡(luò)的學(xué)習(xí)。經(jīng)過固定步數(shù)的訓(xùn)練后，將訓(xùn)練網(wǎng)絡(luò)中的參數(shù)全部賦值給目標(biāo)網(wǎng)絡(luò)。設(shè)置經(jīng)驗(yàn)回放單元的目的是減少訓(xùn)練樣本的相關(guān)行，改善神經(jīng)網(wǎng)絡(luò)逼近強(qiáng)化學(xué)習(xí)的動(dòng)作值函數(shù)不穩(wěn)定的問題。每次訓(xùn)練時(shí)從經(jīng)驗(yàn)庫中均勻選取一批樣本與訓(xùn)練樣本混合在一起，破壞相鄰訓(xùn)練樣本的相關(guān)性，提高樣本的利用率。

圖1 DQN算法示意Fig.1 Schematic diagram of DQN algorithm

DQN的損失函數(shù)是目標(biāo)網(wǎng)絡(luò)的Q-value與評(píng)估網(wǎng)絡(luò)的Q-value差的平方值，表示為：

LOSSt=(targetQt-Q(st,at,wt))2，

(5)

式中，targetQ根據(jù)式(4)可得：

targetQt=rt+γmaxQ′(st+1,at+1,wt+1)，

(6)

w為網(wǎng)絡(luò)參數(shù)，采用梯度下降法學(xué)習(xí)：

wt+1=wt+E[targetQt-Q(st,at,wt)]Q(st,at,wt)。

(7)

1.3 改進(jìn)算法

傳統(tǒng)的DQN算法利用經(jīng)驗(yàn)回放機(jī)制，阻斷了訓(xùn)練樣本的相關(guān)行，改善了不穩(wěn)定的問題，但是采用均勻采樣的方式不利于算法的收斂。另外，DQN算法獎(jiǎng)勵(lì)函數(shù)設(shè)置的比較簡單，往往不能實(shí)現(xiàn)最優(yōu)路線的規(guī)劃。本文針對(duì)經(jīng)驗(yàn)回放和獎(jiǎng)勵(lì)函數(shù)進(jìn)行了改進(jìn)，提出了PRDQN算法。

1.3.1 基于SumTree的優(yōu)先經(jīng)驗(yàn)回放

SumTree采用二叉樹結(jié)構(gòu)，如圖2所示。節(jié)點(diǎn)存儲(chǔ)的是樣本的優(yōu)先級(jí)(Priority)，數(shù)值越大，優(yōu)先級(jí)越高，通過這種方式可以讓好的樣本重復(fù)利用的幾率更大。SumTree中，只有葉子節(jié)點(diǎn)代表具體樣本，非葉子節(jié)點(diǎn)沒有實(shí)際意義，父節(jié)點(diǎn)的優(yōu)先級(jí)是子節(jié)點(diǎn)優(yōu)先級(jí)的和。葉子節(jié)點(diǎn)的優(yōu)先級(jí)通過TD-error[15-17]確定，TD-error是樣本在利用時(shí)序差分(Temporal Difference,TD)更新時(shí)目標(biāo)網(wǎng)絡(luò)值函數(shù)與訓(xùn)練網(wǎng)絡(luò)值函數(shù)的差值，本文TD-error的值采用損失函數(shù)值，如式(5)所示。差值越大說明預(yù)測(cè)精度還有較大的上升空間，被訓(xùn)練的價(jià)值就越大，因此優(yōu)先級(jí)越高。葉子節(jié)點(diǎn)下面的數(shù)值代表該樣本對(duì)應(yīng)的數(shù)值區(qū)間，優(yōu)先級(jí)高的葉子節(jié)點(diǎn)對(duì)應(yīng)的數(shù)值區(qū)間大，在均勻采樣的過程中被選中的概率就高。SumTree的算法實(shí)現(xiàn)如算法1所示。

圖2 SumTree示意Fig.2 Schematic diagram of SumTree

算法1:SumTree算法1) Def SumTree(節(jié)點(diǎn))2) if節(jié)點(diǎn)==葉子節(jié)點(diǎn)3) ifPriority節(jié)點(diǎn)

以圖2為例，假如從(0,52)中抽取樣本S=25，則從SumTree的根節(jié)點(diǎn)0開始，由于左子節(jié)點(diǎn)1的優(yōu)先級(jí)為22，小于25，所以選擇右子節(jié)點(diǎn)2，同時(shí)S=25-22=3，然后判斷節(jié)點(diǎn)2的左子節(jié)點(diǎn)5的優(yōu)先級(jí)值是否大于3，依次判斷下去，最后選擇節(jié)點(diǎn)12。

1.3.2 獎(jiǎng)勵(lì)函數(shù)的設(shè)計(jì)

在RL過程中，智能體在與環(huán)境的交互中能夠獲得獎(jiǎng)勵(lì)，驅(qū)使智能體在不斷的嘗試中選擇獲得獎(jiǎng)勵(lì)多的行為策略。傳統(tǒng)的DQN算法獎(jiǎng)勵(lì)函數(shù)的設(shè)置如下：

(8)

式中，C通常為正整數(shù)?？梢钥闯?，除去到達(dá)目的地和發(fā)生碰撞外，其他情況下智能體獲得的獎(jiǎng)勵(lì)都是0，通過大量訓(xùn)練雖然能夠使智能體到達(dá)目的地，但是無法獲取最優(yōu)路線。為此，本文重新設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)，在沒有到達(dá)目的地或發(fā)生碰撞時(shí)，判斷下一個(gè)行動(dòng)到達(dá)的點(diǎn)中哪一個(gè)距離終點(diǎn)距離更近，距離最近的點(diǎn)對(duì)應(yīng)的行動(dòng)獎(jiǎng)勵(lì)設(shè)為βC：

(9)

式中，與目的地的距離通過歐式距離公式計(jì)算得出，即:

(10)

式中，x(x1,x2,…,xn)是當(dāng)前位置坐標(biāo)；y(y1,y2,…,yn)是目的地坐標(biāo)。

1.3.3 算法描述

本文提出的PRDQN算法流程如下。

算法2:PRDQN算法1) 生成訓(xùn)練數(shù)據(jù)集2) 初始化設(shè)置,利用CNN生成訓(xùn)練網(wǎng)絡(luò)(TrainingNet)和目標(biāo)網(wǎng)絡(luò)(TargetNet)3) 生成初始Q-table4) 訓(xùn)練網(wǎng)絡(luò)5) 設(shè)置epochs,batchsize等相關(guān)變量6) while count

2 實(shí)驗(yàn)及結(jié)果分析

為了驗(yàn)證算法的有效性，本文設(shè)計(jì)了如下實(shí)驗(yàn)。隨機(jī)生成200張25 pixel×25 pixel的圖片作為NPC行進(jìn)訓(xùn)練地圖，每張圖根據(jù)不同的起點(diǎn)，再生成25×25=625張圖片，共計(jì)125 000張，圖中隨機(jī)生成若干黑色像素點(diǎn)代表地圖中的障礙。NPC從左上角的像素點(diǎn)[0,0]出發(fā)，到達(dá)右下角的像素點(diǎn)[24,24]則完成路線規(guī)劃，中途碰到障礙則失敗。實(shí)驗(yàn)軟件環(huán)境：python 3.8,tensorflow 2.4.0,pycharm 2020.3.2。

本文設(shè)計(jì)了2層卷積網(wǎng)絡(luò)加2層全連接網(wǎng)絡(luò)的結(jié)構(gòu)，卷積核大小為2*2，由于圖像包含3個(gè)通道，因此卷積核的厚度為3，第1次卷積包含10個(gè)卷積核，第2次卷積包含20個(gè)卷積核，第1層全連接層包含100個(gè)神經(jīng)元，第2層全連接層包含2個(gè)神經(jīng)元，生成的網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示。

圖3 算法中深度卷積網(wǎng)絡(luò)的處理過程Fig.3 Processing flow of deep convolution network in the algorithm

實(shí)驗(yàn)程序參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置表Tab.1 Parameter setting

訓(xùn)練過程中的參數(shù)變化如圖4所示。橫軸代表w值，縱軸代表的是分布數(shù)量，每個(gè)切片代表在當(dāng)前訓(xùn)練步數(shù)下w值的分布情況。

使用同樣的訓(xùn)練集，分別對(duì)傳統(tǒng)DQN算法和PRDQN算法進(jìn)行訓(xùn)練，損失函數(shù)的變化情況如圖5所示。

從圖5的實(shí)驗(yàn)結(jié)果可以看出，本文提出的PRDQN算法在收斂性上要好于傳統(tǒng)DQN算法，在訓(xùn)練步數(shù)到達(dá)1 000時(shí)，就可以將損失函數(shù)值穩(wěn)定地控制在30以下。

訓(xùn)練完成之后，隨機(jī)生成10張測(cè)試用圖，對(duì)傳統(tǒng)DQN算法和PRDQN算法進(jìn)行測(cè)試，結(jié)果如圖6所示。

從圖6的實(shí)驗(yàn)結(jié)果可以看出，PRDQN算法生成的規(guī)劃路線基本沿圖像對(duì)角線方向，從行進(jìn)的角度來說，利于NPC在最短的時(shí)間內(nèi)到達(dá)指定地點(diǎn)，不僅實(shí)現(xiàn)了路線規(guī)劃，而且優(yōu)化了行進(jìn)路線。傳統(tǒng)DQN算法雖然也能夠完成路線規(guī)劃，但是路線明顯比較曲折。

(a) 第1卷積層的w值

(a) 傳統(tǒng)DQN算法

(a) 傳統(tǒng)DQN算法的測(cè)試效果

3 結(jié)束語

本文改進(jìn)了傳統(tǒng)DQN算法的經(jīng)驗(yàn)回放機(jī)制和獎(jiǎng)勵(lì)函數(shù)，設(shè)計(jì)了PRDQN算法。該算法基于TD-error為經(jīng)驗(yàn)回放單元中的樣本設(shè)置優(yōu)先級(jí)，并利用SumTree算法實(shí)現(xiàn)了優(yōu)先級(jí)經(jīng)驗(yàn)回放機(jī)制。同時(shí)，根據(jù)NPC行進(jìn)的需求，重新設(shè)計(jì)了獎(jiǎng)勵(lì)函數(shù)。實(shí)驗(yàn)證明，PRDQN算法在收斂性和最優(yōu)路線規(guī)劃方面都優(yōu)于傳統(tǒng)的DQN算法。

目前,算法應(yīng)用于二維地圖中，動(dòng)作空間限于二維空間。在三維仿真訓(xùn)練系統(tǒng)中，行為策略將在三維空間中展開，需要針對(duì)獎(jiǎng)勵(lì)函數(shù)做進(jìn)一步改進(jìn)，考慮地形起伏等更多維度的因素對(duì)NPC行進(jìn)的影響。