錢(qián)信，呂成伊，宋世杰

(1.中國(guó)電子科技集團(tuán)公司第三十六研究所，浙江 嘉興 314000;2.南昌大學(xué)信息工程學(xué)院，江西 南昌 330031)

路徑規(guī)劃是指在有障礙物的工作環(huán)境中，機(jī)器人依據(jù)某種評(píng)價(jià)標(biāo)準(zhǔn)，在運(yùn)動(dòng)空間中尋找一條可以避開(kāi)障礙物的最優(yōu)或者接近最優(yōu)的路徑[1]。路徑規(guī)劃的算法有很多，如人工勢(shì)場(chǎng)法[2]、蟻群算法[3]、SARSA算法[4]、Q-learning算法[5]等，其中Q-learning算法作為一種可以探索未知環(huán)境模型的強(qiáng)化學(xué)習(xí)算法，成為近年來(lái)的研究熱點(diǎn)。毛國(guó)君等[6]提出一種改進(jìn)ζ-Q-learning算法，引入動(dòng)態(tài)搜索因子，依據(jù)環(huán)境反饋動(dòng)態(tài)調(diào)節(jié)貪婪因子ζ，提高了算法的收斂速度，Low等[7]將花授粉算法(FPA)與Q-learning算法相結(jié)合優(yōu)化Q表初始值，加速Q(mào)-learning算法的收斂。雖然Q-Learning算法用于路徑規(guī)劃問(wèn)題上的研究有不少，但如何解決其收斂速度慢、如何平衡探索與利用的關(guān)系等問(wèn)題仍是現(xiàn)在研究的熱點(diǎn)[8]。

為了提高Q-Learning算法的效率，本文融入先驗(yàn)知識(shí)，利用人工勢(shì)場(chǎng)優(yōu)化Q-learning算法的Q表初值，引導(dǎo)機(jī)器人在尋優(yōu)初期就能選擇更合適的動(dòng)作；采用多步長(zhǎng)策略，增加機(jī)器人的動(dòng)作集，使機(jī)器人能夠向更多的方向移動(dòng)，增加其靈活性；動(dòng)態(tài)調(diào)節(jié)貪婪因子，使機(jī)器人在尋優(yōu)初期有更多的機(jī)會(huì)積累經(jīng)驗(yàn)，隨著迭代次數(shù)的增加，再增加機(jī)器人利用經(jīng)驗(yàn)選擇動(dòng)作的概率，從而合理平衡探索與利用的關(guān)系。

1 Q-learning算法

Q-learning算法不需要構(gòu)建模型，是強(qiáng)化學(xué)習(xí)中最經(jīng)典的算法。該算法的基本流程[9]為：首先根據(jù)智能體的狀態(tài)集S和動(dòng)作集A建立一個(gè)Q表，智能體在當(dāng)前狀態(tài)s(s∈S)下選擇動(dòng)作a(a∈A)時(shí)將會(huì)獲得環(huán)境反饋的獎(jiǎng)勵(lì)r，之后智能體會(huì)從當(dāng)前狀態(tài)s轉(zhuǎn)移到下一狀態(tài)s'，并獲得回報(bào)的估計(jì)值Q(s,a)。然后用估計(jì)值Q(s,a)對(duì)Q表進(jìn)行更新，若智能體的動(dòng)作行為得到環(huán)境獎(jiǎng)勵(lì)，Q(s,a)就會(huì)增大，若動(dòng)作行為得到環(huán)境懲罰，Q(s,a)會(huì)減小。Q表的更新依賴(lài)動(dòng)作價(jià)值函數(shù)，動(dòng)作價(jià)值函數(shù)如式(1)。

Q(s,a)=Q(s,a)+α[R(s,a)+
γmaxAQ(s',a)-Q(s,a)]

(1)

式中:α表示學(xué)習(xí)率，是權(quán)衡上一次學(xué)習(xí)的結(jié)果和這一次學(xué)習(xí)結(jié)果的量，α∈[0,1]。Q(s,a)表示當(dāng)前狀態(tài)動(dòng)作的估計(jì)值，Q(s',a)為下一狀態(tài)動(dòng)作的估計(jì)值。R(s,a)表示在當(dāng)前狀態(tài)s下執(zhí)行某個(gè)動(dòng)作a，環(huán)境立即給予的獎(jiǎng)勵(lì)值。maxAQ(s',a)表示在動(dòng)作集A中選擇使Q(s',a)最大的動(dòng)作。γ表示獎(jiǎng)勵(lì)值的折扣因子，是考慮后續(xù)動(dòng)作獎(jiǎng)勵(lì)對(duì)當(dāng)前狀態(tài)影響的因子，γ∈[0,1]。γ值接近1表示智能體會(huì)著重考慮后續(xù)狀態(tài)的價(jià)值，即Q(s,a)的估計(jì)值不僅和智能體當(dāng)前得到的獎(jiǎng)勵(lì)值R(s,a)相關(guān)，與Q(s',a)的獎(jiǎng)勵(lì)值也有很大的關(guān)聯(lián)。γ值接近0表示智能體只考慮當(dāng)前的利益影響，即Q(s,a)的估計(jì)值與當(dāng)前得到的獎(jiǎng)勵(lì)值R(s,a)有很大關(guān)系，與Q(s',a)的獎(jiǎng)勵(lì)值關(guān)系較弱。

2 IMD-Q-learnig算法

為解決Q-learning算法用于路徑規(guī)劃時(shí)存在的收斂速度慢、難以平衡探索與利用的關(guān)系等問(wèn)題，本文將從Q表初值、機(jī)器人移動(dòng)步長(zhǎng)以及貪婪因子等3個(gè)方面對(duì)Q-learning算法進(jìn)行改進(jìn)，為討論方便，改進(jìn)后的算法稱(chēng)為IMD-Q-learning。

2.1 Q表初始化

傳統(tǒng)Q-learning算法在初始化時(shí)，一般是2個(gè)選擇，使Q表的初值為0或者隨機(jī)數(shù)[10]，這使得機(jī)器人在探索環(huán)境的初期具有盲目性，導(dǎo)致尋優(yōu)時(shí)間過(guò)長(zhǎng)。本文引入人工勢(shì)場(chǎng)法的思想并對(duì)其進(jìn)行改進(jìn)，有導(dǎo)向性地對(duì)Q表進(jìn)行初始化，使移動(dòng)機(jī)器人可以更快地適應(yīng)障礙環(huán)境，提高算法的尋優(yōu)效率。

人工勢(shì)場(chǎng)法假設(shè)目標(biāo)點(diǎn)和障礙物對(duì)機(jī)器人分別有引力勢(shì)場(chǎng)和斥力勢(shì)場(chǎng)[11]，引力勢(shì)場(chǎng)定義為

(2)

式中：Uatt(p)為引力勢(shì)場(chǎng)；Φ為引力勢(shì)場(chǎng)正增益系數(shù)；ρ(p,pgoal)為機(jī)器人當(dāng)前位置p與目標(biāo)點(diǎn)位置pgoal的歐幾里得距離。顯然機(jī)器人離目標(biāo)點(diǎn)越遠(yuǎn)引力勢(shì)場(chǎng)越小。

斥力勢(shì)場(chǎng)定義為

(3)

式中:Urep(p)為斥力勢(shì)場(chǎng)；η為斥力勢(shì)場(chǎng)增益系數(shù)；ρ(p,pobs)為機(jī)器人位置p與障礙物位置pobs的歐幾里得距離；ρ0為障礙物的影響半徑，顯示機(jī)器人離障礙物越遠(yuǎn)所受斥力越小，當(dāng)機(jī)器人離障礙物的距離大于ρ0時(shí)，所受斥力勢(shì)場(chǎng)為0。

本文在Q-learning算法中引入勢(shì)場(chǎng)的目的是引導(dǎo)機(jī)器人在算法初期的動(dòng)作選擇，使機(jī)器人能夠更早地朝著目標(biāo)點(diǎn)的方向移動(dòng)，同時(shí)回避障礙物，因此本文中機(jī)器人的總勢(shì)場(chǎng)不是傳統(tǒng)的引力勢(shì)場(chǎng)與斥力勢(shì)場(chǎng)之和，而是引力勢(shì)場(chǎng)與斥力勢(shì)場(chǎng)的倒數(shù)之和，這樣做的目的是使距離目標(biāo)點(diǎn)近并且附近沒(méi)有障礙物，即機(jī)器人的總勢(shì)場(chǎng)為

U(p)=Uatt(p)+1/Urep(p)

(4)

式中:U(p)為機(jī)器人處于位置p時(shí)受到的總勢(shì)場(chǎng)；Uatt(p)為機(jī)器人處于位置p時(shí)受到的引力勢(shì)場(chǎng)；Urep(p)為機(jī)器人處于位置p時(shí)受到的斥力勢(shì)場(chǎng)。

對(duì)式(4)進(jìn)行歸一化處理，得

(5)

式中:Umax(p)代表勢(shì)場(chǎng)能最大的值。

Q表的初始值Q0(s,a)定義為

Q0(s,a)=r+γU'(s)

(6)

式中:γ為折扣因子；r為反饋獎(jiǎng)勵(lì)值，其值為

(7)

2.2 多步長(zhǎng)策略

Q-learning算法一次只能移動(dòng)一個(gè)步長(zhǎng)，效率低[12]，本文提出了多步長(zhǎng)動(dòng)作選擇策略，增加機(jī)器人的動(dòng)作集并優(yōu)化Q-learning算法的動(dòng)作選擇，使移動(dòng)機(jī)器人只進(jìn)行一次移動(dòng)，就可以達(dá)到傳統(tǒng)算法多次移動(dòng)的效果。

如圖1所示，圖中黑色方框?yàn)檎系K物，其他為自由柵格，設(shè)A為機(jī)器人所處位置，以A為中心的虛線區(qū)域?yàn)闄C(jī)器人使用多步長(zhǎng)可以一步到達(dá)的范圍(此處假設(shè)最大步長(zhǎng)為3)，從A點(diǎn)到B點(diǎn)，使用單步長(zhǎng)時(shí)，機(jī)器人一次只能移動(dòng)一個(gè)柵格，需要移動(dòng)5次才能到達(dá)B點(diǎn)，如圖中曲線①，若采用多步長(zhǎng)，機(jī)器人只需移動(dòng)2次就能到達(dá)B點(diǎn)，并且路徑更優(yōu)，如圖中曲線②。可見(jiàn)采用多步長(zhǎng)策略不僅可以尋到更優(yōu)的路徑，而且算法的迭代次數(shù)少，路徑中出現(xiàn)的拐點(diǎn)個(gè)數(shù)也少。

圖1 多步長(zhǎng)動(dòng)作選擇策略Fig.1 Multi-step action selection strategy

需要注意的是，采用單步長(zhǎng)時(shí)，Q-learning算法共有8個(gè)動(dòng)作可供選擇[13]，如圖2所示，若采用多步長(zhǎng)，Q-learning算法可供選擇的動(dòng)作將大大增加，并且步長(zhǎng)越大可供選擇的動(dòng)作越多，圖3所示為步長(zhǎng)等于2時(shí)Q-learning算法可選擇的動(dòng)作。

圖2 步長(zhǎng)為1時(shí)的動(dòng)作Fig.2 Action when step size is 1

由于步長(zhǎng)大時(shí)Q-learning算法的尋優(yōu)效率更高并且路徑更優(yōu)，為鼓勵(lì)機(jī)器人采用大步長(zhǎng)，本文對(duì)Q-learning算法的獎(jiǎng)勵(lì)函數(shù)進(jìn)行改進(jìn)，即在原獎(jiǎng)勵(lì)函數(shù)的基礎(chǔ)上，增加一個(gè)多步長(zhǎng)動(dòng)作選擇獎(jiǎng)勵(lì)值，如式(8)所示。

(8)

式中:rx為多步長(zhǎng)額外獎(jiǎng)勵(lì)值rx=(l-1)v;l為步長(zhǎng)長(zhǎng)度;v為單步移動(dòng)的獎(jiǎng)勵(lì)，顯然步長(zhǎng)越大到達(dá)下一柵格得到的獎(jiǎng)勵(lì)就越大;而r1、r2和r3為常數(shù)，并且r1>r2>r3。

圖3 步長(zhǎng)為2時(shí)的動(dòng)作Fig.3 Action when step size is 2

2.3 動(dòng)態(tài)調(diào)節(jié)貪婪因子

探索與利用的關(guān)系是Q-learning算法的重點(diǎn)和難題[14]，為更好地平衡探索與利用的關(guān)系，本文提出以迭代次數(shù)作為自變量的動(dòng)態(tài)調(diào)節(jié)函數(shù)ζ(t)。

(9)

式中:e為自然對(duì)數(shù)底數(shù)；t為迭代次數(shù)；K1、K2為常數(shù)。動(dòng)態(tài)調(diào)節(jié)函數(shù)ζ(t)在迭代初期取最大值，使移動(dòng)機(jī)器人在尋優(yōu)的初始階段能對(duì)環(huán)境進(jìn)行充分探索，增加對(duì)環(huán)境信息的利用率。隨著迭代次數(shù)的增加，機(jī)器人已經(jīng)學(xué)習(xí)到了一些尋找最優(yōu)路徑的經(jīng)驗(yàn)，此時(shí)調(diào)節(jié)函數(shù)ζ(t)隨著探索次數(shù)的增加而衰減，減少了選擇隨機(jī)動(dòng)作的概率，增加了選擇價(jià)值最大動(dòng)作的概率。動(dòng)態(tài)調(diào)節(jié)函數(shù)ζ(t)避免了機(jī)器人因貪婪因子值恒定而無(wú)法在探索過(guò)程中學(xué)習(xí)到經(jīng)驗(yàn)，從而只能找到次優(yōu)路徑的問(wèn)題。

3 仿真及結(jié)果分析

3.1 構(gòu)建柵格地圖以及設(shè)置參數(shù)

圖4 柵格地圖環(huán)境Fig.4 Grid map environment

3.2 仿真結(jié)果與分析

在上述環(huán)境下分別測(cè)試了以下4種算法：

(1)Q-learning算法；

(2)動(dòng)態(tài)調(diào)節(jié)貪婪因子的Q-learning算法；

(3)優(yōu)化Q表初值和多步長(zhǎng)的Q-learning算法；

(4)IMD-Q-learning算法。

圖5所示為上述環(huán)境下的最優(yōu)路徑，其中Q-learning算法最優(yōu)路徑的長(zhǎng)度為33，拐點(diǎn)數(shù)為15。動(dòng)態(tài)調(diào)節(jié)貪婪因子的Q-learning算法的最優(yōu)路徑長(zhǎng)度為33，拐點(diǎn)數(shù)為14。優(yōu)化初始值和增加動(dòng)作的Q-learning算法的最優(yōu)路徑長(zhǎng)度為11.06，拐點(diǎn)數(shù)為12。IMD-Q-learning算法的最優(yōu)路徑長(zhǎng)度為6.9，拐點(diǎn)個(gè)數(shù)為8。

(a) Q-learning算法

算法收斂曲線如圖6所示，圖中用n代表迭代次數(shù)，m代表步數(shù)。其中Q-learning算法的迭代次數(shù)n為2 500，動(dòng)態(tài)調(diào)節(jié)貪婪因子的Q-learning算法的迭代次數(shù)n為1 500，優(yōu)化初始值和增加動(dòng)作的Q-learning算法的迭代次數(shù)n為380，IMD-Q-learning算法的迭代次數(shù)n為290。

n/次(a) Q-learning算法

將上述參數(shù)列于表1，表中l(wèi)為最優(yōu)路徑長(zhǎng)度，n為迭代次數(shù)?？芍?，與Q-learning算法相比，本文所提出的IMD-Q-learning算法，其最優(yōu)路徑長(zhǎng)度縮短了79.09%，拐點(diǎn)個(gè)數(shù)減少46.67%，算法效率提升了88.40%。

表1 路徑綜合評(píng)價(jià)表Tab.1 Path comprehensive evaluation table

4 結(jié)論

(1)采用改進(jìn)后的勢(shì)場(chǎng)對(duì)Q-learning算法的Q表初始值進(jìn)行優(yōu)化，將引力勢(shì)場(chǎng)與斥力勢(shì)場(chǎng)的倒數(shù)之和的歸一化值作為Q表初值，從而在算法初期機(jī)器人經(jīng)驗(yàn)不多的情況下引導(dǎo)機(jī)器人選擇更合適的動(dòng)作，能夠更早地朝著目標(biāo)點(diǎn)的方向移動(dòng)，減少迭代次數(shù)。

(2)采用多步長(zhǎng)策略，增加機(jī)器人的動(dòng)作，使機(jī)器人一次可以移動(dòng)多個(gè)步長(zhǎng)，優(yōu)化了尋優(yōu)路徑，并且減少了算法的迭代次數(shù)和路徑中的拐點(diǎn)個(gè)數(shù)。

(3)采用動(dòng)態(tài)調(diào)節(jié)貪婪因子，使機(jī)器人在尋優(yōu)初期有更多的機(jī)會(huì)對(duì)環(huán)境進(jìn)行探索，積累經(jīng)驗(yàn)，隨著迭代次數(shù)的逐步增加，機(jī)器人已經(jīng)學(xué)習(xí)到了一些尋找最優(yōu)路徑的經(jīng)驗(yàn)，此時(shí)慢慢增加機(jī)器人利用經(jīng)驗(yàn)選擇動(dòng)作的概率，平衡探索與利用的關(guān)系。

(4)使用Python中的Tkinter庫(kù)，構(gòu)建20×20的柵格地圖環(huán)境并進(jìn)行仿真，結(jié)果證明，與Q-learning算法相比，改進(jìn)后的IMD-Q-learning算法在最優(yōu)路徑、收斂速度等方面都得到了大幅度提升。