車間環境下多AGV路徑智能優化研究

摘""要：隨著我國工業技術的高速發展，多自動運輸車（Automated"Guided"Vehicle，AGV）在自主性和節約成本方面受到越來越多的重視。基于多AGV在復雜多變的車間環境中的路徑規劃問題，提出了改進的A*算法（A-star"Algorithm）和DWA算法（Dynamic"Window"Approach）融合的智能優化算法。首先，利用A*算法規劃出從起點到終點的全局路徑，然后針對A*算法多冗余的缺點，提出了一種提取關鍵點的方法，剔除掉全局路徑中的冗余節點和多余拐點，保證了對全局路徑的改進。其次，通過對全局路徑的分段，設置一系列的局部目標點，利用DWA動態窗口法對新增和移動的障礙物進行動態避障的同時不斷地到達局部目標點，得到了多AGV從起點到目標點的最優路徑，最終實現了對多AGV關于路徑長度和安全性方面的改進。

關鍵詞：A*算法""DWA算法""算法融合""路徑規劃

中圖分類號："TP18

Research"on"the"Intelligent"Optimization"of"the""Pathway"of"Multiple"AGVs"in"the"Inter-Vehicle"Environment

TANG"Qiaoling""PENG"Quan""ZHANG"Liao

Neijiang"Normal"University，"Neijian，"Sichuan"Province，"641100"China

Abstract："With"the"rapid"development"of"industrial"technology"in"China，"the"automated"guided"vehicle"（AGV）"is"receiving"increasing"attention"in"terms"of"autonomy"and"cost"saving."This"article"proposes"an"intelligent"optimization"algorithm"that"integrates"the"improved"A*"algorithm"（A-star"algorithm）"and"DWA"（dynamic"window"approach）"for"the"path"planning"problem"of"multiple"AGVs"in"the"complex"and"variable"inter-vehicle"environment."Firstly，"this"article"uses"the"A*"algorithm"to"plan"the"global"path"from"the"starting"point"to"the"endpoint，"and"then，"for"the"shortcoming"of"the"multiple"redundancy"of"the"A*"algorithm，"proposes"a"method"for"extracting"key"points"to"eliminate"the"redundant"nodes"and"inflection"points"of"the"global"path，"which"ensures"the"improvement"of"the"global"path."Secondly，"by"segmenting"the"global"path，"it"sets"a"series"of"local"target"points，"and"uses"the"DWA"to"dynamically"avoid"newly-added"and"moving"obstacles"while"continuously"reaching"the"local"target"points，"so"as"to"obtain"the"optimal"path"for"multiple"AGVs"from"the"starting"point"to"the"target"point，"and"ultimately"achieve"the"improvement"of"the"path"length"and"safety"of"multiple"AGVs.

Key"Words："A-star"algorithm;"Dynamic"window"approach;"Algorithm"fusion;"Path"planning

AGV（Automated"Guided"Vehicle）作為自動運輸小車，擁有自動尋址系統，使其能通過進行非接觸提前路線規劃。按照預先規劃好的路徑獨自運動或牽引貨物從起始點一直行駛到目標地點，完成貨物的自動運輸服務。本文提出了一種基于改進的A*算法和DWA算法的融合算法，通過對A*算法的優化和改進，彌補了A*算法平滑性不高的缺陷，再融合了DWA算法，實現了車間環境中多AGV對新增和移動的障礙物動態避障路徑規劃。

1""多AGV路徑規劃融合算法

在車間環境中，多AGV最優路徑規劃問題，就是在其工作環境中對周圍環境模型進行搜索，依據某種測評找到一條從起始點到目標點的最優路徑，并且此路徑能動態避開環境中的障礙物[1-2]。但常用的路徑規劃算法只考慮單個小車對于障礙物的避碰，沒有考慮車輛之間的碰撞，都是靜態規劃，不能根據實時情況進行路徑動態變化，此外現有的路徑規劃方法只適應于AGV可以在各個方向自由行走的情況，不適用于復雜的車間環境。

本文提出的改進的A*算法和DWA融合算法，充分利用了兩種算法的優勢，實現了路徑平滑度和安全性的改進[3]。首先利用改進的A*算法規劃全局靜態路徑，然后在全局路徑中設置多個局部目標點，再利用DWA算法進行局部動態路徑規劃，使其在最優全局路徑的基礎上可以實現動態地避讓小車和障礙物。

1.1""改進A*全局靜態路徑規劃

在車間環境中，對于傳統A*算法所規劃路徑存在較多冗余節點的缺點，提出了一種關鍵節點提取法，保留路徑必經的關鍵折點，使改進后的路徑長度更短、折點更少[4]。具體步驟如下。

（1）用面積法提取轉折點，依次計算路徑中相鄰三點（p-1、p、p+1）圍成的面積，如果面積不為0，則p為轉折點，否則p不是轉折點。p的初始點為距起點最近的路徑節點，直到p為距目標點最近的路徑節點，轉折點提取結束，將起點和目標點也視為轉折點。

（2）進行關鍵點篩選，在相鄰轉折點（q-1、q、q+1）中，連接不相鄰的兩點（q-1、q+1），如果連線經過障礙物區域，則轉折點q為關鍵點，否則為冗余點。q初始點為距起點最近的轉折點，直到q為距目標點最近的轉折點時，關鍵點篩選結束。

1.2""DWA局部動態路徑規劃

DWA算法是通過運動模型和采樣的運動信息推算出小車可能的多種運動軌跡，然后通過評價函數選取最優的規劃路徑。本文將改進的A*算法中提取的關鍵點設置為局部路徑的局部目標點，使其一一到達并最終抵達終點，從而得到一條改進的路徑。當多輛AGV將會碰撞時，DWA算法會依次設定AGV的優先級，讓優先級高的AGV先通行。為使DWA算法所規劃的局部路徑更接近全局路徑，在預測軌跡評價函數中加入A*算法的代價值函數為全局路徑評價子函數[5]，則融合算法的評價函數為：

（1）

式（1）中，heading（v，w）是方位角評價函數，指小車航向與目標之間的角度差；dist（v，w）是小車與最近障礙物之間的距離；velocity（v，w）是軌跡對應的速度大小。P為t時刻通過v和w預測的移動機器人位置坐標；g（P）表示預測位置到起點的距離；h（P）表示預測位置到局部目標點的距離；為全局路徑評價函數子函數權重（取值小于α和γ，大于β）。H（v，w）值越小，得分越高。

2""算法測試結果及分析

本文采用MATLAB平臺，使用改進的A*算法和DWA算法的融合算法對存在靜態以及動態障礙物的車間環境進行多AGV路徑規劃仿真，實現了智能車間環境中多AGV動態避障路徑規劃。

2.1""改進的A*全局路徑規劃

本文采用柵格化的環境模型，模擬了3輛AGV的起點和終點以及動態的障礙物的起點和終點。設AGV1的起點是（19，26），終點是（9，23）；AGV2的起點是（5，8），終點是（11，16）；AGV3的起點是（17，17），終點是（12，27）。然后根據改進的A*算法進行全局路徑規劃，可以得到3條路徑，改進的A*算法路徑規劃結果如圖2所示。

根據改進的A*全局路徑規劃圖可知，AGV1和AGV2的路徑發生了交叉，因此AGV1和AGV2在運行過程中可能會發生碰撞，此時就需要運用DWA算法進行動態避障，使AGV1和AGV2在相遇時根據優先級，使最優先的AGV先行，次優先AGV避讓，以此來達到多AGV避碰的目的。

2.2""DWA局部路徑優化

DWA局部路徑優化是將全局路徑分成多個局部路徑，設置多個局部目標點，避讓其余AGV和運動的障礙物，從而到達各個局部目標點，并最終各自到達目的地。

根據本文模擬環境，AGV1和AGV2在路徑規劃中相遇，AGV3為了躲避向右的移動障礙物，偏向右邊規劃。然后根據DWA算法設置的優先級AGV1大于AGV2，AGV2停下避讓AGV1。如圖3所示，經過DWA算法局部規劃路徑后，分別得到了3條優化的路徑[5]。

由圖3所示優化后的路徑可知，多AGV的路徑規劃融合算法可以在動態的車間環境中避讓小車和障礙物，能夠實現多AGV在復雜的車間環境下的路徑智能優化。

3""結語

本文針對智能車間環境中使用傳統路徑規劃算法對多AGV路徑規劃造成的平滑性和靈活性不足、安全性不高等問題，提出了改進的A*算法和DWA算法融合的路徑智能優化算法，融合了兩種算法的優勢，并通過MATLAB平臺，模擬了車間中存在的復雜環境，進行了多AGV動態避障路徑規劃的仿真，實現了多AGV在復雜車間情況下的無碰路徑規劃。但在A*算法進行全局規劃時，有出現重復點的可能性，因此DWA算法進行局部規劃追蹤時，會出現重復識別，造成錯誤，未來將針對重復點問題進一步研究。

參考文獻

• 岑云飛.面向智能工廠的多AGV調度系統開發[D].西安：西安理工大學，2023.
• 熊焰，劉金庫.多移動機器人路徑無障礙智能規劃算法仿真[J].計算機仿真，2023，40（4）：434-438.
• 陳嬌，徐菱，陳佳，等.改進A*和動態窗口法的移動機器人路徑規劃[J].計算機集成制造系統，2022，28（6）：1650-1658.
• 于洋，杜學歷，馮迎賓.融合A*算法和動態窗口法的全局動態路徑規劃方法[J].沈陽理工大學學報，2020，39（5）：1-7.
• 王彬，聶建軍，李海洋，等.優化A*與動態窗口法的移動機器人路徑規劃[J/OL].計算機集成制造系統：1-17[2023-12-06].http：//kns.cnki.net/kcms/detail/11.5946.TP.20220305.1932.024.html.