井征淼，劉宏杰，周永錄

（云南大學信息學院，昆明 650504）

0 引言

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

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

1 Q-learning 算法

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

1.1 馬爾科夫決策過程

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

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

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

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

2 人工勢場法

人工勢場法的基本原理為構造出一個虛擬的類似于物理學中電磁場的一個勢場［13］，該勢場包括兩部分：1）在障礙物附近構造斥力勢場，2）在目標點附近構建引力勢場，而機器人則在這兩種勢場作用下去探索一條無碰撞的運動路徑。

2.1 引力函數(shù)

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

2.2 斥力函數(shù)

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

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

3 改進Q-learning 算法

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

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

3.1 動態(tài)選擇獎勵值

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

3.2 計算值后更新Q 值

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

改進后的Q 表更新公式：

3.3 改進Q-learning 算法的步驟

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

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

Step 2 對Q 表進行初始化。令Q（s，a）=0。

Step 3 初始化狀態(tài)s。回到起點位置，初始化狀態(tài)s。

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

Step 5 選擇動作a。機器人在目前狀態(tài)s 下使用ε-greedy 策略進行動作選擇并執(zhí)行，根據(jù)動作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 計算引力函數(shù)數(shù)值，動態(tài)選擇獎勵值。對狀態(tài)s'進行檢查，判斷s'的狀態(tài)，若s'不為障礙物狀態(tài)，則計算上一個狀態(tài)的引力函數(shù)Uatt及更新后狀態(tài)的引力函數(shù)Uatt'，對比兩個引力函數(shù)數(shù)值，動態(tài)選擇獎勵值。

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

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

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

圖1 改進Q-learning 算法流程圖Fig.1 Flow chart of improved Q-learning algorithm

4 實驗仿真

4.1 仿真條件

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

4.2 仿真參數(shù)

使用如圖2 所示Pycharm 構造的20×20 柵格地圖下進行仿真實驗，紅色的格子代表移動機器人所在的起點位置，黃色的格子代表移動機器人的目標終點位置，黑色的圖形代表障礙物，移動機器人的可行動作空間包括：上、下、左、右4 個動作。

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

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

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

4.3 仿真實驗驗證及分析

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

表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 引入引力場算法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ī)劃路線圖，紅色為起點位置，黃色是終點位置，灰色為移動機器人的避障路徑。

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

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

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

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

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

在圖9 的柵格地圖中進行實驗仿真，仿真結果如圖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 引入引力場算法Ⅱ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 引入引力場算法路徑規(guī)劃路線圖ⅡFig.14 Path planning roadmap II WithiIntroduction of gravitational field algorithm

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

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

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

5 結論

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