KIVA機器人路徑規劃問題研究

(北京物資學院 北京 100000)

一、KIVA機器人在亞馬遜倉庫的應用現狀

因為倉儲總是出現在物流各環節的接合部，所以倉儲管理已成為供應鏈管理的核心環節。亞馬遜2012年7.75億美金收購的Kiva Systems，大大提升了亞馬遜的物流系統。機器人每小時可跑30英里，準確率達到99.99%，機器人作業顛覆傳統電商物流中心作業“人找貨、人找貨位”模式，通過作業計劃調動機器人，實現“貨找人、貨位找人”的模式，整個物流中心庫區無人化，各個庫位在KIVA機器人驅動下自動排序到作業崗位。KIVA能在亞馬遜物流中心完成自由“行走”，卸貨、搬運、處理訂單和揀選的全過程。

二、KIVA機器人系統作業流程

KIVA橙色機器人的揀貨流程包括揀出流程和歸位流程。主要包括識別目標貨架、鎖定機器人、舉起貨架、高速運行、交叉運行、排隊等候、工作人員取走貨物、機器人回到儲物區。具體流程操作為：1.識別目標貨架。客戶下單后，管理信息系統按照客戶的訂單需求確定貨物所在的貨架，將其定位，等待機器人進入。2.鎖定機器人。根據確定的貨架的位置，定位離貨架最近的等待作業的機器人，機器人收到信號后以最快的速度達到貨架的底部。3.舉起貨架。機器人將貨架頂起，使貨架處于懸空狀態。4.高速運行。機器人帶著貨架高速離開貨物存儲區。5.交叉運行。由于帶著貨架的機器人都要到達揀貨區，會出現眾多機器人交叉運行的狀態。6.排隊等候。機器人到達指定的揀貨員所在區域后，需要排隊等候揀貨員取貨。7.工作人員取走貨物。待機器人到達工作人員揀貨區后，工作人員取走客戶所需的貨物。8.等待下個命令。待工作人員取走貨物后，機器人將貨架送到儲物區。然后等待下個命令。

三、基于A*算法的KIVA揀選系統路徑規劃

(一)A*算法簡介

A*算法作為一種求解圖論中最短路徑的算法,是計算最短路徑最快的一種方法,具有實時性、高效性等,在實時系統和人工智能系統中得到極其廣泛的應用。A*算法通過選擇合適的估價函數計算從當前節點到目標節點的代價最小的距離,依此確定路徑的搜索方向,并最終確定整個路徑。

(二)KIVA揀選系統的柵格法建模

選擇柵格建模法對KIVA揀選系統進行建模,使用這種方法建模,直觀性強且相對比較簡單。對于KIVA揀選系統環境,假設系統中有m個小車Boti(i=l,2,...,m).n個貨架貨架Podj(j=l,2,...,n)和p個揀選站臺Stak(k=l,2,...,p),小車的運動區域看做是一個二維平面,記此平面為AS。對平面區域AS建立直角坐標系,以AS左上角為坐標原點0,橫向建立X軸,縱向建立Y軸,如下圖3-1所示:

圖3-1 柵格坐標與序號

假設KIVA揀選系統中每個機器人在水平方向和垂直方向上的行走步長為a,并且AS在X、Y軸的最大值分別是Xmax和Ymax。以a為步長形成一個柵格,則每行的柵格數Nx=Xmax/a,每列的柵格數為Ny=Ymax/a。其中Boti、Podj、Stak各占一個柵格.記g∈AS為任意柵格,A為AS中g的集合,記OB={Bot1,Bot2,...Botm}?A為小車柵格集,OP={Pod1,Pod2,...Podn}?A為貨架柵格集，OS={Sta1,Sta2,...Stap}?A為站臺柵格集。每一個柵格g在坐標系中都有確定的坐標(x,y),記做g(x,y),其中x為g所在的行號,y為g所在的列號。定義左上角第一個柵格的坐標為(0,0)。令C={1,2,3,...,M}為柵格序號集,g(0,0)的序號為1,g(l,0)的序號為2,...,如圖3-1所示。

圖3-2為具有數值信息的柵格圖,其中“0”代表自由柵格,即KIVA系統中的通道;“1”代表貨架柵格;“2”代表站臺柵格;“3”代表小車柵格。

圖3-2 Kiva系統具有數值信息的柵格建模圖

記每個機器人小車Boti在二維坐標系AS中的位置為PBoti,所有的PBoti在AS屮都有確定的坐標(x,y),記PBoti在t時刻處于某柵格的位置為PBot(XBoti(t),YBoti(t)),簡記為PBoti。記每個貨架Podj在二維坐標系AS巾的位置為Ppodj,所有的Ppodj在AS中都有確定的坐標(x,y),記Ppodj在t吋刻處于某柵格的位置為Ppod(Xpodi(t),ypodi(t)),簡記為Ppodj。記每個棟選站臺Stak在二維坐標系AS中的位置為Pstak,所有的Pstak在AS屮都有確定的坐標(x,y),記Pstak在t時刻處于某柵格的位置為Pstak(Xstai(t),Ystai(t)),簡記為Pstak。Boti在Kiva環境中具有四個運動方向(North,South,East,West),如圖3-3。機器人小車在系統中,每一吋刻都可以檢測到以小車當甜位置為屮心、以小車的行走步長a為半徑的范圍內的柵格環境信息。

圖3-3 機器人小車運動方向

(三)使用A*算法進行路徑規劃

首先要對小車運動環境進行建模,確定小車的搜索區域;然后,搜索當前節點之后下一個可能的節點的范圍,通過估價函數計算此范圍所有節點的代價,由此確定下一個節點;繼續搜索、估價、確定,直至搜索到目標節點。之后,小車從起點按照使用A*算法規劃好的路徑前往到目標點。具體來說,主要有:

1、確定搜索區域

首先,對多機器人小車的系統環境建立柵格模型,將環境劃分成以機器人小車的步長為單位的二維網格空間,并建立直角坐標系,每個柵格都有確定的坐標和確定的序號。在KIVA揀選系統中,小車的行走步長為一個柵格,每個貨架和小車各占用一個柵格,每一個柵格被稱為“節點”。

2、開始搜索

在確定搜索區域后,路徑規劃的過程就是找到從起點到終點的每一個節點,使得這些節點集合構成的路徑是最優路徑。從起點開始,首先將起點放入幵啟列表中,搜索起點周圍的可行柵格,并將這些柵格放入到開啟列表中,將起點柵格作為這些柵格的父節點;然后,刪除幵啟列表中的起點柵格,將起點柵格放入關閉列表中;按照估價函數對開啟列表中的柵格進行路徑估價,選擇最優柵格,如此往復。其中,對柵格的選擇,需要對路徑進行評分后才能確定。

3、路徑評分

路徑規劃中對路徑的評分,離不幵估價函數的合理選擇。在對路徑進行評分時,通過計算開啟列表中所有節點的估值,然后選擇估值最低的節點,循環往復,不斷重復前面的步驟,直到找到目標節點。

A*算法中的估價函數的表達式為:f(n)=g(n)+h(n)

其中,g值代表從起始節點到當前節點n的代價實際值,可能是距離或時間等指標的實際度量值,而h值代表從當前節點n到目標節點的代價估計值。當規定了柵格之間的垂直、水平以及對角線代價后,在計算沿特定路徑從起點到某一柵格節點的g值時,可以依照路徑的方向增加代價和求解。

4、繼續搜索

遍歷開啟列表,找到估值最小的柵格節點,并將此節點從開啟列表中刪除,放入關閉列表中。繼續搜尋并檢查當前節點的相鄰柵格節點,除去在關閉列表中的節點和不能通過的節點比如障礙物等,如果還有相鄰的節點,則將這些節點加入到開啟列表中,并把當前節點當做下一節點的父節點;如果某個相鄰的節點已經在開啟列表中了,計算選擇此節點情況下的g值,如果數值更低,則將相鄰節點的父節點改為此節點,否則的話不做變動。依次搜索,直到搜索到目標節點,將目標節點添加進關閉列表后,搜索結束。

5、確定路徑

從目標柵格開始,按照父節點的方向逐步移動,直到引導回到起始柵格。此時從起始柵格到目標柵格的路徑即為通過A*算法規劃出的路徑,機器人小車按照此路徑行駛。

6、避障問題

KIVA系統處于不斷變化中,屬于動態路網中路徑規劃的問題，若機器人在行駛過程中遇到動態障礙物，機器人會因為沒有“退路”而處于始終等待的狀態。按照小車的序號大小給出避碰的規則,序號較小的小車首先行動,將另一小車當做是障礙物按照改進A*算法得到下一個最優柵格,并前往此柵格;之后序號較大的柵格按照同樣的方式選擇下一個最優柵格,并前往此柵格。

四、總結與展望

與傳統方式相比較KIVA系統在分揀效率、精準度、噪聲等方面都有了革命性的變化。

KIVA系統與傳統方式對比

但是KIVA機器人的發展也面臨一些挑戰，比如運作成本高，專業化程度高，對物流信息技術要求水平較高，倉庫的利用率只達到了60%等等。

電子商務的迅速發展和物流行業的創新驅動，KIVA在將來的倉庫管理中會成為核心力量。KIVA作為高效的搬運系統，配合強有力的無線系統，如果再輔以合適的物流管理系統，便是高效物流系統的典范。