基于改進Dijkstra算法的AGV智能車路徑規劃

梁彧

基于改進Dijkstra算法的AGV智能車路徑規劃

梁彧

（武漢理工大學 自動化學院，湖北 武漢 430070）

為了解決傳統Dijkstra算法路徑搜索范圍大、效率低的問題，針對自動導引車（Automated Guided Vehicle，AGV）在部分已知的非結構化靜態環境下的路徑規劃進行研究，提出了一種改進Dijkstra算法。這種算法的改進在于引入了估計函數，通過對路徑代價進行估計，可以在縮短響應時間的基礎上規劃出最短路徑，達到在未知環境中為AGV智能車提供無碰撞規劃路線的效果，極大地提高了規劃效率。通過MATLAB軟件進行仿真實驗，驗證了方法的有效性，可以通過數據展示。

Dijkstra算法；AGV智能車；估計函數；路徑規劃

1 引言

隨著工業生產自動化進程的迅速發展，智能倉儲系統、智能物流運輸逐漸成為“智能制造”的一個重要組成部分[1]，自動導引車廣泛應用于智能倉儲物流系統[2]、智能碼垛搬運系統[3]。汽車行業是最早開始使用AGV的制造行業，在汽車誕生之初，其型號比較單一，生產制造都是由人工組裝完成，福特公司率先使用流水線方式進行大批量生產，是汽車制造行業的一次創新[4]。近年來，AGV小車的無線通信系統、小車平臺的升降系統和智能定位系統研究趨于成熟。將AGV運載小車有效運用到物流系統中，可以降低成本，提高工作效率，減少人工分揀失誤，實現物流運輸的智能化 目標[5]。

路徑規劃作為智能車研究的關鍵技術，是研發過程中不可避免的重要環節，即如何在減少碰撞的情況下，高效規劃出一條從初始位置到目標位置的最優運動路徑。針對不同行業對AGV提出不同的應用需求，研究者提出了許多不同的路徑規劃算法。在碼頭集裝箱運輸中，將遺傳算法應用于碼頭環境，與其他工作場景相比，AGV智能車在復雜碼頭進行路徑規劃時會出現擁堵、多載、易碰撞、效率低、耗時長等問題[6]。對于規模過大的問題，遺傳算法會出現求解效率低、編碼復雜及早熟等問題。而蟻群算法（ACO）具有并行性、正反饋性及良好的擴充性等優點[7]，在解決路徑規劃、TSP[8]等問題都有成功的應用。但傳統的蟻群算法存在運行時間長、搜索效率低的問題。針對以上問題，Dijkstra算法得到發展，該算法遇到動態環境時無需對路徑重新規劃，能夠幫助AGV智能車一次性規劃出最優路線。Dijkstra算法因其高實用性至今被學者們在機器人探路、交通路線導航、人工智能、游戲設計等方面廣泛應用，對AGV智能車在不同環境下運行具有很強的擴展性和適應性。但是針對環境復雜的大區域地圖，Dijkstra算法從起始點開始向周圍層層計算擴展，在遍歷大量節點后到達目標節點。因此，該算法速度慢、效率低，并且存儲量會大大增加，當動態障礙頻繁出現后依然需要重新規劃。

基于以上問題，本文在Dijkstra算法的基礎上引入了啟發算法，設計了估價函數，根據傳感器獲得的實時環境信息，改進Dijkstra算法以高效率產生一條滿足AGV智能車非完整性約束的路徑，保證所規劃局部路徑的可行性。能夠在保證路徑盡可能短的基礎上提高AGV智能車路徑規劃的效率，有效解決了傳統Dijkstra算法速度慢且存儲量大的問題，滿足當今“智能制造”環境中高速、高效的需求。

2 Dijkstra算法原理

2.1 原理簡介

Dijkstra算法是解決最短路徑問題的經典算法之一，常用于計算從一個節點到其周圍所有節點的最短路徑，從而幫助AGV智能車在柵格地圖上針對非結構化靜態環境進行路徑規劃。該算法的核心思想是以遍歷的形式找到圖中所有節點的最短路徑，從而確立目標點的最短路徑。采用從目標節點到起始節點的搜索方式，可以運用于起始點改變的情況。傳統的Dijkstra算法在AGV智能車路徑規劃中從起始源節點o開始，對其周圍所有節點的最短路徑進行搜索，基本的思路為：在路網模型中每個節點表示為（|），其中為起始源節點o到目標節點m的最短道路權值，為起始源節點o到目標節點m的前一個節點。Dijkstra算法的計算流程如圖1所示。

Dijkstra算法的優勢在于，當環境中出現新的未知障礙物時，可以快速更新該障礙物周邊節點的信息，并將由此而導致不連續的節點重新壓入優先列表中進行快速的重新規劃。但是在柵格環境下，Dijkstra算法所規劃出的路徑并不平滑；當AGV智能車處于未知環境中，在距離當前位置較近處出現障礙物的可能性非常大。

圖1 Dijkstra算法計算流程圖

2.2 柵格地圖的建立

AGV智能車運動路徑的搜索與規劃必須先采集其工作環境信息后進行建模，然后在建立的地圖模型上進行路徑規劃。柵格地圖結構簡單，空間數據的重疊和組合容易，易于實現算法功能。基于以上優點，本文采用柵格地圖進行建模，柵格信息與AGV智能車的工作環境相對應。地圖中的節點對應其運行過程中的不同站點，邊框代表其實際的運行路徑，其中綠色代表起點，黃色代表目標節點，黑色區域為障礙物信息，如圖2所示。采用柵格地圖建立模型，可以最大限度減少不必要的地圖信息，提高計算機對路徑規劃的處理速度與能力，便于創建與維護。

3 基于改進的Dijkstra算法路徑規劃

傳統的Dijkstra算法需要以遍歷的形式搜索到所有節點的最短路徑，路徑規劃速度慢、效率低。針對以上問題，基于Dijkstra算法提出一種啟發式搜索算法，這種算法的改進在于引入了估計函數，通過對路徑代價進行估計，可以在縮短響應時間的基礎上規劃出最短路徑。

盲目搜索會浪費很多時間和空間，因此在進行路徑搜索時會首先選擇最有希望的節點，這種搜索稱之為“啟發式搜索”[9]。改進后的Dijkstra算法核心為估計函數，在估計函數中加入了啟發式代價值，使搜索的過程由啟發式代價值不斷導向至目標狀態，可以減少大量計算過程，大大提高算法效率。

估計函數（）表示如下：

（）=（）+（） （1）

式（1）中：（）為從初始狀態0經由狀態到目標狀態的代價估計；（）為由起始狀態0到狀態的實際代價；（）為從狀態到目標狀態最佳路徑的估計代價。

在路徑規劃的過程中，需要選擇值最小的下一節點作為最優路徑中的節點。

算法中（）值由起點開始所經過的距離累加而得，（）值則通過距離預估方法求得，如果是狀態坐標是目標狀態坐標，則估計代價表示如下：

（）=|1－2|+|1－2| （2）

通常選取當前節點到目標節點的直線距離（歐幾里得距離）作為啟發式代價，可以表示為：

在（）＜（）的條件下，該算法在遍歷所有節點后可以找到最短路徑。在估計函數中，（）對算法起主要作用；（）估值越小，算法需要計算的節點就越多，導致算法效率降低，趨近于傳統Dijkstra算法；但如果（）估值很大，則會導致（）的作用失效，逐步趨于BFS算法，只追求速度無法獲取合理路徑。

改進的Dijkstra算法在路徑搜索的過程中把起始點o加入open-list，分別往八個方向搜索其連通區域里的子節點，通過式（1）分別計算每個子節點的估計值，再從當前的open-list選取值最小的下一節點n作為最優路徑中的節點，加入close-list。接著遍歷n的后繼節點ns，如果ns是新節點，則加入open-list；如果ns已經位于open-list中，并且當前（ns）的值更小，則更新ns節點并修改parent節點。按以上步驟進行反復更新迭代，直至找到目標節點。最后從目標節點反向追溯其parent節點，從而規劃出最優路徑。改進Dijkstra算法計算流程如圖3所示。

4 仿真實驗分析

本文利用MATLAB軟件編寫了路徑規劃算法的相關程序，并對改進后算法的有效性進行了仿真驗證。

實驗設計思路：預先設定AGV智能車的初始節點、目標節點以及障礙物位置，構建10×10柵格地圖模型對AGV智能車的運行環境進行模擬，分別使用傳統的Dijkstra算法和改進后的Dijkstra算法進行路徑規劃，最后進行結果比對。

在主程序中設置初始節點為（2，6），目標節點為（9，8），子節點分別從8個方向進行路徑搜索，得到的仿真結果如圖4、圖5所示。

如圖4和圖5所示，路徑規劃圖中綠色區域為初始節點，黃色區域為目標節點，黑色區域代表障礙物，紅色區域代表open-list，藍色區域代表close-list。通過2次仿真實驗進行對比，改進Dijkstra算法得到的路徑為7個柵格距離，響應時間為0.098 s，而傳統Dijkstra算法規劃出的路徑為9個柵格距離，響應時間為0.125 s。相較于傳統的Dijkstra算法，改進后的Dijkstra算法行程縮短22.2%，響應時間減少21.6%。根據2張路徑規劃圖進行對比分析，可以發現改進后的Dijkstra算法無需遍歷圖中所有節點，估計函數使搜索的過程由啟發式代價值不斷導向目標狀態，在縮短路徑的同時大大提高了路徑規劃的效率。改進后的算法克服了傳統Dijkstra算法需要遍歷所有節點的弊端，在保證高效率的條件下達到在未知環境中為AGV智能車提供無碰撞規劃路線的效果。

圖2 AGV智能車運行環境的柵格地圖模型

圖3 改進Dijkstra算法計算流程圖

圖4 傳統Dijkstra算法路徑規劃圖

圖5 改進Dijkstra算法路徑規劃圖

5 總結與展望

本文主要對部分已知的非結構化靜態環境中的AGV小車路徑規劃方法進行了研究，為滿足AGV智能車的實際運行要求，基于Dijkstra算法進行改進，引入了啟發算法，設計了估價函數，能夠在保證路徑盡可能短的基礎上提高AGV智能車路徑規劃的效率，有效地解決了傳統Dijkstra算法速度慢且存儲量大的問題。經過MATLAB軟件的仿真實驗，可以驗證改進Dijkstra算法優化AGV智能車的規劃路徑是切實可行的。

［1］唐榆坤，渠水凈.AGV在制造業倉儲分揀業務中的運用［J］.物流技術與應用，2020，25（7）：127-130.

［2］李鵬濤.基于AGV與RFID的智能倉儲系統的應用研究［J］.科技創新與應用，2020（11）：181-183.

［3］吳瑜.智能碼垛系統在物流倉儲中的應用［J］.電子世界，2020（13）：142-143.

［4］AGV小車在汽車行業自動化生產線上的應用［J］.汽車工藝師，2020（7）：16-18.

［5］呂吟雪，周穆新，王超駒，等.AGV小車在物流運輸行業中的應用研究［J］.機電信息，2020（14）：37，39.

［6］宋啟松，李少波，柘龍炫，等.基于改進遺傳算法的自動導引小車路徑規劃［J］.組合機床與自動化加工技術，2020（7）：88-92.

［7］葛志遠，肖本賢.使用改進蟻群算法的AGV路徑規劃研究［J］.機械設計與制造，2020（6）：241-244，248.

［8］顧軍華，范培培，宋慶增.改進的求解TSP問題文化蟻群優化方法［J］.計算機工程與應用，2010（26）：49-52.

［9］李釗，董霄霄，黃程程，等.基于啟發式搜索的浮點表達式設計空間探索方法［J］.計算機應用，2020（9）：2665-2669.

2095－6835（2020）24－0159－03

TP18

A

10.15913/j.cnki.kjycx.2020.24.061

梁彧（2000—），男，本科在讀，研究方向為工控與智能機器人。

〔編輯：張思楠〕