有限狀態自動機產生式推理的一般性建模方法

彭翔王飛

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

0 引言

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

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

1 確定性有限狀態自動機與推理機

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

式中:X為非空有限狀態集;∑為有限事件集;δ為狀態轉移函數;x0∈Xm為初始狀態;Xm∈X為標志狀態集。

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

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

借助DFSA的定義，就可以歸納出產生式推理到有限狀態自動機的映射關系。

①產生式推理有一個開始狀態，表示系統準備就緒，可以開始接收條件進行推理，這對應的就是DFSA的初始狀態。

②產生式的推理過程是接收條件的過程，推理的結束是使得產生式規則中的某個規則觸發。當接收一系列條件，直至這些條件中存在的某些條件使得這些條件構成的某一規則成立，則該規則觸發，推理結束。在DFSA中，事件就是讀入的條件，每個條件都作為一個事件，狀態則描述從初始狀態到當前狀態的所經過的所有事件，即滿足所有條件。這樣，產生規則中的所有規則就可以用DFSA中的事件狀態序列描述。

③在產生式推理過程中，接收到之前已經接收過的條件或接收到與之前條件無規則關聯的條件，則推理原地等待。

在DFSA中，當接收到之前接收過的條件時，則發生了之前發生過的事件，則在原狀態上構造一個自轉移，使得自動機仍然在當前狀態;當接收到與之前條件無規則關聯的條件時，相當于沒有對應的狀態轉移函數，DFSA保持當前狀態不變。

④產生式推理的結束是某個規則的觸發。在DFSA中，推理結束則轉移到終止狀態。在終止狀態之前的事件狀態序列，就是某一規則中的所有條件的滿足過程。

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

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

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

① 邏輯“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

③自轉移關系圖如圖3所示。

圖3 自轉移關系圖Fig.3 Self-transition relationship

2 一般性建模流程

定義3 整齊規則:對于含有多條規則產生同種結果的推理，這些規則中的條件數都是相等的，則稱之為整齊規則。

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

假設某系統有m條規則產生式，每條規則產生式有nm個條件。其中nm代表第m個規則擁有的條件數。

①根據前述推理機的定義構造m個推理機，則每個推理機對應其中的一條規則。第m條規則所對應的狀態事件序列如圖4所示。

圖4 第m條規則的狀態事件序列Fig.4 State-event sequences of rule m

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

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

圖5 構造狀態事件序列流程圖Fig.5 Flowchart of forming state-event sequences

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

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

3 實例驗證與分析

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

圖6 電力網絡實例模型Fig.6 Instance model of electricity network

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

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

表1 保護動作與斷路器動作的產生式規則Tab.1 Production rules of actions of protection and circuit breaker

由以上產生式規則，可以構建相應推理機。保護動作與斷路器動作所對應的事件表如表2所示。

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

首先，以規則1為例，構造的基于單條產生式規則的推理機如圖7所示。

圖7 規則1的推理機Fig.7 Inference engine of rule 1

其次，由綜合推理機建模流程圖，構造綜合狀態事件序列。

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

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

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

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

4 結束語

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

［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］王書振，李雷，王保保.基于有限狀態自動機的產生式推理［J］.儀器儀表學報，2008，29(8):372 －374.

［8］鄭大鐘，趙千川.離散事件動態系統［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網的電網故障診斷方法研究［D］.成都:西南交通大學，2011.

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