胡源，王麗麗，劉祥偉

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽淮南 232001）

近年來，科學(xué)技術(shù)的不斷進(jìn)步與發(fā)展，掃地機(jī)器人的功能也日益完善，但是由于現(xiàn)代房間住房內(nèi)部環(huán)境的復(fù)雜性，導(dǎo)致了掃地機(jī)器人難以完整記錄室內(nèi)環(huán)境，因此如何設(shè)計機(jī)器人的清掃路徑是整個設(shè)計系統(tǒng)的重點(diǎn)。

Petri網(wǎng)的行為輪廓理論是以合理的自由選擇petri網(wǎng)為基礎(chǔ)，從過程行為角度建模，使得Petri網(wǎng)模型間的行為關(guān)系具體化、數(shù)字化，直觀的刻畫了行為間的內(nèi)部關(guān)系[1]，對服務(wù)的交互和組合能從過程行為角度上得到解決。構(gòu)建流程模型[1]能夠清晰地表現(xiàn)出業(yè)務(wù)行為的邏輯性和有序性，建模原理則給出了建模語言所需的形式化的程序。文獻(xiàn)[3]給出了在掃地機(jī)器人工作時，如何尋找內(nèi)層非障礙點(diǎn)的方法建議。文獻(xiàn)[4]提出了在滿足室內(nèi)環(huán)境全覆蓋的情況下，如何規(guī)劃掃地機(jī)器人的路徑問題想法。文獻(xiàn)[5]給出了在業(yè)務(wù)流程建模時，將一個建模目標(biāo)的多個輸入模型根據(jù)模型相關(guān)性合并成一個復(fù)雜的綜合模型，以及子模型的實(shí)現(xiàn)。文獻(xiàn)[6]介紹了一個利用組合性的方法檢測Petri網(wǎng)可達(dá)性。文獻(xiàn)[8]給出了在業(yè)務(wù)流程建模時，將一個建模目標(biāo)的多個輸入模型根據(jù)模型相關(guān)性合并成一個復(fù)雜的綜合模型，建模者可以觀察到輸入模型間的共性和不同之處，以及子模型的實(shí)現(xiàn)，從而能更深一步的服務(wù)于建模目標(biāo)。文獻(xiàn)[9]給出了在業(yè)務(wù)流程建模時，將一個建模目標(biāo)的多個輸入模型根據(jù)模型相關(guān)性合并成一個復(fù)雜的綜合模型，建模者可以觀察到輸入模型間的共性和不同之處，以及子模型的實(shí)現(xiàn)，從而能更深一步的服務(wù)于建模目標(biāo)。

本文基于Petri網(wǎng)和行為輪廓的思想，從過程行為角度進(jìn)行建模，提出了掃地機(jī)器人路徑系統(tǒng)模型的設(shè)計分析。為了使得機(jī)器人在清掃環(huán)境系統(tǒng)中更方便快捷的達(dá)到環(huán)境全覆蓋，并且針對其在打掃過程中碰到路面障礙的情況，結(jié)合Petri網(wǎng)中的行為關(guān)系分析流程模型，使其達(dá)到適用性和一致性。

1 基本概念

下面僅介紹流程模型Petri網(wǎng)的定義及其可達(dá)性，闡述了行為輪廓的相關(guān)定義。

定義1[1]（流程模型Petri網(wǎng)）一個流程模型Petri網(wǎng)PM=(P,T,F,C,s,e)是一個六元組，滿足以下條件：

（1）P是有限庫所集，T是有限活動變遷集；

（2）P≠?,T≠?且P?T=?；

（3）F?(P×T)?(T×P)表示 PN 的流關(guān)系且(P?T,F)是強(qiáng)連通圖；

（4）dom(F)?cod(F)=P?T,

其中

dom(F)={x∈P?T|?y∈P?T,(x,y∈F)} ；cod(F)={x∈P?T|?y∈P?T,(y,x)∈F}。

（5）C={and,xor,or}是流程網(wǎng)的結(jié)構(gòu)類型；

（6）M0是網(wǎng)的初始標(biāo)識，Mf是網(wǎng)的終止標(biāo)識，且Mf是死標(biāo)識；

（7）s∈T是開始活動變遷，e∈T是終止活動變遷。

則稱該網(wǎng)為流程模型Petri網(wǎng)。

在此定義上，定義了網(wǎng)的前集和網(wǎng)的后集。

定 義 2[2]（變 遷 發(fā) 生 規(guī) 則）一 個 四 元 組PN=( )P,T;F,M0稱為Petri網(wǎng)，并具有下面的變遷發(fā)生規(guī)則

（1）變遷t∈T具有發(fā)生權(quán)，當(dāng)且僅當(dāng)對?p∈·t:M(p)≥1，記作M[t＞；

（2）在標(biāo)識M下能使的變遷t經(jīng)發(fā)生后，得到一個新的標(biāo)識M′，記作M[t＞M′，則有

定 義 3[6]（ 可 達(dá) 性 ） 已 知 Petri網(wǎng)PN=(P,T;F,M)，如果存在t∈T，使M[t＞M′，則稱M′為從M直接可達(dá)的。如果存在變遷序列t1,t2,…,tk和標(biāo)識序列M1,M2,…,Mk使得

則稱Mk為從M可達(dá)的。從M可達(dá)的一切標(biāo)識的集合記為R( )M。

圖1 可達(dá)性模型

定義4[9]（行為輪廓）設(shè)是一個網(wǎng)，初始標(biāo)識為M0。對任給的變遷對滿足下面關(guān)系；

（1）若t1?t2且t2?t1，則稱嚴(yán)格序關(guān)系，記作t1→t2；

（2）若t1?t2且t2?t1，則稱嚴(yán)格逆序關(guān)系，記作t1→-1t2；

（3）若t1?t2且t2?t1，則稱排他關(guān)系，記作t1//t2；

（4）若t1?t2且t2?t1，則稱交叉序關(guān)系，記作t1×t2；

2 基于Petri網(wǎng)的掃地機(jī)器人路徑系統(tǒng)的模型建立

本部分首先基于Petri網(wǎng)建立掃地機(jī)器人路徑設(shè)置模型，其次分析該模型中活動間的相互關(guān)系并分析該模型的結(jié)構(gòu)，完善機(jī)器人的路徑系統(tǒng)，使得其能夠更好地完成清潔室內(nèi)的工作。目前來說，掃地機(jī)器人以螺旋式行動來進(jìn)行清掃的方式是效率最高的，它在避免了重復(fù)行走路徑的同時，也能夠有效的遍歷所有的區(qū)域達(dá)到完成各個區(qū)域的清掃目的。但是機(jī)器人在以螺旋模式行動的途中，若是在途中碰到了較大形狀的障礙物，如桌椅，抑或是寵物等物體時，便會中斷它的行動路線[7]。所以，在螺旋行動中加入避開障礙物的算法，如繞開障礙物后再返回原路徑。下面就此方法提基于Petri網(wǎng)的模型建立，使得機(jī)器人可以在陌生的環(huán)境中完成自身的清掃任務(wù)。然后根據(jù)建立的模型，用Java進(jìn)行仿真演示以驗證模型。

圖2 掃地機(jī)器人路徑的Petri網(wǎng)模型

對房間進(jìn)行模塊化分層，清潔機(jī)器人按右螺旋方式對房間進(jìn)行清掃，假定房間分為51*51矩陣，最外層200個點(diǎn)記為1（起始點(diǎn)記為0），第二層196個點(diǎn)記為2，以此類推，最中間點(diǎn)記為26。若房間大小改變，按此方法類似進(jìn)行標(biāo)記分層。

通過模型的運(yùn)行可以直觀的看出活動之間的關(guān)系。在機(jī)器人行進(jìn)至障礙物時，首先會判斷該障礙物為墻壁或一般阻礙物，然后返回判斷信息并根據(jù)返回的信息決定下一步行動方式。若為墻壁則轉(zhuǎn)變方向繼續(xù)前行執(zhí)行清掃，若為一般阻礙物則尋找內(nèi)層緊鄰點(diǎn)，通過移動至內(nèi)層緊鄰點(diǎn)再返回到外層阻礙物后一點(diǎn)繼續(xù)之前的路徑執(zhí)行清掃，直至這一層清掃完畢再運(yùn)行至內(nèi)一層重復(fù)上述工作。下面以跡的方式給出分析：給出如下變遷序列：

當(dāng)機(jī)器人以螺旋方式行動清掃時，會對已清掃后的位置進(jìn)行標(biāo)記，當(dāng)外層清掃完畢后，會移動至內(nèi)層重復(fù)進(jìn)行螺旋式清掃，即為路徑σ=σ1。

若機(jī)器人判斷無內(nèi)層且所經(jīng)過區(qū)域全部已標(biāo)記，則機(jī)器人便完成清掃[4]，其路徑為σ=σ1σ2σ3。

下面用Java來進(jìn)行模擬實(shí)驗，以驗證其有效性。部分核心代碼如下：

表1 圖2變遷符號的含義

圖3 房間內(nèi)部環(huán)境設(shè)置

圖3所顯示的為未清掃之前房間內(nèi)部環(huán)境圖部分，房間障礙物及垃圾隨機(jī)產(chǎn)生。清掃結(jié)果如圖4所示。

圖4 清掃完成后室內(nèi)環(huán)境部分

運(yùn)行結(jié)果顯示完成清掃后，地面已無垃圾，且機(jī)器人避開了所有的障礙物。

3 結(jié)束語

本文基于Petri網(wǎng)構(gòu)建了掃地機(jī)器人的一種路徑設(shè)置模型，其中包含了并發(fā)關(guān)系、排他關(guān)系及順序關(guān)系的流程，根據(jù)Petri網(wǎng)的變遷發(fā)生規(guī)則及其可達(dá)性和行為輪廓等基本性質(zhì)，通過增加相應(yīng)的結(jié)構(gòu)變遷對其進(jìn)行設(shè)計。構(gòu)建的模型包括順序關(guān)系的流程圖及具有排他關(guān)系的變遷發(fā)生序列，使模型應(yīng)用更加全面，也體現(xiàn)了該模型在實(shí)際應(yīng)用中的適用性。

未來關(guān)于路徑設(shè)計建模優(yōu)化還有許多問題去研究，需要基于Petri網(wǎng)及其行為輪廓的相關(guān)性質(zhì)分析其模型優(yōu)化的一致性和合理性。