離散事件系統(tǒng)故障的極小觀測(cè)序列*

歐陽(yáng)丹彤，李江娜，耿雪娜

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春　130012；2. 吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長(zhǎng)春　130012)

?

離散事件系統(tǒng)故障的極小觀測(cè)序列*

歐陽(yáng)丹彤1,2?，李江娜1,2，耿雪娜1,2

(1.吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，吉林 長(zhǎng)春130012；2. 吉林大學(xué) 符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室，吉林 長(zhǎng)春130012)

摘要：為了提高可診斷離散事件系統(tǒng)故障的在線(xiàn)診斷效率，本文從判定故障發(fā)生的可觀測(cè)事件的角度，提出了故障極小觀測(cè)序列方法.文中選取有限狀態(tài)自動(dòng)機(jī)對(duì)離散事件系統(tǒng)進(jìn)行建模.首先，在離線(xiàn)狀態(tài)下，建立系統(tǒng)的故障模型，以排除對(duì)于判定系統(tǒng)故障無(wú)關(guān)的路徑.然后，根據(jù)故障模型進(jìn)一步建立判定系統(tǒng)故障的極小觀測(cè)序列模型.當(dāng)離散事件系統(tǒng)在線(xiàn)診斷時(shí)，僅需將逐步增加的在線(xiàn)觀測(cè)事件序列與故障的極小觀測(cè)序列模型進(jìn)行比對(duì).若能找到滿(mǎn)足該模型的任何一條路徑，則說(shuō)明路徑終止?fàn)顟B(tài)上故障標(biāo)簽對(duì)應(yīng)的系統(tǒng)故障發(fā)生；否則，說(shuō)明系統(tǒng)無(wú)故障發(fā)生.文中對(duì)可診斷離散事件系統(tǒng)進(jìn)行實(shí)驗(yàn)對(duì)比，通過(guò)故障的極小觀測(cè)序列模型能盡快判定有無(wú)故障發(fā)生，以及發(fā)生了哪些故障.該模型能有效地縮小系統(tǒng)在線(xiàn)診斷的時(shí)間，提高系統(tǒng)在線(xiàn)診斷的效率.

關(guān)鍵詞：離散事件系統(tǒng)；故障模型；極小觀測(cè)序列模型；故障診斷

近些年來(lái)，基于模型診斷[1-3]方法成為人工智能領(lǐng)域比較熱門(mén)的研究課題.基于模型診斷方法具有設(shè)備獨(dú)立性，易于更新和維護(hù).因而，不少領(lǐng)域使用基于模型診斷方法對(duì)離散事件系統(tǒng)進(jìn)行診斷[4-6]研究，比如大型通信網(wǎng)絡(luò)故障診斷、配電站故障診斷[7]、航天器故障診斷、汽車(chē)故障診斷、軟件測(cè)試等.基于模型診斷中診斷相關(guān)的極小化研究增強(qiáng)了診斷的精細(xì)程度.診斷相關(guān)的極小化研究包括：極小診斷、極小故障事件集、判定可診斷性的極小事件集等.極小診斷是在部件級(jí)別上對(duì)故障部件的候選沖突集進(jìn)行求碰集，從而得到故障部件的診斷結(jié)果.使用不同的方法求碰集，得到系統(tǒng)極小診斷的效率有所不同.例如，通過(guò)減少一致性檢測(cè)的數(shù)量，避免對(duì)極小化沖突集的計(jì)算，求解系統(tǒng)的極小診斷[8].極小故障事件集則考慮故障事件的先后順序?qū)ο到y(tǒng)的影響，將故障事件構(gòu)成的序列進(jìn)行極小化，從而得到系統(tǒng)故障事件的極小序列診斷[9].而可診斷性的極小事件集則是通過(guò)減少可觀測(cè)事件的種類(lèi)，使系統(tǒng)仍保持可診斷性，求解保證系統(tǒng)可診斷性的極小事件集[10].以上極小化相關(guān)研究都未曾從在線(xiàn)診斷角度考慮如何盡快地確定發(fā)生的故障.為了提高系統(tǒng)在線(xiàn)診斷的效率，使在線(xiàn)診斷時(shí)盡快地判定出故障的發(fā)生，本文對(duì)判定故障發(fā)生的可觀測(cè)事件序列進(jìn)行研究并建立相應(yīng)的模型，使得在系統(tǒng)故障發(fā)生后盡快確定該故障的發(fā)生.假定待測(cè)的離散事件系統(tǒng)是完備且可診斷的.

本文給出了判定系統(tǒng)故障發(fā)生的極小觀測(cè)序列模型Gmos以及建立故障極小觀測(cè)序列模型的算法(約束轉(zhuǎn)換法).對(duì)于給定的離散事件系統(tǒng)，首先建立該系統(tǒng)模型相對(duì)應(yīng)的故障模型Gf，然后在故障模型基礎(chǔ)上求得系統(tǒng)故障的極小觀測(cè)序列模型Gmos.通過(guò)故障的極小觀測(cè)序列模型可以得到某個(gè)或某類(lèi)故障發(fā)生的極小觀測(cè)序列集.這樣，系統(tǒng)在線(xiàn)實(shí)時(shí)診斷時(shí)，將傳感器逐步接收到的觀測(cè)與系統(tǒng)故障的極小觀測(cè)序列模型進(jìn)行比對(duì)，若滿(mǎn)足該模型中的某個(gè)觀測(cè)序列，則說(shuō)明系統(tǒng)發(fā)生了該序列終止?fàn)顟B(tài)標(biāo)簽相對(duì)應(yīng)的故障；否則，系統(tǒng)判定沒(méi)有故障發(fā)生.根據(jù)系統(tǒng)故障的極小觀測(cè)序列模型，能在故障發(fā)生后盡快地判定出系統(tǒng)發(fā)生了哪些故障.

本文結(jié)構(gòu)如下：第1部分給出了相關(guān)概念和定義；第2部分給出了故障極小觀測(cè)序列模型的構(gòu)建算法(約束轉(zhuǎn)換法)；第3部分給出了相關(guān)證明；第4部分給出了實(shí)驗(yàn)及分析；第5部分對(duì)本文工作進(jìn)行總結(jié).

1預(yù)備知識(shí)

本部分給出了文中相關(guān)的概念及模型的定義.

定義1(系統(tǒng)模型)系統(tǒng)模型是一個(gè)有限自動(dòng)機(jī)Gs= (S,E,T,S0,Sf).其中S為狀態(tài)集合；S0為初始狀態(tài)；Sf為終止?fàn)顟B(tài)集合；T為狀態(tài)轉(zhuǎn)換函數(shù)集合，T→S×E×S.E為事件集合，包括可觀測(cè)事件集Eo和不可觀測(cè)事件集Euo，Euo又分為故障事件集和非故障事件集.

定義2(觀測(cè)可達(dá))狀態(tài)si∈S經(jīng)事件e∈Eo可達(dá)狀態(tài)sj∈S(其中si和sj間事件除e外還可存在非連續(xù)的不可觀測(cè)事件)則稱(chēng)si在e下可達(dá)，記作si[e].狀態(tài)sj稱(chēng)為觀測(cè)可達(dá)狀態(tài)，記作R(si,e).

圖2中表示觀測(cè)可達(dá)的幾種情況，其中a,b∈Eo，v,u∈Euo，則有R(S0,a) = {S1}，R(S1,b) = {S2,S3} ,R(S3,c) = {S5}.

為了便于對(duì)系統(tǒng)模型中故障進(jìn)行篩選，給出了故障模型的定義.

定義3(故障模型)故障模型為一個(gè)有限自動(dòng)機(jī)Gf= (S’,E’,T’,S0,Sf’)，其中S’?S，E’?E，T’?T，Sf’?Sf.

為提出建立故障模型的算法，給出以下定義.

圖1　單故障系統(tǒng)模型Gs

圖2　觀測(cè)可達(dá)

由于傳感器無(wú)法觀測(cè)到不可觀測(cè)事件，現(xiàn)定義觀測(cè).

定義6 (觀測(cè))事件序列O=o1o2…on(其中o1,…,on∈E)的觀測(cè)表示為obs(O)，定義如下：

obs(oi)={φ}，當(dāng)oi∈Euo；

obs(oj)={oj}，當(dāng)oj∈Eo；

obs(O=t1o)=obs(t1)obs(o) ，當(dāng)t1∈E*，o∈E.

其中E*={ |ei∈E,i= 1,2,… }.

例如O=abucfcd，其中u,f∈Euo，a,b,c,d∈Eo，得obs(O)=abccd.

本文目的是求解系統(tǒng)故障的極小觀測(cè)序列模型，因此定義了故障的極小觀測(cè)序列以及故障的極小觀測(cè)序列模型.

定義7(故障的極小觀測(cè)序列)存在可觀測(cè)事件序列o1o2…on和o1o2…onon+1…on+k(其中o1，…,on+k∈Eo且k>0) 均可判定某故障發(fā)生，而序列o1o2…on-1無(wú)法確定該故障發(fā)生，則稱(chēng)序列o1o2…on為該故障的極小觀測(cè)序列.所有故障的極小觀測(cè)序列構(gòu)成的模型稱(chēng)為系統(tǒng)故障的極小觀測(cè)序列模型.

圖1當(dāng)接收到觀測(cè)a，無(wú)法判定f發(fā)生，ab能判斷f發(fā)生，abc也可以，可見(jiàn)ab為判定f發(fā)生的一個(gè)極小觀測(cè)序列.

定義8 (故障的極小觀測(cè)序列模型)極小觀測(cè)序列模型為一個(gè)有限自動(dòng)機(jī)：Gmos= (X,Eo’,Tmos,X0,Xf).其中Eo’?E’為可觀測(cè)事件集.X0=(S0,{N})為初始狀態(tài).Tmos為狀態(tài)轉(zhuǎn)換函數(shù)集合.X為狀態(tài)集合，X={xi|xi= {(s1,l1) , …, (sn,ln)} ,s1, …,sn∈S’,l1, … ,ln∈{N,F*}，F(xiàn)*={ |Fi∈F,i= 1, 2,…}}.Xf為終止?fàn)顟B(tài)集合，Xf={(s,Fj)|s∈S’,Fj∈F*}.

根據(jù)模型中狀態(tài)標(biāo)簽的不同，提出了定義模糊狀態(tài)和標(biāo)簽可達(dá).

定義9 (模糊狀態(tài))狀態(tài)xi∈X中既含標(biāo)簽F’∈F*又含標(biāo)簽N，則xi為模糊狀態(tài).

定義10 (標(biāo)簽可達(dá)) 模糊狀態(tài)xi∈X,存在可觀測(cè)事件e∈Eo’,若僅使得帶標(biāo)簽N的狀態(tài)sij其中 (sij,N)∈i)可達(dá)，稱(chēng)xi在e下N標(biāo)簽可達(dá)；若僅使帶標(biāo)簽F∈F*的狀態(tài)可達(dá)，稱(chēng)xi在e下F標(biāo)簽可達(dá)；若同時(shí)存在，稱(chēng)xi在e下NF標(biāo)簽可達(dá).

Tmos(xi,e)定義之前，先定義局部轉(zhuǎn)換函數(shù)Tmos((sij,l(sij)),e) , 來(lái)表示狀態(tài)間通過(guò)事件連接的關(guān)系(其中(sij,l(sij))∈xi).

定義11 (局部轉(zhuǎn)換函數(shù))局部轉(zhuǎn)換函數(shù)Tmos((sij,l(sij)),e) ,其中l(wèi)(sij)∈{N,F*}，當(dāng)fk?t(sij,R(sij,e))時(shí)，則Tmos((sij,l(sij)),e) = (R(sij,e) ,l(sij)).否則，當(dāng)l(sij) =N時(shí)，Tmos((sij,l(sij)),e) = {R(sij,e) ,Fk)}；l(sij)≠N時(shí)，Tmos((sij,l(sij)),e) = {R(sij,e) ,l(sij)∪Fk}.

根據(jù)局部轉(zhuǎn)換函數(shù)進(jìn)一步定義極小觀測(cè)序列模型中狀態(tài)間的轉(zhuǎn)換關(guān)系，稱(chēng)為轉(zhuǎn)換函數(shù)Tmos.

定義12 (轉(zhuǎn)換函數(shù)Tmos)：極小觀測(cè)序列模型中轉(zhuǎn)換函數(shù)Tmos(xi,e).根據(jù)狀態(tài)標(biāo)簽不同進(jìn)行以下分類(lèi)說(shuō)明.

(R1)僅含N標(biāo)簽的狀態(tài)xi= {(s1,N) ,…, (sn,N)}，其中s1,…,sn∈S’，存在可觀測(cè)事件e∈Eo’，那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) |?sj[e] ,sj?{s1,…,sn}}.

(R2)模糊狀態(tài)xi= {(s1,N) ,…, (sk,N) , (sk+1,Fk+1) ,…, (sm,Fm)}，F(xiàn)k+1,…,Fm∈F*，對(duì)于可觀測(cè)事件e∈Eo’存在sj[e] …st[e] ，且滿(mǎn)足j∈[1,k],t∈(k,m]或者滿(mǎn)足j,t∈(k,m]，那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) ,…,Tmos((st,l(st)),e)}.

(R3)僅含F(xiàn)標(biāo)簽的狀態(tài)xi= {(s1,F1) ,…, (sn,Fn)}，F(xiàn)1,…,Fn∈F*,n≥2,存在事件e∈Eo’，令SF’ = {si|?si[e] ,si∈{s1,…,sn}},那么Tmos(xi,e) = {Tmos((sj,l(sj)),e) |?sj∈SF’}.

根據(jù)以上對(duì)3種狀態(tài)下轉(zhuǎn)換函數(shù)的定義，可知終止?fàn)顟B(tài)可由僅含N標(biāo)簽狀態(tài)、模糊狀態(tài)以及僅含F(xiàn)標(biāo)簽狀態(tài)經(jīng)轉(zhuǎn)換函數(shù)Tmos得到.

2故障的極小觀測(cè)序列模型

2.1故障模型

建立系統(tǒng)故障的極小觀測(cè)序列模型需要給定系統(tǒng)的故障模型，本節(jié)首先給出了算法1(篩選法)用于構(gòu)建系統(tǒng)的故障模型.

算法1構(gòu)建系統(tǒng)模型Gras的故障模型Graf

Function: FmBuild(Gras);

Input:Gras;//系統(tǒng)模型對(duì)應(yīng)的圖

Output:Graf;//故障模型對(duì)應(yīng)的圖

Begin

1: Initialization:

Graf←S0;

2: for ?t∈tGs∧fi∈tdo

3:tf←t

4:Graf←tf;

5: end for

6: for eachtfi∈tf,find thetpfido

7: ift’∈tGs∧t’?tf∧t’ =t1’t2’∧

(obs(t1’) =obs(tpfi))then

8:Graf←t’;

9: end if

10: end for

End

算法1中2-5行將系統(tǒng)模型圖Gras中故障路徑集合tf加入到圖Graf.7-9行每條故障路徑tfi∈tf,找到其預(yù)故障路徑tpf,取得與觀測(cè)obs(tpfi)有相同部分觀測(cè)的路徑t’，將t’加入到圖Graf中.

2.2極小觀測(cè)序列模型構(gòu)建算法

根據(jù)系統(tǒng)的故障模型建立判定故障發(fā)生的極小觀測(cè)序列模型.本節(jié)給出了算法2(約束轉(zhuǎn)換法)用于構(gòu)建系統(tǒng)故障模型的極小觀測(cè)序列模型.

算法2構(gòu)建系統(tǒng)故障模型Graf的極小觀測(cè)序列模型Gramos

Function: MosmBuild(Graf);

Input:Graf; //故障模型對(duì)應(yīng)的圖

Output:Gramos; //極小觀測(cè)序列模型對(duì)應(yīng)的圖

Begin

1: Initialization:

X0←(S0,{N});

Gramos←X0;

X←X0;

2:forXi∈X∧isNotEnd(Xi)∧isTerminal(Xi) do

3: ifXi= {(s1,N), ..., (sn,N)}then

4:for ?e∈Eo∧si[e]do

5:Xi+1←trans((si,l(si)),e);

6:X←Xi+1;

8: end for

9: end if

10: ifXi= {(s1,N), …, (sk,N), (sk+1,Fk+1),…,

(sn,Fn)}then

11: for ?e∈Eo∧sj[e],…,st[e]do

12:ifj∈[1,k]∧t∈(k,n]then

13:Xi+1←trans((si,l(si)),e);

14:X←Xi+1;

16:end if

17:ifj∈(k,n]then

18:Xi+1←trans((si,l(si)),e);

19:X←Xi+1;

21:end if

22: end for

23:end if

24: ifXi= {(s1,F1), ..., (sn,Fn)}then

25:for ?e∈Eo∧si[e]do

26:Xi+1←trans((si,l(si)),e);

27:X←Xi+1;

29:end for

30:end if

31:end for

End

算法2中trans((si,l(si)),e)表示狀態(tài)的局部轉(zhuǎn)換函數(shù).

Function:trans((si,l(si)),e);

Inputs:si;//狀態(tài)

l(si) ;//狀態(tài)的標(biāo)簽

e; //可觀測(cè)事件

Begin

1: forr∈R(si,e)do

2:iffj?t(si,r)then

3:x←(r,l(si));

4:else

5:ifl(si) =Nthen

6:x←(r,Fj);

7:else

8:x←(r,l(si)∪Fj);

9:end if

10:end if

11:end for

12:returnx;

End

函數(shù)trans((si,l(si)),e)的第1行R(si,e)表示狀態(tài)si通過(guò)事件e所有可達(dá)狀態(tài)構(gòu)成的集合;2-3行指故障不包含在路徑t(si,r)時(shí)，轉(zhuǎn)換后標(biāo)簽不變；4-8行指故障包含在路徑時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽的情況：5-6行指原有狀態(tài)標(biāo)簽為N時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽為故障標(biāo)簽；7-8行指原有狀態(tài)標(biāo)簽為故障標(biāo)簽時(shí)，轉(zhuǎn)換后狀態(tài)標(biāo)簽為兩個(gè)標(biāo)簽的并集.

3證明

算法2求得的極小觀測(cè)序列模型包含系統(tǒng)中所有故障的所有極小觀測(cè)序列.

證(正確性)極小觀測(cè)序列模型中終止?fàn)顟B(tài)出現(xiàn)在三種狀態(tài)轉(zhuǎn)換后：模糊狀態(tài)、僅含有N標(biāo)簽的狀態(tài)以及僅含有F標(biāo)簽的狀態(tài).由于系統(tǒng)是可診斷的，則故障標(biāo)簽一定可以分離.對(duì)于模糊狀態(tài)(或者僅含有F標(biāo)簽的狀態(tài))經(jīng)轉(zhuǎn)換到終止?fàn)顟B(tài)的過(guò)程為故障分離的過(guò)程，而且首次進(jìn)行分離，所以滿(mǎn)足極小性；而對(duì)于僅含有N標(biāo)簽的狀態(tài)，經(jīng)轉(zhuǎn)換到終止?fàn)顟B(tài)的過(guò)程為正常狀態(tài)首次到達(dá)的含有F標(biāo)簽的狀態(tài)，所以滿(mǎn)足極小性.可見(jiàn)，極小觀測(cè)序列模型中的序列滿(mǎn)足極小性.

(完備性)極小觀測(cè)序列模型是根據(jù)故障模型得到的，需要證明故障模型是完備的.故障模型由系統(tǒng)模型中的故障路徑以及與預(yù)故障路徑相同部分觀測(cè)的路徑組成.故障的極小觀測(cè)序列一定存在于故障路徑中，故障發(fā)生后，影響故障發(fā)生判定的路徑只有與預(yù)故障路徑相同部分觀測(cè)的路徑，所以故障模型是完備的，則極小觀測(cè)序列模型也是完備的.

(復(fù)雜性分析)極小觀測(cè)序列模型的在線(xiàn)診斷時(shí)間取決于實(shí)時(shí)接收的觀測(cè)與離線(xiàn)建立的極小序列模型的比較時(shí)間，當(dāng)觀測(cè)序列長(zhǎng)度為n時(shí)，比較時(shí)間復(fù)雜度為O(n)，故在線(xiàn)診斷的時(shí)間復(fù)雜度為O(n).

4實(shí)驗(yàn)及實(shí)例分析

4.1實(shí)驗(yàn)

由于本文的研究建立在完備且可診斷的離散事件系統(tǒng)基礎(chǔ)上，且此類(lèi)研究沒(méi)有統(tǒng)一的benchmark數(shù)據(jù)測(cè)試集，故選取相關(guān)論文[9]中滿(mǎn)足本文假設(shè)的部分系統(tǒng)模型以及滿(mǎn)足條件的系統(tǒng)模型進(jìn)行以下兩種對(duì)比實(shí)驗(yàn).情形1：使用系統(tǒng)故障的極小觀測(cè)序列模型，記作Mos；情形2：不使用故障的極小觀測(cè)序列模型，記作Ori.對(duì)于相同長(zhǎng)度的故障極小觀測(cè)序列且相同節(jié)點(diǎn)個(gè)數(shù)的系統(tǒng)(單故障系統(tǒng))進(jìn)行實(shí)驗(yàn)，分別得到Mos和Ori的在線(xiàn)診斷的時(shí)間如表1所示：

表1　診斷的時(shí)間對(duì)比

實(shí)驗(yàn)數(shù)據(jù)表明，在相同條件的系統(tǒng)中，Mos診斷時(shí)間均比Ori短，為了更形象地說(shuō)明兩者的時(shí)間差距，診斷時(shí)間差圖3如下.

系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)

由圖3可得，對(duì)于單故障系統(tǒng)，Mos的故障診斷時(shí)間均比Ori的故障診斷時(shí)間短，即Mos下，系統(tǒng)有較高的診斷效率.尤其對(duì)于節(jié)點(diǎn)個(gè)數(shù)多且故障極小觀測(cè)序列較長(zhǎng)的系統(tǒng)模型，Mos比Ori在線(xiàn)診斷時(shí)間有更好的優(yōu)勢(shì).

實(shí)驗(yàn)表明：離線(xiàn)建立系統(tǒng)的極小觀測(cè)序列模型用于在線(xiàn)故障診斷，能有效地提高系統(tǒng)在線(xiàn)故障診斷的效率.既能夠盡快地發(fā)現(xiàn)故障發(fā)生，也能盡快地排除故障的發(fā)生.

4.2實(shí)例分析

圖4為多故障系統(tǒng)模型Gs，根據(jù)算法2得到該系統(tǒng)故障的極小觀測(cè)序列模型Gmos，如圖5所示.可得故障f1的極小觀測(cè)序列為abc，acb，故障f2的極小觀測(cè)序列為abb.

圖4　多故障系統(tǒng)Gs

圖5　極小觀測(cè)序列模型Gmos

系統(tǒng)在初始狀態(tài)0下，當(dāng)接收到觀測(cè)a時(shí)，在Gmos中存在可達(dá)狀態(tài)，當(dāng)再接收到觀測(cè)c，也有可達(dá)狀態(tài)，若繼續(xù)接收到觀測(cè)b到達(dá)Gmos中的帶標(biāo)簽F1的終止節(jié)點(diǎn)，此時(shí)可以判定故障f1發(fā)生.同理，當(dāng)接收到觀測(cè)序列abc，可判定故障f1發(fā)生；接收到觀測(cè)abb，可判定故障f2發(fā)生.

5結(jié)論

本文提出了系統(tǒng)故障的極小觀測(cè)序列模型，用于提高系統(tǒng)在線(xiàn)故障診斷的效率.文中給出了相關(guān)概念定義以及構(gòu)建系統(tǒng)故障的極小觀測(cè)序列模型的算法，而且通過(guò)對(duì)比實(shí)驗(yàn)證明了將故障的極小觀測(cè)序列模型用于系統(tǒng)在線(xiàn)故障診斷，可以有效地減少系統(tǒng)故障診斷的時(shí)間，從而使系統(tǒng)盡快地判定有無(wú)故障發(fā)生.

參考文獻(xiàn)

[1]PENCOLE Y. Diagnosability analysis of distributed discrete event systems[C] //Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-04). Valencia, Spain, 2004:43-47.

[2]RIBOT P, PENCOLE Y, COMBACAU M. Design requirements for the diagnosability of distributed discrete event systems[C] //Proceedings of the 19thInternational Workshop on Principles of Diagnosis (DX-08). Blue Mountains:NSW, 2008: 98-106.

[3]張立明,趙劍,趙相福,等.基于因果關(guān)系的模型診斷[J].吉林大學(xué)學(xué)報(bào):工學(xué)版,2009,39(4):1052-1056.

ZHANG Li-ming, ZHAO Jian, ZHAO Xiang-fu,etal. New method of using causal relations for model-based fault diagnosis[J]. Journal of Jilin University: Engineering and Technology Edition, 2009, 39(4):1052- 1056.(In Chinese)

[4]CASSANDRAS G C, LAFORTUNE S. Introduction of discrete event systems [M].2nd ed. Springer Science+ Business Media, 2008.

[5]SAMPATH M, SENGUPTA R, LAFORTUNE S,etal. Daignosability of discrete event systems[J]. IEEE Transactions on Automatic Control, 1995, 40(9):1555- 1575.

[6]SAMPATH M, SENGUPTA R, LAFORTUNE S,etal. Failure diagnosis using discrete event systems[J]. IEEE Transactions on Control Systems Technology, 1996, 4(2): 105-124.

[7]李帥虎,曹一家,劉光曄,等.UHV對(duì)接入?yún)^(qū)域高壓配電網(wǎng)安全穩(wěn)定的影響[J].湖南大學(xué)學(xué)報(bào):自然科學(xué)版,2014, 41(10)：71-76.

LI Shuai-hu, CAO Yi-jia, LIU Guang-ye,etal. Influence of UHV on the security and stability of the high voltage distribution network of integration area[J]. Journal of Hunan University: Natural Sciences Edition, 2014, 41(10)：71-76. (In Chinese)

[8]SHCHEKOTYKHIN K, FRIEDRICH G, RODLER P,etal. A direct approach to sequential diagnosis of high cardinality faults in knowledge-bases[C] //Proceedings of the 25thInternational Workshop on Principles of Diagnosis (DX-14).Graz:Austria, 2014.

[9]ZHAO Xiang-fu, LAMPERTI G, OU-YANG Dan-tong. Minimal sequential diagnosis of discrete-event systems[C] //Proceedings of Diagnosis(DX-13).Jerusalem: Palestine, 2013:154-159.

[10]BASILIO J C, LINA S T S, LAFORTUNE S,etal. Computation of minimal event bases that ensure diagnosability[J]. Discrete Event Dynamic Synst, 2012:249-292.

Minimal Observation Sequences of Faults in Discrete Event System

OUYANG Dan-tong1,2?，LI Jiang-na1,2，GENG Xue-na1,2

(1.College of Computer Science and Technology,Jinlin Univ, Changchun,Jinlin130012,China; 2.Symbol Computation and Knowledge Engineering of Ministry of Education, Jinlin Univ, Changchun,Jinlin130012,China)

Abstract:In order to improve the efficiency of online diagnose of faults in discrete event system, from the viewpoint of the observable events judging occurrence of faults, this paper proposed a method called minimal observation sequences of faults. The finite state automaton was selected to model the discrete event system. First, a fault model of system was established in the offline, which was used to exclude the path independent of the system failure. Then, a minimal observation sequence model of faults was established according to the fault model. When the discrete event system is diagnosed online, it is necessary to compare the observations received by sensors with the model of minimal observation sequences. If any path in the model is found to satisfy the online observations, the fault in the termination state of the path will be described. Otherwise, no fault occurs. By comparing with the experiment results, the model of minimal observation sequences of faults can be used to determine the occurrence of faults as soon as possible. That is to say, the model for the system can find the faults timely and save the cost of online diagnosis.

Key words:discrete event system; faults model; minimal observation sequences model; fault diagnosis

中圖分類(lèi)號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A

作者簡(jiǎn)介：歐陽(yáng)丹彤(1968-)，女，吉林長(zhǎng)春人，吉林大學(xué)教授，博士?通訊聯(lián)系人，E-mail:ouyangdantong@163.com

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目(61133011, 61272208,61402196,61003101, 61170092)，National Natural Science Foundation of China(61133011，61272208，61402196，61003101，61170092)；吉林省科技發(fā)展計(jì)劃項(xiàng)目基金(20140520067JH)

收稿日期：2015-03-16

文章編號(hào)：1674-2974(2016)04-0147-06