鋼鐵物流中基于D*的路線規(guī)劃算法

薄 勝,李 媛,趙靜怡

(1.北京樂智科技有限公司,北京 100089;2.中國電信集團有限公司河北雄安新區(qū)分公司,河北 雄安 070001; 3.北京郵電大學,北京 100876)

0 引言

路徑是連接起點位置和終點位置的序列點或曲線,用于生成路徑的策略被稱為路徑規(guī)劃算法[1]。路徑規(guī)劃是指在具有障礙物的環(huán)境中,按照一定的評判標準,尋找一條從起始狀態(tài)到目標狀態(tài)的無碰撞路徑。路徑規(guī)劃算法具有廣泛的應用領域,如城市道路網(wǎng)規(guī)劃導航、GPS[2]導航以及基于地理信息系統(tǒng)(GIS)[3]的道路規(guī)劃等。

對于機器人、飛行器等有關路徑尋徑和路徑規(guī)劃的研究,通常需要進行環(huán)境模擬、路徑探索[4]、路徑平滑[5]等常見工作步驟。而在鋼鐵物流場景車輛的路徑規(guī)劃研究中,路徑規(guī)劃算法的性能直接影響物流配送的效率和安全性。因此,路徑規(guī)劃算法需要滿足高效和安全性強等要求。

為實現(xiàn)高效率的路徑搜索,本文基于鋼鐵物流場景的路徑規(guī)劃需求和D*算法的反向搜索、動態(tài)搜索特點,提出了一種面向鋼鐵物流場景D*的路徑規(guī)劃算法,此算法對傳統(tǒng)D*算法作出了相應改進,以避免傳統(tǒng)D*算法為保證路徑規(guī)劃效率而規(guī)劃出的不安全路徑,從而導致配送效率和安全系數(shù)較低的問題。通過引入全新的路徑規(guī)劃算法可以極大的提高物流配送效率,加速整體物流自動化進度,提高物流工業(yè)化安全系數(shù),保障物流配送流程的高效正常運作。

1 相關研究概述

路徑規(guī)劃算法不論是在物流配送,還是日常導航中都起著至關重要的作用。為此,眾多學者對路徑規(guī)劃算法和在不同場景下的應用進行了研究。

路徑規(guī)劃算法是指在給定的地圖和起點終點位置下,通過計算和優(yōu)化算法,找出一條最優(yōu)路徑的算法。1956年,荷蘭科學家Dijkstra提出了Dijkstra算法[6],這是一種基于貪心策略的單源最短路徑算法,其關鍵特點是以起始點為中心向外擴展尋找,直到尋找到目標點[7]。在擴展的過程中,算法會優(yōu)選選取距離起點最近的未訪問結點,并利用該節(jié)點來計算至其余節(jié)點的距離數(shù)值。這種算法可以保證找到圖中的最優(yōu)路徑。但是,隨著擴展的結點增加,算法的效率也會相應降低。1962年,Floyd提出了一種基于動態(tài)規(guī)劃的單源最短路徑算法[8]。隨后,Hart等人提出了A*算法[9],這是一種智能搜索算法,是一種結合了Dijkstra算法和廣度優(yōu)先搜索算法的啟發(fā)式搜索算法,可以快速找到最優(yōu)路徑,是求解靜態(tài)路網(wǎng)中最短路徑時最高效的直接搜索算法。該算法利用啟發(fā)式函數(shù)計算節(jié)點的綜合優(yōu)先級f(n),其中包括從起始點到該節(jié)點的代價值g(n),從該節(jié)點到目標點的估計代價值h(n)。當代價值接近于0,A*算法就相當于Dijkstra算法,能夠保證找到最短路徑,但是速度難以符合預期;當估計代價值接近于0,A*算法就相當于廣度優(yōu)先搜索算法,速度較快但不能完全保證找到路徑的概率。通過調校估計代價值的大小,以平衡算法的精度和速度。A*算法適用于搜索范圍較小的場景,不適用于動態(tài)環(huán)境,且當目標點不可達時會造成難以預估的性能消耗。在之后的不斷發(fā)展中,陸續(xù)有學者提出了分支界限算法、遺傳算法和模擬退火算法等路徑規(guī)劃算法。A.Wang等人[10]提出了一種改進q學習算法的跨區(qū)域定制線路規(guī)劃算法,使得改進的灰狼優(yōu)化算法能有效提高路徑規(guī)劃算法的精度和收斂速度。

D*算法旨在解決A*算法遇到環(huán)境變化時需重新進行路徑規(guī)劃,有可能降低算法計算效率的不良影響,其會存儲場景中每個起終點的最短路徑信息,可有效加強重規(guī)劃能力。與正向搜索的A*算法不同,D*算法采用反向搜索,即從目標點開始搜索。它在首次遍歷時與Dijkstra算法類似,會保存各節(jié)點數(shù)據(jù)。這種算法更適合動態(tài)環(huán)境的路徑規(guī)劃,提供了更高的搜索效率。

本文提出的基于改進的D*的路徑規(guī)劃算法,對鋼鐵物流領域的路徑規(guī)劃需求作出了詳盡的分析。不僅規(guī)避了車輛與障礙物的碰撞或摩擦問題,也盡可能的減少了車輛拐動幅度和頻率,最大程度的提高了大型裝卸車在園區(qū)內部運輸?shù)陌踩浴Ｔ撍惴梢越管囕v從兩個障礙物間狹縫穿過,同時也引入拐點懲罰因子以避免規(guī)劃出與理想路徑偏差較大的路徑,盡可能避免拐動行為。

2 基于D*的路徑規(guī)劃算法

在鋼鐵物流場景中,配送鋼材的車輛主要為大型裝卸車。傳統(tǒng)D*算法由于選取子節(jié)點的不合理,導致規(guī)劃的路徑可能會引導車輛從兩障礙物間狹小的縫隙穿過,考慮到參與鋼鐵物流的車輛規(guī)格,此算法設計會影響規(guī)劃路徑的安全性;傳統(tǒng)D*算法可能會忽略了動態(tài)障礙物而導致最終規(guī)劃路徑出現(xiàn)非必要轉彎的情況,由于大型車輛的拐彎速度相對較慢,多拐點的最終路徑會降低整體的物流運輸效率。

2.1 二維地圖建模

二維地圖建模技術是為車輛導航提供精準的地理信息支持,主要是通過地圖和路況等信息,構建二維地圖模型。可為車輛導航提供更加準確和實時的地理位置信息,實現(xiàn)精確的路徑規(guī)劃和導航。本文將基于鋼鐵物流企業(yè)所提供的園區(qū)地圖,使用柵格法為園區(qū)地圖進行二維建模。

常見的對工作環(huán)境進行二維地圖建模的技術方法為柵格法[14],此方法通過將環(huán)境中的各種障礙物和信息劃分成小方格的集合,實現(xiàn)對場景中所有事物進行權值替代和描述。該方法能夠有效地表達空間的可變性,為路徑規(guī)劃算法提供重要前提條件。采用單元間計算路線的方法,能夠顯著降低連續(xù)環(huán)境空間尋徑計算的負擔,同時保證計算結果的精度。柵格法將園區(qū)地圖離散化為柵格點,使得車輛路徑規(guī)劃問題被轉化為了單元間計算路線的問題求解。柵格類型的對應含義見表1。

表1 柵格類型對應含義

在柵格法對地圖建模后,原始地圖信息將被映射到一個對應的二維矩陣,矩陣的元素為0或1。0代表自由區(qū)域,1代表障礙物區(qū)域。柵格法模擬后的結果示例如圖1所示[1]。

圖1 環(huán)境柵格化示意圖

最后為驗證算法的性能,本文在仿真階段將使用隨機生成障礙物的方式驗證算法可用性和普適性。

2.2 參數(shù)定義

算法參數(shù)定義與說明見表2。

2.3 傳統(tǒng)D*算法

對路徑規(guī)劃算法進行數(shù)學建模,首先需要將實時地圖信息轉化為存儲必要信息的二維矩陣,此處可以調用柵格化算法對外開放的統(tǒng)一函數(shù)Map2Matrix,如公式(1):

Dm=Map2Matrix(map)

(1)

式中:map為存儲地圖信息的地圖文件,Dm為轉換后的w*h矩陣,Dm的元素即對應節(jié)點的地圖信息。

D*算法以節(jié)點間的歐式距離作為計算節(jié)點間損失的依據(jù),任意兩節(jié)點的歐式距離計算如公式(2):

(2)

式中:XN為N節(jié)點在矩陣中的一維索引,YN為N節(jié)點在矩陣中的二維索引。

表2 算法參數(shù)定義與說明

為規(guī)劃全局最優(yōu)路徑,D*算法需要計算并更新每個節(jié)點到達目標點的全局損失,每次計算先更新節(jié)點的h損失,再更新節(jié)點的k損失。損失計算如公式(3)和公式(4):

(3)

(4)

為了規(guī)劃從起點到終點的最優(yōu)路徑,D*算法進行反向搜索,每次從待搜索節(jié)點集合Oopen中選擇全局損失k最小的節(jié)點作為當前節(jié)點C,之后遍歷當前節(jié)點C的候選子節(jié)點集合Ccan,計算并更新每個候選子節(jié)點Ccan的k損失和h損失,計算完成后將候選子節(jié)點放入待搜索集合Oopen中,并將當前節(jié)點放入已搜索集合Cclose中,這樣就完成了一次完整的損失計算過程。重復該過程直到已搜索集合出現(xiàn)起點或待搜索集合為空,此時已搜索集合即為最優(yōu)路徑的節(jié)點集合。

2.4 改進的D*算法

本文改進的D*算法優(yōu)化如下:首先,為提高運輸過程中的安全系數(shù),本算法禁止車輛斜穿兩個障礙物間的狹縫,提出了一種局部規(guī)劃算法對候選子節(jié)點進行約束,避免規(guī)劃路徑斜穿障礙物可能造成的車輛碰撞危險。其次,本算法引入拐點懲罰因子以減小路徑拐動頻率,通過懲罰拐彎幅度與理想路徑偏差較大的路徑,盡可能避免車輛出現(xiàn)不必要的拐動行為。

2.4.1 局部候選子節(jié)點約束

D*算法以當前節(jié)點的8個方向節(jié)點作為候選子節(jié)點,如圖2(a)所示。由于傳統(tǒng)D*算法以歐式距離為參考計算每個節(jié)點的損失,計算過程中算法到達局部最優(yōu),得到的路徑可能會穿過兩障礙物間的狹小空隙,如圖2(b)當前節(jié)點到候選子節(jié)點3所示。為提高最終路徑的安全性,本算法對局部候選子節(jié)點進行規(guī)則約束,從而禁止規(guī)劃路徑橫穿兩障礙物,如圖2(c)所示。

圖2 局部候選子節(jié)點約束

柵格法輸出的矩陣Dm元素數(shù)值為0或1,這樣的設計結合局部候選子節(jié)點約束,節(jié)點的候選優(yōu)先級計算公式如下:

(5)

2.4.2 引入拐點懲罰因子

由于傳統(tǒng)D*算法沒有考慮出現(xiàn)動態(tài)障礙物后重新規(guī)劃的路徑容易出現(xiàn)不必要的拐點,導致在動態(tài)環(huán)境下,傳統(tǒng)D*算法規(guī)劃的路徑并不平滑。針對這個問題本算法引入了拐點懲罰因子,通過懲罰偏離理想路徑的候選路徑,使得選擇的最優(yōu)路徑拐點更少。拐點懲罰因子的定義如公式(6):

(6)

其中θ為待選路徑與理想行駛路徑間的夾角,μ為環(huán)境因子,取值與環(huán)境中障礙物的占比有關。由于θ的實際范圍為(-180°,180°),顯然當90°≤|θ|≤180°時,此時路徑方向為前進方向;而當0°≤|θ|≤60°時,此時路徑方向為回退方向。當出現(xiàn)回退現(xiàn)象時,算法會增大拐角懲罰因子值,并在原基礎上加倍懲罰,以降低路線回退的可能性。引入拐點懲罰因子后,對節(jié)點h損失的計算即對公式(3)更新得到公式(7):

(7)

圖3 20%障礙物覆蓋密度對比仿真結果

圖4 25%障礙物覆蓋密度對比仿真結果

2.5 改進的D*算法仿真與分析

為了對改進的算法性能進行驗證,對傳統(tǒng)D*算法和改進的D*算法對比仿真,使用Python在Visual Studio Code平臺進行編譯執(zhí)行。為保證實驗的普適性,避免柵格地圖中的特定環(huán)境因子給算法帶來偏差,采用不同數(shù)據(jù)在同一主機中進行仿真,隨機生成障礙物后以相同的障礙物覆蓋率執(zhí)行仿真。最終得到的本算法多次仿真結果如圖3—圖5所示,其中圖中(a)、(b)分別為傳統(tǒng)D*算法和改進的D*算法的路徑規(guī)劃結果。根據(jù)仿真結果可知,對于不同障礙物覆蓋密度,改進后的D*算法不會穿過障礙物間隙,保障了車輛的行駛安全。

圖5 30%障礙物覆蓋密度對比仿真結果

為驗證本文算法的改進目標完成度,進行了數(shù)十次實驗以對比不同障礙物覆蓋率和分布的情況,并記錄了本實驗路徑的平均拐點數(shù)量指標,結果見表3。從表3可知,在不同障礙物比率下,改進的D*算法規(guī)劃出的路徑明顯降低了拐點數(shù)量。

表3 仿真路徑的平均拐點數(shù)量指標

3 結論

本文提出了一種面向鋼鐵物流場景改進的基于D*的路徑規(guī)劃算法。該算法可根據(jù)園區(qū)實際配送需求,標準化拐角懲罰因子系數(shù);可細化原始的子節(jié)點選取角度,以避免不同角度的障礙物摩擦;可與鋼鐵物流實際業(yè)務流程結合,根據(jù)物流裝卸貨階段進行具體分階段導航。該算法有效地避免了鋼鐵物流中大型裝卸車輛從障礙物間縫隙穿過的危險性,也降低了車輛拐彎次數(shù),增加了車輛工作在園區(qū)配送中的安全性。