精品久久一区,污黄啪啪网,16女下面流水不遮视频,色婷五月天

隨著電子商務(wù)的飛速發(fā)展,傳統(tǒng)的倉(cāng)儲(chǔ)物流已無(wú)法適應(yīng)現(xiàn)代物流品種多、批量小、批次多、周期短的特點(diǎn),而基于移動(dòng)機(jī)器人的自動(dòng)化倉(cāng)儲(chǔ)物流技術(shù)研究了基于線性時(shí)序邏輯(LTL)理論規(guī)劃倉(cāng)儲(chǔ)機(jī)器人路徑的方法。得到了應(yīng)用和發(fā)展,目前倉(cāng)儲(chǔ)物流業(yè)已成為繼汽車(chē)行業(yè)后的第二大機(jī)器人應(yīng)用領(lǐng)域[1]。倉(cāng)儲(chǔ)物流機(jī)器人的應(yīng)用可以大大提高電商倉(cāng)儲(chǔ)物流工作的效率,緩解當(dāng)前倉(cāng)儲(chǔ)物流行業(yè)供不應(yīng)求的現(xiàn)狀。機(jī)器人應(yīng)用的目的是提高電商的庫(kù)存管理能力與配載能力,而實(shí)現(xiàn)這樣的目的的核心技術(shù)是機(jī)器人的路徑規(guī)劃。路徑規(guī)劃是指根據(jù)當(dāng)前倉(cāng)儲(chǔ)物流物品種類(lèi)多、倉(cāng)儲(chǔ)面積大的特點(diǎn),按照貨單需求規(guī)劃出合理的機(jī)器人路徑,以提高倉(cāng)儲(chǔ)機(jī)器人的作業(yè)效率。本研究根據(jù)實(shí)際應(yīng)用要求,提出了一種基于線性時(shí)序邏輯(linear temporal logic,LTL)理論的倉(cāng)儲(chǔ)移動(dòng)機(jī)器人路徑規(guī)劃方法,該方法可根據(jù)實(shí)際的倉(cāng)儲(chǔ)環(huán)境和任務(wù)需求,規(guī)劃出符合環(huán)境信息的最優(yōu)路徑,確保機(jī)器人完成指定任務(wù)的運(yùn)行路徑總長(zhǎng)度最短,提高倉(cāng)儲(chǔ)工作整體的工作效率。與傳統(tǒng)的方法相比,本文所提出的方法在確保規(guī)劃路徑最優(yōu)的基礎(chǔ)上能夠較好的適用于倉(cāng)儲(chǔ)物流環(huán)境。

目前倉(cāng)儲(chǔ)機(jī)器人的應(yīng)用研究主要集中在調(diào)度和避碰問(wèn)題上,對(duì)針對(duì)具體環(huán)境和具體任務(wù)的路徑規(guī)劃的研究較少。文獻(xiàn)[2]在傳統(tǒng)的A*算法(一類(lèi)啟發(fā)式的路徑搜索算法)中引入時(shí)間參量,將平面二維的A*算法擴(kuò)展到平面空間加時(shí)間的三維時(shí)空中,同時(shí)引入暫停機(jī)制避免機(jī)器人之間發(fā)生碰撞,結(jié)合分層的路徑規(guī)劃算法減少了計(jì)算量;文獻(xiàn)[3]將機(jī)器人調(diào)度與特殊規(guī)則約束下基于A*算法的路徑規(guī)劃相結(jié)合實(shí)現(xiàn)了倉(cāng)儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃;文獻(xiàn)[4]采用改進(jìn)的遺傳算法和SHAA神經(jīng)網(wǎng)絡(luò)算法主要解決了多機(jī)器人避碰問(wèn)題;文獻(xiàn)[5]提出了一種PUSH-SWAP的方法來(lái)避免多移動(dòng)機(jī)器人之間的碰撞。此外,現(xiàn)有的路徑規(guī)劃方法還有諸如人工勢(shì)場(chǎng)法[6]、A*算法[7]、快速擴(kuò)展隨機(jī)樹(shù)(rapiddy-exploring random tree,RRT)算法[8]等都是針對(duì)簡(jiǎn)單的點(diǎn)到點(diǎn)的路徑規(guī)劃任務(wù)。然而,上述方法仍然存在很大的瓶頸,無(wú)法很好的適用于倉(cāng)儲(chǔ)機(jī)器人這類(lèi)包含多點(diǎn)訪問(wèn)等復(fù)雜任務(wù)需求的應(yīng)用中。

線性時(shí)序邏輯(LTL)語(yǔ)言[9]可以描述倉(cāng)儲(chǔ)物流機(jī)器人實(shí)際應(yīng)用中較為復(fù)雜的任務(wù)需求,諸如在倉(cāng)庫(kù)環(huán)境中從起點(diǎn)出發(fā)先后到若干個(gè)貨架取貨后回到指定點(diǎn),途中規(guī)避某些區(qū)域等。目前,基于LTL理論的路徑規(guī)劃方法的研究主要集中在解決旅行商(TSP)問(wèn)題上,文獻(xiàn)[10,11]采用了最小瓶頸環(huán)法解決了單機(jī)器人多點(diǎn)巡回的問(wèn)題;文獻(xiàn)[12]針對(duì)傳統(tǒng)方法無(wú)法直接解決多點(diǎn)最優(yōu)巡回問(wèn)題,采用基于擴(kuò)展乘積自動(dòng)機(jī)的最優(yōu)巡回算法尋優(yōu)路徑;文獻(xiàn)[13]在傳統(tǒng)方法的基礎(chǔ)上加入了時(shí)序要求,針對(duì)兩機(jī)器人同時(shí)巡回某些點(diǎn)的問(wèn)題,采用了同步序列法生成同步路徑以保證兩機(jī)器人的同時(shí)性;文獻(xiàn)[14]將基于LTL理論的路徑規(guī)劃方法擴(kuò)展到有時(shí)間限制的動(dòng)態(tài)環(huán)境中。然而,上述方法由于無(wú)法靈活的應(yīng)用于動(dòng)態(tài)的倉(cāng)儲(chǔ)環(huán)境、無(wú)法保證最優(yōu)性、計(jì)算量大、路徑尋優(yōu)時(shí)間長(zhǎng)等不足,都無(wú)法滿足倉(cāng)儲(chǔ)物流機(jī)器人的應(yīng)用需求。

機(jī)器人的效率與倉(cāng)儲(chǔ)物流系統(tǒng)的運(yùn)作效率直接相關(guān)。因此,需要為倉(cāng)儲(chǔ)機(jī)器人設(shè)計(jì)一種有效的算法來(lái)控制機(jī)器人按指定任務(wù)在倉(cāng)庫(kù)中運(yùn)行,并且能實(shí)現(xiàn)路徑最優(yōu),從而最大限度地提高倉(cāng)儲(chǔ)物流系統(tǒng)的整體運(yùn)作效率。

傳統(tǒng)的路徑規(guī)劃方法,諸如A*算法、人工勢(shì)場(chǎng)法、RRT算法等都需要根據(jù)任務(wù)節(jié)點(diǎn)順序,按序分段進(jìn)行規(guī)劃,規(guī)劃所得路徑受任務(wù)節(jié)點(diǎn)的數(shù)目和順序影響,無(wú)法保證規(guī)劃所得路徑的最優(yōu)性。本文所采用的基于線性時(shí)序邏輯的路徑規(guī)劃方法將環(huán)境信息與任務(wù)需求相融合,構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓?fù)浯_保了尋優(yōu)所得路徑不受任務(wù)節(jié)點(diǎn)順序的影響;此外,采用Dijkstra算法來(lái)搜索路徑保證了規(guī)劃所得路徑的最優(yōu)性。

本文采用基于線性時(shí)序邏輯理論的路徑規(guī)劃方法尋優(yōu)路徑,其具體算法流程圖如圖1所示,主要分為環(huán)境建模與任務(wù)描述和路徑尋優(yōu)兩個(gè)部分。首先,將機(jī)器人運(yùn)行環(huán)境構(gòu)建為可擴(kuò)展的加權(quán)切換系統(tǒng);然后,采用線性時(shí)序任務(wù)公式描述任務(wù)需求,并通過(guò)LTL2BA工具包將其轉(zhuǎn)換為圖表形式(Buchi自動(dòng)機(jī))[15];接著,將加權(quán)切換系統(tǒng)與Buchi自動(dòng)機(jī)作笛卡爾乘積構(gòu)成任務(wù)可行網(wǎng)絡(luò)拓?fù)?Product自動(dòng)機(jī))[16];之后,采用Dijkstra算法[17]在任務(wù)可行網(wǎng)絡(luò)拓?fù)渖纤殉鲎顑?yōu)路徑;最后,將任務(wù)可行網(wǎng)絡(luò)拓?fù)渖蠈?yōu)所得路徑映射回加權(quán)切換系統(tǒng)得到環(huán)境中對(duì)應(yīng)的最優(yōu)路徑。

圖1 基于LTL的路徑規(guī)劃方法流程圖  下載原圖

由于實(shí)際的倉(cāng)儲(chǔ)環(huán)境中貨架數(shù)量非常多,在構(gòu)建環(huán)境模型時(shí)若把所有的貨架信息都包含進(jìn)去,會(huì)導(dǎo)致環(huán)境模型太過(guò)復(fù)雜,增加路徑規(guī)劃的計(jì)算量。因此,本文構(gòu)建了一個(gè)可靈活擴(kuò)展的環(huán)境模型,選取環(huán)境中固定的路徑節(jié)點(diǎn)構(gòu)建環(huán)境模型,當(dāng)選定任務(wù)貨架后再對(duì)環(huán)境模型進(jìn)行擴(kuò)展,以此降低環(huán)境模型的復(fù)雜度,從而降低計(jì)算量。另外,傳統(tǒng)的路徑規(guī)劃方法只能針對(duì)點(diǎn)到點(diǎn)的路徑規(guī)劃,無(wú)法很好地描述倉(cāng)儲(chǔ)物流應(yīng)用中諸如連續(xù)多點(diǎn)訪問(wèn)等復(fù)雜任務(wù)需求,因而本文采用線性時(shí)序任務(wù)公式對(duì)倉(cāng)儲(chǔ)環(huán)境中的任務(wù)進(jìn)行描述,使其能夠適用于實(shí)際應(yīng)用中各類(lèi)復(fù)雜的任務(wù)需求。

假設(shè)倉(cāng)儲(chǔ)環(huán)境如圖2所示,其中帶箭頭矩形代表機(jī)器人,淺灰色矩形代表存放不同貨物的各個(gè)貨架,左上角為倉(cāng)儲(chǔ)機(jī)器人起點(diǎn)和出貨的柜臺(tái),當(dāng)柜臺(tái)接到取貨單時(shí)需要規(guī)劃出最優(yōu)的取貨路徑,然后讓機(jī)器人按指定路徑去取貨,如圖2所示深灰色矩形為貨單上貨物對(duì)應(yīng)的貨架。

圖2 模擬倉(cāng)庫(kù)環(huán)境示意圖  下載原圖

圖2 模擬倉(cāng)庫(kù)環(huán)境示意圖  下載原圖

本文將機(jī)器人在環(huán)境當(dāng)中的運(yùn)動(dòng)建立成一個(gè)可靈活擴(kuò)展的加權(quán)切換系統(tǒng)模型。加權(quán)切換系統(tǒng)模型[18]是一種圖表,它以環(huán)境中的關(guān)鍵位置為節(jié)點(diǎn),如果機(jī)器人能從一個(gè)位置行駛至另一個(gè)位置,則這兩個(gè)節(jié)點(diǎn)間有邊相連。每條邊都標(biāo)有相應(yīng)的權(quán)值,表示機(jī)器人從一個(gè)節(jié)點(diǎn)行駛至另一個(gè)節(jié)點(diǎn)的成本。本文用一個(gè)元組

來(lái)表示機(jī)器人運(yùn)行環(huán)境對(duì)應(yīng)的加權(quán)切換系統(tǒng)模型。其中,Q為一個(gè)有限狀態(tài)集,其每一個(gè)狀態(tài)代表環(huán)境中道路網(wǎng)絡(luò)的一個(gè)節(jié)點(diǎn);q?！蔘代表初始狀態(tài),即機(jī)器人在環(huán)境中所處的初始節(jié)點(diǎn);代表切換關(guān)系,即環(huán)境中節(jié)點(diǎn)間的連通狀態(tài);∏為一個(gè)原子命題集合;ζ:Q→2∏是狀態(tài)的命題函數(shù);ω:R→R>0代表切換權(quán)重,代表機(jī)器人在環(huán)境中從一個(gè)節(jié)點(diǎn)切換到另一節(jié)點(diǎn)所需的成本(如運(yùn)行時(shí)間、路徑長(zhǎng)度等)。

以圖3所示的模擬倉(cāng)庫(kù)環(huán)境模型為例,其中p1為起點(diǎn),p2為終點(diǎn),空白矩形代表各個(gè)存放不同貨物的貨架。倉(cāng)儲(chǔ)機(jī)器人需要從起點(diǎn)出發(fā),到指定貨架取貨后將貨物送回到終點(diǎn)。本文選取倉(cāng)庫(kù)環(huán)境中的22個(gè)關(guān)鍵節(jié)點(diǎn)作為路徑節(jié)點(diǎn),其中節(jié)點(diǎn)p1和p2分別表示機(jī)器人的起點(diǎn)和終點(diǎn),即倉(cāng)庫(kù)接單和出貨的柜臺(tái)。通過(guò)一個(gè)22×22的鄰接矩陣T.adj來(lái)描述各節(jié)點(diǎn)間的連通情況,以及任意兩節(jié)點(diǎn)間的切換成本,即機(jī)器人需要運(yùn)行的距離,其中T.adj的每一行都代表該行對(duì)應(yīng)節(jié)點(diǎn)與其他節(jié)點(diǎn)的連通情況即切換成本。如T.adj的第一行第二列代表節(jié)點(diǎn)p1到節(jié)點(diǎn)p2的連通情況和切換成本,第二行第三列代表節(jié)點(diǎn)p2到節(jié)點(diǎn)p3的連通情況和切換成本,依此類(lèi)推。

圖3 模擬倉(cāng)庫(kù)環(huán)境模型  下載原圖

然后,當(dāng)倉(cāng)庫(kù)接到貨單時(shí),根據(jù)貨單上的貨物所在的貨架選取對(duì)應(yīng)的貨架節(jié)點(diǎn),選定目標(biāo)貨架后的環(huán)境模型如圖4所示,深灰色貨架即為機(jī)器人需要取貨的貨架,淺灰色節(jié)點(diǎn)即為貨架對(duì)應(yīng)的路徑節(jié)點(diǎn)。根據(jù)任務(wù)貨架節(jié)點(diǎn)數(shù)量擴(kuò)展鄰接矩陣T.adj,以圖4所示的任務(wù)為例,需要將T.adj擴(kuò)展為25×25的方陣。

圖4 選定目標(biāo)貨架后的環(huán)境模型  下載原圖

同時(shí),當(dāng)倉(cāng)庫(kù)接到貨單選定任務(wù)貨架后,需要對(duì)任務(wù)進(jìn)行描述。本文采用線性時(shí)序邏輯(LTL)公式來(lái)描述倉(cāng)儲(chǔ)物流機(jī)器人需要完成的復(fù)雜任務(wù)需求。線性時(shí)序邏輯公式φ是由原子命題∏的子集組成的表達(dá)式,其中還包含了布爾算子(非)、∧(與)、∨(或),以及時(shí)序邏輯算子G (始終)、F(最終)、X(接下來(lái))和U(直到)。例如,G P1表示T中狀態(tài)p1始終為真;F p1表示最終達(dá)到T中的狀態(tài)p1;X p1表示接下來(lái)到達(dá)T中的狀態(tài)p1;公式p1 U p2表示當(dāng)?shù)竭_(dá)p1狀態(tài)時(shí),必須到達(dá)狀態(tài)p2才能前往下一個(gè)狀態(tài)。將這些時(shí)序和布爾算子組合可以描述更為復(fù)雜的任務(wù)需求。

以圖4為例,任務(wù)需求:“機(jī)器人從P1節(jié)點(diǎn)出發(fā),先后到p23、p24和p25這三個(gè)節(jié)點(diǎn)取貨,然后回到p2節(jié)點(diǎn)將取回的貨物打包出倉(cāng)”。采用線性時(shí)序邏輯任務(wù)公式可以描述為

其中,起點(diǎn)T.q0=p1。

在得到式(2)所示的任務(wù)公式后,首先,采用LTL2BA工具包將其轉(zhuǎn)換為圖表的形式(Buchi自動(dòng)機(jī))。由于任務(wù)式(2)轉(zhuǎn)換后的圖表較為復(fù)雜,這里以任務(wù)公式

為例。假設(shè)機(jī)器人從p1出發(fā),到p2取貨后最終回到p3。圖5即為式(3)轉(zhuǎn)換后的結(jié)果。環(huán)境模型以圖6所示的加權(quán)切換系統(tǒng)圖為例,可以用一個(gè)4×4的鄰接矩陣來(lái)描述各節(jié)點(diǎn)間的連通情況,以及任意兩節(jié)點(diǎn)間的切換成本。

然后,將轉(zhuǎn)換所得Buchi自動(dòng)機(jī)與加權(quán)切換系統(tǒng)作笛卡爾乘積,得到任務(wù)可行網(wǎng)絡(luò)拓?fù)?Product自動(dòng)機(jī))。圖7所示即為圖6所示加權(quán)切換系統(tǒng)與圖5所示Büchi自動(dòng)機(jī)作笛卡爾乘積后所得的任務(wù)可行網(wǎng)絡(luò)拓?fù)?該拓?fù)浒谁h(huán)境信息和任務(wù)需求。其中,第一行包含S0的狀態(tài)為初始狀態(tài),最后一行包含S4的狀態(tài)為最終的接收狀態(tài)。

圖5 式(2)對(duì)應(yīng)的Büchi自動(dòng)機(jī)  下載原圖

圖6 加權(quán)切換系統(tǒng)例圖  下載原圖

圖7 任務(wù)可行網(wǎng)絡(luò)拓?fù)?a>  下載原圖

接著,采用Dijkstra算法在任務(wù)可行網(wǎng)絡(luò)拓?fù)渖纤阉鞒鰪钠鹗紶顟B(tài)到接收狀態(tài)的最優(yōu)路徑。如圖7中實(shí)線箭頭所示路徑即為采用Dijkstra算法在任務(wù)可行網(wǎng)絡(luò)拓?fù)渖纤阉鲝某跏紶顟B(tài)到最終狀態(tài)實(shí)驗(yàn)所得路徑結(jié)果,即(P0,s0)→(p2,s0)→(P1,s1)→(p3,s3),其中狀態(tài)S3與狀態(tài)S4之間的切換為式(3)中GFp3部分的自循環(huán),所以可以忽略不計(jì)。從圖中可以看出該路徑的總權(quán)重值是最小的,且路徑節(jié)點(diǎn)數(shù)是最少的,因此規(guī)劃所得路徑是最優(yōu)的。由于Dijkstra算法實(shí)質(zhì)是廣度優(yōu)先搜索,因此可以確保路徑的最優(yōu)性。

最后,在得到任務(wù)可行網(wǎng)絡(luò)拓?fù)渖系淖顑?yōu)路徑后,還需將其映射回初始的加權(quán)切換系統(tǒng)中,得到倉(cāng)庫(kù)環(huán)境中完成指定任務(wù)的最優(yōu)路徑,于是引入如下引理:

引理1 (Product自動(dòng)機(jī)路徑映射)[19]對(duì)于任務(wù)可行網(wǎng)絡(luò)拓?fù)渖系娜我饴窂絩p=(p0,s0)(p1,s1)(p2,s2)…,路徑序列rT=P0P1P2…為加權(quán)切換系統(tǒng)中對(duì)應(yīng)的滿足任務(wù)需求的路徑,且rP和rT所對(duì)應(yīng)的權(quán)重相等。

根據(jù)引理1,路徑p0→p2→p1→p3即為圖7所示的任務(wù)可行網(wǎng)絡(luò)拓?fù)渖献顑?yōu)路徑映射回圖6所示的加權(quán)切換系統(tǒng)后所得路徑,即圖6所示的環(huán)境模型中滿足任務(wù)公式(3)的最優(yōu)路徑。

其具體算法如下:

輸入:倉(cāng)儲(chǔ)環(huán)境對(duì)應(yīng)的加權(quán)切換系統(tǒng)模型T;

輸出:倉(cāng)庫(kù)環(huán)境中滿足任務(wù)需求的最優(yōu)路徑rT;

1)選定任務(wù)貨架;

2)根據(jù)選取的目標(biāo)貨架擴(kuò)展加權(quán)切換系統(tǒng)模型T,用線性時(shí)序任務(wù)公式φ描述任務(wù)需求;

3)將線性時(shí)序任務(wù)公式φ轉(zhuǎn)換為圖表的形式,即Buchi自動(dòng)機(jī)B=LTL2BA(Φ);

4)構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓?fù)?

5)采用Dijkatra算法在任務(wù)可行網(wǎng)絡(luò)拓?fù)銹上搜索出一條從初始狀態(tài)到最終狀態(tài)的最優(yōu)路徑rP;

6)將P上尋優(yōu)所得路徑rP映射回加權(quán)切換系統(tǒng),得到倉(cāng)庫(kù)環(huán)境中滿足任務(wù)需求的最優(yōu)路徑rT。

為了驗(yàn)證上述方法的可行性與有效性,本文在MATLAB中采用GUI編程對(duì)上述方法進(jìn)行了仿真驗(yàn)證,其程序操作界面如圖8所示,圖中的模擬倉(cāng)庫(kù)環(huán)境對(duì)應(yīng)的模擬倉(cāng)庫(kù)環(huán)境模型如圖3所示。其中,起點(diǎn)代表倉(cāng)儲(chǔ)機(jī)器人的起始位置,對(duì)應(yīng)圖3中的p1節(jié)點(diǎn);終點(diǎn)代表倉(cāng)儲(chǔ)機(jī)器人完成取貨后需要到達(dá)的最終位置,對(duì)應(yīng)圖3中的p2節(jié)點(diǎn);界面中的小正方形代表倉(cāng)庫(kù)中存放貨物的貨架,倉(cāng)儲(chǔ)機(jī)器人需要按照需求到指定的貨架取貨,若需要倉(cāng)儲(chǔ)機(jī)器人到該貨架取貨則用鼠標(biāo)左鍵單擊選中對(duì)應(yīng)貨架;若環(huán)境中某一路徑節(jié)點(diǎn)發(fā)生變化無(wú)法繼續(xù)通行,則用鼠標(biāo)右鍵單擊對(duì)應(yīng)位置,將其標(biāo)記為障礙物;在選取好任務(wù)貨架和障礙物節(jié)點(diǎn)后點(diǎn)擊“規(guī)劃路徑”按鍵進(jìn)行路徑尋優(yōu)。

圖8 仿真程序操作界面示意圖  下載原圖

在圖3所示的倉(cāng)儲(chǔ)環(huán)境模型中,任意指定7個(gè)任務(wù)貨架,如圖9中深灰色矩形所示,選取的順序?yàn)閺纳系较?從左到右。機(jī)器人需要從p1節(jié)點(diǎn)出發(fā),分別到p23、p24、p25、p26、p27、p28和p29這7個(gè)節(jié)點(diǎn)對(duì)應(yīng)的貨架取貨,然后將貨物送回到p2。

首先,將圖3所示的包含22節(jié)點(diǎn)的倉(cāng)儲(chǔ)環(huán)境模型擴(kuò)展到29節(jié)點(diǎn),對(duì)應(yīng)的22×22的鄰接矩陣T.adj也擴(kuò)展為29×29的方陣;其次,采用線性時(shí)序任務(wù)公式描述給定的任務(wù)需求,如下式所示:

然后,將式(4)轉(zhuǎn)換為Buchi自動(dòng)機(jī)B;接著,將環(huán)境對(duì)應(yīng)的加權(quán)切換系統(tǒng)T與B作笛卡爾乘積,構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓?fù)銹;然后,采用Dijkstra算法在P上搜索出最優(yōu)路徑;最后,將P上尋優(yōu)所得路徑映射回加權(quán)切換系統(tǒng),獲得環(huán)境中對(duì)應(yīng)的最優(yōu)路徑。圖9中深灰色直線即為尋優(yōu)所得路徑。從圖中可以看出基于線性時(shí)序邏輯理論的倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃方法能夠規(guī)劃出既符合環(huán)境信息,又滿足任務(wù)需求的最優(yōu)路徑。

圖9 本文方法規(guī)劃所得路徑  下載原圖

接下來(lái),本文將上述方法與傳統(tǒng)方法做進(jìn)一步的仿真比較。目前已有的路徑規(guī)劃方法有很多,但基本都針對(duì)“從a點(diǎn)到b點(diǎn),途中避開(kāi)障礙物”這類(lèi)簡(jiǎn)單的任務(wù),對(duì)于倉(cāng)儲(chǔ)機(jī)器人這類(lèi)需要從起點(diǎn)出發(fā),到多點(diǎn)取貨后回到終點(diǎn)的復(fù)雜需求還無(wú)法得到很好的解決。本文以目前應(yīng)用較為普遍的A*算法為例。

A*算法是一類(lèi)啟發(fā)式的路徑搜索算法,從起點(diǎn)開(kāi)始逐漸向目標(biāo)點(diǎn)靠近,它在Dijkstra算法的基礎(chǔ)上引入啟發(fā)函數(shù)來(lái)篩選訪問(wèn)節(jié)點(diǎn),從而降低了計(jì)算量,提高了搜索效率。但是啟發(fā)函數(shù)選取好壞直接關(guān)系到A*算法的搜索速度和搜索精度。本文取A*算法的代價(jià)函數(shù)如公式

fn=gn+hn (5)

所示,其中fn為機(jī)器人從起點(diǎn)經(jīng)過(guò)節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的估價(jià)函數(shù),gn為起點(diǎn)到節(jié)點(diǎn)n的實(shí)際成本,n為節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的啟發(fā)式評(píng)估代價(jià)。本文h

使用公式

所示的曼哈頓距離作為hn,其中(n.x,n.y)表示節(jié)點(diǎn)n的橫縱坐標(biāo),(target.x,target.y)表示目標(biāo)節(jié)點(diǎn)的橫縱坐標(biāo),abs表示求絕對(duì)值的函數(shù)。

針對(duì)圖9所示任務(wù),同樣按照從上到下,從左到右的順序選取任務(wù)貨架,采用A*算法規(guī)劃所得路徑如圖10所示。當(dāng)選取貨架的順序發(fā)生變化時(shí),采用A*算法規(guī)劃的路徑也會(huì)隨之變化。對(duì)比圖9和圖10可以看出,基于LTL理論的倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃方法尋優(yōu)所得路徑明顯優(yōu)于A*算法規(guī)劃所得路徑,且基于LTL理論的倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃方法與任務(wù)順序無(wú)關(guān),始終能夠確保規(guī)劃所得路徑的最優(yōu)性。

圖1 0 A*算法規(guī)劃所得路徑  下載原圖

此外,A*算法只能針對(duì)“從a點(diǎn)到b點(diǎn),途中避開(kāi)障礙物”等這類(lèi)簡(jiǎn)單任務(wù),且當(dāng)原有的已知環(huán)境中出現(xiàn)障礙物時(shí)需要對(duì)環(huán)境模型作相應(yīng)的修改,實(shí)現(xiàn)起來(lái)較為繁瑣。而基于LTL理論的路徑規(guī)劃方法可以很好地描述實(shí)際應(yīng)用中較為復(fù)雜的任務(wù)需求,諸如始終保持一定的范圍之內(nèi)(安全性),按序訪問(wèn)某幾個(gè)點(diǎn)(保證性)后,巡回訪問(wèn)某幾個(gè)點(diǎn)(循環(huán)性),圖中避開(kāi)某些點(diǎn)(避障),到達(dá)某些點(diǎn)后必須到達(dá)另外一些點(diǎn)才能繼續(xù)任務(wù)(反應(yīng)性)等。

如圖4所示的環(huán)境和任務(wù),當(dāng)節(jié)點(diǎn)14暢通時(shí)采用基于線性時(shí)序邏輯路徑規(guī)劃方法規(guī)劃所得路徑和采用A*算法規(guī)劃所得路徑相同,結(jié)果如圖11所示。但當(dāng)節(jié)點(diǎn)p14出現(xiàn)突發(fā)狀況(節(jié)點(diǎn)p14所示區(qū)域遇堵等)機(jī)器人無(wú)法通過(guò)時(shí),采用A*算法進(jìn)行規(guī)劃時(shí)需要將環(huán)境模型中節(jié)點(diǎn)p14標(biāo)記為障礙物,對(duì)原有的環(huán)境模型進(jìn)行修改;而采用基于LTL的路徑規(guī)劃方法則只需要在選取任務(wù)貨架的同時(shí)將節(jié)點(diǎn)p14標(biāo)記為障礙物,則對(duì)應(yīng)生成的任務(wù)公式為

Fp1&Fp23&Fp24&Fp25&GFp2&Gp14 (7)其規(guī)劃所得路徑如圖12所示,繞開(kāi)了無(wú)法通過(guò)的節(jié)點(diǎn)p14,仍然可以確保規(guī)劃所得路徑的最優(yōu)性。

圖1 2 節(jié)點(diǎn)p14遇阻規(guī)劃結(jié)果圖1 2 節(jié)點(diǎn)p14遇阻規(guī)劃結(jié)果  下載原圖

其它倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃算法在上述的對(duì)比實(shí)驗(yàn)中與A*算法類(lèi)似,需要對(duì)任務(wù)進(jìn)行分段路徑尋優(yōu),規(guī)劃所得路徑與任務(wù)節(jié)點(diǎn)順序有關(guān),無(wú)法保證最優(yōu)性;當(dāng)環(huán)境發(fā)生變化時(shí)需要根據(jù)當(dāng)前環(huán)境對(duì)原有的環(huán)境模型進(jìn)行修改,相比之下本文所提出的方法能夠更好地適用于倉(cāng)儲(chǔ)機(jī)器人的應(yīng)用。

隨著電子商務(wù)的飛速發(fā)展,各大電商對(duì)基于移動(dòng)機(jī)器人的自動(dòng)化倉(cāng)儲(chǔ)物流技術(shù)的需求越來(lái)越迫切。本文對(duì)倉(cāng)儲(chǔ)物流機(jī)器人路徑規(guī)劃方法的研究與應(yīng)用進(jìn)行了探索:建立了一個(gè)可靈活擴(kuò)展的倉(cāng)儲(chǔ)環(huán)境模型,有效地描述了倉(cāng)儲(chǔ)物流應(yīng)用中的各類(lèi)任務(wù)需求,并將倉(cāng)儲(chǔ)環(huán)境信息與任務(wù)需求相融合,從而規(guī)劃出既滿足任務(wù)需求又符合環(huán)境信息的最優(yōu)路徑。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)方法相比,本文的方法不僅可以靈活地?cái)U(kuò)展環(huán)境模型,而且能夠更好地適應(yīng)實(shí)際應(yīng)用中較為復(fù)雜的任務(wù),較傳統(tǒng)的路徑規(guī)劃方法的適用性更強(qiáng),適用范圍更廣;此外,本文所提出的方法無(wú)需對(duì)任務(wù)進(jìn)行分段的點(diǎn)到點(diǎn)規(guī)劃,與任務(wù)節(jié)點(diǎn)的順序無(wú)關(guān),保證了規(guī)劃所得路徑的最優(yōu)性。因此,基于LTL理論的倉(cāng)儲(chǔ)機(jī)器人路徑規(guī)劃方法能夠滿足實(shí)際的應(yīng)用需求,大大提高倉(cāng)儲(chǔ)物流機(jī)器人的工作效率。

本文主要探究了倉(cāng)儲(chǔ)物流機(jī)器人的路徑規(guī)劃問(wèn)題,未來(lái)還可以拓展到多機(jī)器人領(lǐng)域,實(shí)現(xiàn)一套高度自動(dòng)化的倉(cāng)儲(chǔ)物流機(jī)器人系統(tǒng),更好地將機(jī)器人應(yīng)用到倉(cāng)儲(chǔ)物流領(lǐng)域中去。