基于Petri網的掃地機器人路徑設計分析

胡源，王麗麗，劉祥偉

（安徽理工大學 數學與大數據學院，安徽淮南 232001）

近年來，科學技術的不斷進步與發展，掃地機器人的功能也日益完善，但是由于現代房間住房內部環境的復雜性，導致了掃地機器人難以完整記錄室內環境，因此如何設計機器人的清掃路徑是整個設計系統的重點。

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

本文基于Petri網和行為輪廓的思想，從過程行為角度進行建模，提出了掃地機器人路徑系統模型的設計分析。為了使得機器人在清掃環境系統中更方便快捷的達到環境全覆蓋，并且針對其在打掃過程中碰到路面障礙的情況，結合Petri網中的行為關系分析流程模型，使其達到適用性和一致性。

1 基本概念

下面僅介紹流程模型Petri網的定義及其可達性，闡述了行為輪廓的相關定義。

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

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

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

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

（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}是流程網的結構類型；

（6）M0是網的初始標識，Mf是網的終止標識，且Mf是死標識；

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

則稱該網為流程模型Petri網。

在此定義上，定義了網的前集和網的后集。

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

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

（2）在標識M下能使的變遷t經發生后，得到一個新的標識M′，記作M[t＞M′，則有

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

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

圖1 可達性模型

定義4[9]（行為輪廓）設是一個網，初始標識為M0。對任給的變遷對滿足下面關系；

（1）若t1?t2且t2?t1，則稱嚴格序關系，記作t1→t2；

（2）若t1?t2且t2?t1，則稱嚴格逆序關系，記作t1→-1t2；

（3）若t1?t2且t2?t1，則稱排他關系，記作t1//t2；

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

2 基于Petri網的掃地機器人路徑系統的模型建立

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

圖2 掃地機器人路徑的Petri網模型

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

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

當機器人以螺旋方式行動清掃時，會對已清掃后的位置進行標記，當外層清掃完畢后，會移動至內層重復進行螺旋式清掃，即為路徑σ=σ1。

若機器人判斷無內層且所經過區域全部已標記，則機器人便完成清掃[4]，其路徑為σ=σ1σ2σ3。

下面用Java來進行模擬實驗，以驗證其有效性。部分核心代碼如下：

表1 圖2變遷符號的含義

圖3 房間內部環境設置

圖3所顯示的為未清掃之前房間內部環境圖部分，房間障礙物及垃圾隨機產生。清掃結果如圖4所示。

圖4 清掃完成后室內環境部分

運行結果顯示完成清掃后，地面已無垃圾，且機器人避開了所有的障礙物。

3 結束語

本文基于Petri網構建了掃地機器人的一種路徑設置模型，其中包含了并發關系、排他關系及順序關系的流程，根據Petri網的變遷發生規則及其可達性和行為輪廓等基本性質，通過增加相應的結構變遷對其進行設計。構建的模型包括順序關系的流程圖及具有排他關系的變遷發生序列，使模型應用更加全面，也體現了該模型在實際應用中的適用性。

未來關于路徑設計建模優化還有許多問題去研究，需要基于Petri網及其行為輪廓的相關性質分析其模型優化的一致性和合理性。