基于改進(jìn)Dijkstra算法的AGV智能車(chē)路徑規(guī)劃

梁彧

基于改進(jìn)Dijkstra算法的AGV智能車(chē)路徑規(guī)劃

梁彧

（武漢理工大學(xué) 自動(dòng)化學(xué)院，湖北 武漢 430070）

為了解決傳統(tǒng)Dijkstra算法路徑搜索范圍大、效率低的問(wèn)題，針對(duì)自動(dòng)導(dǎo)引車(chē)（Automated Guided Vehicle，AGV）在部分已知的非結(jié)構(gòu)化靜態(tài)環(huán)境下的路徑規(guī)劃進(jìn)行研究，提出了一種改進(jìn)Dijkstra算法。這種算法的改進(jìn)在于引入了估計(jì)函數(shù)，通過(guò)對(duì)路徑代價(jià)進(jìn)行估計(jì)，可以在縮短響應(yīng)時(shí)間的基礎(chǔ)上規(guī)劃出最短路徑，達(dá)到在未知環(huán)境中為AGV智能車(chē)提供無(wú)碰撞規(guī)劃路線(xiàn)的效果，極大地提高了規(guī)劃效率。通過(guò)MATLAB軟件進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了方法的有效性，可以通過(guò)數(shù)據(jù)展示。

Dijkstra算法；AGV智能車(chē)；估計(jì)函數(shù)；路徑規(guī)劃

1 引言

隨著工業(yè)生產(chǎn)自動(dòng)化進(jìn)程的迅速發(fā)展，智能倉(cāng)儲(chǔ)系統(tǒng)、智能物流運(yùn)輸逐漸成為“智能制造”的一個(gè)重要組成部分[1]，自動(dòng)導(dǎo)引車(chē)廣泛應(yīng)用于智能倉(cāng)儲(chǔ)物流系統(tǒng)[2]、智能碼垛搬運(yùn)系統(tǒng)[3]。汽車(chē)行業(yè)是最早開(kāi)始使用AGV的制造行業(yè)，在汽車(chē)誕生之初，其型號(hào)比較單一，生產(chǎn)制造都是由人工組裝完成，福特公司率先使用流水線(xiàn)方式進(jìn)行大批量生產(chǎn)，是汽車(chē)制造行業(yè)的一次創(chuàng)新[4]。近年來(lái)，AGV小車(chē)的無(wú)線(xiàn)通信系統(tǒng)、小車(chē)平臺(tái)的升降系統(tǒng)和智能定位系統(tǒng)研究趨于成熟。將AGV運(yùn)載小車(chē)有效運(yùn)用到物流系統(tǒng)中，可以降低成本，提高工作效率，減少人工分揀失誤，實(shí)現(xiàn)物流運(yùn)輸?shù)闹悄芑?目標(biāo)[5]。

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

基于以上問(wèn)題，本文在Dijkstra算法的基礎(chǔ)上引入了啟發(fā)算法，設(shè)計(jì)了估價(jià)函數(shù)，根據(jù)傳感器獲得的實(shí)時(shí)環(huán)境信息，改進(jìn)Dijkstra算法以高效率產(chǎn)生一條滿(mǎn)足AGV智能車(chē)非完整性約束的路徑，保證所規(guī)劃局部路徑的可行性。能夠在保證路徑盡可能短的基礎(chǔ)上提高AGV智能車(chē)路徑規(guī)劃的效率，有效解決了傳統(tǒng)Dijkstra算法速度慢且存儲(chǔ)量大的問(wèn)題，滿(mǎn)足當(dāng)今“智能制造”環(huán)境中高速、高效的需求。

2 Dijkstra算法原理

2.1 原理簡(jiǎn)介

Dijkstra算法是解決最短路徑問(wèn)題的經(jīng)典算法之一，常用于計(jì)算從一個(gè)節(jié)點(diǎn)到其周?chē)泄?jié)點(diǎn)的最短路徑，從而幫助AGV智能車(chē)在柵格地圖上針對(duì)非結(jié)構(gòu)化靜態(tài)環(huán)境進(jìn)行路徑規(guī)劃。該算法的核心思想是以遍歷的形式找到圖中所有節(jié)點(diǎn)的最短路徑，從而確立目標(biāo)點(diǎn)的最短路徑。采用從目標(biāo)節(jié)點(diǎn)到起始節(jié)點(diǎn)的搜索方式，可以運(yùn)用于起始點(diǎn)改變的情況。傳統(tǒng)的Dijkstra算法在AGV智能車(chē)路徑規(guī)劃中從起始源節(jié)點(diǎn)o開(kāi)始，對(duì)其周?chē)泄?jié)點(diǎn)的最短路徑進(jìn)行搜索，基本的思路為：在路網(wǎng)模型中每個(gè)節(jié)點(diǎn)表示為（|），其中為起始源節(jié)點(diǎn)o到目標(biāo)節(jié)點(diǎn)m的最短道路權(quán)值，為起始源節(jié)點(diǎn)o到目標(biāo)節(jié)點(diǎn)m的前一個(gè)節(jié)點(diǎn)。Dijkstra算法的計(jì)算流程如圖1所示。

Dijkstra算法的優(yōu)勢(shì)在于，當(dāng)環(huán)境中出現(xiàn)新的未知障礙物時(shí)，可以快速更新該障礙物周邊節(jié)點(diǎn)的信息，并將由此而導(dǎo)致不連續(xù)的節(jié)點(diǎn)重新壓入優(yōu)先列表中進(jìn)行快速的重新規(guī)劃。但是在柵格環(huán)境下，Dijkstra算法所規(guī)劃出的路徑并不平滑；當(dāng)AGV智能車(chē)處于未知環(huán)境中，在距離當(dāng)前位置較近處出現(xiàn)障礙物的可能性非常大。

圖1 Dijkstra算法計(jì)算流程圖

2.2 柵格地圖的建立

AGV智能車(chē)運(yùn)動(dòng)路徑的搜索與規(guī)劃必須先采集其工作環(huán)境信息后進(jìn)行建模，然后在建立的地圖模型上進(jìn)行路徑規(guī)劃。柵格地圖結(jié)構(gòu)簡(jiǎn)單，空間數(shù)據(jù)的重疊和組合容易，易于實(shí)現(xiàn)算法功能。基于以上優(yōu)點(diǎn)，本文采用柵格地圖進(jìn)行建模，柵格信息與AGV智能車(chē)的工作環(huán)境相對(duì)應(yīng)。地圖中的節(jié)點(diǎn)對(duì)應(yīng)其運(yùn)行過(guò)程中的不同站點(diǎn)，邊框代表其實(shí)際的運(yùn)行路徑，其中綠色代表起點(diǎn)，黃色代表目標(biāo)節(jié)點(diǎn)，黑色區(qū)域?yàn)檎系K物信息，如圖2所示。采用柵格地圖建立模型，可以最大限度減少不必要的地圖信息，提高計(jì)算機(jī)對(duì)路徑規(guī)劃的處理速度與能力，便于創(chuàng)建與維護(hù)。

3 基于改進(jìn)的Dijkstra算法路徑規(guī)劃

傳統(tǒng)的Dijkstra算法需要以遍歷的形式搜索到所有節(jié)點(diǎn)的最短路徑，路徑規(guī)劃速度慢、效率低。針對(duì)以上問(wèn)題，基于Dijkstra算法提出一種啟發(fā)式搜索算法，這種算法的改進(jìn)在于引入了估計(jì)函數(shù)，通過(guò)對(duì)路徑代價(jià)進(jìn)行估計(jì)，可以在縮短響應(yīng)時(shí)間的基礎(chǔ)上規(guī)劃出最短路徑。

盲目搜索會(huì)浪費(fèi)很多時(shí)間和空間，因此在進(jìn)行路徑搜索時(shí)會(huì)首先選擇最有希望的節(jié)點(diǎn)，這種搜索稱(chēng)之為“啟發(fā)式搜索”[9]。改進(jìn)后的Dijkstra算法核心為估計(jì)函數(shù)，在估計(jì)函數(shù)中加入了啟發(fā)式代價(jià)值，使搜索的過(guò)程由啟發(fā)式代價(jià)值不斷導(dǎo)向至目標(biāo)狀態(tài)，可以減少大量計(jì)算過(guò)程，大大提高算法效率。

估計(jì)函數(shù)（）表示如下：

（）=（）+（） （1）

式（1）中：（）為從初始狀態(tài)0經(jīng)由狀態(tài)到目標(biāo)狀態(tài)的代價(jià)估計(jì)；（）為由起始狀態(tài)0到狀態(tài)的實(shí)際代價(jià)；（）為從狀態(tài)到目標(biāo)狀態(tài)最佳路徑的估計(jì)代價(jià)。

在路徑規(guī)劃的過(guò)程中，需要選擇值最小的下一節(jié)點(diǎn)作為最優(yōu)路徑中的節(jié)點(diǎn)。

算法中（）值由起點(diǎn)開(kāi)始所經(jīng)過(guò)的距離累加而得，（）值則通過(guò)距離預(yù)估方法求得，如果是狀態(tài)坐標(biāo)是目標(biāo)狀態(tài)坐標(biāo)，則估計(jì)代價(jià)表示如下：

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

通常選取當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的直線(xiàn)距離（歐幾里得距離）作為啟發(fā)式代價(jià)，可以表示為：

在（）＜（）的條件下，該算法在遍歷所有節(jié)點(diǎn)后可以找到最短路徑。在估計(jì)函數(shù)中，（）對(duì)算法起主要作用；（）估值越小，算法需要計(jì)算的節(jié)點(diǎn)就越多，導(dǎo)致算法效率降低，趨近于傳統(tǒng)Dijkstra算法；但如果（）估值很大，則會(huì)導(dǎo)致（）的作用失效，逐步趨于BFS算法，只追求速度無(wú)法獲取合理路徑。

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

4 仿真實(shí)驗(yàn)分析

本文利用MATLAB軟件編寫(xiě)了路徑規(guī)劃算法的相關(guān)程序，并對(duì)改進(jìn)后算法的有效性進(jìn)行了仿真驗(yàn)證。

實(shí)驗(yàn)設(shè)計(jì)思路：預(yù)先設(shè)定AGV智能車(chē)的初始節(jié)點(diǎn)、目標(biāo)節(jié)點(diǎn)以及障礙物位置，構(gòu)建10×10柵格地圖模型對(duì)AGV智能車(chē)的運(yùn)行環(huán)境進(jìn)行模擬，分別使用傳統(tǒng)的Dijkstra算法和改進(jìn)后的Dijkstra算法進(jìn)行路徑規(guī)劃，最后進(jìn)行結(jié)果比對(duì)。

在主程序中設(shè)置初始節(jié)點(diǎn)為（2，6），目標(biāo)節(jié)點(diǎn)為（9，8），子節(jié)點(diǎn)分別從8個(gè)方向進(jìn)行路徑搜索，得到的仿真結(jié)果如圖4、圖5所示。

如圖4和圖5所示，路徑規(guī)劃圖中綠色區(qū)域?yàn)槌跏脊?jié)點(diǎn)，黃色區(qū)域?yàn)槟繕?biāo)節(jié)點(diǎn)，黑色區(qū)域代表障礙物，紅色區(qū)域代表open-list，藍(lán)色區(qū)域代表close-list。通過(guò)2次仿真實(shí)驗(yàn)進(jìn)行對(duì)比，改進(jìn)Dijkstra算法得到的路徑為7個(gè)柵格距離，響應(yīng)時(shí)間為0.098 s，而傳統(tǒng)Dijkstra算法規(guī)劃出的路徑為9個(gè)柵格距離，響應(yīng)時(shí)間為0.125 s。相較于傳統(tǒng)的Dijkstra算法，改進(jìn)后的Dijkstra算法行程縮短22.2%，響應(yīng)時(shí)間減少21.6%。根據(jù)2張路徑規(guī)劃圖進(jìn)行對(duì)比分析，可以發(fā)現(xiàn)改進(jìn)后的Dijkstra算法無(wú)需遍歷圖中所有節(jié)點(diǎn)，估計(jì)函數(shù)使搜索的過(guò)程由啟發(fā)式代價(jià)值不斷導(dǎo)向目標(biāo)狀態(tài)，在縮短路徑的同時(shí)大大提高了路徑規(guī)劃的效率。改進(jìn)后的算法克服了傳統(tǒng)Dijkstra算法需要遍歷所有節(jié)點(diǎn)的弊端，在保證高效率的條件下達(dá)到在未知環(huán)境中為AGV智能車(chē)提供無(wú)碰撞規(guī)劃路線(xiàn)的效果。

圖2 AGV智能車(chē)運(yùn)行環(huán)境的柵格地圖模型

圖3 改進(jìn)Dijkstra算法計(jì)算流程圖

圖4 傳統(tǒng)Dijkstra算法路徑規(guī)劃圖

圖5 改進(jìn)Dijkstra算法路徑規(guī)劃圖

5 總結(jié)與展望

本文主要對(duì)部分已知的非結(jié)構(gòu)化靜態(tài)環(huán)境中的AGV小車(chē)路徑規(guī)劃方法進(jìn)行了研究，為滿(mǎn)足AGV智能車(chē)的實(shí)際運(yùn)行要求，基于Dijkstra算法進(jìn)行改進(jìn)，引入了啟發(fā)算法，設(shè)計(jì)了估價(jià)函數(shù)，能夠在保證路徑盡可能短的基礎(chǔ)上提高AGV智能車(chē)路徑規(guī)劃的效率，有效地解決了傳統(tǒng)Dijkstra算法速度慢且存儲(chǔ)量大的問(wèn)題。經(jīng)過(guò)MATLAB軟件的仿真實(shí)驗(yàn)，可以驗(yàn)證改進(jìn)Dijkstra算法優(yōu)化AGV智能車(chē)的規(guī)劃路徑是切實(shí)可行的。

［1］唐榆坤，渠水凈.AGV在制造業(yè)倉(cāng)儲(chǔ)分揀業(yè)務(wù)中的運(yùn)用［J］.物流技術(shù)與應(yīng)用，2020，25（7）：127-130.

［2］李鵬濤.基于AGV與RFID的智能倉(cāng)儲(chǔ)系統(tǒng)的應(yīng)用研究［J］.科技創(chuàng)新與應(yīng)用，2020（11）：181-183.

［3］吳瑜.智能碼垛系統(tǒng)在物流倉(cāng)儲(chǔ)中的應(yīng)用［J］.電子世界，2020（13）：142-143.

［4］AGV小車(chē)在汽車(chē)行業(yè)自動(dòng)化生產(chǎn)線(xiàn)上的應(yīng)用［J］.汽車(chē)工藝師，2020（7）：16-18.

［5］呂吟雪，周穆新，王超駒，等.AGV小車(chē)在物流運(yùn)輸行業(yè)中的應(yīng)用研究［J］.機(jī)電信息，2020（14）：37，39.

［6］宋啟松，李少波，柘龍炫，等.基于改進(jìn)遺傳算法的自動(dòng)導(dǎo)引小車(chē)路徑規(guī)劃［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2020（7）：88-92.

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

［8］顧軍華，范培培，宋慶增.改進(jìn)的求解TSP問(wèn)題文化蟻群優(yōu)化方法［J］.計(jì)算機(jī)工程與應(yīng)用，2010（26）：49-52.

［9］李釗，董霄霄，黃程程，等.基于啟發(fā)式搜索的浮點(diǎn)表達(dá)式設(shè)計(jì)空間探索方法［J］.計(jì)算機(jī)應(yīng)用，2020（9）：2665-2669.

2095－6835（2020）24－0159－03

TP18

A

10.15913/j.cnki.kjycx.2020.24.061

梁彧（2000—），男，本科在讀，研究方向?yàn)楣た嘏c智能機(jī)器人。

〔編輯：張思楠〕