KIVA機(jī)器人路徑規(guī)劃問(wèn)題研究

(北京物資學(xué)院 北京 100000)

一、KIVA機(jī)器人在亞馬遜倉(cāng)庫(kù)的應(yīng)用現(xiàn)狀

因?yàn)閭}(cāng)儲(chǔ)總是出現(xiàn)在物流各環(huán)節(jié)的接合部，所以倉(cāng)儲(chǔ)管理已成為供應(yīng)鏈管理的核心環(huán)節(jié)。亞馬遜2012年7.75億美金收購(gòu)的Kiva Systems，大大提升了亞馬遜的物流系統(tǒng)。機(jī)器人每小時(shí)可跑30英里，準(zhǔn)確率達(dá)到99.99%，機(jī)器人作業(yè)顛覆傳統(tǒng)電商物流中心作業(yè)“人找貨、人找貨位”模式，通過(guò)作業(yè)計(jì)劃調(diào)動(dòng)機(jī)器人，實(shí)現(xiàn)“貨找人、貨位找人”的模式，整個(gè)物流中心庫(kù)區(qū)無(wú)人化，各個(gè)庫(kù)位在KIVA機(jī)器人驅(qū)動(dòng)下自動(dòng)排序到作業(yè)崗位。KIVA能在亞馬遜物流中心完成自由“行走”，卸貨、搬運(yùn)、處理訂單和揀選的全過(guò)程。

二、KIVA機(jī)器人系統(tǒng)作業(yè)流程

KIVA橙色機(jī)器人的揀貨流程包括揀出流程和歸位流程。主要包括識(shí)別目標(biāo)貨架、鎖定機(jī)器人、舉起貨架、高速運(yùn)行、交叉運(yùn)行、排隊(duì)等候、工作人員取走貨物、機(jī)器人回到儲(chǔ)物區(qū)。具體流程操作為：1.識(shí)別目標(biāo)貨架?？蛻?hù)下單后，管理信息系統(tǒng)按照客戶(hù)的訂單需求確定貨物所在的貨架，將其定位，等待機(jī)器人進(jìn)入。2.鎖定機(jī)器人。根據(jù)確定的貨架的位置，定位離貨架最近的等待作業(yè)的機(jī)器人，機(jī)器人收到信號(hào)后以最快的速度達(dá)到貨架的底部。3.舉起貨架。機(jī)器人將貨架頂起，使貨架處于懸空狀態(tài)。4.高速運(yùn)行。機(jī)器人帶著貨架高速離開(kāi)貨物存儲(chǔ)區(qū)。5.交叉運(yùn)行。由于帶著貨架的機(jī)器人都要到達(dá)揀貨區(qū)，會(huì)出現(xiàn)眾多機(jī)器人交叉運(yùn)行的狀態(tài)。6.排隊(duì)等候。機(jī)器人到達(dá)指定的揀貨員所在區(qū)域后，需要排隊(duì)等候揀貨員取貨。7.工作人員取走貨物。待機(jī)器人到達(dá)工作人員揀貨區(qū)后，工作人員取走客戶(hù)所需的貨物。8.等待下個(gè)命令。待工作人員取走貨物后，機(jī)器人將貨架送到儲(chǔ)物區(qū)。然后等待下個(gè)命令。

三、基于A*算法的KIVA揀選系統(tǒng)路徑規(guī)劃

(一)A*算法簡(jiǎn)介

A*算法作為一種求解圖論中最短路徑的算法,是計(jì)算最短路徑最快的一種方法,具有實(shí)時(shí)性、高效性等,在實(shí)時(shí)系統(tǒng)和人工智能系統(tǒng)中得到極其廣泛的應(yīng)用。A*算法通過(guò)選擇合適的估價(jià)函數(shù)計(jì)算從當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的代價(jià)最小的距離,依此確定路徑的搜索方向,并最終確定整個(gè)路徑。

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

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

圖3-1 柵格坐標(biāo)與序號(hào)

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

圖3-2為具有數(shù)值信息的柵格圖,其中“0”代表自由柵格,即KIVA系統(tǒng)中的通道;“1”代表貨架柵格;“2”代表站臺(tái)柵格;“3”代表小車(chē)柵格。

圖3-2 Kiva系統(tǒng)具有數(shù)值信息的柵格建模圖

記每個(gè)機(jī)器人小車(chē)Boti在二維坐標(biāo)系A(chǔ)S中的位置為PBoti,所有的PBoti在AS屮都有確定的坐標(biāo)(x,y),記PBoti在t時(shí)刻處于某柵格的位置為PBot(XBoti(t),YBoti(t)),簡(jiǎn)記為PBoti。記每個(gè)貨架Podj在二維坐標(biāo)系A(chǔ)S巾的位置為Ppodj,所有的Ppodj在AS中都有確定的坐標(biāo)(x,y),記Ppodj在t吋刻處于某柵格的位置為Ppod(Xpodi(t),ypodi(t)),簡(jiǎn)記為Ppodj。記每個(gè)棟選站臺(tái)Stak在二維坐標(biāo)系A(chǔ)S中的位置為Pstak,所有的Pstak在AS屮都有確定的坐標(biāo)(x,y),記Pstak在t時(shí)刻處于某柵格的位置為Pstak(Xstai(t),Ystai(t)),簡(jiǎn)記為Pstak。Boti在Kiva環(huán)境中具有四個(gè)運(yùn)動(dòng)方向(North,South,East,West),如圖3-3。機(jī)器人小車(chē)在系統(tǒng)中,每一吋刻都可以檢測(cè)到以小車(chē)當(dāng)甜位置為屮心、以小車(chē)的行走步長(zhǎng)a為半徑的范圍內(nèi)的柵格環(huán)境信息。

圖3-3 機(jī)器人小車(chē)運(yùn)動(dòng)方向

(三)使用A*算法進(jìn)行路徑規(guī)劃

首先要對(duì)小車(chē)運(yùn)動(dòng)環(huán)境進(jìn)行建模,確定小車(chē)的搜索區(qū)域;然后,搜索當(dāng)前節(jié)點(diǎn)之后下一個(gè)可能的節(jié)點(diǎn)的范圍,通過(guò)估價(jià)函數(shù)計(jì)算此范圍所有節(jié)點(diǎn)的代價(jià),由此確定下一個(gè)節(jié)點(diǎn);繼續(xù)搜索、估價(jià)、確定,直至搜索到目標(biāo)節(jié)點(diǎn)。之后,小車(chē)從起點(diǎn)按照使用A*算法規(guī)劃好的路徑前往到目標(biāo)點(diǎn)。具體來(lái)說(shuō),主要有:

1、確定搜索區(qū)域

首先,對(duì)多機(jī)器人小車(chē)的系統(tǒng)環(huán)境建立柵格模型,將環(huán)境劃分成以機(jī)器人小車(chē)的步長(zhǎng)為單位的二維網(wǎng)格空間,并建立直角坐標(biāo)系,每個(gè)柵格都有確定的坐標(biāo)和確定的序號(hào)。在KIVA揀選系統(tǒng)中,小車(chē)的行走步長(zhǎng)為一個(gè)柵格,每個(gè)貨架和小車(chē)各占用一個(gè)柵格,每一個(gè)柵格被稱(chēng)為“節(jié)點(diǎn)”。

2、開(kāi)始搜索

在確定搜索區(qū)域后,路徑規(guī)劃的過(guò)程就是找到從起點(diǎn)到終點(diǎn)的每一個(gè)節(jié)點(diǎn),使得這些節(jié)點(diǎn)集合構(gòu)成的路徑是最優(yōu)路徑。從起點(diǎn)開(kāi)始,首先將起點(diǎn)放入幵啟列表中,搜索起點(diǎn)周?chē)目尚袞鸥?并將這些柵格放入到開(kāi)啟列表中,將起點(diǎn)柵格作為這些柵格的父節(jié)點(diǎn);然后,刪除幵啟列表中的起點(diǎn)柵格,將起點(diǎn)柵格放入關(guān)閉列表中;按照估價(jià)函數(shù)對(duì)開(kāi)啟列表中的柵格進(jìn)行路徑估價(jià),選擇最優(yōu)柵格,如此往復(fù)。其中,對(duì)柵格的選擇,需要對(duì)路徑進(jìn)行評(píng)分后才能確定。

3、路徑評(píng)分

路徑規(guī)劃中對(duì)路徑的評(píng)分,離不幵估價(jià)函數(shù)的合理選擇。在對(duì)路徑進(jìn)行評(píng)分時(shí),通過(guò)計(jì)算開(kāi)啟列表中所有節(jié)點(diǎn)的估值,然后選擇估值最低的節(jié)點(diǎn),循環(huán)往復(fù),不斷重復(fù)前面的步驟,直到找到目標(biāo)節(jié)點(diǎn)。

A*算法中的估價(jià)函數(shù)的表達(dá)式為:f(n)=g(n)+h(n)

其中,g值代表從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)n的代價(jià)實(shí)際值,可能是距離或時(shí)間等指標(biāo)的實(shí)際度量值,而h值代表從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的代價(jià)估計(jì)值。當(dāng)規(guī)定了柵格之間的垂直、水平以及對(duì)角線(xiàn)代價(jià)后,在計(jì)算沿特定路徑從起點(diǎn)到某一柵格節(jié)點(diǎn)的g值時(shí),可以依照路徑的方向增加代價(jià)和求解。

4、繼續(xù)搜索

遍歷開(kāi)啟列表,找到估值最小的柵格節(jié)點(diǎn),并將此節(jié)點(diǎn)從開(kāi)啟列表中刪除,放入關(guān)閉列表中。繼續(xù)搜尋并檢查當(dāng)前節(jié)點(diǎn)的相鄰柵格節(jié)點(diǎn),除去在關(guān)閉列表中的節(jié)點(diǎn)和不能通過(guò)的節(jié)點(diǎn)比如障礙物等,如果還有相鄰的節(jié)點(diǎn),則將這些節(jié)點(diǎn)加入到開(kāi)啟列表中,并把當(dāng)前節(jié)點(diǎn)當(dāng)做下一節(jié)點(diǎn)的父節(jié)點(diǎn);如果某個(gè)相鄰的節(jié)點(diǎn)已經(jīng)在開(kāi)啟列表中了,計(jì)算選擇此節(jié)點(diǎn)情況下的g值,如果數(shù)值更低,則將相鄰節(jié)點(diǎn)的父節(jié)點(diǎn)改為此節(jié)點(diǎn),否則的話(huà)不做變動(dòng)。依次搜索,直到搜索到目標(biāo)節(jié)點(diǎn),將目標(biāo)節(jié)點(diǎn)添加進(jìn)關(guān)閉列表后,搜索結(jié)束。

5、確定路徑

從目標(biāo)柵格開(kāi)始,按照父節(jié)點(diǎn)的方向逐步移動(dòng),直到引導(dǎo)回到起始柵格。此時(shí)從起始柵格到目標(biāo)柵格的路徑即為通過(guò)A*算法規(guī)劃出的路徑,機(jī)器人小車(chē)按照此路徑行駛。

6、避障問(wèn)題

KIVA系統(tǒng)處于不斷變化中,屬于動(dòng)態(tài)路網(wǎng)中路徑規(guī)劃的問(wèn)題，若機(jī)器人在行駛過(guò)程中遇到動(dòng)態(tài)障礙物，機(jī)器人會(huì)因?yàn)闆](méi)有“退路”而處于始終等待的狀態(tài)。按照小車(chē)的序號(hào)大小給出避碰的規(guī)則,序號(hào)較小的小車(chē)首先行動(dòng),將另一小車(chē)當(dāng)做是障礙物按照改進(jìn)A*算法得到下一個(gè)最優(yōu)柵格,并前往此柵格;之后序號(hào)較大的柵格按照同樣的方式選擇下一個(gè)最優(yōu)柵格,并前往此柵格。

四、總結(jié)與展望

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

KIVA系統(tǒng)與傳統(tǒng)方式對(duì)比

但是KIVA機(jī)器人的發(fā)展也面臨一些挑戰(zhàn)，比如運(yùn)作成本高，專(zhuān)業(yè)化程度高，對(duì)物流信息技術(shù)要求水平較高，倉(cāng)庫(kù)的利用率只達(dá)到了60%等等。

電子商務(wù)的迅速發(fā)展和物流行業(yè)的創(chuàng)新驅(qū)動(dòng)，KIVA在將來(lái)的倉(cāng)庫(kù)管理中會(huì)成為核心力量。KIVA作為高效的搬運(yùn)系統(tǒng)，配合強(qiáng)有力的無(wú)線(xiàn)系統(tǒng)，如果再輔以合適的物流管理系統(tǒng)，便是高效物流系統(tǒng)的典范。