有限狀態(tài)自動機產(chǎn)生式推理的一般性建模方法

彭翔王飛

(華僑大學信息科學與工程學院，福建 廈門 361021)

0 引言

利用自動機構(gòu)建離散事件動態(tài)系統(tǒng)(discrete event system，DES)診斷模型是一種基于模型的診斷方法［1］。自動機模型的可診斷性［2］以及對于更為復雜的DES診斷的建模［3］都是在此基礎上做延伸?；赑etri網(wǎng)模型的DES故障診斷推理［4－5］也是當今DES故障診斷的研究熱點。在故障診斷推理中，利用窮舉法列出系統(tǒng)的所有狀態(tài)，而后剔除不必要的狀態(tài)進行診斷［6］，這對較為龐大的系統(tǒng)而言是比較繁瑣的。文獻［7］利用自動機對故障推理進行建模，但沒有給出其泛化的建模方式，因此，很難運用到實際多樣化的系統(tǒng)中。

針對現(xiàn)今越來越龐大復雜的系統(tǒng)，系統(tǒng)故障的產(chǎn)生式規(guī)則也愈加繁瑣，本文提出了采用自動機對故障診斷專家系統(tǒng)推理一般性建模的方法。這種方法對于復雜判別規(guī)則較多的產(chǎn)生式推理均適用。此外，還給出了建模后的簡化方法，并用實例驗證了該方法的可行性。

1 確定性有限狀態(tài)自動機與推理機

定義1 一個確定性有限狀態(tài)自動機(deterministic finite state automata，DFSA)定義為一個五元組［8］:

式中:X為非空有限狀態(tài)集;∑為有限事件集;δ為狀態(tài)轉(zhuǎn)移函數(shù);x0∈Xm為初始狀態(tài);Xm∈X為標志狀態(tài)集。

定義2 對有限自動機G和任一狀態(tài)x0∈X，∑*為輸入符號串集合，則自動機G產(chǎn)生的語言L(G)定義為使狀態(tài)轉(zhuǎn)移函數(shù)δ(ω，x0)為輸入符號串ω∈∑*的一個集合［8］，也即:

規(guī)則產(chǎn)生式一般由if與then語句構(gòu)成，如果用DFSA描述一條規(guī)則產(chǎn)生式的推理過程，那么可以將if之后的一個條件作為DFSA的一個事件。滿足這個條件，即事件發(fā)生，將轉(zhuǎn)移到相應的狀態(tài)，這個狀態(tài)即表示此條件滿足，可以進行下一步推理。如果一條規(guī)則需要有多個條件同時滿足才觸發(fā)，那么多個條件則對應多個事件。這些事件都發(fā)生，則表明對應的所有條件都滿足，觸發(fā)規(guī)則，進入終止狀態(tài)，此狀態(tài)即代表推理結(jié)束。

借助DFSA的定義，就可以歸納出產(chǎn)生式推理到有限狀態(tài)自動機的映射關系。

①產(chǎn)生式推理有一個開始狀態(tài)，表示系統(tǒng)準備就緒，可以開始接收條件進行推理，這對應的就是DFSA的初始狀態(tài)。

②產(chǎn)生式的推理過程是接收條件的過程，推理的結(jié)束是使得產(chǎn)生式規(guī)則中的某個規(guī)則觸發(fā)。當接收一系列條件，直至這些條件中存在的某些條件使得這些條件構(gòu)成的某一規(guī)則成立，則該規(guī)則觸發(fā)，推理結(jié)束。在DFSA中，事件就是讀入的條件，每個條件都作為一個事件，狀態(tài)則描述從初始狀態(tài)到當前狀態(tài)的所經(jīng)過的所有事件，即滿足所有條件。這樣，產(chǎn)生規(guī)則中的所有規(guī)則就可以用DFSA中的事件狀態(tài)序列描述。

③在產(chǎn)生式推理過程中，接收到之前已經(jīng)接收過的條件或接收到與之前條件無規(guī)則關聯(lián)的條件，則推理原地等待。

在DFSA中，當接收到之前接收過的條件時，則發(fā)生了之前發(fā)生過的事件，則在原狀態(tài)上構(gòu)造一個自轉(zhuǎn)移，使得自動機仍然在當前狀態(tài);當接收到與之前條件無規(guī)則關聯(lián)的條件時，相當于沒有對應的狀態(tài)轉(zhuǎn)移函數(shù)，DFSA保持當前狀態(tài)不變。

④產(chǎn)生式推理的結(jié)束是某個規(guī)則的觸發(fā)。在DFSA中，推理結(jié)束則轉(zhuǎn)移到終止狀態(tài)。在終止狀態(tài)之前的事件狀態(tài)序列，就是某一規(guī)則中的所有條件的滿足過程。

根據(jù)以上映射關系，可以賦予自動機五元組新的含義，使其成為推理機:

式中:X為有限非空狀態(tài)集合，表示滿足某個規(guī)則的某些條件后到達的已滿足條件狀態(tài);∑為有限事件集合，一條規(guī)則產(chǎn)生式的一個條件為一個事件，條件滿足，則事件發(fā)生;δ為狀態(tài)轉(zhuǎn)移函數(shù);x0為初始狀態(tài)，表示推理機準備就緒，可以開始推理;Xf為終止狀態(tài)，推理完成狀態(tài)，若到達此狀態(tài)，表明觸發(fā)某規(guī)則。

由以上定義的推理機以及前述的產(chǎn)生式推理與有限狀態(tài)自動機的映射關系，得到其“且”、“或”、自轉(zhuǎn)移的邏輯表達，具體表達方式如以下示例所示。

① 邏輯“a且b”關系圖如圖1所示。

圖1 “a且b”關系圖Fig.1 Relationship of a and b

② 邏輯“a或b”關系圖如圖2所示。

圖2 “a或b”關系圖Fig.2 Relationship of a or b

③自轉(zhuǎn)移關系圖如圖3所示。

圖3 自轉(zhuǎn)移關系圖Fig.3 Self-transition relationship

2 一般性建模流程

定義3 整齊規(guī)則:對于含有多條規(guī)則產(chǎn)生同種結(jié)果的推理，這些規(guī)則中的條件數(shù)都是相等的，則稱之為整齊規(guī)則。

這里所述的規(guī)則產(chǎn)生式是由其對應的所有條件通過“與”關系組合，進而觸發(fā)規(guī)則的。若條件之間含有“或”關系，則另建立“或”對應關系的新規(guī)則。建模具體流程如下所述。

假設某系統(tǒng)有m條規(guī)則產(chǎn)生式，每條規(guī)則產(chǎn)生式有nm個條件。其中nm代表第m個規(guī)則擁有的條件數(shù)。

①根據(jù)前述推理機的定義構(gòu)造m個推理機，則每個推理機對應其中的一條規(guī)則。第m條規(guī)則所對應的狀態(tài)事件序列如圖4所示。

圖4 第m條規(guī)則的狀態(tài)事件序列Fig.4 State-event sequences of rule m

這里描述的只是一條規(guī)則中的一個推理路徑，從xm0到xmnm之間，若有n個條件，則應當有條推理路徑，其中為n的全排列。

②整合多條規(guī)則后的綜合推理機的狀態(tài)事件序列流程如圖5所示。先做以下定義:E為所有規(guī)則中所有條件的集合;Em為第m條規(guī)則的所有條件的集合;Eold為流程圖中執(zhí)行循環(huán)操作后已使用過的規(guī)則中的所有條件集合;xmn為第m條規(guī)則中滿足第(n－1)個條件后的狀態(tài);emn為第m條規(guī)則中的第n個條件;Emn={emn丨xm(n+1)=(xmn，emn)}。上述定義中的 m，n=0，1，2，3，…，且不依托于規(guī)則中條件之間的先后關系。

圖5 構(gòu)造狀態(tài)事件序列流程圖Fig.5 Flowchart of forming state-event sequences

③通過以上流程，可以獲得推理過程的狀態(tài)事件序列，進而構(gòu)造推理機。其中x0=x00=x10=…=xm0，合并后得到初始狀態(tài)x0，在Emnm后加入狀態(tài)xf，表示推理結(jié)束的終止狀態(tài)。至此推理機建模完成。

當描述的產(chǎn)生式規(guī)則為整齊規(guī)則且這些規(guī)則有一些具有相同的條件時，可以利用輸入等價［9］原則進行狀態(tài)合并，狀態(tài)合并后其上的自轉(zhuǎn)移事件也取并集。這樣就使得模型得到簡化，從而提高推理效率。

3 實例驗證與分析

“設備”和“斷路器”表示的電力網(wǎng)絡的拓撲結(jié)構(gòu)如圖6所示［10］。本實例旨在對輸電線路故障位置的診斷的推理，所以這里的“設備”為“輸電線路”與“母線”。

圖6 電力網(wǎng)絡實例模型Fig.6 Instance model of electricity network

圖6中，L1～L4代表線路，CB1～CB9為斷路器，B1～B4為母線。

當故障發(fā)生時，相應點的線路保護動作，線路保護動作引起對應的斷路器動作，切除故障點與電網(wǎng)的聯(lián)接，從而達到保護電網(wǎng)的目的;同時，當故障發(fā)生時，數(shù)據(jù)采集與監(jiān)視控制系統(tǒng)(SCADA)會采集各線路保護動作與斷路器動作的數(shù)據(jù)。通過采集得到的數(shù)據(jù)來定位故障點則由相關推理系統(tǒng)完成。線路故障的產(chǎn)生式規(guī)則［11］如表1 所示，推理方式為 if“前件1”and“前件2”then“后件”。

表1 保護動作與斷路器動作的產(chǎn)生式規(guī)則Tab.1 Production rules of actions of protection and circuit breaker

由以上產(chǎn)生式規(guī)則，可以構(gòu)建相應推理機。保護動作與斷路器動作所對應的事件表如表2所示。

表2 保護動作及對其應斷路器動作事件表Tab.2 Event list of protection and corresponding circuit breaker

首先，以規(guī)則1為例，構(gòu)造的基于單條產(chǎn)生式規(guī)則的推理機如圖7所示。

圖7 規(guī)則1的推理機Fig.7 Inference engine of rule 1

其次，由綜合推理機建模流程圖，構(gòu)造綜合狀態(tài)事件序列。

最后，由于本例的產(chǎn)生式規(guī)則是整齊規(guī)則，加入初始和推理結(jié)束狀態(tài)后，可以利用輸入等價原則進行狀態(tài)合并，減少狀態(tài)空間維數(shù)。簡化后的基于表1規(guī)則產(chǎn)生式的最終推理模型如圖8所示。

圖8 最終推理模型Fig.8 The final inference model

在電力網(wǎng)絡實例模型中，當輸電線路某處發(fā)生故障時，若SCADA系統(tǒng)采集到斷路器CB1、CB3、CB5的動作信息，并采集到線路L1的送端主保護、L2的送端遠后備保護和L3的送端遠后備保護動作，則根據(jù)當前的故障信息，結(jié)合圖6可知，可能是線路L1或母線B3故障，但是無法分清到底是哪一個故障。這時，將采集的故障信息輸入到上述構(gòu)建的推理模型中，此時模型中事件 Pzs、CB1、Pyr、CB6發(fā)生，使得自動機模型從初始狀態(tài)x0轉(zhuǎn)移到了終止狀態(tài)xf，這意味著故障發(fā)生。

由于本文所建立的是輸電線路故障診斷模型，所以結(jié)果表示輸電線路L1發(fā)生故障，至此診斷結(jié)束。同樣地，若是建立了關于母線B3的故障診斷的自動機模型，在L1發(fā)生故障的情況下，將不會到達故障發(fā)生的終止狀態(tài)。

4 結(jié)束語

本文采用確定性有限狀態(tài)自動機研究了基于規(guī)則產(chǎn)生式的推理，在給出基于自動機模型的推理機的基礎上，提出了基于多條規(guī)則產(chǎn)生式的自動機推理模型的泛化建模流程。同時，給出了建模的具體流程圖，并利用輸入等價原則進行簡化。最后，對本文提出的建模流程進行實例驗證，將模型應用在輸電線路故障診斷的產(chǎn)生式推理過程中，獲得了較好的效果。這種推理模型也可以作為故障診斷專家系統(tǒng)的輔助決策系統(tǒng)，具有較好的現(xiàn)實意義。

［1］Cassandras C，Lafortune S.Introduction to discrete event systems［M］.Boston MA:Kluwer Academic Publisher，1999.

［2］Sampath M，Sengupta R，Lafortune S，et al.Diagnosability of discreteevent systems［J］.IEEE Transactions on Automatic Control，1995，40(9):1555－1575.

［3］Gascard E，Simeu-abazi Z.Modular modelling for the diagnostic of complex discrete-eventsystems［J］.IEEE Transactions on Automation Science and Engineering，2013(99):1 －23.

［4］Wu Z，Hsieh S.A realtime fuzzy Petri net diagnoser for detecting progressive faults in PLC based discrete manufacturing system［J］.The International Journal of Advanced Manufacturing Technology，2012(61):405－421.

［5］Cabasino M P，Giua A，Lafortune S，et al.A new approach for diagnosability analysis of petri nets using verifier nets［J］.IEEE Transactions on Automatic Control，2012(12):3104 － 3117.

［6］Costa N S，Coury D V，Pereira W D C.Finite automata applied to a classification of fault in an eletric power system［C］∥Transmission ＆Distribution Conference and Exposition，Latin America，2006:1 －5.

［7］王書振，李雷，王保保.基于有限狀態(tài)自動機的產(chǎn)生式推理［J］.儀器儀表學報，2008，29(8):372 －374.

［8］鄭大鐘，趙千川.離散事件動態(tài)系統(tǒng)［M］.北京:清華大學出版社，2001.

［9］Ware S，Malik R.Conflict-preserving abstraction of discrete event systems using annotated automata［J］.Discrete Event Dynamic System，2012(22):451－477.

［10］楊建維.基于模糊Petri網(wǎng)的電網(wǎng)故障診斷方法研究［D］.成都:西南交通大學，2011.

［11］方培培.Perti網(wǎng)理論在電力系統(tǒng)輸電網(wǎng)絡故障診斷［D］.天津:天津大學，2005.