基于線性時(shí)序邏輯理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃①

禹鑫燚 陳 浩 郭永奎 程 誠 歐林林 俞 立

?

基于線性時(shí)序邏輯理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃①

禹鑫燚②陳 浩 郭永奎 程 誠 歐林林③俞 立

(浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023)

首先根據(jù)倉儲(chǔ)物流環(huán)境的特點(diǎn)構(gòu)建了可靈活擴(kuò)展的倉儲(chǔ)環(huán)境模型，并制定了適合倉儲(chǔ)物流需求的機(jī)器人運(yùn)動(dòng)規(guī)則，使該模型能夠適用于動(dòng)態(tài)的倉儲(chǔ)物流環(huán)境；其次采用線性時(shí)序邏輯任務(wù)公式描述具體的任務(wù)需求，使其可以適用于實(shí)際應(yīng)用中更加復(fù)雜的任務(wù)；繼而將任務(wù)需求與環(huán)境信息相融合，構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓?fù)?，避免分段任?wù)搜索；然后采用Dijkstra算法在任務(wù)可行網(wǎng)絡(luò)拓?fù)渖纤阉鞒鲎顑?yōu)路徑，確保規(guī)劃所得路徑的最優(yōu)性；最后將任務(wù)可行網(wǎng)絡(luò)拓?fù)渖系淖顑?yōu)路徑映射回加權(quán)切換系統(tǒng)，獲得環(huán)境中滿足任務(wù)需求的最優(yōu)路徑。與目前廣泛使用的A*算法相比，上述方法不僅能夠滿足復(fù)雜的任務(wù)需求，而且能夠保證路徑規(guī)劃的最優(yōu)性，而不是次優(yōu)解。

路徑規(guī)劃， 線性時(shí)序邏輯(LTL)， 倉儲(chǔ)機(jī)器人，Dijkstra算法

0 引 言

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

1 相關(guān)研究

目前倉儲(chǔ)機(jī)器人的應(yīng)用研究主要集中在調(diào)度和避碰問題上，對(duì)針對(duì)具體環(huán)境和具體任務(wù)的路徑規(guī)劃的研究較少。文獻(xiàn)[2]在傳統(tǒng)的A*算法(一類啟發(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)了倉儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃；文獻(xiàn)[4]采用改進(jìn)的遺傳算法和SHAA神經(jīng)網(wǎng)絡(luò)算法主要解決了多機(jī)器人避碰問題；文獻(xiàn)[5]提出了一種PUSH-SWAP的方法來避免多移動(dòng)機(jī)器人之間的碰撞。此外，現(xiàn)有的路徑規(guī)劃方法還有諸如人工勢(shì)場(chǎng)法[6]、A*算法[7]、快速擴(kuò)展隨機(jī)樹(rapiddy-exploringrandomtree,RRT)算法[8]等都是針對(duì)簡單的點(diǎn)到點(diǎn)的路徑規(guī)劃任務(wù)。然而，上述方法仍然存在很大的瓶頸，無法很好的適用于倉儲(chǔ)機(jī)器人這類包含多點(diǎn)訪問等復(fù)雜任務(wù)需求的應(yīng)用中。

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

2 問題描述

機(jī)器人的效率與倉儲(chǔ)物流系統(tǒng)的運(yùn)作效率直接相關(guān)。因此，需要為倉儲(chǔ)機(jī)器人設(shè)計(jì)一種有效的算法來控制機(jī)器人按指定任務(wù)在倉庫中運(yùn)行，并且能實(shí)現(xiàn)路徑最優(yōu)，從而最大限度地提高倉儲(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ù)目和順序影響，無法保證規(guī)劃所得路徑的最優(yōu)性。本文所采用的基于線性時(shí)序邏輯的路徑規(guī)劃方法將環(huán)境信息與任務(wù)需求相融合，構(gòu)建任務(wù)可行網(wǎng)絡(luò)拓?fù)浯_保了尋優(yōu)所得路徑不受任務(wù)節(jié)點(diǎn)順序的影響；此外，采用Dijkstra算法來搜索路徑保證了規(guī)劃所得路徑的最優(yōu)性。

3 基于LTL理論的路徑規(guī)劃方法

本文采用基于線性時(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ù)需求，并通過LTL2BA工具包將其轉(zhuǎn)換為圖表形式(Büchi自動(dòng)機(jī))[15]；接著，將加權(quán)切換系統(tǒng)與Büchi自動(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ī)劃方法流程圖

3.1 環(huán)境建模與任務(wù)描述

由于實(shí)際的倉儲(chǔ)環(huán)境中貨架數(shù)量非常多，在構(gòu)建環(huán)境模型時(shí)若把所有的貨架信息都包含進(jìn)去，會(huì)導(dǎo)致環(huán)境模型太過復(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ī)劃，無法很好地描述倉儲(chǔ)物流應(yīng)用中諸如連續(xù)多點(diǎn)訪問等復(fù)雜任務(wù)需求，因而本文采用線性時(shí)序任務(wù)公式對(duì)倉儲(chǔ)環(huán)境中的任務(wù)進(jìn)行描述，使其能夠適用于實(shí)際應(yīng)用中各類復(fù)雜的任務(wù)需求。

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

圖2 模擬倉庫環(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è)元組

T=(Q,q0,R, ∏,ζ,ω)

(1)

來表示機(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)；q0∈Q代表初始狀態(tài)，即機(jī)器人在環(huán)境中所處的初始節(jié)點(diǎn)；R?Q×Q代表切換關(guān)系，即環(huán)境中節(jié)點(diǎn)間的連通狀態(tài)；∏為一個(gè)原子命題集合；ζ:Q→2∏是狀態(tài)的命題函數(shù)；ω:R→>0代表切換權(quán)重，代表機(jī)器人在環(huán)境中從一個(gè)節(jié)點(diǎn)切換到另一節(jié)點(diǎn)所需的成本(如運(yùn)行時(shí)間、路徑長度等)。

以圖3所示的模擬倉庫環(huán)境模型為例，其中p1為起點(diǎn)，p2為終點(diǎn)，空白矩形代表各個(gè)存放不同貨物的貨架。倉儲(chǔ)機(jī)器人需要從起點(diǎn)出發(fā)，到指定貨架取貨后將貨物送回到終點(diǎn)。本文選取倉庫環(huán)境中的22個(gè)關(guān)鍵節(jié)點(diǎn)作為路徑節(jié)點(diǎn)，其中節(jié)點(diǎn)p1和p2分別表示機(jī)器人的起點(diǎn)和終點(diǎn)，即倉庫接單和出貨的柜臺(tái)。通過一個(gè)22×22的鄰接矩陣T.adj來描述各節(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的連通情況和切換成本，依此類推。

圖3 模擬倉庫環(huán)境模型

然后，當(dāng)倉庫接到貨單時(shí)，根據(jù)貨單上的貨物所在的貨架選取對(duì)應(yīng)的貨架節(jié)點(diǎn)，選定目標(biāo)貨架后的環(huán)境模型如圖4所示，深灰色貨架即為機(jī)器人需要取貨的貨架，淺灰色節(jié)點(diǎn)即為貨架對(duì)應(yīng)的路徑節(jié)點(diǎn)。

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

根據(jù)任務(wù)貨架節(jié)點(diǎn)數(shù)量擴(kuò)展鄰接矩陣T.adj，以圖4所示的任務(wù)為例，需要將T.adj擴(kuò)展為25×25的方陣。

同時(shí)，當(dāng)倉庫接到貨單選定任務(wù)貨架后，需要對(duì)任務(wù)進(jìn)行描述。本文采用線性時(shí)序邏輯(LTL)公式來描述倉儲(chǔ)物流機(jī)器人需要完成的復(fù)雜任務(wù)需求。線性時(shí)序邏輯公式φ是由原子命題∏的子集組成的表達(dá)式，其中還包含了布爾算子(非)、∧(與)、∨(或)，以及時(shí)序邏輯算子G(始終)、F(最終)、X(接下來)和U(直到)。例如，Gp1表示T中狀態(tài)p1始終為真；Fp1表示最終達(dá)到T中的狀態(tài)p1；Xp1表示接下來到達(dá)T中的狀態(tài)p1；公式p1Up2表示當(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)將取回的貨物打包出倉”。采用線性時(shí)序邏輯任務(wù)公式可以描述為

Fp1&Fp23&Fp24&Fp25&GFp2

(2)

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

3.2 路徑尋優(yōu)

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

Fp1&Fp2&GFp3

(3)

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

然后，將轉(zhuǎn)換所得Büchi自動(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ù)?/p>

接著，采用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)中，得到倉庫環(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)路徑。

其具體算法如下：

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

輸出：倉庫環(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)換為圖表的形式，即Büchi自動(dòng)機(jī)B=LTL2BA(φ)；

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

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

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

4 仿真實(shí)驗(yàn)

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

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

在圖3所示的倉儲(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)的倉儲(chǔ)環(huán)境模型擴(kuò)展到29節(jié)點(diǎn)，對(duì)應(yīng)的22×22的鄰接矩陣T.adj也擴(kuò)展為29×29的方陣；其次，采用線性時(shí)序任務(wù)公式描述給定的任務(wù)需求，如下式所示：

Fp1&Fp23&Fp24&Fp25&Fp26&

Fp27&Fp28&Fp29&GFp2

(4)

然后，將式(4)轉(zhuǎn)換為Büchi自動(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í)序邏輯理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃方法能夠規(guī)劃出既符合環(huán)境信息，又滿足任務(wù)需求的最優(yōu)路徑。

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

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

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

fn=gn+hn

(5)

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

hn=abs(n.x-target.x)+abs(n.y-target.y)

(6)

所示的曼哈頓距離作為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理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃方法尋優(yōu)所得路徑明顯優(yōu)于A*算法規(guī)劃所得路徑，且基于LTL理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃方法與任務(wù)順序無關(guān)，始終能夠確保規(guī)劃所得路徑的最優(yōu)性。

圖10 A*算法規(guī)劃所得路徑

此外，A*算法只能針對(duì)“從a點(diǎn)到b點(diǎn)，途中避開障礙物”等這類簡單任務(wù)，且當(dāng)原有的已知環(huán)境中出現(xiàn)障礙物時(shí)需要對(duì)環(huán)境模型作相應(yīng)的修改，實(shí)現(xiàn)起來較為繁瑣。而基于LTL理論的路徑規(guī)劃方法可以很好地描述實(shí)際應(yīng)用中較為復(fù)雜的任務(wù)需求，諸如始終保持一定的范圍之內(nèi)(安全性)，按序訪問某幾個(gè)點(diǎn)(保證性)后，巡回訪問某幾個(gè)點(diǎn)(循環(huán)性)，圖中避開某些點(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ī)器人無法通過時(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所示，繞開了無法通過的節(jié)點(diǎn)p14，仍然可以確保規(guī)劃所得路徑的最優(yōu)性。

圖11 節(jié)點(diǎn)p14暢通規(guī)劃結(jié)果

圖12 節(jié)點(diǎn)p14遇阻規(guī)劃結(jié)果

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

5 結(jié) 論

隨著電子商務(wù)的飛速發(fā)展，各大電商對(duì)基于移動(dòng)機(jī)器人的自動(dòng)化倉儲(chǔ)物流技術(shù)的需求越來越迫切。本文對(duì)倉儲(chǔ)物流機(jī)器人路徑規(guī)劃方法的研究與應(yīng)用進(jìn)行了探索：建立了一個(gè)可靈活擴(kuò)展的倉儲(chǔ)環(huán)境模型，有效地描述了倉儲(chǔ)物流應(yīng)用中的各類任務(wù)需求，并將倉儲(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)，適用范圍更廣；此外，本文所提出的方法無需對(duì)任務(wù)進(jìn)行分段的點(diǎn)到點(diǎn)規(guī)劃，與任務(wù)節(jié)點(diǎn)的順序無關(guān)，保證了規(guī)劃所得路徑的最優(yōu)性。因此，基于LTL理論的倉儲(chǔ)機(jī)器人路徑規(guī)劃方法能夠滿足實(shí)際的應(yīng)用需求，大大提高倉儲(chǔ)物流機(jī)器人的工作效率。

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

[ 1] 鄒爽心. 倉儲(chǔ)機(jī)器人的應(yīng)用現(xiàn)狀與發(fā)展戰(zhàn)略探討. 物流工程與管理, 2013, 35(6): 171-172

[ 2] 王勇. 智能倉庫系統(tǒng)多移動(dòng)機(jī)器人路徑規(guī)劃研究: [碩士學(xué)位論文]. 哈爾濱: 哈爾濱工業(yè)大學(xué), 2010

[ 3] 沈博聞, 于寧波, 劉景泰. 倉儲(chǔ)物流機(jī)器人集群的智能調(diào)度和路徑規(guī)劃. 智能系統(tǒng)學(xué)報(bào), 2014, 6(9): 659-664

[ 4] 王戌. 智能倉庫多移動(dòng)機(jī)器人的路徑規(guī)劃研究: [碩士學(xué)位論文]. 大連: 大連交通大學(xué), 2014

[ 5]LunaR,BekrisKE.Efficientandcompletecentralizedmulti-robotpathplanning.In:Proceedingsofthe2011IEEE/RSJInternationalConferenceonIntelligentRobotsandSystems(IROS),SanFrancisco,USA, 2011. 3268-3275

[ 6]LeeMC,ParkMG.Artificialpotentialfieldbasedpathplanningformobilerobotsusingavirtualobstacleconcept.In:Proceedingsofthe2003IEEE/ASMEIntelligentConferenceonAdvancedIntelligentMechatronics,PortIsland,Kobe,Japan, 2003. 735-740

[ 7]ZhangSP,WangXK,DuanJ.Applicationofa-staralgorithminmobilerobotpathplanning.MechanicalEngineering&Automation, 2012, 6: 059

[ 8]LavalleSM.Rapidly-exploringrandomtrees:anewtoolforpathplanning.Algorithmic&ComputationalRoboticsNewDirections, 1998: 293-308

[ 9]FainekosGE,Kress-GazitH,PappasGJ.Temporallogicmotionplanningformobilerobots.In:Proceedingsofthe2005IEEEInternationalConferenceonRoboticsandAutomation,Baecelona,Spain, 2005. 2020-2025

[10]SmithS,TumovaJ,BeltaC,etal.Optimalpathplanningforsurveillancewithtemporallogicconstraints.TheInternationalJournalofRoboticsResearch, 2011, 30(14): 695-1708

[11]SmithS,TumovaJ,BeltaC,etal.Optimalpathplanningundertemporallogicconstraints.In:ProceedingsofInternationalConferenceonIntelligentRobotsandSystems,Taipei,China, 2010. 3288-3293

[12] 肖云濤, 歐林林, 俞立. 基于線性時(shí)序邏輯的最優(yōu)巡回路徑規(guī)劃. 自動(dòng)化學(xué)報(bào), 2014, 10(10): 2126-2133

[13]UlusoyA,SmithSL,DingXC,etal.Optimalityandrobustnessinmulti-robotpathplanningwithtemporallogicconstraints.InternationalJournalofRoboticsResearch, 2013, 32(8): 889-911

[14]MaityD,BarasJS.Motionplanningindynamicenvironmentswithboundedtimetemporallogicspecifications.In:Proceedignsofthe23thMediterraneanConferenceonControlandAutomation(MED),Torremolinos,Spain, 2015. 940-946

[15]GastinP,OddouxD.FastLTLtoBüchiAutomataTranslation.In:ComputerAidedVerification,Heidelberg,Germany:SpringerBerlin, 2001. 53-65

[16]KloetzerM,BeltaC.Afullyautomatedframeworkforcontroloflinearsystemsfromtemporallogicspecications.IEEETransactionsonAutomaticControl, 2008, 53(1): 287-297

[17]YangY.AnefficientimplementationofshortestpathalgorithmbasedonDijkstraAlgorithm.JournalofWuhanTechnicalUniversityofSurveying&Mapping, 1999, 24(3): 209-212

[18]BeltaC,IslerV,PappasGJ.Discreteabstractionsforrobotmotionplanningandcontrolinpolygonalenvironments.IEEETransactionsonRobotics, 2005, 21(5): 864-874

Path planing of warehouse robots based on linear temporal logic

YuXinyi,ChenHao,GuoYongkui,ChengCheng,OuLinlin,YuLi

(CollegeofInformationEngineering,ZhejiangUniversityofTechnology,Hangzhou310023)

Thepathplanningforwarehouserobotsbasedonthelineartemporallogic(LTL)theorywasstudied.Firstly,anextensiblewarehousemodelwasbuiltupaccordingtowarehouseenvironmentalcharacteristics,andasetofrulesforgoverningrobotmovementsweredefinedtomakethemodeladaptdynamicwarehouseenvironments.Secondly,theLTLformulawasusedtodescribetaskrequirementstomakeitsuitableformorecomplicatedtasksinpracticalapplications.Thirdly,thetask-feasiblenetworktopologywasbuiltbycombiningtaskrequirementsandenvironmentalinformationtoavoidpiecewisepathsearching.Then,theDijkstraalgorithmwasutilizedtosearchtheglobaloptimalpathonthetask-feasiblenetworktopologytoensuretheoptimalityofthepathplanningresult.Finally,theoptimizedpathwasobtainedbymappingtheoptimalpathonthetaskfeasiblenetworktopologybacktothewarehousemodel.Theabove-mentionedmethodcannotonlysatisfycomplextaskrequirements,butalsocanensuretheoptimalityofthepathplanningresult,ratherthanasuboptimalsolution,comparedwiththecurrentwidelyusedA*algorithm.

pathplanning,lineartemporallogic(LTL),warehouserobot,Dijkstraalgorithm

國家自然科學(xué)基金(61273116)，863計(jì)劃(2014AA041601-05)和浙江省自然科學(xué)基金(LY15F030015)資助項(xiàng)目。

u@zjut.edu.cn(

2015-10-10)

10.3772/j.issn.1002-0470.2016.01.004

男，1979年生，博士(后)；研究方向：機(jī)器人控制與規(guī)劃；E-mail: yuxinyinet@163.com