發(fā)布時(shí)間:2022-12-30 瀏覽量:
跨層作業(yè)逐漸成為倉(cāng)儲(chǔ)物流提高效率的趨勢(shì)之一。ADAPTO是范德蘭德公司為了減輕企業(yè)倉(cāng)儲(chǔ)配送壓力而專(zhuān)門(mén)設(shè)計(jì)的一款創(chuàng)新的3D穿梭小車(chē)。ADAPTO逐漸弱化了倉(cāng)儲(chǔ)系統(tǒng)層與層、巷道與巷道之間的隔離, 同一個(gè)3D穿梭車(chē)可以自由的穿梭于貨架任意位置, 不局限于巷道與層之間。同樣, 瑞士的建筑五金供應(yīng)商SFS采用的跨層穿梭車(chē)系統(tǒng), 立庫(kù)有17層, 這17層僅配備了3臺(tái)穿梭車(chē), 共5個(gè)巷道, 整個(gè)立庫(kù)僅用15臺(tái)穿梭車(chē), 系統(tǒng)設(shè)計(jì)不僅降低成本, 作業(yè)效率也非常高[1]??鐚幼鳂I(yè)極大地增加了揀選作業(yè)的靈活性。
具有3維空間運(yùn)動(dòng)能力的典型移動(dòng)機(jī)器人, 現(xiàn)在研究較多的是各類(lèi)空間和水下機(jī)器人。其中, 智能程度較高的包括MAV、UAV、UUV、AUV等[2]。智能倉(cāng)儲(chǔ)物流領(lǐng)域使用揀選機(jī)器人十分廣泛, 但大部分路徑規(guī)劃研究局限于二維路徑規(guī)劃, 類(lèi)似跨層作業(yè)此類(lèi)約束較少甚至無(wú)約束的通用倉(cāng)儲(chǔ)模型三維路徑規(guī)劃少有研究涉及, 本文提出一種通用的倉(cāng)庫(kù)揀選三維路徑規(guī)劃模型, 并設(shè)計(jì)了與之匹配的尋優(yōu)算法。
通用立體倉(cāng)庫(kù)模型中的揀選小車(chē)路徑規(guī)劃問(wèn)題是一個(gè)三維路徑規(guī)劃, 目前研究較多的是無(wú)人機(jī) (UAV) 的三維路徑規(guī)劃, 倉(cāng)儲(chǔ)環(huán)境下的全地圖三維路徑規(guī)劃研究并不多見(jiàn)。無(wú)人機(jī)三維路徑規(guī)劃的環(huán)境威脅包括地圖環(huán)境威脅、雷達(dá)偵查威脅、敵軍導(dǎo)彈輻射范圍威脅等。倉(cāng)儲(chǔ)揀選設(shè)備的路徑規(guī)劃與之對(duì)比, 顯然倉(cāng)庫(kù)里的揀選車(chē)輛路徑比較規(guī)則, 通常只有水平、豎直直線(xiàn)運(yùn)動(dòng), 相比于無(wú)人機(jī)的飛行軌跡較為簡(jiǎn)單, 一個(gè)無(wú)人機(jī)的路徑選擇在柵格空間中可以有26個(gè)方向[3] (如圖1所示) 。一個(gè)倉(cāng)儲(chǔ)機(jī)器人的路徑選擇在空間中通常只有6個(gè)方向, 如圖2所示。
圖1 無(wú)人機(jī) (UAV) 運(yùn)動(dòng)方向 下載原圖
圖2 倉(cāng)儲(chǔ)機(jī)器人運(yùn)動(dòng)方向 下載原圖
倉(cāng)庫(kù)揀選設(shè)備 (提升機(jī)、堆垛機(jī)、穿梭車(chē)等) 的運(yùn)動(dòng)僅為前、后、左、右、上、下6個(gè)方向。分別對(duì)應(yīng)矩陣:
故將連續(xù)空間變換為柵格空間系統(tǒng)模型, 更符合立體倉(cāng)庫(kù)揀選設(shè)備運(yùn)動(dòng)的客觀規(guī)律, 同時(shí)便于算法搜索。且實(shí)際求解過(guò)程中倉(cāng)庫(kù)尺寸、規(guī)模已知, 因此可以視為全局路徑規(guī)劃問(wèn)題。將倉(cāng)庫(kù)根據(jù)每個(gè)貨位的尺寸按小方塊進(jìn)行劃分, 每個(gè)小立方體代表一個(gè)貨位。
A*算法是一種常見(jiàn)的路徑搜索算法, A*算法的估價(jià)函數(shù)可以表示為:
其中g(shù) (n) 表示從起始節(jié)點(diǎn)Start到節(jié)點(diǎn)n的真實(shí)耗費(fèi)值, h (n) 表示從節(jié)點(diǎn)n到終止點(diǎn)Goal的啟發(fā)估計(jì)耗費(fèi)值。f (n) 表示從起始點(diǎn)開(kāi)始, 經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)的啟發(fā)估計(jì)耗費(fèi)值。h* (n) 是指經(jīng)過(guò)節(jié)點(diǎn)n, 到達(dá)終止目標(biāo)點(diǎn)的實(shí)際最優(yōu)消耗值。其基本思路與經(jīng)典的路徑搜索算法Dijkstra相似, 但在Dijkstra算法的基礎(chǔ)上加上啟發(fā)代價(jià), 路徑代價(jià)通常由距離決定, 距離通常有三種方式計(jì)算:
1) 曼哈頓距離
曼哈頓距離即坐標(biāo)系中兩點(diǎn)的絕對(duì)軸距之和。其表達(dá)式如式 (3) 所示, 效果如圖3所示。
2) 切比雪夫距離
切比雪夫距離被稱(chēng)為棋盤(pán)距離。其表達(dá)式如式 (4) 所示, 效果如圖4所示。
圖3 曼哈頓距離的A*搜索過(guò)程 下載原圖
圖4 切比雪夫距離的A*搜索過(guò)程 下載原圖
3) 歐幾里得距離
歐幾里得距離是衡量?jī)牲c(diǎn)之間距離遠(yuǎn)近的最常用的方法之一, 其值直接可以看作兩個(gè)位置點(diǎn)在歐式空間中的兩點(diǎn)的直線(xiàn)距離, 其表達(dá)式如式 (5) 所示, 效果如圖5所示。
圖5 歐幾里得距離的A*搜索過(guò)程 下載原圖
由于倉(cāng)儲(chǔ)環(huán)境中, 只存在直線(xiàn)運(yùn)動(dòng)且為前、后、左、右、上、下6個(gè)方向, 因此算法的距離選擇應(yīng)以曼哈頓距離為基礎(chǔ), 在此距離公式基礎(chǔ)上增加豎直方向坐標(biāo)差的絕對(duì)值, 距離公式為:
線(xiàn)性函數(shù)歸一化 (Min-Max Scaling) , 也稱(chēng)為離差標(biāo)準(zhǔn)化, 是對(duì)原始數(shù)據(jù)的線(xiàn)性變換, 使結(jié)果值映射到[0-1]之間。轉(zhuǎn)換函數(shù)如下:
其中max為樣本數(shù)據(jù)的最大值, min為樣本數(shù)據(jù)的最小值。本文A*算法的歷史路徑函數(shù)里還包括地圖環(huán)境代價(jià), 環(huán)境代價(jià)的取值為0或1, 在計(jì)算代價(jià)函數(shù)時(shí), 為避免“大數(shù)吃小數(shù)”的現(xiàn)象, 需要對(duì)數(shù)據(jù)進(jìn)行歸一化處理, 本文涉及的標(biāo)準(zhǔn)化參數(shù)有單位距離設(shè)備的能耗和單位距離設(shè)備的揀選時(shí)間兩個(gè)指標(biāo), 其中單位距離設(shè)備的揀選時(shí)間與設(shè)備運(yùn)行速度有關(guān)。
統(tǒng)計(jì)出倉(cāng)儲(chǔ)系統(tǒng)內(nèi)不同執(zhí)行設(shè)備的單位距離能耗和速度, 找出能耗最大值和速度最大值, 根據(jù)以上離散標(biāo)準(zhǔn)化公式將單位能耗和速度歸一化處理, 使之映射到[0-1]之間, 由于系統(tǒng)考量的兩個(gè)指標(biāo)是單位能耗與揀選時(shí)間, 時(shí)間與速度成反比, 因此在速度值的歸一化處理之后可作加一處理, 避免揀選時(shí)間數(shù)值無(wú)窮大, 使單位距離下的設(shè)備運(yùn)行時(shí)間也在[0-1]之間。
假設(shè)縱向移動(dòng)由提升機(jī)執(zhí)行, 其速度為vx、單位能耗 (功率) 為Ex, 水平移動(dòng)由穿梭車(chē)執(zhí)行, 其速度為vy、單位能耗 (功率) 為Ey。則有:
歸一化處理, 將Ex1代入式 (7) :
其余方向能耗和速度數(shù)據(jù)的歸一化過(guò)程同上。
1) 路徑規(guī)劃需要考慮的指標(biāo):
(1) 行走時(shí)間最短:機(jī)器人行走時(shí)間按最低的選取; (2) 能量消耗最小:機(jī)器人所走過(guò)的路徑能量消耗按最低的選取。
2) 環(huán)境模型的建立:
環(huán)境建模的目的是能夠?yàn)槁窂揭?guī)劃提供可用的分析平臺(tái), 常用的分析建模方法有拓?fù)浣7ê蛶缀谓7?span style="padding: 0px; margin: 0px; position: relative; font-size: 12px; line-height: 0; vertical-align: baseline; top: -0.5em;">[4,5], 在本文中選用柵格法對(duì)環(huán)境進(jìn)行建模, 柵格法環(huán)境建模是將倉(cāng)儲(chǔ)環(huán)境分解成一系列尺寸相同的網(wǎng)格單元, 將環(huán)境信息或障礙物信息分布在l×m×n的環(huán)境柵格矩陣中, 由于每個(gè)柵格的像元值都是唯一的、確定的, 所以每個(gè)柵格的標(biāo)識(shí)也是唯一的、確定的[6]。建立環(huán)境模型時(shí)既要滿(mǎn)足算法規(guī)劃的準(zhǔn)確性也要滿(mǎn)足實(shí)時(shí)性, 作以下假設(shè):
(1) 假設(shè)搬運(yùn)設(shè)備 (平移、提升) 無(wú)法穿越已存貨位。
(2) 假設(shè)倉(cāng)庫(kù)內(nèi)的貨物實(shí)時(shí)位置已知。
(3) 假設(shè)設(shè)備性能, 包括能耗、速度均已知。
(4) 假設(shè)將環(huán)境邊界當(dāng)作障礙物處理, 設(shè)備不能越過(guò)邊界行走。
假設(shè)自動(dòng)化立體倉(cāng)庫(kù)中每一個(gè)貨架長(zhǎng)寬高尺寸分別為a, b, c, 由l排m列n層的貨架組成, 則整個(gè)倉(cāng)庫(kù)有l(wèi)×m×n個(gè)貨格, 整個(gè)倉(cāng)庫(kù)貨架區(qū)長(zhǎng)a×l, 寬b×m, 高c×n。地圖環(huán)境代價(jià)值的設(shè)置則根據(jù)倉(cāng)庫(kù)中已被占據(jù)的貨格決定, 若此貨格已被占用, 則無(wú)法存放或穿越, 即此點(diǎn)為障礙點(diǎn), 在matlab中可建立l×m×n的三維數(shù)組, 其中已被占據(jù)的貨格相應(yīng)位置則置INF, 表示障礙, 未被占據(jù)的貨格相應(yīng)位置置0, 表示可存儲(chǔ)或可通行。
圖6 倉(cāng)庫(kù)柵格模型示意 下載原圖
圖6說(shuō)明了一個(gè)4×4×4的倉(cāng)庫(kù)模型, 以圖中填黑區(qū)域?yàn)槔? 簡(jiǎn)單說(shuō)明本文的建模策略, 則該區(qū)域的障礙障礙信息矩陣為一個(gè)l=m=n=4的三維矩陣:
其中每層INF值所在位置即障礙點(diǎn), S點(diǎn)代表出發(fā)點(diǎn)Startpoint, G點(diǎn)則代表終點(diǎn)Goalpoint。
距離函數(shù)的選取, 由式 (6) 可知是根據(jù)曼哈頓距離擴(kuò)展Z方向而來(lái)的, 由于啟發(fā)函數(shù)中只計(jì)算距離函數(shù), 但實(shí)際行走需要考慮揀選時(shí)間、設(shè)備能耗, 且實(shí)際行走過(guò)程中揀選設(shè)備水平方向和豎直方向的運(yùn)行速度和能耗并不完全一樣。因此啟發(fā)函的距離計(jì)算中在豎直方向引入因子γ, 以調(diào)節(jié)豎直方向與水平方向的差異。
DMS表示M和Startpoint點(diǎn)之間的的距離;
表示點(diǎn)s與下一點(diǎn)m水平方
向之間的距離;
表示點(diǎn)s與下一點(diǎn)m豎直方向之間
的距離;
歷史路徑代價(jià)函數(shù)可以如下分段表達(dá):
K (M') 表示地圖環(huán)境代價(jià);
α、β分別表示設(shè)備能耗與運(yùn)行時(shí)間在啟發(fā)函數(shù)中的占比且:
ξ表示啟發(fā)代價(jià)調(diào)節(jié)參數(shù) (為了保證路徑搜索方向始終走向目標(biāo)點(diǎn), 僅避開(kāi)障礙且不受歷史路徑代價(jià)函數(shù)的影響, ξ可適當(dāng)調(diào)節(jié), 使得每次路徑搜索都盡量靠近目標(biāo)點(diǎn)) , ξ值的選取控制在時(shí)間和能耗參數(shù)同一量級(jí), 并略大于αE及βv;
DMG表示點(diǎn)M和路徑終點(diǎn)G之間的距離。
若γ>>11, 表示豎直方向單位能耗是水平方向單位能耗的γ倍>1。則f (M) 為如下分段函數(shù) (水平、豎直) :
目標(biāo)函數(shù):
在三維空間中求解移動(dòng)機(jī)器人最優(yōu)路徑的方法有很多, 如A*算法、D*算法、進(jìn)化算法等[7], 在眾多求解最優(yōu)路徑的方法中, A*算法簡(jiǎn)單、有效, 并且得到了廣泛的應(yīng)用, 本文采用的A*算法進(jìn)行倉(cāng)儲(chǔ)設(shè)備的路徑規(guī)劃, 其算法基本步驟描述:
Step 1:通過(guò)Initialize Field函數(shù)初始化參數(shù), 初始化地圖環(huán)境;將初始節(jié)點(diǎn)存入Set Open數(shù)組中。
S t e p 2:擴(kuò)展當(dāng)前的節(jié)點(diǎn), 即找到以當(dāng)前節(jié)點(diǎn)為中心, 其前、后、左、右、上、下6個(gè)方向鄰域內(nèi)的可通行節(jié)點(diǎn), 將不存在于Set Open數(shù)組和Set Closed數(shù)組中的節(jié)點(diǎn)計(jì)算其啟發(fā)代價(jià)即h (n) , 并將其存入Set Open Heuristics數(shù)組中相對(duì)應(yīng)的位置, 并計(jì)算該節(jié)點(diǎn)的路徑耗費(fèi)即g (n) , 并將其設(shè)定為當(dāng)前節(jié)點(diǎn);在Set Open數(shù)組中刪去當(dāng)前節(jié)點(diǎn), 并將其存入Set Closed表中。
Step3:將擴(kuò)展得到的節(jié)點(diǎn)依次加入Set Open數(shù)組中, 若此節(jié)點(diǎn)不存在Set Open數(shù)組中, 那么就將其加入到Set Open數(shù)組中, 并將計(jì)算得到的路徑耗費(fèi)g (n) 加入到Set Open Cost數(shù)組中相應(yīng)的位置, 并記錄這點(diǎn)的來(lái)源方向到Field Pointers數(shù)組中, 若此節(jié)點(diǎn)己經(jīng)存在于Set Open數(shù)組中, 比較此點(diǎn)記錄在Set Open Cost數(shù)組的路徑消耗與新計(jì)算得到的路徑消耗, 若記錄的路徑消耗小于新計(jì)算得到的路徑消耗, 則對(duì)此點(diǎn)不做任何改變, 反之, 用新的路徑消耗代替此點(diǎn)在Set Open Cost數(shù)組中相對(duì)應(yīng)的路徑消耗, 并更新此點(diǎn)的來(lái)源方向到Field Pointers數(shù)組。
Step4:Set Open Heuristics數(shù)組中和Set Open Cost數(shù)組中相對(duì)應(yīng)位置的值相加, 選取其和最小的節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn), 并將其置入Set Closed數(shù)組中, 將其耗費(fèi)置入Set Closed Cost數(shù)組中, 然后跳轉(zhuǎn)Step2。
Step5:當(dāng)Set Open數(shù)組為空集之后, 從目標(biāo)節(jié)點(diǎn)開(kāi)始, 通過(guò)Find Way Back函數(shù)找到最終路徑。
Step6:作圖并輸出最終結(jié)果。算法流程圖如下:
圖7 算法流程圖 下載原圖
初始化數(shù)據(jù):
假設(shè)某倉(cāng)庫(kù)有20×20×20個(gè)庫(kù)位, 合計(jì)8000個(gè)庫(kù)位。其中已存貨物 (即障礙點(diǎn), 無(wú)法穿越) l=m=n=80;假設(shè)僅有一臺(tái)設(shè)備, 其水平方向、豎直方向能耗、速度各異。
初始化障礙數(shù)據(jù):數(shù)據(jù)量較大, 略。
初始化起點(diǎn)、終點(diǎn):Startpoint: (6, 4, 1) ;Goalpoint: (16, 15, 20) 。
所得路徑數(shù)據(jù):
圖8 80個(gè)障礙點(diǎn)路徑規(guī)劃 下載原圖
圖9 左視圖 下載原圖
由上可知, 路徑規(guī)劃共經(jīng)過(guò)43個(gè)點(diǎn), 除去起點(diǎn)、終點(diǎn), 揀選路徑共經(jīng)過(guò)41個(gè)點(diǎn), 其中水平方向23個(gè)單位長(zhǎng)度, 豎直方向19個(gè)單位長(zhǎng)度。
本文通過(guò)對(duì)立體倉(cāng)庫(kù)環(huán)境的柵格化建模, 創(chuàng)新性地構(gòu)建了無(wú)約束環(huán)境下出入庫(kù)點(diǎn)與倉(cāng)庫(kù)中任意一點(diǎn)的三維路徑規(guī)劃模型。
通過(guò)柵格化三維空間模型, 將設(shè)備運(yùn)行速度、設(shè)備耗能作為系統(tǒng)指標(biāo)進(jìn)行考量, 針對(duì)水平方向和豎直方向的不同移動(dòng)特性, 提出分段路徑代價(jià)函數(shù)的概念, 并通過(guò)A*算法得出該三維空間模型中的最優(yōu)路徑, 從而得到揀選設(shè)備所有經(jīng)過(guò)的路徑節(jié)點(diǎn)。
圖1 0 主視圖 下載原圖
隨著倉(cāng)儲(chǔ)設(shè)備智能化的發(fā)展趨勢(shì), 系統(tǒng)約束及邊界條件越來(lái)越少, 本文研究?jī)?nèi)容對(duì)于跨層作業(yè)系統(tǒng)、新型自動(dòng)化揀選作業(yè)系統(tǒng)的路徑規(guī)劃有普適參考意義。今后可考慮多點(diǎn)、多設(shè)備的三維路徑規(guī)劃研究, 對(duì)于不同倉(cāng)庫(kù)增加相應(yīng)約束即可求解其系統(tǒng)的最優(yōu)路徑。