焦亭,甘永梅,肖國春

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

?

對稱離散事件系統狀態(tài)樹結構模型的控制函數不變性研究

焦亭,甘永梅,肖國春

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

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

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

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

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

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

1 基礎知識

1.1 DES自動機模型

離散事件系統利用自動機對系統進行建模,自動機可表示為5元組G=(Q,Σ,δ,q0,Qm),其中Q為狀態(tài)集合,Σ為事件集合,δ:Q×Σ→Q用于描述系統中狀態(tài)的變遷關系,q0為初始狀態(tài),Qm?Q為標識狀態(tài)集合。一般地,轉移函數可擴展為δ:Q×Σ*→Q,其中Σ*表示空字符串ε與Σ上的所有有限長度字符串的并集,并用δ(q0,s)!表示δ(q0,s)有定義。定義自動機G所表示語言的閉特性為L(G)={s∈Σ*|δ(q0,s)!},標識特性為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)的標識非阻塞監(jiān)督控制為映射V:L(G)→Γ,V/G的標識特性定義為Lm(V/G)=L(V/G)∩M。假設用E?Σ*表示性能指標,E中的所有可控語言表示為C(E)={K?E|K關于G可控}。因C(E)中的元素形成上晶格結構,存在最大元素supC(E)=∪{K|K∈C(E)},并可由TCT軟件中的supcon算法計算得到對應自動機形式的監(jiān)督控制器。

1.2 狀態(tài)樹結構

對DES進行建模的狀態(tài)樹結構[8-9]可表示為6元組Gst=(St,H,Σ,Δ,St0,Stm),其中狀態(tài)樹St將系統狀態(tài)集合表示為分層結構,H為被控系統Gst中描述系統局部行為的各組件實時子整體,Σ為事件集合,其被劃分為可控事件集合Σc與不可控事件集合Σu。令S(St)表示St上所有的子狀態(tài)樹集合,Δ:S(St)×Σ→S(St)為全局轉移函數,St0∈S(St)為初始狀態(tài)樹,Stm?S(St)為標識狀態(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當且僅當(?b∈B(T))bP,狀態(tài)樹Gst也可記作Gst=(St,H,Σ,Δ,P0,Pm),其中P0、Pm為初始謂詞、標識謂詞。

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

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

1.3 事件重標記映射

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

圖1 重標記映射及實現過程示意圖

事件重標記算法λ主要分2步實現:將G中所有不可觀測事件重標記為空字符ε,其余事件按事先制定的重標記規(guī)則進行標記;將事件重標記后得到的不確定有限狀態(tài)自動機通過子集生成算法[15]轉換為確定有限狀態(tài)自動機,即為所求的結果GR。子集生成算法的功能為將不確定有限狀態(tài)自動機轉換為與其等價的確定有限狀態(tài)自動機。對于任意字符串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))。在具有對稱性的離散事件系統G中,被事件重標記映射標記為同一字符串的所有字符串進入的狀態(tài)將生成一個狀態(tài)子集。由于系統的對稱性,所生成狀態(tài)子集為對G中狀態(tài)的一個等價劃分[16],因此生成的狀態(tài)子集總數量少于原系統的狀態(tài)總數,即進行事件重標記后所得結果GR的狀態(tài)數比G的狀態(tài)數少。

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

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

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

圖2 本文制造系統示意圖

在忽略組件個體差異后,針對防止緩沖區(qū)出現上溢或下溢的性能指標,需要獲知各組中當前狀態(tài)處于即將往緩沖區(qū)中放入工件的組件數量,即Ii中處于狀態(tài)1的組件數量。為獲得該數據,給出定義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ū)上溢或下溢無關可設為不可觀測事件,在進行λ運算時這些事件被重標記為ε。

圖3 復雜組件重標記前后的結構示意圖

3 控制函數不變性研究

3.1 問題描述

經事件重標記映射計算得到的各組抽象狀態(tài)信息可建立狀態(tài)樹結構模型,將自動機轉換為狀態(tài)樹結構的具體過程可參見文獻[8],然后通過STSLib軟件計算得到各可控事件對應的控制函數。

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

3.2 并行工作系統控制函數不變性分析

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

圖4 控制函數f11、f21示意圖

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

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

系統對應的狀態(tài)樹結構模型Gst:=(St,H,T,Δ,b0,{b0}),如圖5所示,其中重標記后事件集合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分別表示輸入側與輸出側處于狀態(tài)1的組件數量,k表示緩沖區(qū)中現有組件數量。

圖5 狀態(tài)樹結構Gst

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

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

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

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

3.3 串行工作系統控制函數不變性分析

圖6 具有對稱性的串行工作系統及其自動機示意圖

對于圖6所示串行工作系統,文獻[3]選用構建商自動機的方式對其進行化簡,實現過程較為復雜,本文從控制函數不變性的角度直觀地獲得系統的控制邏輯,并結合系統對稱性證明M0、M1、M2可由同一謂詞進行控制。

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

圖7 控制函數f1、f3、f5示意圖

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

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

4 結 論

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

本文所得的控制函數不變性建立在防止緩沖區(qū)出現上溢與下溢的性能指標之上,由于組件個體的細節(jié)與該性能指標無關,因此各組組件之間的交互不會影響到相應控制函數的選擇,只要組件當前處于可控事件有定義的狀態(tài)且控制函數允許該可控事件對應的重標記事件發(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]晁武杰, 甘永梅, 王兆安, 等. 實時狀態(tài)樹結構模型的最優(yōu)非阻塞模塊化監(jiān)督控制研究 [J]. 西安交通大學學報, 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—),男,博士生;甘永梅(通信作者),女,副教授。 基金項目:國家建設高水平大學公派留學生資助項目(留金發(fā)〔2014〕3026)。

時間:2016-09-14

10.7652/xjtuxb201611007

TP273

A

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

網絡出版地址:http:∥www.cnki.net/kcms/detail/61.1069.T.20160914.1805.006.html