薄 勝,李 媛,趙靜怡

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

0 引言

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

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

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

1 相關(guān)研究概述

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

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

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

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

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

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

2.1 二維地圖建模

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

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

表1 柵格類(lèi)型對(duì)應(yīng)含義

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

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

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

2.2 參數(shù)定義

算法參數(shù)定義與說(shuō)明見(jiàn)表2。

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

對(duì)路徑規(guī)劃算法進(jìn)行數(shù)學(xué)建模,首先需要將實(shí)時(shí)地圖信息轉(zhuǎn)化為存儲(chǔ)必要信息的二維矩陣,此處可以調(diào)用柵格化算法對(duì)外開(kāi)放的統(tǒng)一函數(shù)Map2Matrix,如公式(1):

Dm=Map2Matrix(map)

(1)

式中:map為存儲(chǔ)地圖信息的地圖文件,Dm為轉(zhuǎn)換后的w*h矩陣,Dm的元素即對(duì)應(yīng)節(jié)點(diǎn)的地圖信息。

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

(2)

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

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

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

(3)

(4)

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

2.4 改進(jìn)的D*算法

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

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

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

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

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

(5)

2.4.2 引入拐點(diǎn)懲罰因子

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

(6)

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

(7)

圖3 20%障礙物覆蓋密度對(duì)比仿真結(jié)果

圖4 25%障礙物覆蓋密度對(duì)比仿真結(jié)果

2.5 改進(jìn)的D*算法仿真與分析

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

圖5 30%障礙物覆蓋密度對(duì)比仿真結(jié)果

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

表3 仿真路徑的平均拐點(diǎn)數(shù)量指標(biāo)

3 結(jié)論

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