對稱離散事件系統(tǒng)狀態(tài)樹結(jié)構(gòu)模型的控制函數(shù)不變性研究

焦亭,甘永梅,肖國春

(西安交通大學(xué)電氣工程學(xué)院,710049,西安)

?

對稱離散事件系統(tǒng)狀態(tài)樹結(jié)構(gòu)模型的控制函數(shù)不變性研究

焦亭,甘永梅,肖國春

(西安交通大學(xué)電氣工程學(xué)院,710049,西安)

針對對稱離散事件系統(tǒng)中使用監(jiān)督控制理論計(jì)算得到的自動機(jī)形式的監(jiān)督控制器狀態(tài)數(shù)較多且無法清晰反映控制邏輯等問題,提出了基于狀態(tài)樹結(jié)構(gòu)的抽象控制函數(shù)計(jì)算方法。該方法通過充分利用系統(tǒng)的對稱性,對避免緩沖區(qū)出現(xiàn)上溢或者下溢的性能指標(biāo),采用事件重標(biāo)記映射提取各組中處于加工完成狀態(tài)的組件數(shù)目,從而省去了各組件復(fù)雜的運(yùn)行細(xì)節(jié);然后利用狀態(tài)樹結(jié)構(gòu)計(jì)算得到基于抽象狀態(tài)信息的控制函數(shù);最后,結(jié)合各組組件并行工作與串行工作的實(shí)例,分析所得控制函數(shù)的不變性,即在緩沖區(qū)容量固定的前提下,控制函數(shù)所需的狀態(tài)信息與組件總數(shù)量無關(guān)。實(shí)驗(yàn)結(jié)果表明:在實(shí)際應(yīng)用中借助控制函數(shù)的不變性可在結(jié)構(gòu)相同的組件增減時(shí)免于重復(fù)計(jì)算控制函數(shù);各組中重標(biāo)記為同一事件的各可控事件可由同一控制函數(shù)進(jìn)行使能,有效減少了控制函數(shù)的個(gè)數(shù);相比于自動機(jī)形式的監(jiān)督控制器,控制函數(shù)狀態(tài)數(shù)更少且能更清晰地描述控制邏輯。

離散事件系統(tǒng);監(jiān)督控制理論;狀態(tài)樹結(jié)構(gòu);控制函數(shù);謂詞邏輯

在由Ramadge與Wonham建立的離散事件系統(tǒng)監(jiān)督控制理論[1-2]中,由多組具有相同結(jié)構(gòu)組件組成的系統(tǒng)具有對稱性。對于不關(guān)注各組件之間性能指標(biāo)差異的系統(tǒng),可利用離散事件系統(tǒng)的對稱性對系統(tǒng)進(jìn)行化簡。文獻(xiàn)[3]利用群理論描述具有相同結(jié)構(gòu)組件串聯(lián)所構(gòu)成系統(tǒng)的對稱性,以達(dá)到簡化控制器的目的。文獻(xiàn)[4]對由具有相同結(jié)構(gòu)組件組成的系統(tǒng)執(zhí)行商自動機(jī)構(gòu)建運(yùn)算,以簡化集中監(jiān)督控制器規(guī)模。對于由同一模板生成的系統(tǒng),文獻(xiàn)[5]分析了系統(tǒng)的死鎖與阻塞問題,文獻(xiàn)[6]提出了基于廣播方式且滿足交換律、結(jié)合律的系統(tǒng)合成運(yùn)算算法。這些化簡方法均基于商自動機(jī)構(gòu)建算法,計(jì)算過程復(fù)雜,本文提出通過事件重標(biāo)記映射提取系統(tǒng)的抽象狀態(tài)信息以簡化系統(tǒng)。事件重標(biāo)記映射不但能在很大程度上縮減被控對象與監(jiān)督控制器規(guī)模,而且化簡的實(shí)現(xiàn)過程更加直觀簡便,且所得的重標(biāo)記后的監(jiān)督控制器能直接用于控制。

在利用事件重標(biāo)記映射提取系統(tǒng)的抽象狀態(tài)信息后,基于所得的抽象狀態(tài)信息建立狀態(tài)樹結(jié)構(gòu)模型[7-10],計(jì)算得到系統(tǒng)中各可控事件的控制函數(shù)。此外,文獻(xiàn)[11]通過證明使用supreduce算法計(jì)算所得控制同余(control congruence)的不變性以證明控制器的不變性,但此證明過程較為繁瑣,而狀態(tài)樹結(jié)構(gòu)中控制函數(shù)清晰的控制邏輯使得控制函數(shù)的不變性證明變得直觀簡便。

文獻(xiàn)[12-14]中的性能指標(biāo)主要是參數(shù)化模板或謂詞表達(dá)式,本文主要研究在緩沖區(qū)容量固定的前提下防止緩沖區(qū)上溢與下溢的性能指標(biāo)。在緩沖區(qū)容量固定的情況下,借助狀態(tài)樹結(jié)構(gòu)計(jì)算系統(tǒng)中可控事件的控制函數(shù),可發(fā)現(xiàn)控制函數(shù)具有不變性,即控制函數(shù)不隨組件數(shù)目的增減而變化。

1 基礎(chǔ)知識

1.1 DES自動機(jī)模型

離散事件系統(tǒng)利用自動機(jī)對系統(tǒng)進(jìn)行建模,自動機(jī)可表示為5元組G=(Q,Σ,δ,q0,Qm),其中Q為狀態(tài)集合,Σ為事件集合,δ:Q×Σ→Q用于描述系統(tǒng)中狀態(tài)的變遷關(guān)系,q0為初始狀態(tài),Qm?Q為標(biāo)識狀態(tài)集合。一般地,轉(zhuǎn)移函數(shù)可擴(kuò)展為δ:Q×Σ*→Q,其中Σ*表示空字符串ε與Σ上的所有有限長度字符串的并集,并用δ(q0,s)!表示δ(q0,s)有定義。定義自動機(jī)G所表示語言的閉特性為L(G)={s∈Σ*|δ(q0,s)!},標(biāo)識特性為Lm(G)={s∈Σ*|δ(q0,s)∈Qm}。

對于G的監(jiān)督控制可定義為映射V:L(G)→Γ,其中所有控制模式組成的集合Γ記作Γ={γ∈Pwr(Σ)|γ?Σu}。G在V的監(jiān)控下可記作V/G,并用L(V/G)表示V/G的閉特性[1]。令M?Lm(G),定義(M,G)的標(biāo)識非阻塞監(jiān)督控制為映射V:L(G)→Γ,V/G的標(biāo)識特性定義為Lm(V/G)=L(V/G)∩M。假設(shè)用E?Σ*表示性能指標(biāo),E中的所有可控語言表示為C(E)={K?E|K關(guān)于G可控}。因C(E)中的元素形成上晶格結(jié)構(gòu),存在最大元素supC(E)=∪{K|K∈C(E)},并可由TCT軟件中的supcon算法計(jì)算得到對應(yīng)自動機(jī)形式的監(jiān)督控制器。

1.2 狀態(tài)樹結(jié)構(gòu)

對DES進(jìn)行建模的狀態(tài)樹結(jié)構(gòu)[8-9]可表示為6元組Gst=(St,H,Σ,Δ,St0,Stm),其中狀態(tài)樹St將系統(tǒng)狀態(tài)集合表示為分層結(jié)構(gòu),H為被控系統(tǒng)Gst中描述系統(tǒng)局部行為的各組件實(shí)時(shí)子整體,Σ為事件集合,其被劃分為可控事件集合Σc與不可控事件集合Σu。令S(St)表示St上所有的子狀態(tài)樹集合,Δ:S(St)×Σ→S(St)為全局轉(zhuǎn)移函數(shù),St0∈S(St)為初始狀態(tài)樹,Stm?S(St)為標(biāo)識狀態(tài)樹集合。

B(St)?S(St)表示所有基本狀態(tài)樹集合,定義B(St)上的謂詞P:B(St)→{0,1},其中0、1分別表示邏輯假、邏輯真。謂詞P可由基本狀態(tài)樹集合BP:={b∈B(St)|P(b)=1}判定,其中P(b)=1常被記作bP。對于子狀態(tài)樹T∈S(St)定義TP當(dāng)且僅當(dāng)(?b∈B(T))bP,狀態(tài)樹Gst也可記作Gst=(St,H,Σ,Δ,P0,Pm),其中P0、Pm為初始謂詞、標(biāo)識謂詞。

定義P(St)為B(St)上的謂詞集合。引入偏序關(guān)系,使得PP′,當(dāng)且僅當(dāng)(P)∨P′,對任意b∈B(St),如果bP?bP′,則PP′?？蛇_(dá)謂詞、協(xié)同可達(dá)謂詞可分別記作R(Gst,P)、Cr(Gst,P),如果R(Gst,P)Cr(Gst,P),則稱謂詞P關(guān)于Gst非阻塞。

對任意σ∈Σ定義映射Mσ(P):P(St)→P(St)來表示bMσ(P),當(dāng)且僅當(dāng)Δ(b,σ)P。如果P滿足(?σ∈Σu)PMσ(P),則稱謂詞P弱可控。將謂詞P所有非阻塞且弱可控的子謂詞記作NC(P),由于NC(P)非空且在任意并運(yùn)算∨作用下封閉,故存在最大元素supNC(P):=∨{K|K∈NC(P)}。定義狀態(tài)反饋控制f:B(St)→Π,Π:={Σ′?Σ|Σu?Σ′},對任意事件σ∈Σ定義控制函數(shù)fσ:B(St)→{0,1},fσ(b)=1當(dāng)且僅當(dāng)σ∈f(b),控制函數(shù)f可由集合{fσ|σ∈Σ}表示。由定義可知,對于所有不可控事件σ,fσ(b)=1。狀態(tài)反饋控制f可由控制函數(shù)fσ:=Mσ(supNC(P))表示,對任意b∈B(St),fσ(b)=1,當(dāng)且僅當(dāng)Δ(b,σ)supNC(P)?？刂坪瘮?shù)可由STSLib軟件計(jì)算得到[8]。

1.3 事件重標(biāo)記映射

事件重標(biāo)記映射R的示意圖如圖1所示,φ的結(jié)果代表自動機(jī)對應(yīng)的語言。使用TCT中改進(jìn)后的relabel算法,用λ表示,計(jì)算進(jìn)行事件重標(biāo)記后所得的自動機(jī)GR=λ(G),使其滿足Lm(GR)=R(Lm(G)),L(GR)=R(L(G))。

圖1 重標(biāo)記映射及實(shí)現(xiàn)過程示意圖

事件重標(biāo)記算法λ主要分2步實(shí)現(xiàn):將G中所有不可觀測事件重標(biāo)記為空字符ε,其余事件按事先制定的重標(biāo)記規(guī)則進(jìn)行標(biāo)記;將事件重標(biāo)記后得到的不確定有限狀態(tài)自動機(jī)通過子集生成算法[15]轉(zhuǎn)換為確定有限狀態(tài)自動機(jī),即為所求的結(jié)果GR。子集生成算法的功能為將不確定有限狀態(tài)自動機(jī)轉(zhuǎn)換為與其等價(jià)的確定有限狀態(tài)自動機(jī)。對于任意字符串t∈Lm(GR),均存在s∈Lm(G),使得R(s)=t;反之,對于任意字符串s∈Lm(G),均有R(s)∈Lm(GR),所以Lm(GR)=R(Lm(G)),同理可得L(GR)=R(L(G))。在具有對稱性的離散事件系統(tǒng)G中,被事件重標(biāo)記映射標(biāo)記為同一字符串的所有字符串進(jìn)入的狀態(tài)將生成一個(gè)狀態(tài)子集。由于系統(tǒng)的對稱性,所生成狀態(tài)子集為對G中狀態(tài)的一個(gè)等價(jià)劃分[16],因此生成的狀態(tài)子集總數(shù)量少于原系統(tǒng)的狀態(tài)總數(shù),即進(jìn)行事件重標(biāo)記后所得結(jié)果GR的狀態(tài)數(shù)比G的狀態(tài)數(shù)少。

2 抽象狀態(tài)信息提取

本文研究的系統(tǒng)由n∈N組具有相同結(jié)構(gòu)的組件組成,對于各組Gi,i∈{1,…,n}中的任意組件Gij,Gij′j,j′∈{1,…,|Gi|},λ(Gij)=λ(Gij′),即通過事件重標(biāo)記映射忽略各組中組件個(gè)體差異。

本文制造系統(tǒng)如圖2所示,系統(tǒng)中的組件劃分為G1={Ii},i∈{1,…,m};G2={Oj},j∈{1,…,n},對所有i∈{1,…,m},j∈{1,…,n},將事件i11、i12、j21、j22分別重標(biāo)記為11、12、21、22。本文所有的狀態(tài)轉(zhuǎn)移圖中,用無源的單向箭頭進(jìn)入狀態(tài)表示初始狀態(tài),用無目標(biāo)狀態(tài)的箭頭出來狀態(tài)表示標(biāo)識狀態(tài),如果一個(gè)狀態(tài)既是初始狀態(tài)又是標(biāo)識狀態(tài),則用雙向箭頭表示。

圖2 本文制造系統(tǒng)示意圖

在忽略組件個(gè)體差異后,針對防止緩沖區(qū)出現(xiàn)上溢或下溢的性能指標(biāo),需要獲知各組中當(dāng)前狀態(tài)處于即將往緩沖區(qū)中放入工件的組件數(shù)量,即Ii中處于狀態(tài)1的組件數(shù)量。為獲得該數(shù)據(jù),給出定義Ii=(Zi,ΣIi,δIi,zio,Zim),將其中取工件和往緩沖區(qū)中放入工件的事件分別記作σIil、σIiu。假定δIi(q,σIiu)=q′,擬放入工件事件集合為ΣIiq={σ∈ΣIi|σ≠σIiu,δIi(q,σ)!}。對于圖2中的組件Ii,q=1,σIil=i11,σIiu=i12,ΣIiq=?;對于圖3中的組件Ii,q=1,σIil=i11,σIiu=i12,ΣIiq={i14}。ΣIi中其他事件因與緩沖區(qū)上溢或下溢無關(guān)可設(shè)為不可觀測事件,在進(jìn)行λ運(yùn)算時(shí)這些事件被重標(biāo)記為ε。

圖3 復(fù)雜組件重標(biāo)記前后的結(jié)構(gòu)示意圖

3 控制函數(shù)不變性研究

3.1 問題描述

經(jīng)事件重標(biāo)記映射計(jì)算得到的各組抽象狀態(tài)信息可建立狀態(tài)樹結(jié)構(gòu)模型,將自動機(jī)轉(zhuǎn)換為狀態(tài)樹結(jié)構(gòu)的具體過程可參見文獻(xiàn)[8],然后通過STSLib軟件計(jì)算得到各可控事件對應(yīng)的控制函數(shù)。

對于基于抽象狀態(tài)信息建立的狀態(tài)樹結(jié)構(gòu)Gst與防止緩存區(qū)上溢與下溢的性能指標(biāo)對應(yīng)的謂詞表達(dá)式P,假設(shè)利用STSLib軟件計(jì)算得到各可控事件τi,對應(yīng)的控制函數(shù)為fi,i∈{1,…,|Tc|},其中Tc=R(Σc):={τi}表示重標(biāo)記后系統(tǒng)的可控事件集合。如果對任意數(shù)目的組件,控制函數(shù)fi保持不變,則稱控制函數(shù)具有不變性。

3.2 并行工作系統(tǒng)控制函數(shù)不變性分析

對于圖2中所示系統(tǒng),各組中的組件均處于并行工作狀態(tài),利用事件重標(biāo)記映射分別計(jì)算輸入側(cè)與輸出側(cè)的控制信息模型IR、OR。令m=3,n=1,經(jīng)STSLib軟件計(jì)算可得事件11、21的控制函數(shù)分別為f11、f21,如圖4所示。其中,實(shí)線箭頭代表邏輯真,虛線箭頭代表邏輯假。

圖4 控制函數(shù)f11、f21示意圖

以f11為例,IR有4個(gè)狀態(tài),用IR0=0、IR1=0表示IR的當(dāng)前狀態(tài)為狀態(tài)0,用IR0=1、IR1=0表示IR的當(dāng)前狀態(tài)為狀態(tài)1,用IR0=0、IR1=1表示IR的當(dāng)前狀態(tài)為狀態(tài)2,用IR0=1、IR1=1表示IR的當(dāng)前狀態(tài)為狀態(tài)3。由于緩沖區(qū)B有3個(gè)狀態(tài),因此用B0=0、B1=0表示B的當(dāng)前狀態(tài)為狀態(tài)0;用B0=1、B1=0表示B的當(dāng)前狀態(tài)為狀態(tài)1;用B0=0、B1=1表示B的當(dāng)前狀態(tài)為狀態(tài)2。箭頭所指向的方框如果為0,則表示系統(tǒng)在當(dāng)前狀態(tài)組合下事件11(即各事件i11)不能發(fā)生;箭頭所指向的方框如果為1,則表示系統(tǒng)在當(dāng)前狀態(tài)組合下事件11(即各事件i11)可以發(fā)生,此時(shí)緩沖區(qū)中有1個(gè)工件,輸入側(cè)無組件工作,可再允許輸入側(cè)1個(gè)組件取工件。

命題1 對任意m≥3,n≥1,f11,f21具有不變性。

系統(tǒng)對應(yīng)的狀態(tài)樹結(jié)構(gòu)模型Gst:=(St,H,T,Δ,b0,{b0}),如圖5所示,其中重標(biāo)記后事件集合T={11,12,21,22}。b0表示初始基本狀態(tài)樹,其中vRI=0,vRO=0,vB=0,即IR、OR、B均處于初始狀態(tài)。由f11可知使能事件11的謂詞為i+k<2,其中i∈{0,…,m},j∈{0,…,n},k∈{0,…,2},i、j分別表示輸入側(cè)與輸出側(cè)處于狀態(tài)1的組件數(shù)量,k表示緩沖區(qū)中現(xiàn)有組件數(shù)量。

圖5 狀態(tài)樹結(jié)構(gòu)Gst

由于IR中僅有狀態(tài)0、1、2可在系統(tǒng)運(yùn)行過程中被訪問到,因此B11不變,并且只有狀態(tài)0、1允許事件11發(fā)生,因此B11可等價(jià)地表示成f11。f11可解讀為:如果B0=0、B1=0緩沖區(qū)為空,當(dāng)輸入側(cè)無組件處于狀態(tài)1(IR0=0,IR1=0)或僅有1個(gè)組件處于狀態(tài)1(IR0=1,IR1=0)時(shí)事件11被使能;如果B0=1、B1=0,即緩沖區(qū)已有1個(gè)工件,則輸入側(cè)無組件處于狀態(tài)1(IR0=0,IR1=0)時(shí)事件11才能被使能;如果B0=0、B1=1,即緩沖區(qū)已滿,則事件11不被使能,f11具有不變性。使能事件21的謂詞為k=1或2,在緩沖區(qū)容量固定為2的前提下,對任意m≥3、n≥1該謂詞保持不變,f21具有不變性。

由命題1可知,對任意數(shù)量的輸入側(cè)與輸出側(cè)組件m≥3、n≥1,輸入側(cè)組件開始工作(事件i11被使能)當(dāng)且僅當(dāng)f11使能事件11;輸出側(cè)組件開始工作(事件j21被使能)當(dāng)且僅當(dāng)f21使能事件21。由于f11、f21與m、n取值無關(guān),因此控制函數(shù)具有不變性。

當(dāng)m=1時(shí),IR僅有2個(gè)狀態(tài),輸入側(cè)至多有1個(gè)組件處于狀態(tài)1,因此只要緩沖區(qū)未滿(B1=0),f11就可使能事件11。當(dāng)m=2時(shí),IR有3個(gè)狀態(tài),此時(shí)輸入側(cè)至多有2個(gè)組件處于狀態(tài)1,當(dāng)緩沖區(qū)為空時(shí),不論輸入側(cè)組件處于何種狀態(tài),f11均可使能事件11。因此,m=1或2只是m≥3時(shí)的特殊情況。

針對防止緩存區(qū)上溢與下溢的性能指標(biāo),以m=9、n=9為例,文獻(xiàn)[11]中計(jì)算得到的集中監(jiān)督控制器有29 184個(gè)狀態(tài),其對應(yīng)的重標(biāo)記后的自動機(jī)有60個(gè)狀態(tài);相比之下,滿足相同的性能指標(biāo),f11、f21比集中監(jiān)督控制器更為簡化。此外,集中監(jiān)督控制器的規(guī)模將隨著輸入側(cè)與輸出側(cè)組件數(shù)量的增多而增大,而f11、f21保持不變。

3.3 串行工作系統(tǒng)控制函數(shù)不變性分析

圖6 具有對稱性的串行工作系統(tǒng)及其自動機(jī)示意圖

對于圖6所示串行工作系統(tǒng),文獻(xiàn)[3]選用構(gòu)建商自動機(jī)的方式對其進(jìn)行化簡,實(shí)現(xiàn)過程較為復(fù)雜,本文從控制函數(shù)不變性的角度直觀地獲得系統(tǒng)的控制邏輯,并結(jié)合系統(tǒng)對稱性證明M0、M1、M2可由同一謂詞進(jìn)行控制。

該系統(tǒng)中,緩沖區(qū)B0、B1、B2的容量均為1,初始值分別為0,1,1;M0、M1、M2具有對稱性。建立該系統(tǒng)的狀態(tài)樹結(jié)構(gòu)模型可得圖7所示的可控事件1、3、5的控制函數(shù)f1、f3、f5。由于f1、f3、f5只與緩沖區(qū)B0、B1、B2的狀態(tài)(空或者滿)有關(guān),因此系統(tǒng)中可控事件的使能只取決于緩沖區(qū)狀態(tài)(空或者滿),而與各組件狀態(tài)無關(guān);由觀察可知f1、f3、f5滿足謂詞P:αi,i∈{0,1,2}被使能當(dāng)且僅當(dāng)緩沖區(qū)Bi空、Bi?2滿,其中i?2=(i+2)mod3。

圖7 控制函數(shù)f1、f3、f5示意圖

命題2f1、f3、f5滿足謂詞P。

由命題2可知,可利用謂詞P對各組件的運(yùn)行進(jìn)行監(jiān)督控制,并且對于不同的緩沖區(qū)初始狀態(tài),謂詞P均能防止各緩沖區(qū)出現(xiàn)上溢與下溢,因此具有不變性。

4 結(jié) 論

本文利用離散事件系統(tǒng)的對稱性選用事件重標(biāo)記映射提取各組組件的狀態(tài)信息,然后基于狀態(tài)信息構(gòu)建狀態(tài)樹結(jié)構(gòu)從而計(jì)算系統(tǒng)中可控事件對應(yīng)的控制函數(shù),并結(jié)合組件并行與串行工作的實(shí)例證明控制函數(shù)的不變性。由于控制函數(shù)具有不變性,在實(shí)際應(yīng)用中可在組件增減時(shí)免于重復(fù)計(jì)算控制函數(shù),且各組中重標(biāo)記為同一事件的各可控事件可由同一控制函數(shù)進(jìn)行使能,有效減小了控制函數(shù)的個(gè)數(shù)。相比于自動機(jī)形式的監(jiān)督控制器,控制函數(shù)所需狀態(tài)數(shù)更少。

本文所得的控制函數(shù)不變性建立在防止緩沖區(qū)出現(xiàn)上溢與下溢的性能指標(biāo)之上,由于組件個(gè)體的細(xì)節(jié)與該性能指標(biāo)無關(guān),因此各組組件之間的交互不會影響到相應(yīng)控制函數(shù)的選擇,只要組件當(dāng)前處于可控事件有定義的狀態(tài)且控制函數(shù)允許該可控事件對應(yīng)的重標(biāo)記事件發(fā)生,就允許組件執(zhí)行該可控事件。

[1] WONHAM W M. Supervisory control of discrete-event systems [EB/OL]. [2016-03-01]. http: ∥www.control.utoronto.ca/～wonham/.

[2] CASSANDRAS C G, LAFORTUNE S. Introduction to discrete event systems [M]. Berlin, Germany: Springer, 2008: 268-369.

[3] EYZELL J M, CURY J E R. Exploiting symmetry in the synthesis of supervisors for discrete event systems [J]. IEEE Transactions on Automatic Control, 2001, 46(9): 1500-1505.

[4] ROHLOFF K, LAFORTUNE S. The verification and control of interacting similar discrete event systems [J]. SIAM Journal on Control and Optimization, 2006, 45(2): 634-667.

[5] WANG W, SU R, LIN L. On analysis of deadlock and blocking freeness in isomorphic module systems [C]∥American Control Conference. Piscataway, NJ, USA: IEEE, 2013: 923-928.

[6] SU R. Discrete-event modeling of multi-agent systems with broadcasting-based parallel composition [J]. Automatica, 2013, 49(11): 3502-3506.

[7] BRYANT R. Graph-based algorithms for Boolean function manipulation [J]. IEEE Transactions on Computers, 1986, 35(8): 677-691.

[8] MA C, WONHAM W M. Nonblocking supervisory control of state tree structures [M]. Berlin, Germany: Springer, 2005: 11-125.

[9] MA C, WONHAM W M. Nonblocking supervisory control of state tree structures [J]. IEEE Transactions on Automatic Control, 2006, 51(5): 782-793.

[10]晁武杰, 甘永梅, 王兆安, 等. 實(shí)時(shí)狀態(tài)樹結(jié)構(gòu)模型的最優(yōu)非阻塞模塊化監(jiān)督控制研究 [J]. 西安交通大學(xué)學(xué)報(bào), 2013, 47(4): 86-91. CHAO Wujie, GAN Yongmei, WANG Zhao’an, et al. An optimal nonblocking modular supervisory control to real-time state tree structures [J]. Journal of Xi’an Jiaotong University, 2013, 47(4): 86-91.

[11]JIAO T, GAN Y, YANG X, et al. Exploiting symmetry of discrete-event systems with parallel components by relabeling [C]∥TENCON 2015-2015 IEEE Region 10 Conference. Piscataway, NJ, USA: IEEE, 2015: 1-4.

[12]BHERER H, DESHARNAIS J, ST-DENIS R. Control of parameterized discrete event systems [J]. Discrete Event Dynamic Systems, 2009, 19(2): 213-265.

[13]GRIGOROV L, BUTLER B E, CURY J E R, et al. Conceptual design of discrete-event systems using templates [J]. Discrete Event Dynamic Systems, 2011, 21(2): 257-303.

[14]GRIGOROV L, CURY J E R, RUDIE K. Design of discrete-event systems using templates [C]∥Proceedings of the American Control Conference. Piscataway, NJ, USA: IEEE, 2008: 499-504.

[15]RABIN M O, SCOTT D. Finite automata and their decision problems [J]. IBM Journal of Research and Development, 1959, 3(2): 114-125.

[16]JIAO T, GAN Y, XIAO G, et al. Exploiting symmetry of state tree structures for discrete-event systems with parallel components [C]∥13th International Workshop on Discrete Event Systems. Piscataway, NJ, USA: IEEE, 2016: 97-102.

(編輯 趙煒)

Invariance Property of the Control Functions in Symmetric Discrete-Event Systems Modeled by State Tree Structures

JIAO Ting,GAN Yongmei,XIAO Guochun

(School of Electrical Engineering, Xi’an Jiaotong University, Xi’an 710049, China)

The symmetric discrete-event systems (DES) consist of groups of identical components. For such DES, the supervisor in the form of automata synthesized by the supervisory control theory often has large number of state and is nontransparent in control logic. Thus a computational approach of abstract control function is proposed. This approach fully exploits the symmetry of the system. For the performance index to avoid the underflow or overflow of buffers, the number of components in the status of processing finish is extracted with event relabeling map, thereby the processing details of each component are omitted. Then the abstract control functions are computed with the state tree structures (STS) based on the abstract status information. Finally, by illustrating examples of components working in parallel and serial, the invariance property of control functions are analyzed. Namely, with fixed buffer sizes, the status information required by the control function is irrelevant to the total number of components. The experimental results showed that by utilizing the invariance property of control functions, the repeated computation of control functions is avoided when identical components are added or deleted. Meanwhile, all controllable events relabeled by the same symbol can be enabled by one abstract control function; thus the number of control functions is reduced. Moreover, compared with the controller represented by automata, the control functions have fewer states and are more transparent in control logic.

discrete-event systems; supervisory control theory; state tree structures; control functions; predicate logic

2016-05-12。 作者簡介:焦亭(1988—),男,博士生;甘永梅(通信作者),女,副教授。 基金項(xiàng)目:國家建設(shè)高水平大學(xué)公派留學(xué)生資助項(xiàng)目(留金發(fā)〔2014〕3026)。

時(shí)間:2016-09-14

10.7652/xjtuxb201611007

TP273

A

0253-987X(2016)11-0043-06

網(wǎng)絡(luò)出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160914.1805.006.html