OOPN網精細化操作及在垃圾分類建模中的應用

王兆誠 夏傳良 張 瑋 王壯壯

(山東建筑大學計算機科學與技術學院 山東 濟南 250101)

0 引 言

在日常生活中，垃圾分類處理逐漸被政府和人們重視并實踐應用，但人為垃圾分類需要公眾有高度的自覺意識，收效甚微，于是智能垃圾分類揀放機應運而生，為了加快揀放機垃圾分類處理的速度并降低功耗，有必要對這類系統進行建模研究和管理。智能垃圾分類的過程有很明顯的模塊化、功能化特征，如垃圾識別、垃圾分揀、垃圾對應回收和垃圾運輸處理等。Petri網作為一種系統模型，一般對系統及行為進行統一考慮，但不能體現出系統功能模塊的劃分。而利用面向對象的相關定義對系統進行功能、模塊的劃分，將整個復雜系統的建模過程有效地劃分為多個簡單子系統，并相應進行建模研究正是面向對象Petri網建模技術的突出優勢所在[1]。

本文選擇面向對象Petri網作為智能垃圾分類揀放機系統的建立模型，用于研究、分析的工具，鑒于一次性建模存在復雜性、不確定性因素大的問題，首先利用OOPN建立原始系統粗略、大體的模型，然后再運用相應的精細化方法對大概的模型進行精細化處理，從而可得更加詳細、精確的目標網系統模型。

為了使復雜業務處理過程的建模變得簡單、清晰，那絕對必要的是采用精細化方法來把復雜的主過程進行分解，形成更小的子過程，這樣才能有效降低復雜度，也就是所謂的“分而治之”策略[2]。潘衛軍等[3]對機坪內各交通模塊進行精細化建模，采用基本網模型的精細化代替方法，清晰自然地得到機坪運行過程的全局著色Petri網模型；Xia等[4]提出了PRES+(Petri net based Representation for Embedded Systems)，即基于Petri網表示的嵌入式系統模型的細化方法，使得運用Petri網對嵌入式系統建模時的復雜度降低，效率增高。

除此之外，不少學者對面向對象Petri網的性質及精細化設計也做了研究。文獻[5]給出了擴展面向對象Petri網(EOOPN)的定義及性質，如封裝性、抽象性；文獻[6]研究了將面向對象的繼承性以及與之緊密聯系的多態性引入OOPN網；文獻[7-8]研究了面向對象Petri網的信息交互性，并基于OOPN對高速鐵路行車指揮系統進行建模；文獻[9]給出了EOOPN模型中的構件細化及其一種類型，指出精細化的主要思想是將抽象的庫所(ABP)、變遷(ABT)和標識(Token)精細化為構件子網或更詳細的抽象庫所、變遷和標識；文獻[10]詳細給出了EOOPN中的其他三種構件細化方法(ABP細化、ABT細化和Token細化)，提出了結構良好性的定義，也證明了細化后仍保持結構良好性。上述工作雖然研究了OOPN的一些性質和精細化操作方法，但對OOPN的活性、有界性及精細化后對該性質的保持未做詳細研究說明。

本文提出了一種面向對象Petri網的類網精細化方法并研究了如何使精細化后的目標網系統保持原有的活性、有界性。首先，根據相關條件要求，對原始OOPN系統進行類網精細化操作，此操作完成后，便可得到更細致的期望目標網系統，則該系統仍能保持活性、有界性的條件是:當且僅當原始OOPN系統和進行替換的閉類網系統都是活的、有界的。這對于Petri網復雜大系統的分析具有重要的指導意義，值得一提的是，本文給出的OOPN類網精細化操作模型絕不僅僅可用來描述和處理“智能垃圾分類揀放”的具體過程，可覆蓋柔性制造系統中諸如“某車間的若干臺機器為其生產某些部件”的問題類。

1 基本定義和符號

本節給出面向對象Petri網及系統的相關定義和示例，以及系統活性、有界性的定義。

定義1設六元組N=(P,T,F,Q,G,W)是一個OOPN模型：

P={p1,p2,…,pm}是一確定庫所集合，P≠?；

T={t1,t2,…,tm}是一確定變遷集合，T≠?；

F={FI,FO}是網N的流關系，FI?(T×P或T×Q或G×Q)是一確定的輸入弧集合，FO?(P×T或Q×T或Q×G)是一確定的輸出弧集合；

Q={q1,q2,…,qm}是一確定非空的消息庫所集合，分為輸入消息庫所QI和輸出消息庫所QO，從網關接收到消息的為輸入消息庫所，向網關發送消息的為輸出消息庫所；

G={G1,G2,…,Gm}是對象間的網關集合；

W:F→{1,2,3，…}稱為權函數；

Σ=(N,M)稱為一個OOPN系統，M:P→{0,1,2,…}和QI→{0,1,2，…}是Σ的一個標識，其中，M0是初始標識。

用示例來闡明這部分提出的模型定義，如圖1所示。

圖1 一個OOPN示例

圖1中:P={p1,p2};T={t1,t2};

FI={(t1,p2),(t2,p1),(t1,q2),(G1,q1)};

FO={(p1,t1),(p2,t2),(q1,t2),(q2,G2)};

G={G1,G2};QI={q1,q3};QO={q2,q4};

M0=[M(p),M(q)]=[1,0,0,0,0,0];

權函數W未標識出的默認為1。

其中，消息庫所Q用橢圓形表示，它類似于對象與外界的通信窗口；通信網關G用粗實線表示，它與變遷類似，用來實現對象間的連接；抽象和封裝好的類用圓角矩形來表示；類的“實例”數目用Petri網中的標識來表示[11]。

定義2設N=(P,T;F,Q,G,W)是一個OOPN模型，Σ=(N,M0)是一個OOPN系統，M∈R(M0)。

1) 變遷t∈T，當·t∩Q=Φ時，t可稱為在M下使能的充分必要條件為:

?p∈P:M(p)≥W(p,t)

(1)

滿足式(1)記作M[t>。

當t∩Q≠Φ時，t可稱為在M下使能的充分必要條件為:

?p∈P∧?q∈Q:M(p)≥W(p,t)∧M(q)≥W(q,t)

(2)

滿足式(2)記作M[t>。

2) 變遷t可以發生的條件為:t能夠在標識M下使能；發生的結果為:M→M′。

(3)

(4)

定義3設Σ=(N,M0)是一個OOPN系統：

1) 變遷t∈T是活的，當且僅當?M∈R(M0),?M′∈R(M),M′[t>;

2)Σ是活的，當且僅當?t∈T,t是活的。

定義4設Σ=(N,M0)是一個OOPN系統：

1) 庫所p∈P是有界的,當且僅當?k1>0,使得M(p)≤k1,?M∈R(M0);消息庫所q∈Q是有界的,當且僅當?k2>0,使得M(q)≤k2,?M∈R(M0)。

2)Σ是有界的，當且僅當?p∈P∧?q∈Q,p和q都是有界的。

定義5設N=(P,T;F,Q,G,W)和Na=(Pa,Ta;Fa,Qa,Ga,Wa)是兩個OOPN網，若滿足：

1)Pa?P,Ta?T,Qa?Q,Ga?G且Pa≠?,Ta≠?,Qa≠?;

2)Fa=F∩((Pa×Ta)∪(Ta×Pa)∪(Qa×Ta)∪(Ta×Qa)∪(Ga×Qa)∪(Qa×Ga))。

則稱Na是N的一個OOPN子網，或者稱為類網，記為CNa。

為了更形象準確地定義類網，規定：

在類網中，消息標識只能從輸入消息庫所進，從輸出消息庫所出，不可逆。

定義6類網精細化操作Re f(pA,CNa):將面向對象Petri網N=(P,T;F,Q,G,W)中的庫所pA精細化為一個類網CNa=(Pa,Ta;Fa,Qa,Ga,Wa)(用類網CNa來替換pA)，得到OOPN模型，N′=(P′,T′;F′,Q′,G′,W′)。其中：

1)P′=(P-{pA})∪Pa;

2)T′=T∪Ta;

4)Q′=Q∪Qa;

5)G′=G∪Ga;

6)W′(x,y)=

(5)

(6)

式中：M(PpA)為M中去掉pA所對應的分量以后的向量，?A是Ma的零向量。

2 OOPN的類網精細化操作性質分析

本節先提出關于OOPN系統的活性、有界性定理，再提出經過類網精細化操作后系統仍保持活性、有界性的充要條件。

證明：(1)p?q。

(2)p?q。

證明：(1)p?q。

∵ 系統Σ1是有界的，則?p∈P1∧?q∈Q1,?k1>0使得M1(p)≤k1∧M1(q)≤k1,?M1∈R(M01);同理，Σ2有界的，則?p∈P2∧?q∈Q2,?k2>0使得M2(p)≤k2∧M2(q)≤k2,?M2∈R(M02)。此類推，令k=max{k1,k2,…,kk},則?p∈P∧?q∈Q,M(p)≤k∧M(q)≤k,?M∈R(M0)，∴ OOPN系統Σ=(N,M0)是有界的。

(2)p?q。

證明：(1)p?q。

(2)p?q。

顯然,?M(PpA)*∈R(M(PpA)),使得(M(PpA)*[t>)。因為M(PpA)0是在(N,M0)上的投影,假設M(PpA)0[σ>M(PpA)[σ*>M(PpA)*,σ,σ*∈T,現在加入中的變遷(或變遷步)σa,可得σ′,σ″∈T″。又因為OOPN系統是活的,結合定義6可知,并且M(PpA)是M′在(N,M0)的投影,M(PpA)*是M*′在(N,M0)上的投影,所以對應于使得對應于?M(PpA)*∈R(M(PpA)),?M*′∈R(M′),(M(PpA)*[t′>)?(M*′[t>),所以不活,矛盾。因此可以得出從中通過抽象化操作獲得的系統(N,M0)和從中通過抽象化操作獲得的閉類網系統都是活的。因為{p|p∈Pa∧Ma(p)>0}?{p|p∈P′∧M′(p)>0}，則從OOPN系統中通過類網精細化操作所得到的系統Σ=(N,M0)和閉類網系統都是活的。

證明：(1)p?q。

(2)p?q。

3 應用實例

本節將提出的OOPN類網精細化操作方法應用到對智能垃圾分類揀放系統的建模分析，在準確反映系統工作流程的同時，也有利于工作人員對該系統進行研究和管理，說明了該方法的可行性和有效性。

智能垃圾分類揀放機模型主要由傳送帶，智能掃碼識別系統和揀放控制系統三部分組成。貼有專用二維碼的垃圾袋(內含垃圾)通過傳送帶運輸，到達掃碼區，掃碼區感應到垃圾，掃描儀自動掃碼，識別垃圾袋中所裝垃圾為可回收垃圾、有毒有害垃圾、干垃圾或濕垃圾中的一種，繼而揀放控制系統工作，對應垃圾倉門打開，機械臂自動將垃圾拎入對應倉內，繼續傳送后續垃圾進行處理。

首先給出粗略OOPN系統模型Σ=(N,M0)(見圖2)，然后用類網CNa(見圖3)對粗略模型中的pA進行細化。閉類網系統Σa如圖4所示。此時，精細化后的完整的OOPN系統模型已得到(見圖5)。同理，根據具體情況，還可以對圖2中的B、C先建立粗略模型，再進一步細化。

圖2 Σ=(N,M0)

圖3 類網CNa

圖4 閉類網系統

圖

圖2中圖例的含義如下：

pA:傳送帶 G3:通信網關

B:掃描識別區 C:分類揀放區

p21:空閑 p31:空閑

p22:等待掃碼許可 p32:等待揀放許可

p23:掃碼 p33:揀放垃圾

t21:申請掃碼 t31:申請揀放

t22:獲得掃碼許可 t32:獲得揀放許可

t23:完成掃碼 t33:完成揀放

q3、q4:消息庫所 q5、q6:消息庫所

G2:通信網關 G3:通信網關

圖2包括B:掃碼識別區、C:分類揀放區兩個對象。圖3、圖4中圖例含義如下：

p11:空閑 t11:感應到垃圾

p12:傳送垃圾 t12:到達掃描

p13:暫停 t13:運行通告

q1、q2:消息庫所 G1:通信網關

圖5中圖例的含義同圖2、圖3中相應圖例的含義。包含A:傳送帶、B:掃碼識別區、C:分類揀放區三個對象。

開始時，傳送帶轉動，掃碼區感應到有垃圾時，通過G1向B發送消息，使其獲得掃碼許可，從而進行掃碼得到垃圾類別，完成掃碼后通過G2向C發送消息，使其獲得分類揀放許可，從而將垃圾按類別揀放處理，揀放完成后，通過G3再向A發送消息，告知垃圾揀放完畢，可繼續運行。

實際上，對于OOPN系統Σ=(N,M0)，初始標識M0=(M0(pA),M0(p21),M0(p22),M0(p23),M0(p31),M0(p32),M0(p33),M0(q3),M0(q4),M0(q5),M0(q6))=(1,1,0,0,1,0,0,0,0,0,0)，易知Σ=(N,M0)是活的。

4 結 語

本文就面向對象Petri網的活性、有界性給出較完備的定義并提出OOPN類網精細化操作及其動態性質保持問題，然后利用提出的精細化操作對智能垃圾分類揀放系統進行建模分析，并證明了活性、有界性保持良好，進一步說明了該方法的實際價值。本文的結果為OOPN應用于復雜大系統的分析管理提供了有力支持。經精細化后得到目標網保持可回復性、公平性等性質是下一步的研究重點。