基于改進(jìn)Q-learning 算法的移動(dòng)機(jī)器人路徑規(guī)劃

井征淼，劉宏杰，周永錄

（云南大學(xué)信息學(xué)院，昆明 650504）

0 引言

隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，人工智能應(yīng)用在近年來已成為研究熱點(diǎn)，而其中備受關(guān)注的就是移動(dòng)機(jī)器人應(yīng)用。在對(duì)移動(dòng)機(jī)器人的研究里，路徑規(guī)劃是極其重要的核心部分，能夠直接反映出移動(dòng)機(jī)器人的智能程度［1］。路徑規(guī)劃是指在給定的區(qū)域范圍內(nèi)，讓移動(dòng)機(jī)器人在不碰到障礙物的情況下，發(fā)現(xiàn)起點(diǎn)與終點(diǎn)之間的一條無(wú)碰撞的通路［2］。根據(jù)障礙物的類別，可將其分為靜態(tài)障礙物與動(dòng)態(tài)障礙物，本文將重點(diǎn)探尋靜態(tài)障礙物環(huán)境下移動(dòng)機(jī)器人的路徑規(guī)劃問題。

現(xiàn)今的路徑規(guī)劃算法按照特點(diǎn)可以分為基于傳統(tǒng)方式的方法和基于人工智能的方法，基于傳統(tǒng)方式的方法包括A*算法、遺傳算法、粒子群算法、人工勢(shì)場(chǎng)法等，基于人工智能的方法包括Q-learning 算法、Sarsa 算法等［3-5］。作為機(jī)器學(xué)習(xí)算法的分支，Q-learning 算法在移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域有了十分顯著的成果［6，10］，但是該算法在應(yīng)用中仍然存在許多問題，如算法收斂速度慢、學(xué)習(xí)時(shí)間長(zhǎng)、花費(fèi)代價(jià)高等。因此，如何解決這些問題，是當(dāng)前人工智能領(lǐng)域里學(xué)者重點(diǎn)關(guān)注的內(nèi)容。徐曉蘇等在Q 值初始化的過程中引入了人工勢(shì)場(chǎng)法中的引力勢(shì)場(chǎng)，從而使收斂速度加快，再通過在狀態(tài)集中增加了方向因素，使規(guī)劃路線的精度得以提高［6］。楊秀霞等在環(huán)境建模時(shí)設(shè)置每個(gè)階段的搜索步長(zhǎng)，設(shè)置獎(jiǎng)勵(lì)池與獎(jiǎng)勵(lì)閾值，使路徑規(guī)劃為全局最優(yōu)路徑［7］。毛國(guó)君等引入了動(dòng)態(tài)搜索因子，根據(jù)環(huán)境的反饋來動(dòng)態(tài)調(diào)整貪婪因子，降低了算法搜索代價(jià)［8］。王付宇等利用螢火蟲算法初始化Q 值，設(shè)計(jì)了貪婪搜索和玻爾茲曼搜索結(jié)合的混合選擇搜索，使算法學(xué)習(xí)時(shí)間減少，且在路徑平滑度等方面有了進(jìn)一步提升［9］。由此可見，雖然Q-learning 算法在路徑規(guī)劃領(lǐng)域已研究許久，但如何加快收斂速度、減少學(xué)習(xí)時(shí)間、降低花費(fèi)代價(jià)等依然是目前移動(dòng)機(jī)器人路徑規(guī)劃研究的重點(diǎn)和熱點(diǎn)問題［10-11］。

1 Q-learning 算法

作為機(jī)器學(xué)習(xí)領(lǐng)域的一種極其重要的學(xué)習(xí)方法，強(qiáng)化學(xué)習(xí)在移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃的領(lǐng)域受到了更多的關(guān)注和應(yīng)用［12］，主要是針對(duì)機(jī)器人進(jìn)行的研究，以解決機(jī)器人在環(huán)境中不斷學(xué)習(xí)后，能得出一個(gè)合理決策，即獲得最大獎(jiǎng)勵(lì)的問題。

1.1 馬爾科夫決策過程

馬爾科夫決策過程多數(shù)應(yīng)用于一定量的動(dòng)作和不同模式的決策分析模型中，MDP 模型即具有決策狀態(tài)的馬爾可夫獎(jiǎng)勵(lì)過程。而馬爾可夫決策過程定義為MDP={S，A，P，R，γ}，其中：S 為所用可行狀態(tài)的空間，A 為所有可行動(dòng)作的空間，P 為預(yù)判可能動(dòng)作的概率矩陣，R 為獲得的正負(fù)向獎(jiǎng)勵(lì)，γ 為折扣系數(shù)。馬爾可夫?qū)傩员硎鞠乱粻顟B(tài)的內(nèi)容只取決于當(dāng)前狀態(tài)的決策而不受之前狀態(tài)決策的影響。

1.2 傳統(tǒng)Q-learning 算法

Q-learning 算法是強(qiáng)化學(xué)習(xí)中較為經(jīng)典的算法之一，其特性是value-based 的算法，也是一種時(shí)間差分更新方法［5］。它的基本內(nèi)容包括機(jī)器人、動(dòng)作、狀態(tài)、獎(jiǎng)勵(lì)、環(huán)境。Q-learning 算法將機(jī)器人與環(huán)境之間的交互過程看成是一個(gè)馬爾科夫決策過程。Q-learning 的學(xué)習(xí)過程為：機(jī)器人在當(dāng)前狀態(tài)s 下，選擇某一策略進(jìn)行動(dòng)作的選擇，該策略通常為ε-greedy 策略，在可行動(dòng)作空間中選擇動(dòng)作a 去執(zhí)行，再根據(jù)此動(dòng)作后獲得的獎(jiǎng)勵(lì)以及新狀態(tài)s'對(duì)Q表進(jìn)行更新，更新公式為：

式中，α 表示學(xué)習(xí)率，γ 表示折扣系數(shù)，α 與γ 的取值范圍在（0，1）之間。ε-greedy 策略是一種貪心選擇策略，ε 表示貪心度，取值范圍在（0，1）之間，表示系統(tǒng)有ε 的概率在可行動(dòng)作空間中選擇Q 值最大的動(dòng)作執(zhí)行，有1-ε 的概率在可行動(dòng)作空間內(nèi)任意地選擇一個(gè)動(dòng)作執(zhí)行。

2 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法的基本原理為構(gòu)造出一個(gè)虛擬的類似于物理學(xué)中電磁場(chǎng)的一個(gè)勢(shì)場(chǎng)［13］，該勢(shì)場(chǎng)包括兩部分：1）在障礙物附近構(gòu)造斥力勢(shì)場(chǎng)，2）在目標(biāo)點(diǎn)附近構(gòu)建引力勢(shì)場(chǎng)，而機(jī)器人則在這兩種勢(shì)場(chǎng)作用下去探索一條無(wú)碰撞的運(yùn)動(dòng)路徑。

2.1 引力函數(shù)

引力場(chǎng)應(yīng)滿足隨著距離目標(biāo)點(diǎn)越近而呈現(xiàn)單調(diào)遞增的性質(zhì)。

2.2 斥力函數(shù)

斥力場(chǎng)應(yīng)滿足隨著距離障礙物越遠(yuǎn)而呈現(xiàn)單調(diào)遞減的性質(zhì)。

式中，η 為斥力增益系數(shù)，ρ（q-q0）表示當(dāng)前點(diǎn)和機(jī)器人附件障礙物區(qū)域中離機(jī)器人較近的點(diǎn)q0之間的距離，ρ0表示在機(jī)器人周圍障礙物區(qū)域?qū)C(jī)器人產(chǎn)生的最大距離。

3 改進(jìn)Q-learning 算法

傳統(tǒng)的Q-learning 算法對(duì)于在柵格地圖中的路徑規(guī)劃是把每一個(gè)柵格歸于可行狀態(tài)空間中，每個(gè)狀態(tài)的可行動(dòng)作空間為上、下、左、右，并且每個(gè)動(dòng)作的步長(zhǎng)為一個(gè)柵格的大小。其在柵格地圖路徑規(guī)劃中存在收斂速度慢、花費(fèi)代價(jià)高、運(yùn)行時(shí)間長(zhǎng)的缺陷。

針對(duì)這些缺陷，本文在傳統(tǒng)Q-learning 算法的基礎(chǔ)上結(jié)合人工勢(shì)場(chǎng)法對(duì)其進(jìn)行了一些改進(jìn)，主要思想是引入人工勢(shì)場(chǎng)法的引力函數(shù)與斥力函數(shù)。首先用引力函數(shù)對(duì)獎(jiǎng)勵(lì)函數(shù)進(jìn)行改進(jìn)，從而起到啟發(fā)式作用，明確機(jī)器人前進(jìn)的方向。其次用斥力函數(shù)創(chuàng)造一個(gè)值對(duì)Q 表的更新公式進(jìn)行改進(jìn)，使機(jī)器人運(yùn)動(dòng)時(shí)會(huì)選擇向離障礙物更遠(yuǎn)的位置移動(dòng)。

3.1 動(dòng)態(tài)選擇獎(jiǎng)勵(lì)值

檢查目前狀態(tài)是否為終點(diǎn)狀態(tài)或障礙物狀態(tài)，若為否，則計(jì)算目前狀態(tài)的引力函數(shù)Uatt與前一狀態(tài)的引力函數(shù)Uatt'，判斷Uatt、Uatt'之間的大小關(guān)系，如果目前狀態(tài)的引力函數(shù)大于前一狀態(tài)的引力函數(shù)，說明移動(dòng)機(jī)器人在進(jìn)行狀態(tài)改變之后距離終點(diǎn)狀態(tài)越來越遠(yuǎn)。根據(jù)目前狀態(tài)的引力函數(shù)與前一狀態(tài)的引力函數(shù)的對(duì)比，動(dòng)態(tài)地選擇獎(jiǎng)勵(lì)值，這就使移動(dòng)機(jī)器人在前進(jìn)時(shí)可以保持向終點(diǎn)方向，達(dá)到具有目的性地去選擇下一個(gè)狀態(tài)的位置，從而避免了盲目地去探索每個(gè)位置。為使機(jī)器人能盡快學(xué)會(huì)避開障礙物和到達(dá)終點(diǎn)，故對(duì)到達(dá)終點(diǎn)取較高獎(jiǎng)勵(lì)值，對(duì)到達(dá)障礙物取較低獎(jiǎng)勵(lì)值。根據(jù)上述的獎(jiǎng)勵(lì)值函數(shù)為：

3.2 計(jì)算值后更新Q 值

檢查目前狀態(tài)是否為終點(diǎn)狀態(tài)或障礙物狀態(tài)，若為否，則計(jì)算目前狀態(tài)的斥力函數(shù)Urep與前一狀態(tài)的斥力函數(shù)Urep'，判斷Urep、Urep'的大小關(guān)系以及目前狀態(tài)的斥力函數(shù)是否大于設(shè)定值1，如果當(dāng)前狀態(tài)的斥力函數(shù)大于前一狀態(tài)的斥力函數(shù)，說明移動(dòng)機(jī)器人在進(jìn)行狀態(tài)改變之后距離障礙物越來越遠(yuǎn)。而目前狀態(tài)的斥力函數(shù)小于1，則表示移動(dòng)機(jī)器人的位置距離障礙物較遠(yuǎn)，值較小，可以忽略不計(jì)。所以當(dāng)目前狀態(tài)的斥力函數(shù)大于前一狀態(tài)的斥力函數(shù)，且目前狀態(tài)的斥力函數(shù)大于設(shè)定值1 時(shí)，動(dòng)態(tài)計(jì)算值，并將值代入Q 表更新公式中，使移動(dòng)機(jī)器人在Q 表更新后更傾向于選擇距離障礙物更遠(yuǎn)的狀態(tài)位置，從而在很大程度上提升機(jī)器人避開障礙物的能力。計(jì)算值的公式如下：

改進(jìn)后的Q 表更新公式：

3.3 改進(jìn)Q-learning 算法的步驟

根據(jù)上述內(nèi)容，給出改進(jìn)Q-learning 算法的詳細(xì)步驟如下：

Step 1 初始化環(huán)境、參數(shù)。確定柵格環(huán)境的大小，確定起點(diǎn)位置、終點(diǎn)位置、障礙物位置確定起點(diǎn)位置、終點(diǎn)位置、障礙物位置，選擇合適的學(xué)習(xí)率α，折扣系數(shù)γ，選擇合適的ε-greedy 策略中的epsilon值，以及設(shè)置最大迭代次數(shù)episode。

Step 2 對(duì)Q 表進(jìn)行初始化。令Q（s，a）=0。

Step 3 初始化狀態(tài)s?；氐狡瘘c(diǎn)位置，初始化狀態(tài)s。

Step 4 判斷是否為終點(diǎn)。若為是，選擇獎(jiǎng)勵(lì)值，更新Q 值，Q（s，a）更新為然后執(zhí)行Step 10；若為否，則執(zhí)行Step 5。

Step 5 選擇動(dòng)作a。機(jī)器人在目前狀態(tài)s 下使用ε-greedy 策略進(jìn)行動(dòng)作選擇并執(zhí)行，根據(jù)動(dòng)作a更新狀態(tài)s 為s'。

Step 6 判斷s'是否為障礙物狀態(tài)。若為是，更新Q 值，Q（s，a）更新為返回上一步狀態(tài)s，執(zhí)行Step 5；若為否，執(zhí)行Step 7。

Step 7 計(jì)算引力函數(shù)數(shù)值，動(dòng)態(tài)選擇獎(jiǎng)勵(lì)值。對(duì)狀態(tài)s'進(jìn)行檢查，判斷s'的狀態(tài)，若s'不為障礙物狀態(tài)，則計(jì)算上一個(gè)狀態(tài)的引力函數(shù)Uatt及更新后狀態(tài)的引力函數(shù)Uatt'，對(duì)比兩個(gè)引力函數(shù)數(shù)值，動(dòng)態(tài)選擇獎(jiǎng)勵(lì)值。

Step 9 計(jì)算Q 值，更新Q 表。Q（s，a）更新為，后執(zhí)行Step 4。

Step 10 判斷迭代次數(shù)episode 是否達(dá)到設(shè)置的最大迭代次數(shù)，若判斷結(jié)果為是，則結(jié)束整個(gè)學(xué)習(xí)過程，若為否，則回到Step 3。

根據(jù)上述算法過程，可得改進(jìn)Q-learning 算法的流程圖如圖1 所示。

圖1 改進(jìn)Q-learning 算法流程圖Fig.1 Flow chart of improved Q-learning algorithm

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

4.1 仿真條件

仿真實(shí)驗(yàn)在Pycharm2022.1.3 的環(huán)境下進(jìn)行。操作系統(tǒng)為windows11 x64，使用的編譯工具包為python3.10.5，設(shè)備參數(shù)為Intel i7-12700H、DDR5 16GB和RTX 3060。

4.2 仿真參數(shù)

使用如圖2 所示Pycharm 構(gòu)造的20×20 柵格地圖下進(jìn)行仿真實(shí)驗(yàn)，紅色的格子代表移動(dòng)機(jī)器人所在的起點(diǎn)位置，黃色的格子代表移動(dòng)機(jī)器人的目標(biāo)終點(diǎn)位置，黑色的圖形代表障礙物，移動(dòng)機(jī)器人的可行動(dòng)作空間包括：上、下、左、右4 個(gè)動(dòng)作。

圖2 路徑規(guī)劃柵格地圖示意圖IFig.2 Schematic diagram I of path planning grid map

在仿真實(shí)驗(yàn)中，3 種算法所使用的實(shí)驗(yàn)參數(shù)如表1 所示。

表1 算法實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters of the algorithm

4.3 仿真實(shí)驗(yàn)驗(yàn)證及分析

根據(jù)上述的實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)參數(shù)，在圖2 所示的柵格地圖下進(jìn)行傳統(tǒng)Q-learning 算法、引入引力場(chǎng)的算法與本文算法的實(shí)驗(yàn)仿真。將3 種算法分別進(jìn)行了連續(xù)150 次迭代實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如下頁(yè)圖3～圖8 及第140 頁(yè)表2 所示。由圖3 可得，傳統(tǒng)Q-learning 算法在迭代次數(shù)為101 次時(shí)趨于收斂，由圖4 可得，引入引力場(chǎng)的算法在迭代次數(shù)為60 次時(shí)趨于收斂，由圖5 可得，本研究的改進(jìn)Q-learning 算法在迭代次數(shù)為21 次時(shí)趨于收斂。對(duì)比圖3～圖5 可以看出，在收斂之前，傳統(tǒng)Q-learning 算法和引入引力場(chǎng)的算法使用了較多的步數(shù)去探索，而本文改進(jìn)Q-learning 算法使用的步數(shù)很少，證明了在相同的仿真環(huán)境情況下，本研究改進(jìn)的Q-learning 算法在探索期間具有更強(qiáng)的目的性找到下一位置，從而使探索的步數(shù)大為降低，且能更快地達(dá)到收斂。

表2 3 種算法仿真數(shù)據(jù)ITable 2 Simulation data 1 of three kinds of algorithms

圖3 傳統(tǒng)Q learning 算法迭代收斂圖IFig.3 Iterative convergence diagram of traditional Q learning algorithm I

圖4 引入引力場(chǎng)算法IFig.4 Algorithm I for introduction of gravitational field

圖5 本文算法迭代收斂圖IFig.5 Iterative convergence diagram I of the studied algorithm

圖6～圖8 為3 種算法在柵格地圖示意圖1 中所得到的路徑規(guī)劃路線圖，紅色為起點(diǎn)位置，黃色是終點(diǎn)位置，灰色為移動(dòng)機(jī)器人的避障路徑。

圖6 傳統(tǒng)Q-learning 算法路徑規(guī)劃路線圖IFig.6 Path planning roadmap I with traditional Q-learning algorithm

圖8 改進(jìn)Q-learning 算法路徑規(guī)劃路線圖IFig.8 Path planning roadmap I with Improved Q-learning algorithm

下頁(yè)表2 是3 種算法在進(jìn)行了150 次迭代的仿真數(shù)據(jù)對(duì)比。根據(jù)圖6～圖8 及表2 可以看出，本文算法較之其他算法具有更高的效率，并且能花更少的代價(jià)完成學(xué)習(xí)，以及更不易與障礙物相撞，能夠快速地使移動(dòng)機(jī)器人找到一條無(wú)碰撞的通路。

接下來在障礙物擺放更為復(fù)雜的環(huán)境中對(duì)3種算法進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)參數(shù)與上相同，環(huán)境柵格地圖如圖9 所示。

圖9 路徑規(guī)劃柵格地圖示意圖IIFig.9 Schematic diagram II of path planning grid map

在圖9 的柵格地圖中進(jìn)行實(shí)驗(yàn)仿真，仿真結(jié)果如圖10～圖12、圖13～圖15 和表3 所示。

表3 3 種算法仿真數(shù)據(jù)ⅡTable 3 Simulation data II of three kinds of algorithms

圖10 傳統(tǒng)Q-learning 算法收斂圖ⅡFig.10 Convergence diagram II of traditional Q-learning algorithm

圖11 引入引力場(chǎng)算法ⅡFig.11 Introduction of gravity field algorithm II

圖12 本研究算法收斂圖ⅡFig.12 Convergence diagram II of the studied algorithm

圖13 傳統(tǒng)Q-learning 算法路徑規(guī)劃路線圖ⅡFig.13 Path planning roadmap II with traditional Q-learning algorithm

圖14 引入引力場(chǎng)算法路徑規(guī)劃路線圖ⅡFig.14 Path planning roadmap II WithiIntroduction of gravitational field algorithm

圖15 改進(jìn)Q-learning 算法路徑規(guī)劃路線圖ⅡFig.15 Path planning roadmap II with improved Q-learning algorithm

圖13～圖15 為3 種算法在柵格地圖示意圖2中所得到的路徑規(guī)劃路線圖。

根據(jù)以上的仿真結(jié)果可得，本研究的改進(jìn)Q-learning 算法在障礙物更復(fù)雜的環(huán)境中，依然具有較少的探索步數(shù)和較快收斂的能力，并且撞到障礙物的概率較之其他算法更低。

5 結(jié)論

針對(duì)傳統(tǒng)的Q-learning 算法在移動(dòng)機(jī)器人路徑規(guī)劃時(shí)存在收斂速度慢、花費(fèi)代價(jià)高、運(yùn)行時(shí)間長(zhǎng)的缺陷，本文提出了將人工勢(shì)場(chǎng)法與傳統(tǒng)Q-learning算法結(jié)合的一種改進(jìn)Q-learning 算法，利用引力函數(shù)來動(dòng)態(tài)地選擇獎(jiǎng)勵(lì)值，使移動(dòng)機(jī)器人在探索時(shí)就明確了方向，避免了盲目探索；利用斥力函數(shù)來動(dòng)態(tài)地更新Q 值，達(dá)到遠(yuǎn)離障礙物的目的，從而能夠更快速、更準(zhǔn)確地到達(dá)終點(diǎn)位置。實(shí)驗(yàn)表明，改進(jìn)后的Q-learning 算法收斂速度明顯加快，所需代價(jià)降低，運(yùn)行效率提高，并且更加不易與障礙物相撞，更有利于移動(dòng)機(jī)器人在路徑規(guī)劃方面的實(shí)際應(yīng)用。