雙向搜索機(jī)制的改進(jìn)A＊算法研究

孔繼利，張鵬坤，劉曉平

北京郵電大學(xué) 現(xiàn)代郵政學(xué)院，北京100876

隨著經(jīng)濟(jì)日益發(fā)展以及生產(chǎn)管理水平的進(jìn)步，高度自動(dòng)化、智能化的AGV應(yīng)用愈加廣泛，柔性制造系統(tǒng)[1]、智慧倉儲(chǔ)[2]、自動(dòng)化碼頭[3]、智能停車場(chǎng)[4]都是AGV常見的應(yīng)用場(chǎng)景。對(duì)AGV 調(diào)度而言，最重要的內(nèi)容之一就是路徑規(guī)劃。AGV的路徑規(guī)劃是指選取從任務(wù)起始點(diǎn)到目標(biāo)點(diǎn)的一條路線，使一定目標(biāo)（時(shí)間、距離、能耗等）達(dá)到最優(yōu)化，并且避免與已知障礙物的碰撞。為AGV選擇有效的路徑，可以提高物流效率，降低運(yùn)輸成本。因此，對(duì)AGV路徑規(guī)劃算法進(jìn)行研究具有重要意義。

在點(diǎn)點(diǎn)間運(yùn)輸問題的路徑規(guī)劃中，常見的算法有Dijkstra 算法[5]、Floyd 算法[6]、人工勢(shì)場(chǎng)法等。A*算法同樣作為常見的點(diǎn)點(diǎn)間路徑規(guī)劃算法[7]，與Dijkstra算法和Floyd 算法相比具有更強(qiáng)的啟發(fā)式信息，在最短路徑的搜索效率上存在一定優(yōu)勢(shì)。A*算法是一種基于全局的最短路徑搜索算法，能夠較好地避免人工勢(shì)場(chǎng)法頻繁出現(xiàn)的局部最優(yōu)問題。A*算法已經(jīng)廣泛應(yīng)用于多種場(chǎng)景，包括室內(nèi)機(jī)器人的路徑規(guī)劃、無人船的路徑規(guī)劃和電子游戲中的無碰撞檢測(cè)等。但A*算法在實(shí)際應(yīng)用中存在著遍歷節(jié)點(diǎn)多、搜索過程中計(jì)算量龐大等問題，在大規(guī)模環(huán)境下不斷調(diào)用A*算法會(huì)占據(jù)大量?jī)?nèi)存資源。因此，傳統(tǒng)A*算法以及改進(jìn)A*算法在計(jì)算效率上依舊有提升空間。

國(guó)內(nèi)外已有不少學(xué)者針對(duì)A*算法的局限性，對(duì)A*算法進(jìn)行改進(jìn)。Harabor 和Grastien[8]提出了跳點(diǎn)算法，其OPEN列表中只儲(chǔ)存有代表性的跳點(diǎn)，通過對(duì)跳點(diǎn)的連接可以實(shí)現(xiàn)長(zhǎng)距離的跳躍，提高計(jì)算效率；但當(dāng)?shù)貓D中障礙物較多時(shí)，會(huì)找到過多的跳點(diǎn)，降低算法求解效率。王小紅和葉濤[9]提出了一種多鄰域搜索的改進(jìn)A*算法，在小地圖中效果較為顯著，但當(dāng)?shù)貓D規(guī)模較大時(shí)計(jì)算量過大，導(dǎo)致搜索效率降低。Wang和Xiang[10]提出了一種改進(jìn)A*算法，生成的路徑比傳統(tǒng)A*算法更優(yōu)，但計(jì)算效率并未得到較高的提升。Lin等[11]分析了當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)對(duì)啟發(fā)式函數(shù)的影響，并利用最優(yōu)權(quán)值來優(yōu)化路徑，提出了一種提高計(jì)算效率的改進(jìn)A*算法，但以犧牲最優(yōu)路徑為代價(jià)。吳鵬等[12]提出了一種雙向搜索A*算法，正向、反向搜索過程分別以對(duì)方所擴(kuò)展的最優(yōu)節(jié)點(diǎn)作為自己的目標(biāo)節(jié)點(diǎn)，該算法可大幅縮短路徑尋優(yōu)時(shí)間，但同樣會(huì)以犧牲最優(yōu)路徑為代價(jià)。王中玉等[13]對(duì)評(píng)價(jià)函數(shù)進(jìn)行了改進(jìn)，并且提出了減少路徑冗余點(diǎn)的方法，通過仿真證明了改進(jìn)算法的平滑性更強(qiáng)，但該方法的計(jì)算效率仍舊有提升空間。

本文為了進(jìn)一步提升路徑尋優(yōu)的計(jì)算效率與保證路徑的最優(yōu)化，設(shè)計(jì)了一種基于雙向搜索機(jī)制的改進(jìn)A*算法，從搜索方式與評(píng)價(jià)函數(shù)兩方面對(duì)傳統(tǒng)A*算法進(jìn)行優(yōu)化。該算法可應(yīng)用于倉儲(chǔ)系統(tǒng)等已知障礙物的場(chǎng)景。

1 環(huán)境模型的建立

在AGV 的路徑規(guī)劃中，首先需要建立合適的地圖模型。常用的地圖表示方法有柵格法[14]、拓?fù)涞貓D法[15]等。柵格法構(gòu)建地圖模型可以直接有效地進(jìn)行環(huán)境信息的描述，并且在編碼過程中易于實(shí)現(xiàn)。因此，柵格法在AGV的路徑規(guī)劃中得到了廣泛應(yīng)用。

本文利用柵格法進(jìn)行地圖模型的構(gòu)建，并且根據(jù)實(shí)際情況將柵格分成兩種：白色和黑色；白色代表可通行狀態(tài)，黑色代表障礙狀態(tài)，如圖1所示。

圖1 柵格地圖

根據(jù)應(yīng)用場(chǎng)景的實(shí)際需求，本文在AGV 運(yùn)行過程中做出如下假設(shè)：

（1）假設(shè)AGV 在水平方向與垂直方向的正常直線行走中不會(huì)與旁邊柵格中的障礙物相撞，且只能在可通行狀態(tài)下的柵格中運(yùn)行。

（2）在不存在邊界和障礙物的情況下，通常AGV在柵格中的行進(jìn)為一步行走。由于本文考慮的是以室內(nèi)倉儲(chǔ)空間為應(yīng)用場(chǎng)景，在實(shí)際的應(yīng)用中AGV 小車在某些方向（如柵格中心連線與橫軸呈45°的方向）經(jīng)過障礙物時(shí)可能會(huì)與障礙物發(fā)生碰撞，造成損失，如圖2 所示。故本文假設(shè)AGV只能在當(dāng)前節(jié)點(diǎn)周圍的4個(gè)方向上遍歷并依據(jù)選擇標(biāo)準(zhǔn)選擇節(jié)點(diǎn)，并且不考慮AGV 自身高度的影響。AGV可能的運(yùn)行方向如圖3所示。

圖2 AGV在某些方向可能發(fā)生碰撞示意圖

圖3 AGV可能的運(yùn)行方向

（3）在AGV運(yùn)動(dòng)過程中，周圍環(huán)境保持不變。

2 基于雙向搜索機(jī)制的改進(jìn)A＊算法設(shè)計(jì)

2.1 改進(jìn)A＊算法的描述

傳統(tǒng)A*算法為單向搜索，遍歷的節(jié)點(diǎn)較多，計(jì)算效率較低。本文提出的改進(jìn)A*算法為雙向搜索機(jī)制，通過正反兩個(gè)方向的交替搜索減少計(jì)算過程中的冗余節(jié)點(diǎn)，并通過設(shè)置合理的評(píng)估函數(shù)進(jìn)一步提升搜索效率。

文獻(xiàn)[12]所提出的改進(jìn)A*算法同樣為雙向搜索機(jī)制，故選擇文獻(xiàn)[12]中的算法作為對(duì)比算法。本文分別設(shè)置正向搜索的OPEN1列表、CLOSE1列表、評(píng)估函數(shù)，反向搜索的OPEN2列表、CLOSE2列表、評(píng)估函數(shù)。n1、n2分別作為正向搜索和反向搜索過程中的當(dāng)前節(jié)點(diǎn)。正向搜索過程在搜索任務(wù)終點(diǎn)e的同時(shí)考慮反向搜索的當(dāng)前點(diǎn)n2，在啟發(fā)式函數(shù)中對(duì)n1相距e的距離和n1相距n2的距離進(jìn)行加權(quán)處理，共同引導(dǎo)正向搜索方向；反向搜索過程在搜索任務(wù)起點(diǎn)s的同時(shí)考慮正向搜索的當(dāng)前點(diǎn)n1，在啟發(fā)式函數(shù)中對(duì)n2相距s的距離和n2相距n1的距離進(jìn)行加權(quán)處理，共同引導(dǎo)反向搜索方向。這樣的雙向搜索方式可以較好地避免啟發(fā)式信息過強(qiáng)導(dǎo)致犧牲路徑長(zhǎng)度作為代價(jià)的問題，并且能夠保證在路徑尋優(yōu)過程中盡可能少地遍歷無關(guān)節(jié)點(diǎn)，提高算法的計(jì)算效率。

2.2 改進(jìn)A＊算法的處理流程

當(dāng)改進(jìn)A*算法開始運(yùn)行，首先需要初始化OPEN1列表、CLOSE1列表和OPEN2列表、CLOSE2列表。搜索過程中正向搜索與反向搜索交替進(jìn)行。

改進(jìn)A*算法處理流程如下：

（1）將起始點(diǎn)s設(shè)置為正向當(dāng)前節(jié)點(diǎn)n1，并加入OPEN1列表。

（2）搜索n1點(diǎn)周圍可到達(dá)的節(jié)點(diǎn)，把它們加入OPEN1列表。將起始點(diǎn)s設(shè)置為新加入節(jié)點(diǎn)的父節(jié)點(diǎn)。

（3）將起始點(diǎn)s從OPEN1列表中刪除，加入CLOSE1列表中。

（4）將目標(biāo)點(diǎn)e設(shè)置為反向當(dāng)前節(jié)點(diǎn)n2，并加入OPEN2列表。

（5）搜索n2點(diǎn)周圍可到達(dá)的節(jié)點(diǎn)，把它們加入OPEN2列表。將目標(biāo)點(diǎn)e設(shè)置為新加入節(jié)點(diǎn)的父節(jié)點(diǎn)。

（6）將目標(biāo)點(diǎn)e從OPEN2列表中刪除，加入CLOSE2列表中。

（7）重復(fù)如下步驟：

①遍歷OPEN1列表，找到其中評(píng)估函數(shù)f1( )x值最小的節(jié)點(diǎn)，將其設(shè)置為正向當(dāng)前節(jié)點(diǎn)n1。

②將n1點(diǎn)從OPEN1列表中刪除，加入CLOSE1列表中。

③檢查n1點(diǎn)周圍可到達(dá)的節(jié)點(diǎn)，并忽略其中已在CLOSE1列表的節(jié)點(diǎn)或障礙物。如果可到達(dá)的節(jié)點(diǎn)不在OPEN1列表中，則將其加入到OPEN1列表，并且將n1點(diǎn)設(shè)定為它們的父節(jié)點(diǎn)。如果可到達(dá)的節(jié)點(diǎn)存在于OPEN1列表中，稱該節(jié)點(diǎn)為x點(diǎn)，計(jì)算經(jīng)過n1點(diǎn)到達(dá)x點(diǎn)的g1(x)值，如果該g1(x)值小于原g1(x)值，則將n1點(diǎn)作為x點(diǎn)的父節(jié)點(diǎn)，更新OPEN1列表中的f1(x)和g1(x)。

④遍歷OPEN2列表，找到其中評(píng)估函數(shù)f2(y)值最小的節(jié)點(diǎn)，將其設(shè)置為反向當(dāng)前節(jié)點(diǎn)n2。

⑤將n2點(diǎn)從OPEN2列表中刪除，加入CLOSE2列表中。

⑥檢查n2點(diǎn)周圍可到達(dá)的節(jié)點(diǎn)，并忽略其中已在CLOSE2列表的節(jié)點(diǎn)或障礙物。如果可到達(dá)的節(jié)點(diǎn)不在OPEN2列表中，則將其加入到OPEN2列表。并且將n2點(diǎn)設(shè)定為它們的父節(jié)點(diǎn)。如果可到達(dá)的節(jié)點(diǎn)存在于OPEN2列表中，稱該節(jié)點(diǎn)為y點(diǎn)，計(jì)算經(jīng)過n2點(diǎn)到達(dá)y點(diǎn)的g2(y)值，如果該g2(y)值小于原g2(y)值，則將n2點(diǎn)作為y點(diǎn)的父節(jié)點(diǎn)，更新OPEN2列表中的f2(y)和g2(y)。

（8）終止條件為：

①當(dāng)OPEN1列表中包含CLOSE2列表中的點(diǎn)或OPEN2列表中包含CLOSE1列表中的點(diǎn)，此時(shí)路徑已找到。

②當(dāng)OPEN1列表或OPEN2列表任何一個(gè)為空時(shí)，此時(shí)尋路失敗，輸出尋路失敗提示。

改進(jìn)A*算法的具體流程圖如圖4所示。

綜上所述，數(shù)形結(jié)合思想是數(shù)學(xué)研究與學(xué)習(xí)中的重要數(shù)學(xué)思想，對(duì)于解答問題、記憶數(shù)學(xué)知識(shí)發(fā)揮著關(guān)鍵作用，希望通過本文的闡述可以使得初中數(shù)學(xué)教育工作者深刻認(rèn)識(shí)到數(shù)形結(jié)合思想的重要意義，在教學(xué)實(shí)踐中充分、全面、系統(tǒng)地滲透數(shù)形結(jié)合思想。

圖4 改進(jìn)A*算法具體流程圖

改進(jìn)A*算法的偽代碼如下：

insert start node in OPEN1

insert target node in OPEN2

//將兩個(gè)OPEN列表進(jìn)行初始化操作。

While OPEN1≠null & OPEN2≠null

computen1child nodex

//遍歷n1的子節(jié)點(diǎn)并更新OPEN1列表。

ifxis in the CLOSE2

break

//當(dāng)n1的子節(jié)點(diǎn)在CLOSE2列表時(shí)，則尋找到了一條最短路徑，跳出循環(huán)。

endif

find minf1(x) in OPEN1

n1=x

insertn1in CLOSE1

//將OPEN1列表中f1(x)最小值的點(diǎn)設(shè)置為n1并更新CLOSE1列表

computen2child nodey

update OPEN2

//遍歷n2的子節(jié)點(diǎn)并更新OPEN2列表。

ifyis in the CLOSE1

break

//當(dāng)n2的子節(jié)點(diǎn)在CLOSE1列表時(shí)，則尋找到了一條最短路徑，跳出循環(huán)。

endif

find minf2(y) in OPEN2

n2=y

insertn2in CLOSE2

//將OPEN2列表中f2(y)最小值的點(diǎn)設(shè)置為n2并更新CLOSE2列表

Get path/Fail to get path

2.3 改進(jìn)A＊算法的評(píng)估函數(shù)

2.3.1 評(píng)估函數(shù)的設(shè)計(jì)

本文從尋找合適的啟發(fā)式函數(shù)和加權(quán)處理兩方面對(duì)傳統(tǒng)A*算法的評(píng)估函數(shù)進(jìn)行改進(jìn)，平衡啟發(fā)式信息的強(qiáng)度，提高算法搜索效率。

（1）正向搜索

正向搜索的評(píng)估函數(shù)如式（1）：

其中，n1為正向搜索中的當(dāng)前點(diǎn)；f1(n1)為正向搜索的評(píng)估函數(shù)；h1(n1)為正向搜索中以任務(wù)終點(diǎn)e為目標(biāo)點(diǎn)的啟發(fā)式函數(shù)，采用歐式距離；h'1(n1)為正向搜索中以反向搜索當(dāng)前點(diǎn)n2為目標(biāo)點(diǎn)的啟發(fā)式函數(shù)，采用歐式距離；a為啟發(fā)式函數(shù)中h1(n1)與h'1(n1)之間的權(quán)重系數(shù)，取值范圍[0,+∞)；b為歷史代價(jià)函數(shù)的權(quán)重系數(shù)，取值范圍為（0，1）；(1-b)為啟發(fā)式函數(shù)的權(quán)重系數(shù)；g1(n1)表示正向搜索歷史代價(jià)函數(shù)，其計(jì)算方式如下：

g1(n1-1) 為n1的父節(jié)點(diǎn)的歷史代價(jià)；g1'(n1)為父節(jié)點(diǎn)到n1的成本代價(jià)，采用歐式距離。

（2）反向搜索

反向搜索的評(píng)估函數(shù)如式（3）：

其中，n2為反向搜索中的當(dāng)前點(diǎn)；f2(n2)為反向搜索的評(píng)估函數(shù)；h2(n2)為反向搜索中以任務(wù)起點(diǎn)s為目標(biāo)點(diǎn)的啟發(fā)式函數(shù)，采用歐式距離；h'2(n2)為反向搜索中以正向搜索當(dāng)前點(diǎn)n1為目標(biāo)點(diǎn)的啟發(fā)式函數(shù)，采用歐式距離；g2(n2)表示反向搜索歷史代價(jià)函數(shù)，其計(jì)算方式如下：

g2(n2-1) 為n2的父節(jié)點(diǎn)的歷史代價(jià)；g2'(n2)為父節(jié)點(diǎn)到n2的成本代價(jià)，采用歐式距離。

2.3.2 評(píng)估函數(shù)參數(shù)值的確定

在參數(shù)a和參數(shù)b的確定過程中，本文選擇尺寸為50×50 的柵格地圖進(jìn)行測(cè)試。每組參數(shù)測(cè)試5 次，記錄該組參數(shù)的路徑長(zhǎng)度、遍歷節(jié)點(diǎn)數(shù)量與平均路徑尋優(yōu)時(shí)間。實(shí)驗(yàn)發(fā)現(xiàn)：當(dāng)參數(shù)b超過0.5時(shí)，算法遍歷的節(jié)點(diǎn)數(shù)量與路徑尋優(yōu)時(shí)間將會(huì)明顯上升，這主要是由于歷史代價(jià)函數(shù)g1(n1)與g2(n2)的權(quán)重過高，使算法更傾向于Dijkstra算法，而啟發(fā)式信息較弱，所以路徑尋優(yōu)時(shí)間較長(zhǎng)。遍歷節(jié)點(diǎn)數(shù)量與路徑尋優(yōu)時(shí)間如圖5、圖6所示（當(dāng)參數(shù)b取值為0.1、0.2、0.3 時(shí)，遍歷點(diǎn)的數(shù)量相同，路徑尋優(yōu)時(shí)間高度相似，故在圖5、圖6 中的折線重疊，原本的7個(gè)類型在折線圖中顯示為5個(gè)）。

圖5 不同參數(shù)下遍歷點(diǎn)的數(shù)量

圖6 不同參數(shù)下的路徑尋優(yōu)時(shí)間

剔除掉初次實(shí)驗(yàn)中不好的參數(shù)組合后，為防止出現(xiàn)啟發(fā)式函數(shù)權(quán)重過高而導(dǎo)致尋找到的路徑不是最短路徑的問題，更換測(cè)試的起點(diǎn)和終點(diǎn)進(jìn)行二次測(cè)試，路徑尋優(yōu)的路徑長(zhǎng)度如圖7所示。

圖7 不同參數(shù)下的路徑長(zhǎng)度

由圖6 可知：當(dāng)參數(shù)b取0.5 且參數(shù)a在[2,7]區(qū)間內(nèi)時(shí)，可以保證找到最短路徑，在a∈[2,7]區(qū)間時(shí)的路徑尋優(yōu)時(shí)間與遍歷節(jié)點(diǎn)數(shù)量如表1所示。

表1 不同a值對(duì)應(yīng)路徑尋優(yōu)時(shí)間和遍歷節(jié)點(diǎn)數(shù)量

由表1可知：當(dāng)參數(shù)a取4時(shí)，遍歷節(jié)點(diǎn)數(shù)量為1 792，尋路時(shí)間為19.31 s，為最優(yōu)結(jié)果。經(jīng)過測(cè)試，當(dāng)參數(shù)a取4，參數(shù)b取0.5時(shí)在其他地圖中的路徑尋優(yōu)結(jié)果同樣較為優(yōu)異，故本文最終確定參數(shù)a取4，參數(shù)b取0.5。正向搜索的最終評(píng)估函數(shù)如式（5）所示，反向搜索的最終評(píng)估函數(shù)如式（6）所示：

3 仿真分析

為了驗(yàn)證本文提出的基于雙向搜索機(jī)制的改進(jìn)A*算法的求解效率和效果，現(xiàn)將其在MATLAB2018b實(shí)驗(yàn)平臺(tái)下進(jìn)行編程，在不同的柵格地圖下進(jìn)行仿真實(shí)驗(yàn)，并與傳統(tǒng)A*算法、文獻(xiàn)[12]中的改進(jìn)A*算法進(jìn)行比較。計(jì)算機(jī)配置為：Windows 10 操作系統(tǒng)，處理器為i7-8565U，主頻1.8 GHz，運(yùn)行內(nèi)存為16 GB。

本文構(gòu)建了不同尺寸的包含已知障礙物的柵格地圖。在地圖中，黑色柵格代表障礙物，白色柵格為無障礙的可行區(qū)間，藍(lán)色柵格為搜索到的可行路徑，灰色柵格為已經(jīng)參與搜索計(jì)算的柵格，綠色柵格代表任務(wù)起點(diǎn)，紅色柵格代表任務(wù)終點(diǎn)。

本文算法與傳統(tǒng)A*算法的部分仿真結(jié)果如圖8所示。

圖8 路徑規(guī)劃部分仿真結(jié)果1

由圖8可知：本文提出的改進(jìn)A*算法在不同尺寸的含已知障礙物的柵格地圖中所遍歷節(jié)點(diǎn)明顯減少，搜索效率明顯提高，可節(jié)約大量的計(jì)算資源。

對(duì)文獻(xiàn)[12]中的算法與地圖進(jìn)行編碼仿真，設(shè)置與文獻(xiàn)[12]相同的起始點(diǎn)與目標(biāo)點(diǎn)，測(cè)試結(jié)果如圖9 所示。因?yàn)閮蓷l路徑有重疊部分，為防止混淆，將兩條路徑放在兩張圖中，圖9（a）為圖10 中目標(biāo)點(diǎn)1 的情況，圖9（b）為圖10中目標(biāo)點(diǎn)2的情況。

圖9 編碼文獻(xiàn)[12]算法的仿真結(jié)果

圖10 文獻(xiàn)[12]的仿真結(jié)果

圖10為文獻(xiàn)[12]搜索到的路徑，與圖9中所搜到的路徑相似。兩個(gè)算法求解結(jié)果的主要區(qū)別為搜索目標(biāo)點(diǎn)2時(shí)的路徑繞行障礙物的方向不同，但均可搜索到最短路徑。這主要是由于文獻(xiàn)[12]中采取的節(jié)點(diǎn)擴(kuò)展方向?yàn)? 方向，而本文在編碼時(shí)采取的節(jié)點(diǎn)擴(kuò)展方向?yàn)?方向。

在不同地圖環(huán)境下對(duì)傳統(tǒng)A*算法、文獻(xiàn)[12]中的改進(jìn)A*算法、Dijkstra算法、蟻群算法、本文的改進(jìn)A*算法進(jìn)行對(duì)比。表2與表3給出了三種算法在不同柵格地圖中的搜索時(shí)間、擴(kuò)展節(jié)點(diǎn)數(shù)量和路徑長(zhǎng)度的對(duì)比；其中，搜索時(shí)間之比、擴(kuò)展節(jié)點(diǎn)之比是表中較優(yōu)異的求解結(jié)果與本文改進(jìn)A*算法的相應(yīng)求解結(jié)果的比值。

由表2和表3的計(jì)算結(jié)果可知：本文的改進(jìn)A*算法與文獻(xiàn)[12]中的改進(jìn)A*算法相較于傳統(tǒng)的Dijkstra 算法、蟻群算法和A*算法在搜索時(shí)間與擴(kuò)展節(jié)點(diǎn)上具有較大優(yōu)勢(shì)，并且隨著柵格地圖的尺寸規(guī)模增大，搜索效率的提升效果更加明顯；與文獻(xiàn)[12]中的改進(jìn)A*算法求解結(jié)果相比，本文設(shè)計(jì)的改進(jìn)A*算法在四種規(guī)模的柵格地圖中可獲得相同的路徑長(zhǎng)度，但搜索時(shí)間更短、擴(kuò)展節(jié)點(diǎn)數(shù)量更少，在效率上具有明顯優(yōu)勢(shì)。部分仿真結(jié)果如圖11所示。

圖11 路徑規(guī)劃部分仿真結(jié)果2

更換起始點(diǎn)與目標(biāo)點(diǎn)，重新通過不同算法進(jìn)行路徑規(guī)劃，表4 和表5 給出了不同算法在不同柵格地圖中的搜索時(shí)間、擴(kuò)展節(jié)點(diǎn)數(shù)量和路徑長(zhǎng)度的對(duì)比。

表2 不同算法的仿真結(jié)果對(duì)比1

表3 不同算法的仿真結(jié)果對(duì)比2

表4 不同算法的仿真結(jié)果對(duì)比3

表5 不同算法的仿真結(jié)果對(duì)比4

由表4 可以看出在100×100 柵格地圖下，文獻(xiàn)[12]中的改進(jìn)A*算法與本文的改進(jìn)A*算法的搜索時(shí)間與擴(kuò)展節(jié)點(diǎn)數(shù)量相當(dāng)，這主要是因?yàn)樵诠?jié)點(diǎn)搜索的過程中沒有接觸到障礙物，形成了簡(jiǎn)易的直達(dá)路徑。在30×30與50×50柵格地圖下，本文的改進(jìn)A*算法在搜索時(shí)間與擴(kuò)展節(jié)點(diǎn)數(shù)量上具有一定的優(yōu)勢(shì)，搜索效率較高，且在30×30 柵格地圖下本文的改進(jìn)A*算法搜索的路徑長(zhǎng)度相較于文獻(xiàn)[12]中的改進(jìn)A*算法具有一定優(yōu)勢(shì)。在75×75 柵格地圖下，雖然本文的改進(jìn)A*算法相較于文獻(xiàn)[12]中的改進(jìn)A*算法的搜索時(shí)間與擴(kuò)展節(jié)點(diǎn)數(shù)量存在一定劣勢(shì)，但可求得最短路徑，這主要是因?yàn)楸疚闹械母倪M(jìn)A*算法的啟發(fā)式信息弱于文獻(xiàn)[12]中的改進(jìn)A*算法，導(dǎo)致尋路時(shí)間較長(zhǎng)，但保證了最短路徑。部分仿真結(jié)果如圖12所示。

圖12 路徑規(guī)劃部分仿真結(jié)果3

4 結(jié)束語

由于傳統(tǒng)A*算法在路徑規(guī)劃過程中所遍歷的點(diǎn)過多，在其搜索過程中存在計(jì)算量龐大、內(nèi)存占用嚴(yán)重等缺點(diǎn)，無法滿足AGV 小車在規(guī)模較大的倉儲(chǔ)系統(tǒng)內(nèi)路徑規(guī)劃的實(shí)時(shí)性要求。為了提高路徑規(guī)劃的效率，本文提出了一種雙向搜索機(jī)制的改進(jìn)A*算法。經(jīng)過在Matlab平臺(tái)中的不同尺寸柵格地圖進(jìn)行仿真實(shí)驗(yàn)，并與傳統(tǒng)A*算法和文獻(xiàn)[12]中的改進(jìn)A*算法進(jìn)行對(duì)比，證明了本文提出的改進(jìn)A*算法可生成最短路徑的同時(shí)可以明顯提升尋路速度，尤其是在規(guī)模較大的場(chǎng)景下效果更加明顯。

雖然本文所提出的改進(jìn)A*算法相較于傳統(tǒng)A*算法與文獻(xiàn)[12]中的改進(jìn)A*算法在效率上有了較大提升，但并未考慮場(chǎng)景的動(dòng)態(tài)變化和由于AGV發(fā)生轉(zhuǎn)向所花費(fèi)的時(shí)間成本、電量成本等。在未來的研究中可將這些因素作為改進(jìn)算法的依據(jù)，提高AGV 路徑規(guī)劃的應(yīng)用價(jià)值。