基于賦時(shí)Petri網(wǎng)的磁導(dǎo)航AGV路徑優(yōu)化方法

張 斌,李 建,馬錦程,何仁杰

(中國(guó)計(jì)量大學(xué) 計(jì)量測(cè)試工程學(xué)院,浙江 杭州 310018)

隨著工業(yè)生產(chǎn)技術(shù)的不斷提高,效率低下的傳統(tǒng)物流方式已經(jīng)不能滿足現(xiàn)代化企業(yè)的要求。自動(dòng)導(dǎo)引小車(Automated guided vehicle,AGV)的出現(xiàn)使企業(yè)意識(shí)到自動(dòng)化物流的重要性[1,2],在物流系統(tǒng)里面,使用自動(dòng)導(dǎo)引小車可以讓企業(yè)成本大大降底,并且還可以使自動(dòng)化程度及效率和物流系統(tǒng)的柔性得到提升[3,4]。

磁條導(dǎo)航[5](以下簡(jiǎn)稱磁導(dǎo)航)具有現(xiàn)場(chǎng)施工簡(jiǎn)單、周期短、成本低的優(yōu)點(diǎn),其技術(shù)成熟可靠,對(duì)于聲光無干擾性。AGV運(yùn)行路徑明顯,線路二次變更容易、變更成本低。磁條導(dǎo)航是眾多AGV導(dǎo)航技術(shù)中使用最多的導(dǎo)航方式。但是磁條導(dǎo)航技術(shù)仍然面臨著一些技術(shù)問題,需要進(jìn)行改進(jìn)。主要問題有:

(1)AGV小車的站點(diǎn)位置信息不連續(xù),無絕對(duì)位置信息。當(dāng)小車處于兩站點(diǎn)之間時(shí),無法通過RFID傳感器獲取小車的位置信息。

(2)小車在拐彎、到達(dá)目標(biāo)站點(diǎn)或者避讓需要減速時(shí),無法進(jìn)行很好的預(yù)判,導(dǎo)致高速運(yùn)轉(zhuǎn)時(shí)穩(wěn)定性較差。

(3)AGV調(diào)度方式單一,一般采用區(qū)域管制,無法適應(yīng)復(fù)雜的現(xiàn)場(chǎng)工況,AGV的運(yùn)行效率較低。

因此,為了能夠進(jìn)一步提升磁條導(dǎo)航AGV的應(yīng)用水平,必須解決好以上諸多問題,關(guān)鍵是獲取AGV運(yùn)行過程的完整信息,構(gòu)建完善的AGV系統(tǒng)模型,解決AGV系統(tǒng)運(yùn)行時(shí)的無碰撞的最優(yōu)路徑規(guī)劃問題。

國(guó)內(nèi)的劉國(guó)棟[6]等人提出一種動(dòng)態(tài)路徑規(guī)劃算法。首先,離線找出所有可通行的路徑,再通過啟發(fā)式算法對(duì)其進(jìn)行路徑優(yōu)化。焦福明[7]針對(duì)整批執(zhí)行任務(wù),通過使行駛時(shí)間最長(zhǎng)的AGV時(shí)間最短來規(guī)劃每個(gè)AGV的行駛路線。邢科新[8]提出了一種動(dòng)態(tài)時(shí)間窗路徑規(guī)劃方法:首先,規(guī)劃每個(gè)AGV的時(shí)間最短路徑,獲得AGV經(jīng)過路徑上所有節(jié)點(diǎn)和路段的時(shí)間窗,然后通過比較各個(gè)AGV的時(shí)間窗,對(duì)其進(jìn)行調(diào)整,從而實(shí)現(xiàn)多AGV的路徑規(guī)劃。趙東雄[9]通過速度調(diào)節(jié)平移時(shí)間窗,調(diào)用優(yōu)化算法與規(guī)避策略實(shí)現(xiàn)AGV無碰撞路徑規(guī)劃。國(guó)外的Jeon等[10]提出一種基于Q學(xué)習(xí)的路徑規(guī)劃算法,通過估計(jì)行駛中因沖突產(chǎn)生的等待時(shí)間,為AGV規(guī)劃一條行駛時(shí)間最短的路徑,但是該算法用時(shí)較長(zhǎng),且不能避免死鎖。

Petri網(wǎng)理論在AGV系統(tǒng)中的應(yīng)用給AGV系統(tǒng)整體建模提供了一種新的思路[11]。任小龍[12]采用無向Petri網(wǎng)對(duì)AGV系統(tǒng)路徑布局進(jìn)行建模,與時(shí)間窗結(jié)合建立基于時(shí)間的可達(dá)狀態(tài)圖,提出了時(shí)間最短的路徑優(yōu)化算法。胡源[13]基于Petri網(wǎng)和行為輪廓的思想,從過程行為角度進(jìn)行建模,對(duì)掃地機(jī)器人路徑系統(tǒng)模型的設(shè)計(jì)進(jìn)行了分析。趙思萌[14]針對(duì)鐵路物流中心的卸車業(yè)務(wù)流程,建立了基于Petri網(wǎng)的業(yè)務(wù)流程模型并進(jìn)行了仿真?？偟膩碇v,Petri網(wǎng)理論在AGV系統(tǒng)中的應(yīng)用還處于初級(jí)階段,沒有建立起完整的理論體系,有待進(jìn)一步的研究。

基于以上對(duì)研究現(xiàn)狀的調(diào)研分析,本文將通過研究基于賦時(shí)Petri網(wǎng)理論的磁導(dǎo)航AGV系統(tǒng)建模理論與方法,并結(jié)合改進(jìn)Dijkstra路徑搜索算法實(shí)現(xiàn)動(dòng)態(tài)的、可避障的多AGV路徑規(guī)劃及調(diào)度,進(jìn)一步提升磁導(dǎo)航AGV的應(yīng)用水平。

1 賦時(shí)Petri網(wǎng)

1.1 時(shí)間窗

AGV在執(zhí)行任務(wù)的過程中,如要實(shí)時(shí)了解AGV的位置信息,可以將AGV經(jīng)過節(jié)點(diǎn)和路徑的時(shí)間以時(shí)間窗的形式記錄下來。對(duì)于多AGV路徑節(jié)點(diǎn)占用的情況可以通過集合的方式準(zhǔn)確描述:針對(duì)AGVk而言,其路徑表示為:

pathk={pi,pj,…,pn}

AGVk在執(zhí)行當(dāng)前任務(wù)的路徑節(jié)點(diǎn)的時(shí)間窗表示為:

對(duì)于路徑集合(i-j-k)的時(shí)間窗的顯示情況如圖1所示:

圖1 路徑集合(i-j-k)的時(shí)間窗Figure 1 Time window of path set(i-j-k)

1.2 賦時(shí)Petri網(wǎng)

賦時(shí)Petri網(wǎng)屬于高級(jí)Petri網(wǎng),它在普通Petri網(wǎng)基礎(chǔ)上加入了時(shí)間因素,模擬系統(tǒng)中不同變化的延時(shí),以此來對(duì)系統(tǒng)的性能進(jìn)行分析。

賦時(shí)Petri網(wǎng)通常分為兩類,第一類TTPN(Transition-timed petri net),即變遷時(shí)間增加時(shí)的延時(shí);第二類PTPN(Place-timed petri net),即庫所時(shí)間增加時(shí)的延時(shí)。將TTPN與PTPN相結(jié)合,可構(gòu)建磁導(dǎo)航AGV的賦時(shí)Petri網(wǎng)模型。

在模型中,用庫所表示節(jié)點(diǎn),用變遷表示可雙向通行的路徑,用令牌表示AGV,用標(biāo)識(shí)描述AGV系統(tǒng)狀態(tài)。如果庫所為空,說明AGV不在該位置;如果庫所中有一個(gè)令牌,代表AGV停留或者是正在穿過該位置。模型可用以下六元組進(jìn)行描述:

PN=(P,T,F,D0,D1,M0)

◆P={p1,p2,…,pm},pi代表庫所,i=(1,2,…,m)。

◆T={t1,t2,…,tn},tj代表變遷,j=(1,2,…,n)。

◆F為m×n的矩陣,其元素fij為0時(shí),表示pi與tj不相連;fij為1時(shí),表示pi與tj相連。

◆D0={d1,d2,…,dn}為變遷的可變時(shí)延集,其中di為變遷ti的時(shí)延。

◆D1={g1,g2,…,gm}為庫所的可變時(shí)延集,其中g(shù)i為庫所pi的時(shí)延。

◆M0為系統(tǒng)的初始狀態(tài)。

該模型描述了AGV系統(tǒng)的地圖拓?fù)浣Y(jié)構(gòu)及時(shí)間信息。

在任意時(shí)刻,某一節(jié)點(diǎn)或者某一段路徑上只能存在一個(gè)AGV,所以變遷的激發(fā)指AGV離開當(dāng)前節(jié)點(diǎn),沿著原有路線向另外一個(gè)連接的路線行駛,對(duì)于同一變遷,在不同狀態(tài)下完成該變遷的時(shí)間是不同的。

變遷的激發(fā)規(guī)則:庫所pi里面有一個(gè)令牌,在時(shí)刻Ta激發(fā)與其相連接的變遷tj,在Tb時(shí)刻,把令牌轉(zhuǎn)移到和變遷tj連接的庫所pk,而且這個(gè)時(shí)候庫所pk為空,同時(shí)Tb-Ta≥dj(dj就是在理想狀態(tài)下變遷tj激發(fā)的時(shí)間延遲),即AGV穿越同一路徑要用到的時(shí)間由系統(tǒng)的交通狀況決定,但通過時(shí)間都應(yīng)大于或者等于理想狀態(tài)下穿越路徑的時(shí)間。

庫所的時(shí)延規(guī)則:令牌在Te時(shí)刻移入庫所pi,在Tr時(shí)刻令牌移出庫所pi,激發(fā)與其相連接的變遷,要求Tr-Te≥gi,gi為理想狀態(tài)下令牌在庫所pi的停留時(shí)間,即AGV通過節(jié)點(diǎn)所用的時(shí)間均應(yīng)大于或者等于理想狀態(tài)下穿越節(jié)點(diǎn)的時(shí)間。AGV穿越同一節(jié)點(diǎn)時(shí)的行駛狀態(tài)可以分兩種情況:AGV直行通過該節(jié)點(diǎn),要求Tr-Te≥tc,即gi=tc;AGV在該節(jié)點(diǎn)處轉(zhuǎn)彎,要求Tr-Te≥tb,即gi=tb。

根據(jù)上述模型和相關(guān)規(guī)則定義,可以用Mi=[mi,TMi]來表示AGV的狀態(tài),其中mi為系統(tǒng)Petri網(wǎng)的標(biāo)識(shí),TMi為此標(biāo)識(shí)形成的時(shí)刻,故m相同而時(shí)間不同表示不同的狀態(tài)。AGV系統(tǒng)的狀態(tài)變化過程即標(biāo)識(shí)M的演變過程。因此,AGV的運(yùn)動(dòng)狀態(tài)可以通過一系列賦時(shí)Petri網(wǎng)標(biāo)識(shí)的變化來體現(xiàn)。

2 單AGV路徑規(guī)劃

AGV的路徑規(guī)劃是在全局信息已知的靜態(tài)環(huán)境下進(jìn)行的,單AGV的路徑規(guī)劃是在起始點(diǎn)處,利用已知環(huán)境找尋到一條評(píng)價(jià)指標(biāo)最優(yōu)的路徑。本文選用Dijkstra算法作為單臺(tái)AGV路徑搜索算法,將AGV的行駛時(shí)間當(dāng)作優(yōu)化目標(biāo),考慮AGV行駛到交叉路口時(shí)候的直行和轉(zhuǎn)彎兩種路線。

如圖2所示,當(dāng)小車從3號(hào)站點(diǎn)運(yùn)動(dòng)至1號(hào)站點(diǎn)時(shí),可以有多個(gè)路徑選項(xiàng),比如路線1和路線2等。路線1與路線2經(jīng)過的站點(diǎn)相同,轉(zhuǎn)彎次數(shù)相同,但是路線1比路線2行程短,所用的運(yùn)動(dòng)時(shí)間較少。

圖2 最短行程示意圖Figure 2 Schematic diagram of the shortest stroke

但是行程最短時(shí),AGV完成任務(wù)的時(shí)間不一定最優(yōu)。如下圖3所示,路線1比路線2的行程短,但是考慮到AGV小車在轉(zhuǎn)彎時(shí)所需的加減速時(shí)間和轉(zhuǎn)彎時(shí)間,路線2的運(yùn)動(dòng)時(shí)間很有可能是優(yōu)于路線1的。同樣,途經(jīng)的站點(diǎn)數(shù)最少的路線也未必是時(shí)間最優(yōu)的。

圖3 時(shí)間最優(yōu)路線示意圖Figure 3 Schematic diagram of time optimal route

為了方便評(píng)估AGV運(yùn)動(dòng)過程所需要的時(shí)間,得到時(shí)間最優(yōu)的路徑,現(xiàn)對(duì)AGV系統(tǒng)作如下設(shè)定:

(1)AGV行駛速度恒定,直行和轉(zhuǎn)彎速度分別為Vs和Vr;

(2)AGV啟停時(shí)間為td,即速度可以在td時(shí)間內(nèi)實(shí)現(xiàn)從零到AGV的勻速段行駛速度,以及從AGV的勻速段行駛速度到零的變化;

(3)AGV從某一站點(diǎn)到相鄰站點(diǎn)的勻速運(yùn)動(dòng)時(shí)間為ta,在站點(diǎn)處轉(zhuǎn)彎所需時(shí)間為tb,AGV直行通過站點(diǎn)的時(shí)間為tc。

那么AGV的整個(gè)運(yùn)動(dòng)過程所需要的時(shí)間:

H(R)=∑ta+∑tb+∑td+∑tc

(1)

根據(jù)改進(jìn)的Dijkstra算法,可獲得時(shí)間最優(yōu)的AGV運(yùn)行路徑,算法如下:

步驟1:設(shè)初始節(jié)點(diǎn)p0,目標(biāo)節(jié)點(diǎn)pg,建立空的搜索路徑表SELECT表和可達(dá)路徑表REACH表。

步驟2:將初始節(jié)點(diǎn)p0作為唯一站點(diǎn)生成初始路徑,放入SELECT表。

步驟3:對(duì)SELECT表中的所有路徑進(jìn)行擴(kuò)展,在路徑末尾添加最末節(jié)點(diǎn)plast的所有相鄰節(jié)點(diǎn)p＇,p＇必須是該路徑中未曾出現(xiàn)的,并且是無障礙的節(jié)點(diǎn)。如果符合要求的相鄰節(jié)點(diǎn)不存在,則刪除該路徑。

步驟4:如果p′=pg,則將該路徑放入REACH表中。

步驟5:完畢所有可行的路徑后,根據(jù)式(1)計(jì)算出每條可行路徑完成所需要的時(shí)間。對(duì)REACH表中的所有路徑按照時(shí)間進(jìn)行排序,找出時(shí)間最優(yōu)的路徑作為搜索結(jié)果。

改進(jìn)后的Dijkstra算法以時(shí)間最優(yōu)為指標(biāo),提高AGV的工作效率。

3 多AGV的路徑規(guī)劃

對(duì)于多AGV路徑規(guī)劃問題,將基于賦時(shí)Petri網(wǎng)的AGV系統(tǒng)模型與單AGV的路徑規(guī)劃算法相結(jié)合,實(shí)現(xiàn)多AGV的路徑規(guī)劃與調(diào)度。

圖4 變遷tj的第q段空閑時(shí)間示意圖Figure 4 Schematic diagram of the q-th period of free time in the transition tj

圖5 庫所pi的第h段空閑時(shí)間示意圖Figure 5 Schematic diagram of the h-th period of free time in the place pi

對(duì)于多AGV行駛過程中的沖突問題可以分為節(jié)點(diǎn)沖突、同向沖突、相向沖突三類。沖突不同,解決的策略不同。

3.1 等待策略

節(jié)點(diǎn)沖突與同向沖突是常見沖突,可以采用等待策略解決。對(duì)于賦時(shí)Petri網(wǎng)而言,首先要進(jìn)行變遷激發(fā)的判定,保證小車正常啟動(dòng)。判定方法如下:

(1)AGV接受任務(wù),確定起始節(jié)點(diǎn)p0和目標(biāo)節(jié)點(diǎn)pg,對(duì)于Petri網(wǎng)模型是確定初始標(biāo)識(shí)m0與目標(biāo)標(biāo)識(shí)mg,及接受的時(shí)間TM0,故初始狀態(tài)為M0=[m0,TM0]。

(2)若m0與mg相同,則返回1)。若兩者不相同,則利用改進(jìn)的Dijkstra算法規(guī)劃出一條時(shí)間最優(yōu)的路徑,更新系統(tǒng)變遷與庫所的時(shí)間窗。

變遷激發(fā)判定后,行駛過程中遇到?jīng)_突采用等待策略。方法如下:

物理意義為兩輛AGV同時(shí)爭(zhēng)奪庫所的使用權(quán),即AGV1在變遷tj的路徑上行駛,欲要穿越節(jié)點(diǎn)pi,此時(shí)節(jié)點(diǎn)pi正在被AGV2所占用,為了避免沖突,AGV1需要在變遷tj的路徑上減速或者等待,當(dāng)庫所處于空閑狀態(tài)下再繼續(xù)行駛。

行駛中不僅要考慮下一庫所是否沖突,還要在此基礎(chǔ)上考慮下一路段的交通狀況。方法如下:

(C)其他情況則后繼狀態(tài)不存在。

在上述情況中,狀態(tài)m0經(jīng)變遷tj后產(chǎn)生多個(gè)后繼狀態(tài)mi,將每一種狀態(tài)對(duì)應(yīng)的變遷占用的時(shí)間段在系統(tǒng)時(shí)間窗內(nèi)進(jìn)行相應(yīng)的更新。

上述(B)的意義為:AGV1在變遷tj所代表的路徑上行駛,欲要穿越節(jié)點(diǎn)pi后使用變遷ti所代表的路徑,但此時(shí)ti代表的路徑正在被另一個(gè)AGV2占用,為了避免沖突,AGV1應(yīng)在變遷tj所代表的路徑上減速等待,當(dāng)變遷ti所代表的路徑空閑時(shí)再繼續(xù)正常行駛。

3.2 重新規(guī)劃策略

對(duì)于相向沖突,若采用上述策略AGV系統(tǒng)會(huì)發(fā)生死鎖,所以采用重新規(guī)劃策略解決該沖突。以兩車為例,若存在AGV1在變遷ti路段上行駛,欲穿過庫所pk進(jìn)入變遷tj路段,此時(shí)AGV2在路段上行駛,欲要穿過庫所pk進(jìn)入變遷ti路段,如圖6所示。

圖6 變遷路段相向沖突示意圖Figure 6 Schematic diagram of the conflict between changing road sections

此時(shí),比較兩車正常到達(dá)庫所pk的時(shí)間,若AGV1經(jīng)過變遷ti路段到達(dá)庫所pk時(shí)產(chǎn)生新的標(biāo)志mj,其狀態(tài)mj的時(shí)間為TMj,AGV2經(jīng)過變遷tj路段到達(dá)庫所pk時(shí)產(chǎn)生新的標(biāo)志mi,其狀態(tài)mi的時(shí)間為TMi。當(dāng)系統(tǒng)檢測(cè)到上述情況時(shí),若TMi≥TMj,則代表AGV2先到達(dá)庫所pk,此時(shí)AGV1在變遷ti路段等待,AGV2到達(dá)庫所pk后,系統(tǒng)再次利用改進(jìn)Dijkstra算法,以庫所pk為新的起點(diǎn),重新搜索新的路徑,AGV1待AGV2駛出庫所pk后正常行駛,系統(tǒng)將后續(xù)的時(shí)間窗進(jìn)行相應(yīng)的更新。反之,AGV2原地等待,直至AGV1找尋新的路徑后正常行駛。

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

為了驗(yàn)證上述方法的可行性,對(duì)其進(jìn)行仿真驗(yàn)證。如圖7所示,系統(tǒng)滿足任意兩個(gè)庫所之間至少存在兩條路徑,且任意變遷代表的路段中只允許一個(gè)AGV存在。系統(tǒng)包括兩臺(tái)AGV,p1和p3表示存放AGV的工作站,p12和p13表示生產(chǎn)產(chǎn)品的工作站,p2表示儲(chǔ)存產(chǎn)品的工作站,其它庫所表示磁條鋪設(shè)時(shí)的交叉點(diǎn)。圖8為AGV的Petri網(wǎng)模型的仿真界面,表1為理想狀態(tài)下AGV穿越各路徑所需時(shí)間,表2為系統(tǒng)向AGV發(fā)出的運(yùn)送請(qǐng)求,根據(jù)上述算法得到的多AGV運(yùn)行優(yōu)化路徑如表3,表中[]表示節(jié)點(diǎn)和路段的起止時(shí)間,節(jié)點(diǎn)轉(zhuǎn)彎所需時(shí)間設(shè)置為3 s,直行通過節(jié)點(diǎn)的時(shí)間為1 s。

圖7 AGV的Petri網(wǎng)模型Figure 7 Petri net model of AGV

圖8 多AGV路徑規(guī)劃的仿真界面Figure 8 Simulation interface of multiple AGV path planning

表1 理想狀態(tài)下在T1～T18路徑行駛所需時(shí)間Table 1 Traveling time on the T1～T18 route under ideal conditions

表2 向AGV提出的運(yùn)送請(qǐng)求Table 2 Shipping request to AGV

表3 多AGV運(yùn)行優(yōu)化路徑Table 3 Optimization path of multi-AGV operation

上述事件中,AGV1在路段T12處行駛,欲要經(jīng)過庫所p10后使用路段T13,此時(shí)AGV2先經(jīng)過庫所p10占用了路段T13,根據(jù)上述算法中的(B)情況,AGV1需在路段T12處等待,直至AGV2駛出路段T13。當(dāng)兩車返回時(shí),AGV1優(yōu)先經(jīng)過庫所p11,進(jìn)入路段T13,AGV2需在路段T14處等待,直至AGV1駛出路段T13。兩車在路段T13處發(fā)生兩次占用路段沖突,運(yùn)用上述算法后有效解決了該沖突問題。

本文設(shè)計(jì)的AGV調(diào)度控制軟件在實(shí)際生產(chǎn)中已經(jīng)得到應(yīng)用,圖9是AGV調(diào)度控制軟件在某生產(chǎn)車間內(nèi)的實(shí)際應(yīng)用效果場(chǎng)景圖。在每個(gè)生產(chǎn)線上都放有一個(gè)呼叫器,方便任務(wù)的發(fā)布。當(dāng)上位機(jī)調(diào)度控制軟件收到呼叫請(qǐng)求時(shí),就會(huì)自動(dòng)搜索出呼叫站點(diǎn)與AGV當(dāng)前所在的位置之間的最優(yōu)路徑,并且通過無線通訊模塊對(duì)AGV發(fā)出指令,AGV就會(huì)沿著最優(yōu)路徑到達(dá)目標(biāo)站點(diǎn),完成對(duì)應(yīng)的任務(wù)。

圖9 調(diào)度軟件的實(shí)際應(yīng)用效果場(chǎng)景圖Figure 9 Scenario diagram of actual application effect of scheduling software

圖10是生產(chǎn)車間工作需要而鋪設(shè)的磁條路徑軌道,每一個(gè)路口都存在一條生產(chǎn)流水線,雖然實(shí)際的實(shí)驗(yàn)環(huán)境與仿真系統(tǒng)存在差別,但是規(guī)劃出的行駛路徑依然是時(shí)間最優(yōu)路徑,實(shí)際表明本文設(shè)計(jì)的調(diào)度控制軟件可以用于實(shí)際生產(chǎn)中,效果良好。

圖10 現(xiàn)場(chǎng)車間鋪設(shè)的磁條路線Figure 10 The magnetic stripe route laid by the on-site workshop

5 結(jié) 論

本文以提升AGV調(diào)度系統(tǒng)的靈活性和運(yùn)行效率為研究目標(biāo),對(duì)AGV的路徑規(guī)劃及避障問題進(jìn)行了相關(guān)的研究。以賦時(shí)Petri網(wǎng)理論為基礎(chǔ),構(gòu)建了磁導(dǎo)航AGV的系統(tǒng)模型,結(jié)合改進(jìn)的Dijkstra算法,實(shí)現(xiàn)了AGV的時(shí)間最優(yōu)路徑的規(guī)劃,并且在動(dòng)態(tài)情況下有效解決了障礙沖突,提高了系統(tǒng)的運(yùn)輸能力。該優(yōu)化方法有助于解決動(dòng)態(tài)AGV路徑優(yōu)化問題,具有借鑒作用,并且設(shè)計(jì)的AGV調(diào)度軟件可以滿足工況需求,具有實(shí)際應(yīng)用價(jià)值。