風電機組總裝環境中智能自適應AGV路徑規劃算法

摘 要：由于風電機組總裝環境的特殊性，經典動態規劃算法和蒙特卡洛樹搜索（MCTS）算法的路徑計算效率較低。為降低計算復雜度，提出1種基于改進MCTS的自動引導車（AGV）自適應路徑規劃算法（即DP-MCTS算法）。首先通過柵格化方法對環境進行抽象建模；然后在MCTS算法中引入啟發式搜索引導搜索樹向目標點方向擴展，并使用單步更新法對節點進行實時評價；結合動態規劃多階段優化的思想建立動態MCTS算法，進一步提高路徑尋優效率；最后在不同場景下通過實際案例仿真驗證了所提出算法的可行性及有效性。研究結果表明：DP-MCTS算法可有效提高AGV的路徑規劃效率、減少系統的能量消耗，其可為此類環境下AGV路徑規劃提供設計基礎。

關鍵詞：風電機組；總裝環境；動態規劃；蒙特卡洛樹搜索；自動導引車；智能自適應路徑規劃

中圖分類號：TP399/TM614 文獻標志碼：A

0 "引言

在新能源產業蓬勃發展的背景下，風電機組總裝效率成為制約其規?；l展的關鍵因素之一。在風電機組總裝過程中，物料的高效運輸是確?？傃b工作順利進行的重要環節。自動引導車（automatic guided vehicle，AGV）作為1種先進的物流自動化設備，是典型的工業4.0應用場景，其憑借高度的靈活性和自動化程度，已成為風電機組總裝環境中物料運輸的核心工具。AGV能夠實現無人工參與的自動化作業，顯著提高了物料存取的效率和準確性。隨著智慧制造技術的發展，AGV路徑規劃在風電機組總裝環境中的應用愈發廣泛，不僅在倉儲系統（automated storage and retrieval system，AS/RS）和柔性制造系統（flexible manufacturing system，FMS）中有重要作用，還拓展至車輛運輸網絡、城市交通規劃[1]、能量傳輸[2]和計算機網絡規劃[3]等多個領域。AGV路徑規劃逐漸演化為多目標組合優化問題，其優化目標不僅包括算法快速性，還需要考慮路徑距離最短、時間最小和耗能最少。因此，風電機組總裝環境下的AGV路徑規劃問題得到了廣泛的關注。

總裝環境中AGV路徑規劃屬于單源路徑尋優問題，目的是找到指定起點至指定目標點間可滿足某些限制條件的最短路徑。常用的方法包括：Dijkstra最短路算法[4]、A*算法[5]、D*算法[6]、概率圖法[7]、快速探索隨機樹（rapidly-exploring random tree，RRT）算法[8]、人工勢場（artificial potential field，APF）算法[9]、神經網絡法[10]、遺傳算法[11]、蟻群算法[12]等。其中，Dijkstra算法、A*算法、D*算法是最常用的路徑搜索算法，與現在流行的基于學習（learning-based）算法[13]相比，此類算法的結構簡單且易于實現，能滿足實際應用中對計算結束實時性的要求。但是，這3種算法本質上屬于廣度優先搜索，Dijkstra算法和A*算法的計算復雜度為O（n2）（其中：O表示算法的時間復雜度或空間復雜度；n表示算法處理的數據量），D*算法的計算復雜度為O（2n），在節點較多的環境中算法效率均不高。

馬爾可夫決策過程（markov decision process，MDP）是動態規劃的建?；A，隨著人工智能的發展，MDP再次掀起了研究熱潮。Yuan等[14]提出了似動態規劃方法，并將其應用于起重機調度問題中，顯著減小整個系統的處理時間；Mustafa等[15]提出了1種基于MDP和ADP算法的車輛路徑優化算法——近似動態規劃（approximate dynamic programming，ADP），證明動態規劃可用于解決車輛路徑問題。Ulmer等[16]提出了1種離線Value Function預測方法，減小了動態規劃的求解時間。動態規劃是強化學習的理論基礎，其可將多階段優化過程轉化為一系列單階段優化問題，傳統算法是通過隨機選擇起點對樣本集進行迭代，直到得到最優策略。隨著路徑規劃環境規模的擴大，訓練次數和單次訓練時間也會增加，因此在大型環境中，計算量會隨著節點數的增加而呈指數性增長[17]。

蒙特卡洛樹搜索（monte carlo tree search，MCTS）通過在給定區域中構建非對稱樹來構建最優動作列表，通過由已知節點向未知節點擴展來尋找起點至目標點的最優路徑。但是在多節點大型環境中，由于缺少啟發機制不能平衡“探索”與“利用”，在構建搜索樹的過程中會逐一遍歷所有未展開過的節點，然后在其中選擇上置信界（upper confidence bound，UCB）值最大的作為下1個目標，這使得該算法在實時性要求較高的場景中不適用。此外，當葉子節點擴展至目標點時才對已遍歷過的節點進行評價，這也是該算法在大型環境中應用時算法效率不高的原因之一。

本文提出1種改進的智能自適應AGV路徑規劃算法（即“DP-MCTS算法”）。首先提出改進的MDP建模方法，為風電機組總裝環境中的AGV路徑規劃提供建?；A；接著將動態規劃多階段優化問題的思想引入上述改進中，根據AGV起點和目標點的位置進行自適應區域分割，排除無關節點以增加路徑規劃效率；其次，在傳統MCTS中加入啟發式搜索，比較當前節點與目標點的位置，限定葉子節點的擴展方向，加快路徑尋優速度；然后，針對傳統MCTS在擴展至目標點后再進行反向傳播造成算法效率不高的問題，將反向傳播提前，采用單步更新法建立搜索樹；最后，提出基于路徑權重（Move值）的路徑評價標準，并找到轉彎最少的最短路徑。通過上述改進，將DP-MCTS算法的計算復雜度降低至O（nlogn）級別。

1 "AGV運行環境建模

本文采用柵格化方法對實際環境進行建模：將風電機組總裝環境設為m·n個柵格（其中：m為列節點個數；n為行節點個數）；環境的左上角坐標為（x=0， y=0），右下角坐標為（x=n–1， y=m–1）。每個工作點對應坐標（a，b）（其中：a≤n–1且b≤m–1），AGV的起點為（1，1），目標點為（m，n）；工作點的編號用數字表示，這些編號作為每個工作點的唯一標識。設環境模型為e（V，O，E），其中：V為節點集合；O為表示障礙節點集合（裝配工位點），且OV；E為供AGV行駛的路徑集合。設AGV的長為LAGV、寬為WAGV，每個柵格的長Lg等于AGV的長與AGV行駛安全裕度β（為正數，根據實際要求設定）的和；每個柵格的寬Wg等于AGV的寬與AGV行駛安全裕度的和；環境的長為LWT、寬為WWT。

基于上述設定，環境地圖的表達式為：

（1）

式中：Rg為環境地圖的行數；Cg為環境地圖的列數（即每行有多少節點）；二者均向下取整，也就是柵格數量為環境地圖行數與列數的乘積向上取整。

AGV可以雙向通行且每個工作點只能同時容納1臺AGV，AGV經過的工作點個數代表AGV前進的距離。

以某風電機組總裝廠的FMS為例，該FMS中包含7臺AGV（分別為AGV1～AGV7），如圖1所示。圖中：①～表示AGV的工作點，其中紅色的表示AGV的充電工位；白色數字1～48表示行駛路線交叉點。

采用上述方法對該FMS進行柵格化，將其分成840個（為20×42）柵格，如圖2所示。圖中：紅字表示圖1中的AGV工作點；藍色柵格表示障礙節點；白色柵格表示空閑節點。

2 "結合改進動態規劃和MCTS的路徑規劃

2.1 "風電機組總裝環境中的MDP

2.1.1 "獎勵矩陣

以圖2為例，風電機組總裝環境中的獎勵定義為：負載AGV（即載貨的AGV）進入障礙節點，獲得獎勵為-r（r為正整數）；空載AGV（即未載貨的AGV）進入障礙節點，獲得獎勵為零；AGV（空載或負載）到達目標點，獲得獎勵為ε（ε為正整數）；AGV（空載或負載）進入空閑節點，獲得獎勵為-δ（δ為正整數，且δ≤ε），也就是說，AGV在到達目標點前每多走1步，就得到懲罰δ。

設獎勵矩陣RM的維度為m·n，與總裝環境相同，則其表達式為：

（2）

式中：下角標首位表示行數，第2位表示列數。例如：r11表示AGV到達第1行第1列節點獲得的獎勵，rmn即表示AGV到達第m行第n列節點獲得的獎勵。

2.1.2 "轉移概率矩陣

風電機組總裝環境中轉移概率矩陣PM的表達式為：

（3）

對于1個維度為m·n的總裝環境，原則上不論AGV是負載還是空載，其進入任何相鄰節點（即到達每個相鄰節點）的概率相同，可表示為：

（4）

式中：P為概率；Pij為坐標（i， j）節點的概率；St為t時刻AGV所處節點；St+1為下一時刻AGV所處節點。

總裝環境共有m·n個節點，則傳統的獎勵矩陣應有（m·n）·（m·n）行、（m·n）·（m·n）列，而本文提出的獎勵矩陣及轉移概率矩陣的維度為m·n，與總裝環境統一，減小了計算復雜度，提高了算法效率。

2.1.3 "最優策略選擇標準

經典MDP的目標是在環境中找到1條達到目標的最優方法，使累計獎勵最大化。但是在風電機組總裝環境中，AGV路徑規劃的目標是找到從起點到目標點的時間最短路徑，并非累計獎勵最大。因此，需要修改最優策略選擇標準，以適應風電機組總裝環境的實際情況。

當AGV到達任意1個節點時，通過藍牙、Wi-Fi等無線傳輸方法向服務器上傳其當前所在節點的坐標，服務器便可獲知此AGV在環境中的位置。總裝環境中，工位點即為節點，AGV車頭進入節點為開始占用節點，車尾離開節點則釋放此節點，則AGV經過每兩個相鄰節點的時間tc的計算式為：

（5）

式中：v為AGV正常行駛的車速。

AGV只能沿路徑向正東、正南、正西、正北行駛，并且只能在節點處轉彎；轉彎要經過減速、自轉、加速的過程。設AGV出發的時間為0 s，其到達目標點的總用時T的計算式為：

（6）

式中：nc為路徑中包含的節點總數；nu為路徑中轉彎的個數；tu為轉彎耗時。

因此，最優策略選擇標準是為AGV找到1條到達目標點總用時T最小的路徑T（s），其計算式為：

（7）

2.2 "DP-MCTS算法的AGV路徑規劃

2.2.1 "抽象環境區域分割

動態規劃的兩個關鍵特點是最優子結構和重復子結構。加快樣本訪問速度最有效的方法之一是刪除無效樣本，減少訓練樣本個數。借鑒此方法，本文提出抽象環境區域分割的方法為：根據AGV的起點和目標點與風電機組總裝環境邊界的相對位置，劃分路徑規劃區域。

設AGV的起點坐標為（SX，SY），目標點坐標為（GX，GY）；風電機組總裝環境左邊界的橫坐標為X1、右邊界的橫坐標為Xr、上邊界的縱坐標為Yu、下邊界的縱坐標為Yl，則路徑規劃區域的左上角坐標為（XWT，ul，YWT，ul）、右上角坐標為（XWT，ur，YWT，ur）、左下角坐標為（XWT，ll，YWT，ll）、右下角坐標為（XWT，lr，YWT，lr），路徑規劃區域共有nrow行ncol列。

路徑規劃區域的計算方法如下：

風電機組總裝環境中節點數很多，且起點至目標點的距離較遠，因此要經過多次搜索才能找到起點至目標點的最優路徑。如果不限定搜索方向，所有與當前節點相鄰的節點都有可能被擴展。為了賦予DP-MCTS算法啟發式搜索的能力，提出啟發式搜索過程：設AGV當前所在節點的坐標為（VX，VY），要擴展的子節點坐標為（VX′，VY′）。子節點選擇的方法為：若GX≥SX且GY≥SY，則VX′≥VX且VY′≥VY；若GX≥SX且GYlt;SY，則VX′≥VX且VY′lt;VY；若GXlt;SX且GY≥SY，則VX′ lt;VX且VY′≥VY；若GXlt;SX且GYlt;SY，則VX′lt;VX且VY′lt;VY。由此可以看出：若目標點位于起點的右下、右上、左下、左上方向，則只考慮擴展位于當前節點右下、右上、左下、左上的節點。

2.2.2 "計算時間最短路徑

為找到時間最短路徑，可根據角度偏差決定前進方向，具體步驟分為兩步，如圖3所示。圖中：紅色方塊表示AGV；θ為角度；黑色箭頭為此AGV當前的前進方向。

1）步驟1：將AGV進入環境的角度與備選路徑的行駛方向進行對比，找出角度偏差絕對值最小的路徑作為出發路徑，如圖3a所示。AGV初始方向與每條備選路徑的角度對比后決定的出發路徑角度θini的計算式為：

（9）

式中：θ1#0為以節點0為基準的路徑1的角度；θ2#0為以節點0為基準的路徑2的角度；θAGV#0為AGV進入環境時在節點0初始角度。

根據圖3a，AGV的當前方向與路徑1的角度偏差絕對值為0°，而與路徑2的角度偏差絕對值為90°，因此選擇路徑1作為出發路徑。

2） 步驟2：當AGV有1條以上路徑備選，計算AGV到達該節點的方向和下一段路徑的行駛方向的角度偏差，實時選擇角度偏差絕對值較小的路徑作為下一段行駛路徑。如圖3b所示，當AGV到達節點2，坐標為（2，0），其面前有2條最短路徑備選，則下一段路徑的角度θne的計算式為：

（10）

式中：θ1#2為路徑1的角度；θ2#2為路徑2的角度；θAGV#2為AGV在節點2的角度。

根據圖3b，AGV的當前方向與路徑1的角度偏差絕對值為0°，而與路徑2的角度偏差絕對值為90°，因此選擇路徑1作為下一段行駛路徑。

2.2.3 "獲得距離和時間均最短的路徑

為了找到起點至目標點的距離和耗時均最小的路徑，提出為轉彎增加懲罰項，通過AGV行駛方向判斷某個節點是否為轉彎點，行駛方向滿足以下判斷式之一即轉彎：

（11）

（12）

式中：Xi為當前節點i的橫坐標；Yi為當前節點i的縱坐標；i+1為下游節點；i–1為上游節點。

本文提出的DP-MCTS算法的偽代碼圖如圖4所示，圖中：1～5行可根據鄰接表找到可行路徑，6～15行可選出耗時最少的路徑。

當FMS系統在接到新的運輸任務時，此時備選的AGV需完成運輸任務并處于空閑狀態，且電量高于20%。FMS系統實時計算每臺AGV與任務起點的曼哈頓距離，最終所選的AGV即為曼哈頓距離最小的。

3 "實例研究

對DP-MCTS算法進行仿真案例研究，仿真環境為：Windows 10操作系統，Intel Core i7-8700K CPU@3.70GHz x64-based處理器；Python 3.7.3編程軟件；節點（工作點）間距為5 m；AGV車速為勻速1 m/s，在兩節點間行駛、在節點處轉彎均需要5 s。

3.1 "案例1

案例1為10臺AGV（編號為1#～10#）同時行駛在AS/RS中，對AS/RS柵格化，結果如圖5所示。圖中：灰色柵格為障礙節點；白色柵格組成的路段為AGV移動通道；黑色圓圈表示搜索過程。

10臺AGV的初始任務列表如表1所示；行駛約80 s后，AS/RS接到一批新的任務，如表2所示。

此時服務器調用AGV調度程序，選擇距離任務出發點曼哈頓距離最近的AGV執行此任務（見圖5），具體為：1#AGV執行任務1、3#AGV執行任務2、6#AGV執行任務3、7#AGV執行任務4、9#AGV執行任務5、10#AGV執行任務6。

分別使用傳統動態規劃算法和DP-MCTS算法找到距離和時間均最短路徑并進行沖突解決，對比結果如圖6所示。

從圖6可以看出：傳統動態規劃算法的平均初始路徑計算時間為0.6674 s，平均能量消耗為6125.8 W，平均單位時間完成任務數量（即吞吐量）為74.25個/min；DP-MCTS算法的平均初始路徑計算時間為0.2101 s，平均能量消耗為5906.7 W，平均單位時間完成任務數量為134.25個/min。由此可得：DP-MCTS算法提高了多AGV路徑規劃效率約68.52%，減少了AS/RS能量消耗約35.77%，增加了AS/RS的吞吐量約80.80%。

3.2 "案例2

案例2為7臺AGV同時行駛在FMS中，以上文圖1為例，7臺AGV的起點和目標點如表3所示。

分別使用傳統動態規劃算法和DP-MCTS算法找到距離和時間均最短路徑并進行沖突解決，對比結果如圖7所示。

從圖7可以看出：采用傳統動態規劃算法的平均初始路徑計算時間為0.8250 s，平均能量消耗為1854.6 W；采用DP-MCTS算法的平均初始路徑計算時間為0.0242 s，平均能量消耗為1339.2 W。由此可得：DP-MCTS算法提高了多AGV路徑規劃效率約97.97%，減少了FMS能量消耗約27.78%。

3.3 "案例3

案例3對比了傳統動態規劃算法和DP-MCTS算法在不同數量節點環境中的路徑計算時間和能量消耗，對比結果如圖8所示。

從圖8可以看出：在不同規模環境下，DP-MCTS算法均可減少路徑計算時間，且可以節省能量消耗；隨著環境規模擴大（節點數量增多），DP-MCTS算法的優勢會更明顯。

4 "結論

針對風電機組總裝環境中AGV路徑規劃問題，為降低計算復雜度，本文提出了1種改進的智能自適應AGV路徑規劃算法——DP-MCTS算法，其根據AGV的尺寸對環境進行柵格化，可實現對AGV的精確定位；然后針對傳統MCTS路徑規劃效率不高的問題，提出了一系列改進措施；最后通過實際案例對所提DP-MCTS算法進行了仿真驗證。研究結果表明：DP-MCTS算法加入限制環節引導搜索樹向著目標點的方向擴展；使用單步更新法對節點進行評價，找到起點至目標點的可行路徑；通過基于Move值的路徑評價標準，得到起點與目標點之間距離和時間均最短路徑；并結合動態規劃多階段優化的思想實現了區域分割，顯著提高了路徑規劃尋優效率。經仿真驗證，DP-MCTS算法可有效提高AGV的路徑規劃效率，減少系統的能量消耗。

［參考文獻］

[1] YANG G，YAO Y. Vehicle local path planning and time consistency of unmanned driving system based on convolutional neural network[J]. Neural computing and applications，2022，34（15）：12385-12398.

[2] GLORIEUX E，FRANCIOSA P，CEGLAREK D. Coverage path planning with targetted viewpoint sampling for robotic free-form surface inspection[J]. Robotics and computer-integrated manufacturing，2020，61：101843.

[3] WANG X W，YAN Y X，GU X S. Spot welding robot path planning using intelligent algorithm[J]. Journal of manufacturing processes，2019，42：1-10.

[4] DIJKSTRA E W. A note on two problems in connexion with graphs[J]. Numerische mathematik，1959，1（1）：269-271.

[5] ANGAPPAMUDALIAR PALANISAMY S K，SELVARAJ D，RAMASAMY S. Hybrid multi-objective optimization approach intended for mobile robot path planning model[J]. Journal of intelligent amp; fuzzy systems，2022，42（3）：2681-2693.

[6] JIANG L Q，WANG S T，MENG J，et al. A fast path planning method for mobile robot based on voronoi diagram and improved D* algorithm[C]//2019 IEEE/ASME International conference on advanced intelligent mechatronics （AIM），July 08-12，2019，Hong Kong，China. New York：IEEE，2019：784-789.

[7] AKBARIPOUR H，MASEHIAN E. Semi-lazy probabilistic roadmap：a parameter-tuned，resilient and robust path planning method for manipulator robots[J]. The international journal of advanced manufacturing technology，2017，89（5）：1401-1430.

[8] XU T，XU Y，WANG D，et al. Path planning for autonomous articulated vehicle based on improved goal-directed rapid-exploring random tree[J]. Mathematical problems in engineering，2020，5：7123164.

[9] HE L，ZHANG S，ZHANG H，et al. Multiple interaction strategies for mobile robots based on improved dynamic window approach in unknown dynamic environments[J]. Industrial robot：the international journal of robotics research and application，2024，51（1）：105-116.

[10] YU Y H，ZHANG Y T. Collision avoidance and path planning for industrial manipulator using slice-based heuristic fast marching tree[J]. Robotics and computer-integrated manufacturing，2022，75：102289.

[11] 劉振忠. 多軸聯動系統的運動規劃與結構變形補償[D]. 天津：天津大學，2012.

[12] ORAL T，POLAT F. MOD* lite：an incremental path planning algorithm taking care of multiple objectives[J]. IEEE transactions on cybernetics，2016，46（1）：245-257.

[13] JOHNER R，LANAIA A，DORNBERGER R，et al. Comparing the pathfinding algorithms A*，Dijkstra’s，bellman-ford，floyd-warshall，and best first search for the paparazzi problem[C]//Congress on intelligent systems. September 04-05，2021，Bengaluru，India. Singapore：Springer Nature，2022：561-576.

[14] YUAN Y，TANG L X. Novel time-space network flow formulation and approximate dynamic programming approach for the crane scheduling in a coil warehouse[J]. European journal of operational research，2017，262（2）：424-437.

[15] MUSTAFA ?，SOYSAL M. Time-dependent green vehicle routing problem with stochastic vehicle speeds：an approximate dynamic programming algorithm[J]. Transportation research part D：transport and environment，2017，54：82-98.

[16] ULMER M W，SOEFFKER N，MATTFELD D C. Value function approximation for dynamic multi-period vehicle routing[J]. European journal of operational research，2018，269（3）：883-899.

[17] GARGIANI M，MARTINELLI A，MARTINEZ M R，et al. Parallel and flexible dynamic programming via the mini-batch bellman operator[J]. IEEE transactions on automatic control，2024，69（1）：455-462.

AGV PATH PLANNING ALGORITHM BASED ON INTELLIGENT ADAPTIVE IN WIND TURBINE ASSEMBLY ENVIRONMENTS

Zhang Zheng

（Beijing Goldwind Science amp; Creation Wind power Equipment Co.，Ltd.，Beijing 100176，China）

Abstract：Due to the particularity of the wind turbine assembly environments，the path calculation efficiency of classical dynamic programming programming and Monte Carlo Tree Search （MCTS） algorithm is relatively low. To reduce computational complexity，an adaptive path planning algorithm for AGVs based on improved MCTS （i.e. DP-MCTS algorithm） is proposed in this paper. Firstly，the environment is abstractly modeled by gridding method. Then，heuristic search is introduced in MCTS algorithm to guide the search tree to expand towards the target point，and single-step update method is used to evaluate nodes in real time. The idea of multi-stage optimization of dynamic programming is combined to establish a dynamic MCTS algorithm，which further improves the path optimization efficiency. Finally，the feasibility and effectiveness of the proposed algorithm are simulated and verified through actual cases in different scenarios. The research results show that the DP-MCTS algorithm can effectively improve the efficiency of AGV path planning and reduce the energy consumption of the system. It can provide a design a basis for AGV path planning in such environments.

Keywords：wind turbines；assembly environments；dynamic programming；MCTS；AGV；intelligent adaptive path planning