隨著電子商務(wù)的飛速發(fā)展,傳統(tǒng)的倉儲物流已無法適應(yīng)現(xiàn)代物流品種多、批量小、批次多、周期短的特點,而基于移動機器人的自動化倉儲物流技術(shù)研究了基于線性時序邏輯(LTL)理論規(guī)劃倉儲機器人路徑的方法。得到了應(yīng)用和發(fā)展,目前倉儲物流業(yè)已成為繼汽車行業(yè)后的第二大機器人應(yīng)用領(lǐng)域[1]。倉儲物流機器人的應(yīng)用可以大大提高電商倉儲物流工作的效率,緩解當前倉儲物流行業(yè)供不應(yīng)求的現(xiàn)狀。機器人應(yīng)用的目的是提高電商的庫存管理能力與配載能力,而實現(xiàn)這樣的目的的核心技術(shù)是機器人的路徑規(guī)劃。路徑規(guī)劃是指根據(jù)當前倉儲物流物品種類多、倉儲面積大的特點,按照貨單需求規(guī)劃出合理的機器人路徑,以提高倉儲機器人的作業(yè)效率。本研究根據(jù)實際應(yīng)用要求,提出了一種基于線性時序邏輯(linear temporal logic,LTL)理論的倉儲移動機器人路徑規(guī)劃方法,該方法可根據(jù)實際的倉儲環(huán)境和任務(wù)需求,規(guī)劃出符合環(huán)境信息的最優(yōu)路徑,確保機器人完成指定任務(wù)的運行路徑總長度最短,提高倉儲工作整體的工作效率。與傳統(tǒng)的方法相比,本文所提出的方法在確保規(guī)劃路徑最優(yōu)的基礎(chǔ)上能夠較好的適用于倉儲物流環(huán)境。
目前倉儲機器人的應(yīng)用研究主要集中在調(diào)度和避碰問題上,對針對具體環(huán)境和具體任務(wù)的路徑規(guī)劃的研究較少。文獻[2]在傳統(tǒng)的A*算法(一類啟發(fā)式的路徑搜索算法)中引入時間參量,將平面二維的A*算法擴展到平面空間加時間的三維時空中,同時引入暫停機制避免機器人之間發(fā)生碰撞,結(jié)合分層的路徑規(guī)劃算法減少了計算量;文獻[3]將機器人調(diào)度與特殊規(guī)則約束下基于A*算法的路徑規(guī)劃相結(jié)合實現(xiàn)了倉儲物流機器人集群的智能調(diào)度和路徑規(guī)劃;文獻[4]采用改進的遺傳算法和SHAA神經(jīng)網(wǎng)絡(luò)算法主要解決了多機器人避碰問題;文獻[5]提出了一種PUSH-SWAP的方法來避免多移動機器人之間的碰撞。此外,現(xiàn)有的路徑規(guī)劃方法還有諸如人工勢場法[6]、A*算法[7]、快速擴展隨機樹(rapiddy-exploring random tree,RRT)算法[8]等都是針對簡單的點到點的路徑規(guī)劃任務(wù)。然而,上述方法仍然存在很大的瓶頸,無法很好的適用于倉儲機器人這類包含多點訪問等復(fù)雜任務(wù)需求的應(yīng)用中。
線性時序邏輯(LTL)語言[9]可以描述倉儲物流機器人實際應(yīng)用中較為復(fù)雜的任務(wù)需求,諸如在倉庫環(huán)境中從起點出發(fā)先后到若干個貨架取貨后回到指定點,途中規(guī)避某些區(qū)域等。目前,基于LTL理論的路徑規(guī)劃方法的研究主要集中在解決旅行商(TSP)問題上,文獻[10,11]采用了最小瓶頸環(huán)法解決了單機器人多點巡回的問題;文獻[12]針對傳統(tǒng)方法無法直接解決多點最優(yōu)巡回問題,采用基于擴展乘積自動機的最優(yōu)巡回算法尋優(yōu)路徑;文獻[13]在傳統(tǒng)方法的基礎(chǔ)上加入了時序要求,針對兩機器人同時巡回某些點的問題,采用了同步序列法生成同步路徑以保證兩機器人的同時性;文獻[14]將基于LTL理論的路徑規(guī)劃方法擴展到有時間限制的動態(tài)環(huán)境中。然而,上述方法由于無法靈活的應(yīng)用于動態(tài)的倉儲環(huán)境、無法保證最優(yōu)性、計算量大、路徑尋優(yōu)時間長等不足,都無法滿足倉儲物流機器人的應(yīng)用需求。
機器人的效率與倉儲物流系統(tǒng)的運作效率直接相關(guān)。因此,需要為倉儲機器人設(shè)計一種有效的算法來控制機器人按指定任務(wù)在倉庫中運行,并且能實現(xiàn)路徑最優(yōu),從而最大限度地提高倉儲物流系統(tǒng)的整體運作效率。
傳統(tǒng)的路徑規(guī)劃方法,諸如A*算法、人工勢場法、RRT算法等都需要根據(jù)任務(wù)節(jié)點順序,按序分段進行規(guī)劃,規(guī)劃所得路徑受任務(wù)節(jié)點的數(shù)目和順序影響,無法保證規(guī)劃所得路徑的最優(yōu)性。本文所采用的基于線性時序邏輯的路徑規(guī)劃方法將環(huán)境信息與任務(wù)需求相融合,構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓撲確保了尋優(yōu)所得路徑不受任務(wù)節(jié)點順序的影響;此外,采用Dijkstra算法來搜索路徑保證了規(guī)劃所得路徑的最優(yōu)性。
本文采用基于線性時序邏輯理論的路徑規(guī)劃方法尋優(yōu)路徑,其具體算法流程圖如圖1所示,主要分為環(huán)境建模與任務(wù)描述和路徑尋優(yōu)兩個部分。首先,將機器人運行環(huán)境構(gòu)建為可擴展的加權(quán)切換系統(tǒng);然后,采用線性時序任務(wù)公式描述任務(wù)需求,并通過LTL2BA工具包將其轉(zhuǎn)換為圖表形式(Buchi自動機)[15];接著,將加權(quán)切換系統(tǒng)與Buchi自動機作笛卡爾乘積構(gòu)成任務(wù)可行網(wǎng)絡(luò)拓撲(Product自動機)[16];之后,采用Dijkstra算法[17]在任務(wù)可行網(wǎng)絡(luò)拓撲上所搜出最優(yōu)路徑;最后,將任務(wù)可行網(wǎng)絡(luò)拓撲上尋優(yōu)所得路徑映射回加權(quán)切換系統(tǒng)得到環(huán)境中對應(yīng)的最優(yōu)路徑。
由于實際的倉儲環(huán)境中貨架數(shù)量非常多,在構(gòu)建環(huán)境模型時若把所有的貨架信息都包含進去,會導(dǎo)致環(huán)境模型太過復(fù)雜,增加路徑規(guī)劃的計算量。因此,本文構(gòu)建了一個可靈活擴展的環(huán)境模型,選取環(huán)境中固定的路徑節(jié)點構(gòu)建環(huán)境模型,當選定任務(wù)貨架后再對環(huán)境模型進行擴展,以此降低環(huán)境模型的復(fù)雜度,從而降低計算量。另外,傳統(tǒng)的路徑規(guī)劃方法只能針對點到點的路徑規(guī)劃,無法很好地描述倉儲物流應(yīng)用中諸如連續(xù)多點訪問等復(fù)雜任務(wù)需求,因而本文采用線性時序任務(wù)公式對倉儲環(huán)境中的任務(wù)進行描述,使其能夠適用于實際應(yīng)用中各類復(fù)雜的任務(wù)需求。
假設(shè)倉儲環(huán)境如圖2所示,其中帶箭頭矩形代表機器人,淺灰色矩形代表存放不同貨物的各個貨架,左上角為倉儲機器人起點和出貨的柜臺,當柜臺接到取貨單時需要規(guī)劃出最優(yōu)的取貨路徑,然后讓機器人按指定路徑去取貨,如圖2所示深灰色矩形為貨單上貨物對應(yīng)的貨架。
本文將機器人在環(huán)境當中的運動建立成一個可靈活擴展的加權(quán)切換系統(tǒng)模型。加權(quán)切換系統(tǒng)模型[18]是一種圖表,它以環(huán)境中的關(guān)鍵位置為節(jié)點,如果機器人能從一個位置行駛至另一個位置,則這兩個節(jié)點間有邊相連。每條邊都標有相應(yīng)的權(quán)值,表示機器人從一個節(jié)點行駛至另一個節(jié)點的成本。本文用一個元組
來表示機器人運行環(huán)境對應(yīng)的加權(quán)切換系統(tǒng)模型。其中,Q為一個有限狀態(tài)集,其每一個狀態(tài)代表環(huán)境中道路網(wǎng)絡(luò)的一個節(jié)點;q?!蔘代表初始狀態(tài),即機器人在環(huán)境中所處的初始節(jié)點;代表切換關(guān)系,即環(huán)境中節(jié)點間的連通狀態(tài);∏為一個原子命題集合;ζ:Q→2∏是狀態(tài)的命題函數(shù);ω:R→R>0代表切換權(quán)重,代表機器人在環(huán)境中從一個節(jié)點切換到另一節(jié)點所需的成本(如運行時間、路徑長度等)。
以圖3所示的模擬倉庫環(huán)境模型為例,其中p1為起點,p2為終點,空白矩形代表各個存放不同貨物的貨架。倉儲機器人需要從起點出發(fā),到指定貨架取貨后將貨物送回到終點。本文選取倉庫環(huán)境中的22個關(guān)鍵節(jié)點作為路徑節(jié)點,其中節(jié)點p1和p2分別表示機器人的起點和終點,即倉庫接單和出貨的柜臺。通過一個22×22的鄰接矩陣T.adj來描述各節(jié)點間的連通情況,以及任意兩節(jié)點間的切換成本,即機器人需要運行的距離,其中T.adj的每一行都代表該行對應(yīng)節(jié)點與其他節(jié)點的連通情況即切換成本。如T.adj的第一行第二列代表節(jié)點p1到節(jié)點p2的連通情況和切換成本,第二行第三列代表節(jié)點p2到節(jié)點p3的連通情況和切換成本,依此類推。
然后,當倉庫接到貨單時,根據(jù)貨單上的貨物所在的貨架選取對應(yīng)的貨架節(jié)點,選定目標貨架后的環(huán)境模型如圖4所示,深灰色貨架即為機器人需要取貨的貨架,淺灰色節(jié)點即為貨架對應(yīng)的路徑節(jié)點。根據(jù)任務(wù)貨架節(jié)點數(shù)量擴展鄰接矩陣T.adj,以圖4所示的任務(wù)為例,需要將T.adj擴展為25×25的方陣。
同時,當倉庫接到貨單選定任務(wù)貨架后,需要對任務(wù)進行描述。本文采用線性時序邏輯(LTL)公式來描述倉儲物流機器人需要完成的復(fù)雜任務(wù)需求。線性時序邏輯公式φ是由原子命題∏的子集組成的表達式,其中還包含了布爾算子(非)、∧(與)、∨(或),以及時序邏輯算子G (始終)、F(最終)、X(接下來)和U(直到)。例如,G P1表示T中狀態(tài)p1始終為真;F p1表示最終達到T中的狀態(tài)p1;X p1表示接下來到達T中的狀態(tài)p1;公式p1 U p2表示當?shù)竭_p1狀態(tài)時,必須到達狀態(tài)p2才能前往下一個狀態(tài)。將這些時序和布爾算子組合可以描述更為復(fù)雜的任務(wù)需求。
以圖4為例,任務(wù)需求:“機器人從P1節(jié)點出發(fā),先后到p23、p24和p25這三個節(jié)點取貨,然后回到p2節(jié)點將取回的貨物打包出倉”。采用線性時序邏輯任務(wù)公式可以描述為
其中,起點T.q0=p1。
在得到式(2)所示的任務(wù)公式后,首先,采用LTL2BA工具包將其轉(zhuǎn)換為圖表的形式(Buchi自動機)。由于任務(wù)式(2)轉(zhuǎn)換后的圖表較為復(fù)雜,這里以任務(wù)公式
為例。假設(shè)機器人從p1出發(fā),到p2取貨后最終回到p3。圖5即為式(3)轉(zhuǎn)換后的結(jié)果。環(huán)境模型以圖6所示的加權(quán)切換系統(tǒng)圖為例,可以用一個4×4的鄰接矩陣來描述各節(jié)點間的連通情況,以及任意兩節(jié)點間的切換成本。
然后,將轉(zhuǎn)換所得Buchi自動機與加權(quán)切換系統(tǒng)作笛卡爾乘積,得到任務(wù)可行網(wǎng)絡(luò)拓撲(Product自動機)。圖7所示即為圖6所示加權(quán)切換系統(tǒng)與圖5所示Büchi自動機作笛卡爾乘積后所得的任務(wù)可行網(wǎng)絡(luò)拓撲,該拓撲包含了環(huán)境信息和任務(wù)需求。其中,第一行包含S0的狀態(tài)為初始狀態(tài),最后一行包含S4的狀態(tài)為最終的接收狀態(tài)。
接著,采用Dijkstra算法在任務(wù)可行網(wǎng)絡(luò)拓撲上搜索出從起始狀態(tài)到接收狀態(tài)的最優(yōu)路徑。如圖7中實線箭頭所示路徑即為采用Dijkstra算法在任務(wù)可行網(wǎng)絡(luò)拓撲上搜索從初始狀態(tài)到最終狀態(tài)實驗所得路徑結(jié)果,即(P0,s0)→(p2,s0)→(P1,s1)→(p3,s3),其中狀態(tài)S3與狀態(tài)S4之間的切換為式(3)中GFp3部分的自循環(huán),所以可以忽略不計。從圖中可以看出該路徑的總權(quán)重值是最小的,且路徑節(jié)點數(shù)是最少的,因此規(guī)劃所得路徑是最優(yōu)的。由于Dijkstra算法實質(zhì)是廣度優(yōu)先搜索,因此可以確保路徑的最優(yōu)性。
最后,在得到任務(wù)可行網(wǎng)絡(luò)拓撲上的最優(yōu)路徑后,還需將其映射回初始的加權(quán)切換系統(tǒng)中,得到倉庫環(huán)境中完成指定任務(wù)的最優(yōu)路徑,于是引入如下引理:
引理1 (Product自動機路徑映射)[19]對于任務(wù)可行網(wǎng)絡(luò)拓撲上的任意路徑rp=(p0,s0)(p1,s1)(p2,s2)…,路徑序列rT=P0P1P2…為加權(quán)切換系統(tǒng)中對應(yīng)的滿足任務(wù)需求的路徑,且rP和rT所對應(yīng)的權(quán)重相等。
根據(jù)引理1,路徑p0→p2→p1→p3即為圖7所示的任務(wù)可行網(wǎng)絡(luò)拓撲上最優(yōu)路徑映射回圖6所示的加權(quán)切換系統(tǒng)后所得路徑,即圖6所示的環(huán)境模型中滿足任務(wù)公式(3)的最優(yōu)路徑。
其具體算法如下:
輸入:倉儲環(huán)境對應(yīng)的加權(quán)切換系統(tǒng)模型T;
輸出:倉庫環(huán)境中滿足任務(wù)需求的最優(yōu)路徑rT;
1)選定任務(wù)貨架;
2)根據(jù)選取的目標貨架擴展加權(quán)切換系統(tǒng)模型T,用線性時序任務(wù)公式φ描述任務(wù)需求;
3)將線性時序任務(wù)公式φ轉(zhuǎn)換為圖表的形式,即Buchi自動機B=LTL2BA(Φ);
4)構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓撲;
5)采用Dijkatra算法在任務(wù)可行網(wǎng)絡(luò)拓撲P上搜索出一條從初始狀態(tài)到最終狀態(tài)的最優(yōu)路徑rP;
6)將P上尋優(yōu)所得路徑rP映射回加權(quán)切換系統(tǒng),得到倉庫環(huán)境中滿足任務(wù)需求的最優(yōu)路徑rT。
為了驗證上述方法的可行性與有效性,本文在MATLAB中采用GUI編程對上述方法進行了仿真驗證,其程序操作界面如圖8所示,圖中的模擬倉庫環(huán)境對應(yīng)的模擬倉庫環(huán)境模型如圖3所示。其中,起點代表倉儲機器人的起始位置,對應(yīng)圖3中的p1節(jié)點;終點代表倉儲機器人完成取貨后需要到達的最終位置,對應(yīng)圖3中的p2節(jié)點;界面中的小正方形代表倉庫中存放貨物的貨架,倉儲機器人需要按照需求到指定的貨架取貨,若需要倉儲機器人到該貨架取貨則用鼠標左鍵單擊選中對應(yīng)貨架;若環(huán)境中某一路徑節(jié)點發(fā)生變化無法繼續(xù)通行,則用鼠標右鍵單擊對應(yīng)位置,將其標記為障礙物;在選取好任務(wù)貨架和障礙物節(jié)點后點擊“規(guī)劃路徑”按鍵進行路徑尋優(yōu)。
在圖3所示的倉儲環(huán)境模型中,任意指定7個任務(wù)貨架,如圖9中深灰色矩形所示,選取的順序為從上到下,從左到右。機器人需要從p1節(jié)點出發(fā),分別到p23、p24、p25、p26、p27、p28和p29這7個節(jié)點對應(yīng)的貨架取貨,然后將貨物送回到p2。
首先,將圖3所示的包含22節(jié)點的倉儲環(huán)境模型擴展到29節(jié)點,對應(yīng)的22×22的鄰接矩陣T.adj也擴展為29×29的方陣;其次,采用線性時序任務(wù)公式描述給定的任務(wù)需求,如下式所示:
然后,將式(4)轉(zhuǎn)換為Buchi自動機B;接著,將環(huán)境對應(yīng)的加權(quán)切換系統(tǒng)T與B作笛卡爾乘積,構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓撲P;然后,采用Dijkstra算法在P上搜索出最優(yōu)路徑;最后,將P上尋優(yōu)所得路徑映射回加權(quán)切換系統(tǒng),獲得環(huán)境中對應(yīng)的最優(yōu)路徑。圖9中深灰色直線即為尋優(yōu)所得路徑。從圖中可以看出基于線性時序邏輯理論的倉儲機器人路徑規(guī)劃方法能夠規(guī)劃出既符合環(huán)境信息,又滿足任務(wù)需求的最優(yōu)路徑。
接下來,本文將上述方法與傳統(tǒng)方法做進一步的仿真比較。目前已有的路徑規(guī)劃方法有很多,但基本都針對“從a點到b點,途中避開障礙物”這類簡單的任務(wù),對于倉儲機器人這類需要從起點出發(fā),到多點取貨后回到終點的復(fù)雜需求還無法得到很好的解決。本文以目前應(yīng)用較為普遍的A*算法為例。
A*算法是一類啟發(fā)式的路徑搜索算法,從起點開始逐漸向目標點靠近,它在Dijkstra算法的基礎(chǔ)上引入啟發(fā)函數(shù)來篩選訪問節(jié)點,從而降低了計算量,提高了搜索效率。但是啟發(fā)函數(shù)選取好壞直接關(guān)系到A*算法的搜索速度和搜索精度。本文取A*算法的代價函數(shù)如公式
fn=gn+hn (5)
所示,其中fn為機器人從起點經(jīng)過節(jié)點n到達目標節(jié)點的估價函數(shù),gn為起點到節(jié)點n的實際成本,n為節(jié)點n到目標節(jié)點的啟發(fā)式評估代價。本文h
使用公式
所示的曼哈頓距離作為hn,其中(n.x,n.y)表示節(jié)點n的橫縱坐標,(target.x,target.y)表示目標節(jié)點的橫縱坐標,abs表示求絕對值的函數(shù)。
針對圖9所示任務(wù),同樣按照從上到下,從左到右的順序選取任務(wù)貨架,采用A*算法規(guī)劃所得路徑如圖10所示。當選取貨架的順序發(fā)生變化時,采用A*算法規(guī)劃的路徑也會隨之變化。對比圖9和圖10可以看出,基于LTL理論的倉儲機器人路徑規(guī)劃方法尋優(yōu)所得路徑明顯優(yōu)于A*算法規(guī)劃所得路徑,且基于LTL理論的倉儲機器人路徑規(guī)劃方法與任務(wù)順序無關(guān),始終能夠確保規(guī)劃所得路徑的最優(yōu)性。
此外,A*算法只能針對“從a點到b點,途中避開障礙物”等這類簡單任務(wù),且當原有的已知環(huán)境中出現(xiàn)障礙物時需要對環(huán)境模型作相應(yīng)的修改,實現(xiàn)起來較為繁瑣。而基于LTL理論的路徑規(guī)劃方法可以很好地描述實際應(yīng)用中較為復(fù)雜的任務(wù)需求,諸如始終保持一定的范圍之內(nèi)(安全性),按序訪問某幾個點(保證性)后,巡回訪問某幾個點(循環(huán)性),圖中避開某些點(避障),到達某些點后必須到達另外一些點才能繼續(xù)任務(wù)(反應(yīng)性)等。
如圖4所示的環(huán)境和任務(wù),當節(jié)點14暢通時采用基于線性時序邏輯路徑規(guī)劃方法規(guī)劃所得路徑和采用A*算法規(guī)劃所得路徑相同,結(jié)果如圖11所示。但當節(jié)點p14出現(xiàn)突發(fā)狀況(節(jié)點p14所示區(qū)域遇堵等)機器人無法通過時,采用A*算法進行規(guī)劃時需要將環(huán)境模型中節(jié)點p14標記為障礙物,對原有的環(huán)境模型進行修改;而采用基于LTL的路徑規(guī)劃方法則只需要在選取任務(wù)貨架的同時將節(jié)點p14標記為障礙物,則對應(yīng)生成的任務(wù)公式為
Fp1&Fp23&Fp24&Fp25&GFp2&Gp14 (7)其規(guī)劃所得路徑如圖12所示,繞開了無法通過的節(jié)點p14,仍然可以確保規(guī)劃所得路徑的最優(yōu)性。
其它倉儲機器人路徑規(guī)劃算法在上述的對比實驗中與A*算法類似,需要對任務(wù)進行分段路徑尋優(yōu),規(guī)劃所得路徑與任務(wù)節(jié)點順序有關(guān),無法保證最優(yōu)性;當環(huán)境發(fā)生變化時需要根據(jù)當前環(huán)境對原有的環(huán)境模型進行修改,相比之下本文所提出的方法能夠更好地適用于倉儲機器人的應(yīng)用。
隨著電子商務(wù)的飛速發(fā)展,各大電商對基于移動機器人的自動化倉儲物流技術(shù)的需求越來越迫切。本文對倉儲物流機器人路徑規(guī)劃方法的研究與應(yīng)用進行了探索:建立了一個可靈活擴展的倉儲環(huán)境模型,有效地描述了倉儲物流應(yīng)用中的各類任務(wù)需求,并將倉儲環(huán)境信息與任務(wù)需求相融合,從而規(guī)劃出既滿足任務(wù)需求又符合環(huán)境信息的最優(yōu)路徑。實驗結(jié)果表明,與傳統(tǒng)方法相比,本文的方法不僅可以靈活地擴展環(huán)境模型,而且能夠更好地適應(yīng)實際應(yīng)用中較為復(fù)雜的任務(wù),較傳統(tǒng)的路徑規(guī)劃方法的適用性更強,適用范圍更廣;此外,本文所提出的方法無需對任務(wù)進行分段的點到點規(guī)劃,與任務(wù)節(jié)點的順序無關(guān),保證了規(guī)劃所得路徑的最優(yōu)性。因此,基于LTL理論的倉儲機器人路徑規(guī)劃方法能夠滿足實際的應(yīng)用需求,大大提高倉儲物流機器人的工作效率。
本文主要探究了倉儲物流機器人的路徑規(guī)劃問題,未來還可以拓展到多機器人領(lǐng)域,實現(xiàn)一套高度自動化的倉儲物流機器人系統(tǒng),更好地將機器人應(yīng)用到倉儲物流領(lǐng)域中去。
權(quán)所有©:上海陽合儲運
專業(yè)承接上海倉庫租賃、上海倉儲配送物流、上海電商倉儲企業(yè)服務(wù)與微笑同在"的先進理念不斷發(fā)展壯大。