基于A*算法的通用倉儲物流三維路徑規劃研究

2018-07-21 07:35:18

制造業自動化 2018年7期

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

0 引言

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

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

1 問題分析

1.1 倉儲環境描述

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

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

圖2 倉儲機器人運動方向

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

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

1.2 A＊算法距離選擇

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

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

1）曼哈頓距離

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

2）切比雪夫距離

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

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

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

3）歐幾里得距離

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

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

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

2 模型建立

2.1 參數歸一化處理

線性函數歸一化（Min-Max Scaling），也稱為離差標準化，是對原始數據的線性變換，使結果值映射到[0-1]之間。轉換函數如下：

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

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

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

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

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

2.2 估價函數設計

1）路徑規劃需要考慮的指標：

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

2）環境模型的建立：

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

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

（2）假設倉庫內的貨物實時位置已知。

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

（4）假設將環境邊界當作障礙物處理，設備不能越過邊界行走。

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

圖6 倉庫柵格模型示意

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

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

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

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

歷史路徑代價函數可以如下分段表達：

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

α、β分別表示設備能耗與運行時間在啟發函數中的占比且：

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

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

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

目標函數：

3 仿真驗證

3.1 算法步驟

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

Step 1：通過InitializeField函數初始化參數，初始化地圖環境；將初始節點存入SetOpen數組中。

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

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

Step4：SetOpenHeuristics數組中和SetOpenCost數組中相對應位置的值相加，選取其和最小的節點為當前節點，并將其置入SetClosed數組中，將其耗費置入SetClosedCost數組中，然后跳轉Step2。

Step5：當SetOpen數組為空集之后，從目標節點開始，通過FindWayBack函數找到最終路徑。

Step6：作圖并輸出最終結果。

算法流程圖如下：