（同濟大學(xué) 機械與能源工程學(xué)院，上海 201800）

0 引言

跨層作業(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)算法。

1 問題分析

1.1 倉儲環(huán)境描述

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

圖1 無人機（UAV）運動方向

圖2 倉儲機器人運動方向

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

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

1.2 A＊算法距離選擇

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

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

1）曼哈頓距離

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

2）切比雪夫距離

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

圖3 曼哈頓距離的A*搜索過程

圖4 切比雪夫距離的A*搜索過程

3）歐幾里得距離

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

圖5 歐幾里得距離的A*搜索過程

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

2 模型建立

2.1 參數(shù)歸一化處理

線性函數(shù)歸一化（Min-Max Scaling），也稱為離差標(biāo)準(zhǔn)化，是對原始數(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ù)進(jìn)行歸一化處理，本文涉及的標(biāo)準(zhǔn)化參數(shù)有單位距離設(shè)備的能耗和單位距離設(shè)備的揀選時間兩個指標(biāo)，其中單位距離設(shè)備的揀選時間與設(shè)備運行速度有關(guān)。

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

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

歸一化處理，將Ex1代入式(7)：

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

2.2 估價函數(shù)設(shè)計

1）路徑規(guī)劃需要考慮的指標(biāo)：

（1）行走時間最短：機器人行走時間按最低的選取；（2）能量消耗最小：機器人所走過的路徑能量消耗按最低的選取。

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

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

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

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

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

（4）假設(shè)將環(huán)境邊界當(dāng)作障礙物處理，設(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 倉庫柵格模型示意

圖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點之間的的距離；

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

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

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

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

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

若γ＞1，表示豎直方向單位能耗是水平方向單位能耗的γ倍。則f(M)為如下分段函數(shù)（水平、豎直）：

目標(biāo)函數(shù)：

3 仿真驗證

3.1 算法步驟

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

Step 1：通過InitializeField函數(shù)初始化參數(shù)，初始化地圖環(huán)境；將初始節(jié)點存入SetOpen數(shù)組中。

Step2：擴展當(dāng)前的節(jié)點，即找到以當(dāng)前節(jié)點為中心，其前、后、左、右、上、下6個方向鄰域內(nèi)的可通行節(jié)點，將不存在于SetOpen數(shù)組和SetClosed數(shù)組中的節(jié)點計算其啟發(fā)代價即h(n)，并將其存入SetOpenHeuristics數(shù)組中相對應(yīng)的位置，并計算該節(jié)點的路徑耗費即g(n)，并將其設(shè)定為當(dāng)前節(jié)點；在SetOpen數(shù)組中刪去當(dāng)前節(jié)點，并將其存入SetClosed表中。

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

Step4：SetOpenHeuristics數(shù)組中和SetOpenCost數(shù)組中相對應(yīng)位置的值相加，選取其和最小的節(jié)點為當(dāng)前節(jié)點，并將其置入SetClosed數(shù)組中，將其耗費置入SetClosedCost數(shù)組中，然后跳轉(zhuǎn)Step2。

Step5：當(dāng)SetOpen數(shù)組為空集之后，從目標(biāo)節(jié)點開始，通過FindWayBack函數(shù)找到最終路徑。

Step6：作圖并輸出最終結(jié)果。

算法流程圖如下：

圖7 算法流程圖

3.2 算例分析

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

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

表1 初始化各項參數(shù)

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

初始化起點、終點：Startpoint：（6，4，1）；Goalpoint：（16，15，20）。

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

表2 障礙數(shù)為80時路徑規(guī)劃結(jié)果

圖8 80個障礙點路徑規(guī)劃

圖9 左視圖

圖10 主視圖

圖11 俯視圖

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

4 結(jié)論

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

通過柵格化三維空間模型，將設(shè)備運行速度、設(shè)備耗能作為系統(tǒng)指標(biāo)進(jìn)行考量，針對水平方向和豎直方向的不同移動特性，提出分段路徑代價函數(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)路徑。