王兆誠(chéng) 夏傳良 張 瑋 王壯壯

(山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山東 濟(jì)南 250101)

0 引 言

在日常生活中，垃圾分類(lèi)處理逐漸被政府和人們重視并實(shí)踐應(yīng)用，但人為垃圾分類(lèi)需要公眾有高度的自覺(jué)意識(shí)，收效甚微，于是智能垃圾分類(lèi)揀放機(jī)應(yīng)運(yùn)而生，為了加快揀放機(jī)垃圾分類(lèi)處理的速度并降低功耗，有必要對(duì)這類(lèi)系統(tǒng)進(jìn)行建模研究和管理。智能垃圾分類(lèi)的過(guò)程有很明顯的模塊化、功能化特征，如垃圾識(shí)別、垃圾分揀、垃圾對(duì)應(yīng)回收和垃圾運(yùn)輸處理等。Petri網(wǎng)作為一種系統(tǒng)模型，一般對(duì)系統(tǒng)及行為進(jìn)行統(tǒng)一考慮，但不能體現(xiàn)出系統(tǒng)功能模塊的劃分。而利用面向?qū)ο蟮南嚓P(guān)定義對(duì)系統(tǒng)進(jìn)行功能、模塊的劃分，將整個(gè)復(fù)雜系統(tǒng)的建模過(guò)程有效地劃分為多個(gè)簡(jiǎn)單子系統(tǒng)，并相應(yīng)進(jìn)行建模研究正是面向?qū)ο驪etri網(wǎng)建模技術(shù)的突出優(yōu)勢(shì)所在[1]。

本文選擇面向?qū)ο驪etri網(wǎng)作為智能垃圾分類(lèi)揀放機(jī)系統(tǒng)的建立模型，用于研究、分析的工具，鑒于一次性建模存在復(fù)雜性、不確定性因素大的問(wèn)題，首先利用OOPN建立原始系統(tǒng)粗略、大體的模型，然后再運(yùn)用相應(yīng)的精細(xì)化方法對(duì)大概的模型進(jìn)行精細(xì)化處理，從而可得更加詳細(xì)、精確的目標(biāo)網(wǎng)系統(tǒng)模型。

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

除此之外，不少學(xué)者對(duì)面向?qū)ο驪etri網(wǎng)的性質(zhì)及精細(xì)化設(shè)計(jì)也做了研究。文獻(xiàn)[5]給出了擴(kuò)展面向?qū)ο驪etri網(wǎng)(EOOPN)的定義及性質(zhì)，如封裝性、抽象性；文獻(xiàn)[6]研究了將面向?qū)ο蟮睦^承性以及與之緊密聯(lián)系的多態(tài)性引入OOPN網(wǎng)；文獻(xiàn)[7-8]研究了面向?qū)ο驪etri網(wǎng)的信息交互性，并基于OOPN對(duì)高速鐵路行車(chē)指揮系統(tǒng)進(jìn)行建模；文獻(xiàn)[9]給出了EOOPN模型中的構(gòu)件細(xì)化及其一種類(lèi)型，指出精細(xì)化的主要思想是將抽象的庫(kù)所(ABP)、變遷(ABT)和標(biāo)識(shí)(Token)精細(xì)化為構(gòu)件子網(wǎng)或更詳細(xì)的抽象庫(kù)所、變遷和標(biāo)識(shí)；文獻(xiàn)[10]詳細(xì)給出了EOOPN中的其他三種構(gòu)件細(xì)化方法(ABP細(xì)化、ABT細(xì)化和Token細(xì)化)，提出了結(jié)構(gòu)良好性的定義，也證明了細(xì)化后仍保持結(jié)構(gòu)良好性。上述工作雖然研究了OOPN的一些性質(zhì)和精細(xì)化操作方法，但對(duì)OOPN的活性、有界性及精細(xì)化后對(duì)該性質(zhì)的保持未做詳細(xì)研究說(shuō)明。

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

1 基本定義和符號(hào)

本節(jié)給出面向?qū)ο驪etri網(wǎng)及系統(tǒng)的相關(guān)定義和示例，以及系統(tǒng)活性、有界性的定義。

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

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

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

F={FI,FO}是網(wǎng)N的流關(guān)系，F(xiàn)I?(T×P或T×Q或G×Q)是一確定的輸入弧集合，F(xiàn)O?(P×T或Q×T或Q×G)是一確定的輸出弧集合；

Q={q1,q2,…,qm}是一確定非空的消息庫(kù)所集合，分為輸入消息庫(kù)所QI和輸出消息庫(kù)所QO，從網(wǎng)關(guān)接收到消息的為輸入消息庫(kù)所，向網(wǎng)關(guān)發(fā)送消息的為輸出消息庫(kù)所；

G={G1,G2,…,Gm}是對(duì)象間的網(wǎng)關(guān)集合；

W:F→{1,2,3，…}稱(chēng)為權(quán)函數(shù)；

Σ=(N,M)稱(chēng)為一個(gè)OOPN系統(tǒng)，M:P→{0,1,2,…}和QI→{0,1,2，…}是Σ的一個(gè)標(biāo)識(shí)，其中，M0是初始標(biāo)識(shí)。

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

圖1 一個(gè)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];

權(quán)函數(shù)W未標(biāo)識(shí)出的默認(rèn)為1。

其中，消息庫(kù)所Q用橢圓形表示，它類(lèi)似于對(duì)象與外界的通信窗口；通信網(wǎng)關(guān)G用粗實(shí)線(xiàn)表示，它與變遷類(lèi)似，用來(lái)實(shí)現(xiàn)對(duì)象間的連接；抽象和封裝好的類(lèi)用圓角矩形來(lái)表示；類(lèi)的“實(shí)例”數(shù)目用Petri網(wǎng)中的標(biāo)識(shí)來(lái)表示[11]。

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

1) 變遷t∈T，當(dāng)·t∩Q=Φ時(shí)，t可稱(chēng)為在M下使能的充分必要條件為:

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

(1)

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

當(dāng)t∩Q≠Φ時(shí)，t可稱(chēng)為在M下使能的充分必要條件為:

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

(2)

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

2) 變遷t可以發(fā)生的條件為:t能夠在標(biāo)識(shí)M下使能；發(fā)生的結(jié)果為:M→M′。

(3)

(4)

定義3設(shè)Σ=(N,M0)是一個(gè)OOPN系統(tǒng)：

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

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

定義4設(shè)Σ=(N,M0)是一個(gè)OOPN系統(tǒng)：

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

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

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

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))。

則稱(chēng)Na是N的一個(gè)OOPN子網(wǎng)，或者稱(chēng)為類(lèi)網(wǎng)，記為CNa。

為了更形象準(zhǔn)確地定義類(lèi)網(wǎng)，規(guī)定：

在類(lèi)網(wǎng)中，消息標(biāo)識(shí)只能從輸入消息庫(kù)所進(jìn)，從輸出消息庫(kù)所出，不可逆。

定義6類(lèi)網(wǎng)精細(xì)化操作Re f(pA,CNa):將面向?qū)ο驪etri網(wǎng)N=(P,T;F,Q,G,W)中的庫(kù)所pA精細(xì)化為一個(gè)類(lèi)網(wǎng)CNa=(Pa,Ta;Fa,Qa,Ga,Wa)(用類(lèi)網(wǎng)CNa來(lái)替換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所對(duì)應(yīng)的分量以后的向量，?A是Ma的零向量。

2 OOPN的類(lèi)網(wǎng)精細(xì)化操作性質(zhì)分析

本節(jié)先提出關(guān)于OOPN系統(tǒng)的活性、有界性定理，再提出經(jīng)過(guò)類(lèi)網(wǎng)精細(xì)化操作后系統(tǒng)仍保持活性、有界性的充要條件。

證明：(1)p?q。

(2)p?q。

證明：(1)p?q。

∵ 系統(tǒng)Σ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)。此類(lèi)推，令k=max{k1,k2,…,kk},則?p∈P∧?q∈Q,M(p)≤k∧M(q)≤k,?M∈R(M0)，∴ OOPN系統(tǒng)Σ=(N,M0)是有界的。

(2)p?q。

證明：(1)p?q。

(2)p?q。

顯然,?M(PpA)*∈R(M(PpA)),使得(M(PpA)*[t>)。因?yàn)镸(PpA)0是在(N,M0)上的投影,假設(shè)M(PpA)0[σ>M(PpA)[σ*>M(PpA)*,σ,σ*∈T,現(xiàn)在加入中的變遷(或變遷步)σa,可得σ′,σ″∈T″。又因?yàn)镺OPN系統(tǒng)是活的,結(jié)合定義6可知,并且M(PpA)是M′在(N,M0)的投影,M(PpA)*是M*′在(N,M0)上的投影,所以對(duì)應(yīng)于使得對(duì)應(yīng)于?M(PpA)*∈R(M(PpA)),?M*′∈R(M′),(M(PpA)*[t′>)?(M*′[t>),所以不活,矛盾。因此可以得出從中通過(guò)抽象化操作獲得的系統(tǒng)(N,M0)和從中通過(guò)抽象化操作獲得的閉類(lèi)網(wǎng)系統(tǒng)都是活的。因?yàn)閧p|p∈Pa∧Ma(p)>0}?{p|p∈P′∧M′(p)>0}，則從OOPN系統(tǒng)中通過(guò)類(lèi)網(wǎng)精細(xì)化操作所得到的系統(tǒng)Σ=(N,M0)和閉類(lèi)網(wǎng)系統(tǒng)都是活的。

證明：(1)p?q。

(2)p?q。

3 應(yīng)用實(shí)例

本節(jié)將提出的OOPN類(lèi)網(wǎng)精細(xì)化操作方法應(yīng)用到對(duì)智能垃圾分類(lèi)揀放系統(tǒng)的建模分析，在準(zhǔn)確反映系統(tǒng)工作流程的同時(shí)，也有利于工作人員對(duì)該系統(tǒng)進(jìn)行研究和管理，說(shuō)明了該方法的可行性和有效性。

智能垃圾分類(lèi)揀放機(jī)模型主要由傳送帶，智能掃碼識(shí)別系統(tǒng)和揀放控制系統(tǒng)三部分組成。貼有專(zhuān)用二維碼的垃圾袋(內(nèi)含垃圾)通過(guò)傳送帶運(yùn)輸，到達(dá)掃碼區(qū)，掃碼區(qū)感應(yīng)到垃圾，掃描儀自動(dòng)掃碼，識(shí)別垃圾袋中所裝垃圾為可回收垃圾、有毒有害垃圾、干垃圾或濕垃圾中的一種，繼而揀放控制系統(tǒng)工作，對(duì)應(yīng)垃圾倉(cāng)門(mén)打開(kāi)，機(jī)械臂自動(dòng)將垃圾拎入對(duì)應(yīng)倉(cāng)內(nèi)，繼續(xù)傳送后續(xù)垃圾進(jìn)行處理。

首先給出粗略O(shè)OPN系統(tǒng)模型Σ=(N,M0)(見(jiàn)圖2)，然后用類(lèi)網(wǎng)CNa(見(jiàn)圖3)對(duì)粗略模型中的pA進(jìn)行細(xì)化。閉類(lèi)網(wǎng)系統(tǒng)Σa如圖4所示。此時(shí)，精細(xì)化后的完整的OOPN系統(tǒng)模型已得到(見(jiàn)圖5)。同理，根據(jù)具體情況，還可以對(duì)圖2中的B、C先建立粗略模型，再進(jìn)一步細(xì)化。

圖2 Σ=(N,M0)

圖3 類(lèi)網(wǎng)CNa

圖4 閉類(lèi)網(wǎng)系統(tǒng)

圖

圖2中圖例的含義如下：

pA:傳送帶 G3:通信網(wǎng)關(guān)

B:掃描識(shí)別區(qū) C:分類(lèi)揀放區(qū)

p21:空閑 p31:空閑

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

p23:掃碼 p33:揀放垃圾

t21:申請(qǐng)掃碼 t31:申請(qǐng)揀放

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

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

q3、q4:消息庫(kù)所 q5、q6:消息庫(kù)所

G2:通信網(wǎng)關(guān) G3:通信網(wǎng)關(guān)

圖2包括B:掃碼識(shí)別區(qū)、C:分類(lèi)揀放區(qū)兩個(gè)對(duì)象。圖3、圖4中圖例含義如下：

p11:空閑 t11:感應(yīng)到垃圾

p12:傳送垃圾 t12:到達(dá)掃描

p13:暫停 t13:運(yùn)行通告

q1、q2:消息庫(kù)所 G1:通信網(wǎng)關(guān)

圖5中圖例的含義同圖2、圖3中相應(yīng)圖例的含義。包含A:傳送帶、B:掃碼識(shí)別區(qū)、C:分類(lèi)揀放區(qū)三個(gè)對(duì)象。

開(kāi)始時(shí)，傳送帶轉(zhuǎn)動(dòng)，掃碼區(qū)感應(yīng)到有垃圾時(shí)，通過(guò)G1向B發(fā)送消息，使其獲得掃碼許可，從而進(jìn)行掃碼得到垃圾類(lèi)別，完成掃碼后通過(guò)G2向C發(fā)送消息，使其獲得分類(lèi)揀放許可，從而將垃圾按類(lèi)別揀放處理，揀放完成后，通過(guò)G3再向A發(fā)送消息，告知垃圾揀放完畢，可繼續(xù)運(yùn)行。

實(shí)際上，對(duì)于OOPN系統(tǒng)Σ=(N,M0)，初始標(biāo)識(shí)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 結(jié) 語(yǔ)

本文就面向?qū)ο驪etri網(wǎng)的活性、有界性給出較完備的定義并提出OOPN類(lèi)網(wǎng)精細(xì)化操作及其動(dòng)態(tài)性質(zhì)保持問(wèn)題，然后利用提出的精細(xì)化操作對(duì)智能垃圾分類(lèi)揀放系統(tǒng)進(jìn)行建模分析，并證明了活性、有界性保持良好，進(jìn)一步說(shuō)明了該方法的實(shí)際價(jià)值。本文的結(jié)果為OOPN應(yīng)用于復(fù)雜大系統(tǒng)的分析管理提供了有力支持。經(jīng)精細(xì)化后得到目標(biāo)網(wǎng)保持可回復(fù)性、公平性等性質(zhì)是下一步的研究重點(diǎn)。