魏 濤

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

0 引 言

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

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

1 AGV 運行環(huán)境建模

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

圖1 柵格法環(huán)境建模Fig. 1 Grid based environmental modeling

采用柵格法環(huán)境建模，其優(yōu)點在于：

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

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

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

2 改進A?算法的路徑規(guī)劃

2.1 A?算法

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

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

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

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

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

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

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

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

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

②如果相鄰節(jié)點m已經(jīng)存在于CLOSE 表中，則跳過該節(jié)點，并繼續(xù)處理下一個節(jié)點。

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

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

（6）循環(huán)執(zhí)行步驟（3）到步驟（5），直至找到終止節(jié)點或者OPEN 表為空。

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

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

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

2.2 A?算法的不足

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

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

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

（4）A?算法對空間的要求較高。 A?算法需要維護一個優(yōu)先隊列來存儲已經(jīng)搜索過的節(jié)點。 如果目標狀態(tài)太大，可能會出現(xiàn)內(nèi)存不足，從而導(dǎo)致算法無法運行。

（5）A?算法的實現(xiàn)較為復(fù)雜。 在編寫A?算法時，除了需要合理選擇啟發(fā)式函數(shù)以外，還需要得到優(yōu)先隊列和開放列表等輔助工具。 因此，需要花費一定時間來構(gòu)建和調(diào)試算法。

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

2.3 AGV 碰撞類型

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

（1）節(jié)點沖突。 節(jié)點沖突是指整個運行線路中，在某一時刻，有2 個或多個AGV 同時經(jīng)過某一節(jié)點。 節(jié)點沖突示意如圖2 所示。 通過設(shè)置AGV路徑優(yōu)先級，可以避免發(fā)生節(jié)點沖突。

圖2 節(jié)點沖突Fig. 2 Node conflict

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

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

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

圖4 相遇沖突Fig. 4 Encounter conflict

2.4 A?算法的改進

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

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

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

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

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

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

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

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

3 仿真實驗

3.1 參數(shù)設(shè)置

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

3.2 AGV 防碰撞分析

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

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

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

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

3.3 AGV 分揀效率分析

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

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

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

4 結(jié)束語

本文針對智慧工廠中AGV 路徑規(guī)劃采用柵格法建模，基于傳統(tǒng)的A?算法，提出了一種改進A?算法的路徑規(guī)劃，在不影響AGV 運行效率的前提下，利用啟發(fā)信息快速導(dǎo)向目標節(jié)點，能夠?qū)崿F(xiàn)AGV 路徑規(guī)劃和主動避障，從而緩解交通擁堵和避免碰撞。 未來工作應(yīng)該針對不同的應(yīng)用環(huán)境研發(fā)更加高效的路徑規(guī)劃算法。