孔繼利，張鵬坤，劉曉平

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

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

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

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

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

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

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

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

圖1 柵格地圖

根據(jù)應用場景的實際需求，本文在AGV 運行過程中做出如下假設：

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

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

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

圖3 AGV可能的運行方向

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

2 基于雙向搜索機制的改進A＊算法設計

2.1 改進A＊算法的描述

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

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

2.2 改進A＊算法的處理流程

當改進A*算法開始運行，首先需要初始化OPEN1列表、CLOSE1列表和OPEN2列表、CLOSE2列表。搜索過程中正向搜索與反向搜索交替進行。

改進A*算法處理流程如下：

（1）將起始點s設置為正向當前節(jié)點n1，并加入OPEN1列表。

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

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

（4）將目標點e設置為反向當前節(jié)點n2，并加入OPEN2列表。

（5）搜索n2點周圍可到達的節(jié)點，把它們加入OPEN2列表。將目標點e設置為新加入節(jié)點的父節(jié)點。

（6）將目標點e從OPEN2列表中刪除，加入CLOSE2列表中。

（7）重復如下步驟：

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

②將n1點從OPEN1列表中刪除，加入CLOSE1列表中。

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

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

⑤將n2點從OPEN2列表中刪除，加入CLOSE2列表中。

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

（8）終止條件為：

①當OPEN1列表中包含CLOSE2列表中的點或OPEN2列表中包含CLOSE1列表中的點，此時路徑已找到。

②當OPEN1列表或OPEN2列表任何一個為空時，此時尋路失敗，輸出尋路失敗提示。

改進A*算法的具體流程圖如圖4所示。

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

圖4 改進A*算法具體流程圖

改進A*算法的偽代碼如下：

insert start node in OPEN1

insert target node in OPEN2

//將兩個OPEN列表進行初始化操作。

While OPEN1≠null & OPEN2≠null

computen1child nodex

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

ifxis in the CLOSE2

break

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

endif

find minf1(x) in OPEN1

n1=x

insertn1in CLOSE1

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

computen2child nodey

update OPEN2

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

ifyis in the CLOSE1

break

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

endif

find minf2(y) in OPEN2

n2=y

insertn2in CLOSE2

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

Get path/Fail to get path

2.3 改進A＊算法的評估函數(shù)

2.3.1 評估函數(shù)的設計

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

（1）正向搜索

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

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

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

（2）反向搜索

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

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

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

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

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

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

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

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

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

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

表1 不同a值對應路徑尋優(yōu)時間和遍歷節(jié)點數(shù)量

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

3 仿真分析

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

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

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

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

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

對文獻[12]中的算法與地圖進行編碼仿真，設置與文獻[12]相同的起始點與目標點，測試結果如圖9 所示。因為兩條路徑有重疊部分，為防止混淆，將兩條路徑放在兩張圖中，圖9（a）為圖10 中目標點1 的情況，圖9（b）為圖10中目標點2的情況。

圖9 編碼文獻[12]算法的仿真結果

圖10 文獻[12]的仿真結果

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

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

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

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

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

表2 不同算法的仿真結果對比1

表3 不同算法的仿真結果對比2

表4 不同算法的仿真結果對比3

表5 不同算法的仿真結果對比4

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

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

4 結束語

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

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