基于改進Q-learning的AGV路徑規劃研究

摘" 要：針對AGV路徑規劃中的收斂速度慢和路徑動態調整的問題，提出了一種改進的Q-learning算法。首先，引入了曼哈頓距離作為額外的啟發信息，結合Q-learning算法進行路徑規劃，以加速算法的收斂速度。其次，增加了故障點的考慮，并在路徑規劃過程中動態調整路徑，驗證了算法對于動態環境的可行性。此外，還設計了路徑中可以收集貨物的機制，使得AGV在執行任務的同時能夠完成貨物的搬運任務。通過對比實驗，驗證了改進算法在不同場景下的有效性和性能優勢。實驗結果表明，改進的Q-learning算法在提高收斂速度、適應復雜環境和靈活執行任務方面取得了顯著的效果，為AGV路徑規劃提供了一種新的解決方案。

關鍵詞：路徑規劃；曼哈頓距離；動態調整；貨物收集

中圖分類號：F253.9" " 文獻標志碼：A" " DOI：10.13714/j.cnki.1002-3100.2025.01.006

Abstract： For addressing the slow convergence and dynamic path adjustment issues in AGV path planning， an enhanced Q-learning algorithm is proposed. Firstly， the Manhattan distance is introduced as additional heuristic information， combined with the Q

-learning algorithm for path planning to accelerate the convergence speed of the algorithm. Secondly， the consideration of fault points is added， and the path is dynamically adjusted during the path planning process， validating the algorithm's feasibility for dynamic environments. Additionally， a mechanism for collecting goods along the path is designed， allowing the AGV to perform cargo transportation tasks while executing its main tasks. Through comparative experiments， the effectiveness and performance advantages of the improved algorithm in various scenarios are verified. The experimental results demonstrate significant improvements in convergence speed， adaptation to complex environments， and flexible task execution， providing a novel solution for AGV path planning.

Key words： path planning; Manhattan distance; dynamic adjustment; cargo collection

0" 引" 言

自動導引車（Automated Guided Vehicle，AGV）路徑規劃是該領域的一個核心問題，其核心目標是在存在障礙物限制的情況下，根據已知的起點和終點，以最短路徑或最短時間為優先考慮，尋找一條最佳或接近最佳的安全且通暢的路徑。由于應用場景廣泛，因此大體可以分為兩種應用場景，即全局靜態場景和局部動態場景。不同場景也有不同算法適配，如全局靜態場景普遍為全局信息已知，常用算法為蟻群算法[1]、Dijkstra算法[2]、A*算法[3]等；局部動態場景為部分信息未知或動態改變，常用算法為動態窗口法[4]、強化學習[5]等。

針對AGV路徑規劃問題，文獻[6]針對AGV局部路徑規劃，提出了基于強化學習混合增強蟻群算法。針對傳統蟻群算法效率低下的缺陷，提出將置信上界（Upper Confidence Bound，UCB）算法中的UCB值和Q值更新策略引入蟻群算法、改善啟發函數、改進障礙節點懲罰原則以及綜合局部最佳路徑的路線搜索方法，使得最短路線的搜尋效率得到提升；文獻[7]提出一種改進的動態調整探索因子ε策略，即在強化學習的不同階段選擇不同的探索因子ε值，提高了改進后強化學習算法的收斂速度以及調高了收斂結果的穩定性。文獻[8]設計了一種啟發式獎勵函數和啟發式動作選擇策略，以此強化智能體對優質行為的探索，提高算法學習效率并證明了改進啟發式強化學習算法在探索次數、規劃時間、路徑長度與路徑轉角上都具有一定的優勢。

目前采用強化學習算法解決AGV路徑規劃問題的研究上，大多存在迭代次數過多、收斂速度慢、實用性較差等現象，本文在增加多種貼合實際的實驗場景的前提下，提出一種改進Q-learning算法，可以更高效地解決強化學習效率低下的問題，同時驗證可行性。

1" 環境概述

在本文所考慮的路徑規劃問題中，地圖呈現為一個柵格地圖，并且智能體只能執行上、下、左、右四個基本動作。地圖中包含了起點、障礙點和終點，它們都被建模成了橢圓形矩形。

地圖坐標表示為橢圓形矩形的左上角和右下角的位置。起點的坐標為10，10，50，50，終點的坐標為550，550，590，590，其他障礙物坐標如圖1所示。其中前兩個數字表示了左上角的坐標，而后兩個數字則表示了右下角的坐標。

在這樣的地圖環境下，智能體需要保證在避開障礙物的同時，從起點移動到終點。由于動作約束僅限于上、下、左、右四個方向，智能體只能選擇這四個動作中的一個來執行。因此，路徑規劃問題在這樣的地圖環境中變得更加具體和實際。

這種地圖表示方法能夠清晰地定義地圖的布局和智能體的行動空間，為路徑規劃算法的設計和實現提供了基礎。同時，通過合理設計起點、障礙點和終點的位置和形狀，也可以模擬出各種復雜的路徑規劃場景，從而驗證算法的性能和魯棒性。

2" 改進Q-learning算法

2.1" Q-learning算法工作原理

Q-learning算法是一種經典的強化學習算法，其工作原理基于馬爾可夫決策過程（Markov Decision Process， MDP）。其核心思想是通過學習一個價值函數（Value Function），來指導智能體在環境中做出動作，以達到最大化累積獎勵的目標。具體來說，Q-learning算法通過學習一個狀態-動作值函數（Q函數），記為Qs，a，其中：s表示狀態，a表示動作。這個函數表示在狀態s下采取動作a所能獲得的累積獎勵的期望值。Q-learning算法的更新規則如下：

Qs，a=Qs，a+αr+γmaxQs，a-Qs，a" " " " " " " " " " " " " " " " "（1）

式中：α是學習率，r是智能體執行動作a后所獲得的即時獎勵，γ是折扣因子，s是執行動作a后智能體進入的下一個狀態，maxQs，a表示在下一個狀態下采取所有可能動作中能夠獲得的最大累積獎勵的值。

Q-learning算法通過不斷地與環境交互，根據當前狀態和動作的獎勵來更新Q值，以逐步優化智能體的決策策略。在訓練過程中，智能體通過探索-利用策略來平衡探索新策略和利用已有經驗的權衡，最終學得一個最優的策略來在環境中實現特定的任務。

2.2" Q-learning算法改進

2.2.1" 曼哈頓距離

曼哈頓距離[9]，又稱為城市街區距離或L1距離，是一種常用的距離度量方式，用于衡量在規定了直角坐標系中兩點之間的距離。它的命名來源于曼哈頓的街道布局，其中車輛只能沿著網格狀的街道行駛，因此兩點之間的距離必須沿著網格線走。在數學上，曼哈頓距離是通過將兩點的各坐標數值差的絕對值相加而得出的。具體而言，對于二維平面上的兩點Px，y和Px，y之間的曼哈頓距離d可以表示為（在正文中可能會引用到前文章節的內容，按照下面的方式進行敘述）：

d=x-x+y-y" " " " " " " " " " " " " " " " " " " " " "（2）

而在更高維度的空間中，曼哈頓距離的計算方式類似，即將各坐標分量的絕對值之和作為距離。相較于其他距離度量方式如歐氏距離，曼哈頓距離更直觀地反映了在規定直角坐標系中，從一個點到另一個點沿著網格線移動所需的最小步數。

2.2.2" 增加啟發信息

傳統的Q-learning算法受限于僅考慮狀態、動作和獎勵，常常在訓練初期出現過度訓練的問題。這種情況顯著影響了學習速度和收斂速度，限制了其在實際應用中的效果。在路徑規劃問題中，地圖本身具有豐富的信息，其中包括未開發的參數，如距離。然而，傳統Q-learning算法并未充分利用這些信息，導致其在面對復雜環境時前期表現不佳。

為了克服這一問題，本文提出了一種新的Q-learning算法，即基于曼哈頓距離調整的方法。曼哈頓距離在路徑規劃領域被廣泛應用，特別適用于具有離散動作空間的問題。通過將曼哈頓距離融入獎勵函數中，可以在訓練過程中引導智能體更有效的學習，從而提高學習速度和收斂速度。

在本文研究中，將地圖上的曼哈頓距離作為一種額外的信息引入Q-learning算法中。具體地說根據智能體與目標之間的曼哈頓距離來調整獎勵值，從而在靠近目標的狀態下提供更多的獎勵。這種方式使得智能體更傾向于朝向目標移動，加速了學習過程的收斂。

此外，該方法幾乎適用于任何起點與終點的應用場景，因為曼哈頓距離作為一種啟發式函數[10]，能夠有效地指導路徑規劃過程。通過在后續實驗中驗證，發現基于曼哈頓距離調整的Q-learning算法相較于傳統方法在學習速度和收斂速度上均取得了顯著的提升。假設當前位置為x，x，y，y曼哈頓距離的計算公式表示為：

550-x+550-x/2+590-y+590-y/2" " " " " " " " " " " " " " " "（3）

2.2.3" 獎勵設計改進

在考慮到每個位置都有對應到達終點的曼哈頓距離情況下，可以調整獎勵函數，使得靠近終點的位置獲得更大的獎勵，以此來引導智能體更快地選擇靠近終點的路徑。

在對獎勵函數進行調整時，需要考慮到曼哈頓距離可能遠大于獎勵參數的情況。因此，歸一化處理是至關重要的，它確保了獎勵值的合理范圍，避免了過大的獎勵值對算法學習的干擾。通過引入歸一化參數，可以對曼哈頓距離進行適當的縮放，使得其范圍與獎勵參數相匹配。這樣一來，即使在距離較遠的位置，智能體也能夠獲得合理的獎勵，從而保持了對學習過程的有效引導。

在本文的應用場景中，曼哈頓距離最大為1 080，最小為0。通過歸一化后，得到了一個位于0，1范圍內的歸一化距離值。這個歸一化的距離值可以直觀地表示智能體距離終點的相對距離，并且保證不會過大的影響獎勵的分數，從而成為調整獎勵的重要依據。

將原本的固定獎勵進行變更，數學公式為：

r=r+d/maxd" " " " " " " " " " " " " " " " " " " " " " " "（4）

通過在獎勵函數中結合歸一化的曼哈頓距離，有效地將環境中的啟發信息引入到了Q-learning算法中，使得智能體更加智能地選擇動作，并更快地學習到最優策略。這種基于歸一化曼哈頓距離的獎勵調整策略為路徑規劃問題提供了一種新的思路和方法。

3" 方法設計與實現

本文利用Python實現傳統Q-learning算法和改進Q-learning算法，通過可視化路徑搜索展示它們在三種不同應用場景下的效果，并且在學習結束后，可視化最終選擇的路徑以及迭代次數和最終收益的折線圖。

這三種應用場景分別是最短路徑規劃、收集貨物路徑規劃以及動態故障點增加路徑規劃。通過比較兩種算法在這些場景下的性能差異，深入探討改進算法的優勢和適用性。

在最短路徑規劃場景中，將建立一個柵格地圖模型，并使用傳統Q-learning算法和改進Q-learning算法尋找起點到終點的最短路徑，完成一個最簡單的AGV路徑規劃問題；在收集貨物路徑規劃場景中，將考慮智能體需要在地圖上收集分布的貨物，然后再前往終點的場景，該場景更加貼合日常AGV運營方式；在動態故障點增加路徑規劃場景中，將模擬在地圖上增加故障點，智能體需要避開這些故障點并收集貨物找到最短路徑到達目標，該場景主要檢測應對突發情況，傳統Q-learning算法和改進Q-learning算法的應對能力。

通過可視化路徑搜索和可視化最終選擇的路徑以及迭代次數和最終收益的折線圖，可以清晰地觀察到傳統Q-learning算法和改進Q-learning算法在不同場景下的路徑搜索過程和結果并進行對比。在比對兩種算法的差異時，將著重考察它們在學習速度、路徑質量等的表現。這樣的對比分析有助于評估改進算法在解決實際問題中的應用潛力，并為進一步研究提供參考和啟示。

為保證實驗嚴謹性，所以實驗參數設置均為一致，如表1所示。

動作選擇策略添加了ε-greedy策略，貪婪系數逐次遞減0.001，以此保證智能體可以進行足夠的探索，并在后期可以利用已知信息來盡可能地執行最優動作。

兩種算法獎勵機制稍有不同，主要區別在于移動的獎勵，改進Q-learning獎勵增加了歸一化后的曼哈頓距離。如表2所示。

3.1" 最短路徑規劃

最短路徑規劃實驗中，首先考察了傳統Q-learning算法和改進Q-learning算法在尋找起點到終點的最短路徑方面的性能表現。傳統Q-learning算法最短路徑規和迭代次數以及改進Q-learning算法最短路徑規和迭代次數如圖2所示。

圖左為傳統Q-learning算法結果，圖右為改進Q-learning算法結果。從圖中可以觀察到，對于最短路徑的規劃問題，雖然路徑長短一致，但傳統Q-learning算法選擇的路徑存在7次轉彎，而改進Q-learning算法選擇的路徑則僅僅需要3次轉彎，具有一定優勢。而迭代次數方面，改進Q-learning算法在約1 500次迭代后趨于收斂，而傳統Q-learning算法則需要大約1 750次迭代才能達到相似的收斂狀態。這表明改進后的算法在最短路徑規劃問題上具有更快的收斂速度，也可以更有效地找到最優路徑。

3.2" 收集貨物路徑規劃

在收集貨物路徑規劃實驗中，在原有地圖的基礎上增加了三個貨物點，模擬了真實AGV取貨的場景。地圖構建如圖3所示。

黃色點位標識貨物的位置，當智能體移動到貨物點時表示成功取貨。為了防止智能體頻繁在貨物點刷分，采取了以下策略：使用三個數組來存儲貨物的坐標信息，包括貨物點坐標、當前訓練貨物坐標和已取得貨物坐標。其中，貨物點坐標數組用于保存貨物位置信息，當前訓練貨物坐標數組用于在訓練過程中動態復制貨物點坐標，已取得貨物坐標數組用于記錄智能體成功取得的貨物坐標。在每次訓練中，當智能體移動到某一貨物點時，該貨物點坐標將被添加到已取得貨物坐標數組中，并從當前訓練貨物坐標數組中移除，以確保每個貨物只能被成功取得一次，從而避免智能體刷分的情況發生。

傳統Q-learning算法收集貨物路徑規劃和迭代次數以及改進Q-learning算法收集貨物路徑規劃和迭代次數如圖4所示。

路徑長度方面兩種算法選擇的路徑距離相等，轉彎次數方面兩種算法的選擇路徑也一致，因此這方面并不存在突出優勢。在貨物收集程度方面，兩種算法選擇的路徑，貨物也都收集到滿足了該需求，也不存在突出優勢。而迭代次數方面，改進

Q-learning算法在900次左右趨于收斂，而傳統Q-learning算法則是在1 150次左右趨于收斂，改進Q-learning算法比傳統

Q-learning算法迭代次數有一個明顯降低，由此可見在收集貨物的路徑規劃問題上，改進后的算法更具有優勢。

3.3" 動態故障點增加路徑規劃

在該場景下，除了保留了部分貨物點，本文還引入了一個新的動態元素：故障點。當迭代次數達到300時，系統會動態增加兩個故障點，這些故障點會限制智能體的移動。地圖變化如圖5所示。

這樣的設定旨在模擬真實環境中的突發狀況，使智能體在路徑規劃過程中需要應對更復雜的情況。

智能體在遇到故障點時需要重新規劃路徑，以繞過這些障礙物繼續執行任務。這種動態的環境變化要求智能體具備靈活的路徑規劃能力，并及時作出調整以應對變化的情況。因此，在這樣的場景下，本文認為改進Q-learning算法在適應性和響應速度方面可能會展現出更明顯的優勢。

傳統Q-learning算法動態故障點增加路徑規劃和迭代次數以及改進Q-learning算法動態故障點增加路徑規劃和迭代次數如圖6所示。

本文的結果并不如同開始的設想，兩種算法在面對該情況的問題時，表現的能力幾乎無差異，在路徑選擇方面，最終選擇的路徑一致。在收集貨物方面，兩種算法的貨物也均收集到。在迭代次數方面，兩種算法也并無太大差異。初步分析也許是使用場景較為簡單，因此不足以表現改進算法的優勢，因此改進地圖并再次做出實驗驗證結果。改進地圖變化如圖7所示。

在改進的實驗環境中，本次適當地調整了貨物點位置以及障礙物生成位置。對于智能體限制較為明顯。

傳統Q-learnin算法動態故障點增加路徑規劃和迭代次數以及改進Q-learning算法動態故障點增加路徑規劃和迭代次數如圖8所示。

根據上述圖例可知經過調整后的地圖，傳統Q-learning算法選擇的路徑長度，轉彎次數均明顯劣于改進Q-learning算法選擇的路徑，而迭代次數方面，改進Q-learning算法在約為750次左右開始收斂，而傳統Q-learning算法則是超過1 000次才達到相似收斂。由此可知改進Q-learning算法在該實驗環境下，依然具有一定的優異性。

3.4" 分析和比較

通過上述三種實驗場景的分析比較，可以得出結論，在不同的應用場景下，改進的Q-learning算法相比傳統的Q-learning算法具有一定的優勢，并且更加符合AGV實際場景的需求。

首先，在最短路徑規劃場景中，改進算法在收斂速度方面表現更佳。通過迭代次數的比較可以看出，在相同的訓練輪次下，改進算法達到收斂所需的迭代次數明顯少于傳統算法。

其次，在收集貨物路徑規劃場景中，改進算法同樣展現出了明顯的優勢。盡管在路徑長度和轉彎次數等方面兩種算法的表現相近，但改進算法在收斂速度上依然明顯優于傳統算法。改進算法在較少的迭代次數內便能夠達到收斂，這意味著在實際應用中，改進算法能夠更快地找到最優的貨物收集路徑。

最后，在動態故障點增加路徑規劃場景中，盡管兩種算法在路徑選擇和貨物收集方面表現相似，但改進算法在應對動態環境的能力方面仍然具有一定優勢。即使在增加了故障點后，改進算法依然能夠保持較快的收斂速度，這說明改進算法具有更強的適應性和魯棒性。

兩種算法具體差異如表3所示。

綜上所述，改進的Q-learning算法在不同的應用場景下都表現出了明顯的優勢，其快速的收斂速度和良好的適應性使其更加適合應用于AGV路徑規劃問題中。因此，可以將改進的Q-learning算法視為一種有效的路徑規劃解決方案，為AGV等智能系統的實際應用提供了有力支持。

4" 結束語

在本文中，通過對傳統Q-learning算法和改進Q-learning算法在三種不同應用場景下的實驗比較，深入探討了它們的性能差異及優勢。通過實驗結果的分析，發現改進的Q-learning算法在最短路徑規劃、收集貨物路徑規劃以及動態故障點增加路徑規劃等場景下均表現出了明顯的優勢。尤其是在收斂速度和適應性方面，改進Q-learning算法展現出了更好的性能，能夠更快地找到最優路徑，并且在動態環境下具有更強的應對能力。

這些實驗結果不僅對路徑規劃領域具有重要意義，也為智能系統的實際應用提供了有力支持。改進的Q-learning算法的快速收斂速度和良好的適應性使其更加適合應用于AGV等智能系統中，為提高智能體的決策能力和應對復雜環境能力提供了有效的解決方案。

然而，雖然改進的Q-learning算法在實驗中表現出了明顯的優勢，但仍有一些方面可以進一步完善和探索。例如，可以進一步研究如何結合其他強化學習算法或者引入更復雜的獎勵機制來進一步提升算法的性能和適用性。期待未來的研究能夠在這方面取得更多的進展，為智能系統的發展和應用提供更多的可能性。

參考文獻：

[1] 胡春陽，姜平，周根榮. 改進蟻群算法在AGV路徑規劃中的應用[J]. 計算機工程與應用，2020，56（8）：270-278.

[2] 宋佳. 基于Dijkstra算法的AGV綠色節能路徑規劃研究[D]. 南昌：南昌大學，2023.

[3] 李艷珍，詹昊，鐘鳴長. 基于A～*算法優化AGV/機器人路徑規劃的研究進展[J]. 常州信息職業技術學院學報，2024，23（1）：29-36.

[4] 魏閣安，張建強. 基于改進動態窗口法的無人艇編隊集結研究[J]. 艦船科學技術，2023，45（23）：91-95，99.

[5] 黃巖松，姚錫凡，景軒，等. 基于深度Q網絡的多起點多終點AGV路徑規劃[J]. 計算機集成制造系統，2023，29（8）：2550-2562.

[6] 馬卓. AGV路徑規劃的強化學習算法研究[D]. 青島：青島大學，2023.

[7] 韓召，韓宏飛，于會敏，等. 改進強化學習算法在AGV路徑規劃中的應用研究[J]. 遼寧科技學院學報，2022，24（6）：22-25，44.

[8] 唐恒亮，唐滋芳，董晨剛，等. 基于啟發式強化學習的AGV路徑規劃[J]. 北京工業大學學報，2021，47（8）：895-903.

[9] 耿宏飛，神健杰. A～*算法在AGV路徑規劃上的改進與驗證[J]. 計算機應用與軟件，2022，39（1）：282-286.

[10] 郝兆明，安平娟，李紅巖，等. 增強目標啟發信息蟻群算法的移動機器人路徑規劃[J]. 科學技術與工程，2023，23（22）：9585-9591.