跨層作業(yè)逐漸成為倉儲物流提高效率的趨勢之一。ADAPTO是范德蘭德公司為了減輕企業(yè)倉儲配送壓力而專門設(shè)計的一款創(chuàng)新的3D穿梭小車。ADAPTO逐漸弱化了倉儲系統(tǒng)層與層、巷道與巷道之間的隔離, 同一個3D穿梭車可以自由的穿梭于貨架任意位置, 不局限于巷道與層之間。同樣, 瑞士的建筑五金供應(yīng)商SFS采用的跨層穿梭車系統(tǒng), 立庫有17層, 這17層僅配備了3臺穿梭車, 共5個巷道, 整個立庫僅用15臺穿梭車, 系統(tǒng)設(shè)計不僅降低成本, 作業(yè)效率也非常高[1]?？鐚幼鳂I(yè)極大地增加了揀選作業(yè)的靈活性。

具有3維空間運動能力的典型移動機器人, 現(xiàn)在研究較多的是各類空間和水下機器人。其中, 智能程度較高的包括MAV、UAV、UUV、AUV等[2]。智能倉儲物流領(lǐng)域使用揀選機器人十分廣泛, 但大部分路徑規(guī)劃研究局限于二維路徑規(guī)劃, 類似跨層作業(yè)此類約束較少甚至無約束的通用倉儲模型三維路徑規(guī)劃少有研究涉及, 本文提出一種通用的倉庫揀選三維路徑規(guī)劃模型, 并設(shè)計了與之匹配的尋優(yōu)算法。

通用立體倉庫模型中的揀選小車路徑規(guī)劃問題是一個三維路徑規(guī)劃, 目前研究較多的是無人機 (UAV) 的三維路徑規(guī)劃, 倉儲環(huán)境下的全地圖三維路徑規(guī)劃研究并不多見。無人機三維路徑規(guī)劃的環(huán)境威脅包括地圖環(huán)境威脅、雷達偵查威脅、敵軍導(dǎo)彈輻射范圍威脅等。倉儲揀選設(shè)備的路徑規(guī)劃與之對比, 顯然倉庫里的揀選車輛路徑比較規(guī)則, 通常只有水平、豎直直線運動, 相比于無人機的飛行軌跡較為簡單, 一個無人機的路徑選擇在柵格空間中可以有26個方向[3] (如圖1所示) 。一個倉儲機器人的路徑選擇在空間中通常只有6個方向, 如圖2所示。

倉庫揀選設(shè)備 (提升機、堆垛機、穿梭車等) 的運動僅為前、后、左、右、上、下6個方向。分別對應(yīng)矩陣:

故將連續(xù)空間變換為柵格空間系統(tǒng)模型, 更符合立體倉庫揀選設(shè)備運動的客觀規(guī)律, 同時便于算法搜索。且實際求解過程中倉庫尺寸、規(guī)模已知, 因此可以視為全局路徑規(guī)劃問題。將倉庫根據(jù)每個貨位的尺寸按小方塊進行劃分, 每個小立方體代表一個貨位。

A*算法是一種常見的路徑搜索算法, A*算法的估價函數(shù)可以表示為:

其中g(shù) (n) 表示從起始節(jié)點Start到節(jié)點n的真實耗費值, h (n) 表示從節(jié)點n到終止點Goal的啟發(fā)估計耗費值。f (n) 表示從起始點開始, 經(jīng)過節(jié)點n到達目標的啟發(fā)估計耗費值。h* (n) 是指經(jīng)過節(jié)點n, 到達終止目標點的實際最優(yōu)消耗值。其基本思路與經(jīng)典的路徑搜索算法Dijkstra相似, 但在Dijkstra算法的基礎(chǔ)上加上啟發(fā)代價, 路徑代價通常由距離決定, 距離通常有三種方式計算:

1) 曼哈頓距離

曼哈頓距離即坐標系中兩點的絕對軸距之和。其表達式如式 (3) 所示, 效果如圖3所示。

2) 切比雪夫距離

切比雪夫距離被稱為棋盤距離。其表達式如式 (4) 所示, 效果如圖4所示。

3) 歐幾里得距離

歐幾里得距離是衡量兩點之間距離遠近的最常用的方法之一, 其值直接可以看作兩個位置點在歐式空間中的兩點的直線距離, 其表達式如式 (5) 所示, 效果如圖5所示。

由于倉儲環(huán)境中, 只存在直線運動且為前、后、左、右、上、下6個方向, 因此算法的距離選擇應(yīng)以曼哈頓距離為基礎(chǔ), 在此距離公式基礎(chǔ)上增加豎直方向坐標差的絕對值, 距離公式為:

線性函數(shù)歸一化 (Min-Max Scaling) , 也稱為離差標準化, 是對原始數(shù)據(jù)的線性變換, 使結(jié)果值映射到[0-1]之間。轉(zhuǎn)換函數(shù)如下:

其中max為樣本數(shù)據(jù)的最大值, min為樣本數(shù)據(jù)的最小值。本文A*算法的歷史路徑函數(shù)里還包括地圖環(huán)境代價, 環(huán)境代價的取值為0或1, 在計算代價函數(shù)時, 為避免“大數(shù)吃小數(shù)”的現(xiàn)象, 需要對數(shù)據(jù)進行歸一化處理, 本文涉及的標準化參數(shù)有單位距離設(shè)備的能耗和單位距離設(shè)備的揀選時間兩個指標, 其中單位距離設(shè)備的揀選時間與設(shè)備運行速度有關(guān)。

統(tǒng)計出倉儲系統(tǒng)內(nèi)不同執(zhí)行設(shè)備的單位距離能耗和速度, 找出能耗最大值和速度最大值, 根據(jù)以上離散標準化公式將單位能耗和速度歸一化處理, 使之映射到[0-1]之間, 由于系統(tǒng)考量的兩個指標是單位能耗與揀選時間, 時間與速度成反比, 因此在速度值的歸一化處理之后可作加一處理, 避免揀選時間數(shù)值無窮大, 使單位距離下的設(shè)備運行時間也在[0-1]之間。

假設(shè)縱向移動由提升機執(zhí)行, 其速度為vx、單位能耗 (功率) 為Ex, 水平移動由穿梭車執(zhí)行, 其速度為vy、單位能耗 (功率) 為Ey。則有:

歸一化處理, 將Ex1代入式 (7) :

其余方向能耗和速度數(shù)據(jù)的歸一化過程同上。

1) 路徑規(guī)劃需要考慮的指標:

(1) 行走時間最短:機器人行走時間按最低的選取; (2) 能量消耗最小:機器人所走過的路徑能量消耗按最低的選取。

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

環(huán)境建模的目的是能夠為路徑規(guī)劃提供可用的分析平臺, 常用的分析建模方法有拓撲建模法和幾何建模法[4,5], 在本文中選用柵格法對環(huán)境進行建模, 柵格法環(huán)境建模是將倉儲環(huán)境分解成一系列尺寸相同的網(wǎng)格單元, 將環(huán)境信息或障礙物信息分布在l×m×n的環(huán)境柵格矩陣中, 由于每個柵格的像元值都是唯一的、確定的, 所以每個柵格的標識也是唯一的、確定的[6]。建立環(huán)境模型時既要滿足算法規(guī)劃的準確性也要滿足實時性, 作以下假設(shè):

(1) 假設(shè)搬運設(shè)備 (平移、提升) 無法穿越已存貨位。

(2) 假設(shè)倉庫內(nèi)的貨物實時位置已知。

(3) 假設(shè)設(shè)備性能, 包括能耗、速度均已知。

(4) 假設(shè)將環(huán)境邊界當作障礙物處理, 設(shè)備不能越過邊界行走。

假設(shè)自動化立體倉庫中每一個貨架長寬高尺寸分別為a, b, c, 由l排m列n層的貨架組成, 則整個倉庫有l(wèi)×m×n個貨格, 整個倉庫貨架區(qū)長a×l, 寬b×m, 高c×n。地圖環(huán)境代價值的設(shè)置則根據(jù)倉庫中已被占據(jù)的貨格決定, 若此貨格已被占用, 則無法存放或穿越, 即此點為障礙點, 在matlab中可建立l×m×n的三維數(shù)組, 其中已被占據(jù)的貨格相應(yīng)位置則置INF, 表示障礙, 未被占據(jù)的貨格相應(yīng)位置置0, 表示可存儲或可通行。

圖6說明了一個4×4×4的倉庫模型, 以圖中填黑區(qū)域為例, 簡單說明本文的建模策略, 則該區(qū)域的障礙障礙信息矩陣為一個l=m=n=4的三維矩陣:

其中每層INF值所在位置即障礙點, S點代表出發(fā)點Startpoint, G點則代表終點Goalpoint。

距離函數(shù)的選取, 由式 (6) 可知是根據(jù)曼哈頓距離擴展Z方向而來的, 由于啟發(fā)函數(shù)中只計算距離函數(shù), 但實際行走需要考慮揀選時間、設(shè)備能耗, 且實際行走過程中揀選設(shè)備水平方向和豎直方向的運行速度和能耗并不完全一樣。因此啟發(fā)函的距離計算中在豎直方向引入因子γ, 以調(diào)節(jié)豎直方向與水平方向的差異。

DMS表示M和Startpoint點之間的的距離;

表示點s與下一點m水平方

向之間的距離;

表示點s與下一點m豎直方向之間

的距離;

歷史路徑代價函數(shù)可以如下分段表達:

K (M') 表示地圖環(huán)境代價;

α、β分別表示設(shè)備能耗與運行時間在啟發(fā)函數(shù)中的占比且:

ξ表示啟發(fā)代價調(diào)節(jié)參數(shù) (為了保證路徑搜索方向始終走向目標點, 僅避開障礙且不受歷史路徑代價函數(shù)的影響, ξ可適當調(diào)節(jié), 使得每次路徑搜索都盡量靠近目標點) , ξ值的選取控制在時間和能耗參數(shù)同一量級, 并略大于αE及βv;

DMG表示點M和路徑終點G之間的距離。

若γ>>11, 表示豎直方向單位能耗是水平方向單位能耗的γ倍>1。則f (M) 為如下分段函數(shù) (水平、豎直) :

目標函數(shù):

在三維空間中求解移動機器人最優(yōu)路徑的方法有很多, 如A*算法、D*算法、進化算法等[7], 在眾多求解最優(yōu)路徑的方法中, A*算法簡單、有效, 并且得到了廣泛的應(yīng)用, 本文采用的A*算法進行倉儲設(shè)備的路徑規(guī)劃, 其算法基本步驟描述:

Step 1:通過Initialize Field函數(shù)初始化參數(shù), 初始化地圖環(huán)境;將初始節(jié)點存入Set Open數(shù)組中。

S t e p 2:擴展當前的節(jié)點, 即找到以當前節(jié)點為中心, 其前、后、左、右、上、下6個方向鄰域內(nèi)的可通行節(jié)點, 將不存在于Set Open數(shù)組和Set Closed數(shù)組中的節(jié)點計算其啟發(fā)代價即h (n) , 并將其存入Set Open Heuristics數(shù)組中相對應(yīng)的位置, 并計算該節(jié)點的路徑耗費即g (n) , 并將其設(shè)定為當前節(jié)點;在Set Open數(shù)組中刪去當前節(jié)點, 并將其存入Set Closed表中。

Step3:將擴展得到的節(jié)點依次加入Set Open數(shù)組中, 若此節(jié)點不存在Set Open數(shù)組中, 那么就將其加入到Set Open數(shù)組中, 并將計算得到的路徑耗費g (n) 加入到Set Open Cost數(shù)組中相應(yīng)的位置, 并記錄這點的來源方向到Field Pointers數(shù)組中, 若此節(jié)點己經(jīng)存在于Set Open數(shù)組中, 比較此點記錄在Set Open Cost數(shù)組的路徑消耗與新計算得到的路徑消耗, 若記錄的路徑消耗小于新計算得到的路徑消耗, 則對此點不做任何改變, 反之, 用新的路徑消耗代替此點在Set Open Cost數(shù)組中相對應(yīng)的路徑消耗, 并更新此點的來源方向到Field Pointers數(shù)組。

Step4:Set Open Heuristics數(shù)組中和Set Open Cost數(shù)組中相對應(yīng)位置的值相加, 選取其和最小的節(jié)點為當前節(jié)點, 并將其置入Set Closed數(shù)組中, 將其耗費置入Set Closed Cost數(shù)組中, 然后跳轉(zhuǎn)Step2。

Step5:當Set Open數(shù)組為空集之后, 從目標節(jié)點開始, 通過Find Way Back函數(shù)找到最終路徑。

Step6:作圖并輸出最終結(jié)果。算法流程圖如下:

初始化數(shù)據(jù):

假設(shè)某倉庫有20×20×20個庫位, 合計8000個庫位。其中已存貨物 (即障礙點, 無法穿越) l=m=n=80;假設(shè)僅有一臺設(shè)備, 其水平方向、豎直方向能耗、速度各異。

初始化障礙數(shù)據(jù):數(shù)據(jù)量較大, 略。

初始化起點、終點:Startpoint: (6, 4, 1) ;Goalpoint: (16, 15, 20) 。

所得路徑數(shù)據(jù):

由上可知, 路徑規(guī)劃共經(jīng)過43個點, 除去起點、終點, 揀選路徑共經(jīng)過41個點, 其中水平方向23個單位長度, 豎直方向19個單位長度。

本文通過對立體倉庫環(huán)境的柵格化建模, 創(chuàng)新性地構(gòu)建了無約束環(huán)境下出入庫點與倉庫中任意一點的三維路徑規(guī)劃模型。

通過柵格化三維空間模型, 將設(shè)備運行速度、設(shè)備耗能作為系統(tǒng)指標進行考量, 針對水平方向和豎直方向的不同移動特性, 提出分段路徑代價函數(shù)的概念, 并通過A*算法得出該三維空間模型中的最優(yōu)路徑, 從而得到揀選設(shè)備所有經(jīng)過的路徑節(jié)點。

隨著倉儲設(shè)備智能化的發(fā)展趨勢, 系統(tǒng)約束及邊界條件越來越少, 本文研究內(nèi)容對于跨層作業(yè)系統(tǒng)、新型自動化揀選作業(yè)系統(tǒng)的路徑規(guī)劃有普適參考意義。今后可考慮多點、多設(shè)備的三維路徑規(guī)劃研究, 對于不同倉庫增加相應(yīng)約束即可求解其系統(tǒng)的最優(yōu)路徑。