AGV 路徑規劃在智慧工廠中的應用

魏 濤

（青島理工大學信息與控制工程學院，山東 青島 266525）

0 引 言

引入AGV 后，傳統的“人到貨”的分揀方式轉變為“貨到人”的新模式，其優勢在于可以通過自動化的方式，實現更高效、更智能的貨物分揀生產模式。 AGV 的應用可以滿足智慧工廠貨物分揀的各種需求，帶來了工作效率和精度的雙重提升。 因此，AGV 在智能制造領域扮演了至關重要的角色，是實現工業自動化不可或缺的關鍵技術之一。 AGV 對提高產業生產效率、減輕操作人員的負擔、降低企業生產成本都具有非常重要的意義。 路徑規劃是智慧工廠生產過程中實現貨物運輸的必要前提條件。 在現代智能制造系統中，通過對AGV 進行路徑規劃和任務調度，可以實現貨物的智能化自動化運輸，有效提高生產效率和產能，降低生產成本和風險。 因此，深入研究AGV 路徑規劃算法，優化和應用路徑規劃策略，對智慧工廠的生產運作具有至關重要的作用。關于AGV 路徑規劃算法，目前有多種研究方法和實踐應用，比如經典的Dijkstra 算法、A?算法、蟻群算法、遺傳算法和模糊邏輯算法等。 不同算法適用于不同的場景和問題，需要根據實際情況和需求進行選擇和應用。 房殿軍等學者［1］以電子商務行業倉儲需求為基礎，提出了自動化立體倉庫中AGV 的靜態路徑規劃方法和動態避障決策策略。 Mohammad等學者［2］研究一種高效的2－opt 運算符，在AGV 路徑規劃過程中用以解決路徑重組問題，以此進一步提高路徑規劃的效率和準確性。 在此基礎上，還將A?算法與該運算符相結合，實現了多AGV 線路的規劃任務。 Thomas 探究了一種局部搜索算符，并采用了蜂群優化的算法來解決AGV 路徑規劃任務合理性分配問題［3］。 文獻［4］利用局部搜索和隨機搜索的策略來解決AGV 系統調度和無碰撞路徑規劃問題。 通過分析AGV 系統調度和路徑前瞻搜索算法結構，引入一種基于啟發式的局部搜索算法來解決AGV 調度問題。 文獻［5］基于蟻群算法提出AGV 車間任務調度和無碰撞路徑集成模型，有效地解決AGV 任務分配和路徑規劃的問題，提高生產效率和安全性。

本文主要研究的是基于改進的A?算法在智慧工廠貨物分揀系統中AGV 如何進行路徑規劃。 首先，利用柵格法描述AGV 在智慧工廠貨物運輸過程。 其次，為了解決多AGV 在貨物運輸過程中帶來的交通堵塞，通過在多AGV 共同路線上加入懲罰值來改善交通擁堵情況。 然后，結合改進的A?算法針對多AGV 運行線路規劃出一條無碰撞路徑。 最后，通過仿真實驗對改進的A?算法的路徑規劃效率進行驗證，并與其他算法的路徑規劃效率進行比較。

1 AGV 運行環境建模

研究中，可以把智慧工廠生產車間中AGV 工作環境理想化視為矩形方陣。 在環境建模的過程中，有多種常用的方法，其中包括拓撲圖法、導航網絡法以及柵格法等。 以上3 種方法都有其優缺點和適用范圍。 需要根據實際情況，選取最合適的方法進行建模，以保證建出的環境模型能夠符合實際需求。本文采用柵格法來生成環境模型，柵格法環境建模如圖1 所示。

圖1 柵格法環境建模Fig. 1 Grid based environmental modeling

采用柵格法環境建模，其優點在于：

（1）利用矩陣來近似模擬生產車間的工作環境，可能規劃出來AGV 最短無碰撞路徑并非最短路徑，但可以增大AGV 安全運行距離，提高安全性。

（2）柵格法可對隨機障礙域進行準確表達，不容易發生丟失障礙域等情況。

（3）柵格法對障礙域的描述相對簡單，從而可以提高AGV 路徑規劃效率。

2 改進A?算法的路徑規劃

2.1 A?算法

A?算法是一種啟發式搜索算法，通常被用于尋找最短路徑。 是基于估價函數來指導搜索方向，在保證最優解的前提下，提高搜索效率和速度。 其成本估計函數為：

其中，函數f（n）用于估計從起始節點通過任意節點n到目標節點的總成本。 這個函數是由當前節點n的實際成本g（n） 和當前節點n到目標節點的最優路徑估計成本h（n） 之和得出的。 實際成本g（n） 表示起始節點到當前節點n的實際代價。 當擴展節點n時，會將其所有鄰居節點添加到OPEN表中，并將這些節點的g（n） 值設為n的g（n） 加上從n到對應節點的實際代價。 這樣就可以不斷更新每個節點的實際成本，直至找到目標節點為止。h（n） 表示當前節點n到目標節點的最佳路徑的估計成本。 通常使用啟發式函數來估算，例如曼哈頓距離、歐幾里得距離等。 啟發式函數可以有助于在搜索過程中更好地指導搜索方向，從而更快地找到最優解。

A?算法思想：A?算法使用優先級隊列來循環擴展最低成本估計節點，并把這個隊列稱為開集。在每一步執行過程中，從開集中刪除f（n） 值最低的節點，然后更新它的相鄰節點的f（n）和g（n） 值，把這些節點添加到優先級隊列中。 A?算法持續執行，直到找到目標節點，或者開集為空為止。 最終的路徑長度是目標節點的值，該值總是比開集中所有節點的值更低。使用優先級隊列可以確保在每一個步驟中按照f（n）值遞增的順序，獲取到開集中最低估計成本的節點，并且保證插入新的節點時能夠自動維護開集中f（n） 值的最低節點。 A?算法實現步驟詳見如下：

（1）定義節點類，包含節點坐標和距離起點的代價g（n）以及到終點的啟發式代價估計值h（n）。

（2）初始化起始和終止節點，并將起始節點加入OPEN 表中。

（3）在每個循環中，從OPEN 表中選取f（n） 值最小的節點n，將其從OPEN 表中移除，并將其加入CLOSE 表中。

（4）檢查節點n是否為終止節點。 如果是，則停止搜索并返回從起點到終點的路徑。

（5）如果節點n不是終止節點，則對其相鄰節點進行以下操作：

①對于每個相鄰節點m，計算從起點到該節點的代價g（n） 加上從該節點到終點的啟發式代價估計值h（m）。 計算得到相鄰節點m的f（m） 值。

②如果相鄰節點m已經存在于CLOSE 表中，則跳過該節點，并繼續處理下一個節點。

③如果相鄰節點m不在OPEN 表中，則將其加入OPEN 表中，并將節點n設置為相鄰節點m的父節點，計算相鄰節點m的g（m） 和h（m） 值。

④否則，如果新的g（m） 值比原來的小，則更新相鄰節點m的g（m） 值和父節點，并重新計算f（m） 值。

（6）循環執行步驟（3）到步驟（5），直至找到終止節點或者OPEN 表為空。

（7）如果OPEN 表為空、并且未找到終止節點，則無法到達終止節點，搜索失敗。

（8）如果找到了終止節點，并且從起點到終點的路徑已經確定，則可以將該路徑返回。

需要注意的是，在執行步驟（5）時，需要使用優先隊列存儲OPEN 表中的節點，并總是選取f（n） 值最小的節點進行擴展。 此外，啟發式估價函數的準確性對A?算法的性能和路徑質量有著很大的影響。

2.2 A?算法的不足

（1）啟發式函數不準確時，A?算法可能找到的不是最優解。 A?算法的性能高度依賴所使用的啟發式函數的準確性，在某些情況下，因為啟發式函數不準確，A?算法會找出次優解或者被卡在一些費時的路徑上。

（2）A?算法可能會陷入局部最優解。 在某些情況下，A?算法可能會受到其所使用的啟發式函數的影響，沿著一個看似有趣、但是實際上并不符合題意的方向前進，最終陷入局部最優解。

（3）A?算法不適用于無向加權圖。 在無向圖中，最短路徑搜索的運行過程通常會出現節點被一次又一次地遍歷的現象，這將明顯增加該算法的復雜度，算法效率也將隨之降低。

（4）A?算法對空間的要求較高。 A?算法需要維護一個優先隊列來存儲已經搜索過的節點。 如果目標狀態太大，可能會出現內存不足，從而導致算法無法運行。

（5）A?算法的實現較為復雜。 在編寫A?算法時，除了需要合理選擇啟發式函數以外，還需要得到優先隊列和開放列表等輔助工具。 因此，需要花費一定時間來構建和調試算法。

綜上所述，A?算法雖然在很多情況下表現優異，但也存在一些不足。 因此，在具體應用時，需要綜合考慮算法的優點和缺點，選擇合適的算法并加以改進。

2.3 AGV 碰撞類型

在智慧工廠生產環境中，AGV 在運行過程中難免會出現碰撞情況，下面將介紹一些常見的AGV 碰撞類型。

（1）節點沖突。 節點沖突是指整個運行線路中，在某一時刻，有2 個或多個AGV 同時經過某一節點。 節點沖突示意如圖2 所示。 通過設置AGV路徑優先級，可以避免發生節點沖突。

圖2 節點沖突Fig. 2 Node conflict

（2）趕超沖突。 趕超沖突是指2 個AGV 以不同的速度同向行駛。 由于后車的速度大于前車的速度，兩車的距離越來越近，如果保持這種狀態，會導致兩車發生追尾。 趕超總突示意如圖3 所示。

圖3 趕超沖突Fig. 3 Catch up and surpass conflict

（3）相遇沖突。 相遇沖突也叫做相向沖突。 指2 輛正在執行任務的AGV 在同一條線路上相向而行。 在同一時間節點，某條路線只能允許有一輛AGV 通過，但如果此時有另外一臺AGV 也要通過該條路線，那么這2 臺AGV 之間就會迎面發生碰撞。 相遇沖突示意如圖4 所示。

圖4 相遇沖突Fig. 4 Encounter conflict

2.4 A?算法的改進

基于上述的A?算法的不足以及AGV 路徑碰撞類型，研究中提出對A?算法的改進。

在A?算法中，節點的g（n） 值是實際值，h（n）值是啟發式估計值。 選擇適當的啟發式估計函數能夠提高算法的效率和尋找到更優路徑。 常用的啟發式估價函數包括曼哈頓距離、歐幾里得距離［6－8］、對角線距離等。 對此擬做闡釋分述如下。

（1）曼哈頓距離。 是根據標準坐標系中的絕對軸距總和來計算節點間的距離，相比于歐幾里得距離，其計算簡單、效率高，但是在尋找路徑的質量上較低。

（2）對角線距離。 在估價函數中考慮了沿對角線移動的情況，相對于曼哈頓距離和歐幾里得距離，在進行評估值計算時與最優路徑的評估值誤差較小，因此可以有效提高路徑的質量和算法的效率。

（3）歐幾里得距離。 是計算兩點之間最短距離的一種方法，通常被用作啟發式函數之一。 但是，歐幾里得距離計算涉及平方和開方運算，因此在尋找大型圖形上的最短路徑時，效率較低。

分析可知，選擇合適的啟發式函數取決于特定應用場景，通常需要平衡最短路徑的質量和算法執行效率。 在本文中，選擇對角線距離作為啟發式函數，因為該函數與最優路徑的評估值誤差較小，且計算相對簡單，能夠提高路徑的質量和算法的效率。改進的啟發式函數計算公式如下：

其中，在柵格法地圖中，c表示水平或豎直移動一步的代價，而對角線移動的代價為√2c。 由式（2）～（4） 可計算得到對角線距離的代價估值。

在同樣的條件下，經計算對比發現，改進的A?算法運行效率得到了提高，同時擴展的節點并沒有減少，因此仍可得到與原A?算法相同的路徑規劃結果。

3 仿真實驗

3.1 參數設置

在智慧工廠的模擬實驗中，網格的大小為8 m×8 m，工廠的長度和寬度均為800 m。 AGV 數量為100 臺，AGV 的運行速度為1 m／s。 為了設置適當的x、y參數，需要考慮每個參數的含義和對路徑規劃的影響。 在該實驗中，需要使距離越近的節點受到更多的懲罰，從而避免AGV 出現擁堵或者交叉運行的情況。 本文利用C＋＋語言開發智慧工廠中多AGV 貨物分揀的仿真軟件。 該軟件可以監控AGV運動軌跡，調整AGV 運行速度，通過柵格法建模，可根據系統需求自動設置工廠所要用的AGV 數量。

3.2 AGV 防碰撞分析

由于本次仿真實驗所有的AGV 運行速度均為1 m／s，并規定后面的AGV 停止等待前面的AGV 通過后再繼續運行。 因此本次實驗不考慮趕超沖突，只考慮節點沖突。 多AGV 防碰撞路徑規劃涉及到對多輛AGV 路徑的規劃，可以采用改進的A?算法和蟻群算法。 針對這2 種算法，本文進行了實驗比較，結果見表1。

表1 改進的A?算法與蟻群算法防碰撞對比Tab. 1 Comparison of improved A?algorithm and ant colony algorithm in collision prevention

從表1 數據結果可以發現，隨著AGV 發生碰撞次數的增加，采用蟻群算法和改進的A?算法的路徑規劃模擬時間和停止等待時間也會隨之增加。 使用改進的A?算法進行多AGV 防碰撞路徑規劃時，隨著防碰撞次數的增加，模擬時間呈線性增長趨勢。相比之下，蟻群算法的模擬時間則呈現出指數型增長，這是由于蟻群算法需要進行多次路徑搜索和計算，而每次迭代都需要重新計算AGV 的路徑、尤其是在交叉口防碰撞時，其迭代次數就與碰撞次數相關，增加了計算復雜度。

本文中采用的改進A?算法在停止等待時間上稍優于蟻群算法。 這是因為改進A?算法所用的網格節點作為AGV 的停止點，使得在交叉口防碰撞實驗時，AGV 停止點與交叉口的距離更近，從而減少了等待時間，加快了AGV 再次啟動的時間。 相比之下，蟻群算法的路徑搜索過程比較復雜，在交叉口防碰撞時，需要較長時間進行路徑搜索和計算，導致停止等待時間相對較長。 因此，采用改進的A?算法進行路徑規劃可以有效緩解交通擁堵問題。

3.3 AGV 分揀效率分析

與傳統A?算法相比，基于改進A?算法的多AGV 路徑規劃能夠更有效地提高AGV 的路徑規劃效率，并進一步提升貨物分揀系統的運行效率。 A?算法與改進A?算法分揀高效率對比見表2。 由表2可知，通過改進A?算法后，每秒平均分揀數（ASP／s）可以明顯提高，這得益于在改進的A?算法中，優化了AGV 路徑的選取和優先級的調控，同時還加入了一系列的啟發式函數和判定條件來提高搜索效率。 這種多AGV 防碰撞路徑規劃算法的優勢在于對分揀系統整體性能的提升，可以更加高效、穩定地實現高速、大規模的貨物分揀工作。

表2 A?算法與改進A?算法分揀效率對比Tab. 2 Comparison of sorting efficiency between A?algorithm and improved A?algorithm

從表2 數據結果可以看出，在貨物分揀系統中，無論是傳統的A?算法、還是基于改進的A?算法，隨著時間的增長，分揀速度都會逐漸減緩。 然而，基于改進的A?算法在面對更多的貨物時，可以更好地應對系統的需求，從而提高分揀速度，獲得了更好的穩定性。 這是因為基于改進的A?算法考慮了交通擁堵和防碰撞，能夠規避道路擁堵和車輛碰撞的問題，提高了整個分揀系統的運作效率。 因此，基于改進的A?算法進行多AGV 路徑規劃可以提高分揀系統的整體效率和生產力。

4 結束語

本文針對智慧工廠中AGV 路徑規劃采用柵格法建模，基于傳統的A?算法，提出了一種改進A?算法的路徑規劃，在不影響AGV 運行效率的前提下，利用啟發信息快速導向目標節點，能夠實現AGV 路徑規劃和主動避障，從而緩解交通擁堵和避免碰撞。 未來工作應該針對不同的應用環境研發更加高效的路徑規劃算法。