DECS的產(chǎn)生式規(guī)則建模與規(guī)則的結(jié)構(gòu)錯誤檢測

畢 翔， 王科富， 魏振春， 韓江洪， 張 宏

(1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，安徽合肥 230009;2.合肥工業(yè)大學(xué)安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心，安徽合肥230009;3.安徽恒源煤電股份公司，安徽宿州 234000)

基于規(guī)則的系統(tǒng)(Rule-based System，簡稱RBS)已經(jīng)被廣泛用于各類專家系統(tǒng)中，用于刻畫領(lǐng)域知識及推理規(guī)則，通過邏輯推理，實現(xiàn)領(lǐng)域內(nèi)困難問題的有效求解[1]。系統(tǒng)的結(jié)構(gòu)具有知識與推理機分離特點，當(dāng)知識改變時，只需更新知識庫，而推理機不用改變，所以系統(tǒng)具有很好的可維護性和可擴展性。離散事件控制系統(tǒng)(Discrete Event Control Systems，簡稱DECS)是指系統(tǒng)由離散事件驅(qū)動，當(dāng)一個離散事件到來時，會引發(fā)系統(tǒng)中某些對象狀態(tài)發(fā)生變化，這些變化又會按照某種規(guī)則使其它對象狀態(tài)發(fā)生改變。系統(tǒng)遵循的是復(fù)雜的人為規(guī)則[2-5]，所以在對離散事件系統(tǒng)進行建模時，采用基于規(guī)則的系統(tǒng)架構(gòu)，系統(tǒng)的控制邏輯方案由規(guī)則庫描述。當(dāng)系統(tǒng)控制邏輯改變時，只需更新規(guī)則庫。此時控制程序只需接收系統(tǒng)對象狀態(tài)消息，將系統(tǒng)輸入消息與規(guī)則庫進行匹配，得到待執(zhí)行的匹配結(jié)果，實現(xiàn)規(guī)則與控制分離，使系統(tǒng)具有很好的可維護性和可擴展性。系統(tǒng)結(jié)構(gòu)如圖1所示。

RBS的建立需要解決2個基本問題:①將系統(tǒng)模型用規(guī)則表示;②對生成的規(guī)則庫進行結(jié)構(gòu)驗證。本文針對離散事件系統(tǒng)模型定義，采用產(chǎn)生式規(guī)則表示法描述系統(tǒng)規(guī)則，同時對生成的規(guī)則庫進行邏輯結(jié)構(gòu)驗證，為復(fù)雜系統(tǒng)設(shè)計提供一種可行方案。

圖1 基于規(guī)則的系統(tǒng)結(jié)構(gòu)

1 離散事件系統(tǒng)中規(guī)則的表示

1.1 產(chǎn)生式規(guī)則表示法

產(chǎn)生式規(guī)則表示法是由美國數(shù)學(xué)家波斯特(Post)于1943年提出的，它依據(jù)人類大腦記憶模式中各種知識塊之間大量存在的因果關(guān)系，并以IF…THEN…的形式表示出來[6]。產(chǎn)生式規(guī)則表示法形式單一，便于理解，易于計算機編碼實現(xiàn)，且規(guī)則之間相互獨立，規(guī)則的結(jié)構(gòu)化較好，有利于知識的提取和形式化，其求解問題的過程同人類的認知過程相似，因而廣泛應(yīng)用于各類專家系統(tǒng)及人工智能、模糊控制等領(lǐng)域[7]。

結(jié)合產(chǎn)生式規(guī)則表示法，分析離散事件系統(tǒng)運行過程:當(dāng)一個事件發(fā)生時，會引起系統(tǒng)對象狀態(tài)發(fā)生變化，這些對象狀態(tài)的變化會按照某種規(guī)則改變其它對象的狀態(tài)。簡而言之就是如果(IF)某些對象狀態(tài)發(fā)生改變，那么(THEN)有可能改變其它對象的狀態(tài)，這種敘述完全符合產(chǎn)生式規(guī)則表示法中的IF…THEN…表達形式。

1.2 離散事件系統(tǒng)模型

離散事件系統(tǒng)模型可用一個5元組來表示:

其中，A代表系統(tǒng)實體對象集，A={α1，α2，…，αm}，|A|=m表示系統(tǒng)實體個數(shù);Sαi表示實體對象αi的狀態(tài)集合，即(1)式，αij表示αi的第j個狀態(tài)，|Sαi|=λi表示實體對象αi的狀態(tài)個數(shù);E表示外部事件的集合，它觸發(fā)實體對象的狀態(tài)發(fā)生變化，可由實體對象的狀態(tài)轉(zhuǎn)移式集合表示。

其中，δ表示系統(tǒng)內(nèi)部的狀態(tài)轉(zhuǎn)移，即表示系統(tǒng)中某些實體對象狀態(tài)發(fā)生變化時將導(dǎo)致其它實體對象狀態(tài)發(fā)生改變，它發(fā)生在外部事件觸發(fā)之后，即。其中，Sα表示實體集A中所有實體在某一時刻的狀態(tài)集合;SA0為系統(tǒng)對象的初始狀態(tài)集;e為由隨機事件觸發(fā);δ表達系統(tǒng)內(nèi)部狀態(tài)轉(zhuǎn)移關(guān)系，可見δ是系統(tǒng)的運行機制，實例化后就是系統(tǒng)運行的規(guī)則。

用IF…THEN…形式描述δ:IF Sα′THEN Sα″，即如果Sα′滿足，將使Sα″發(fā)生。

1.3 產(chǎn)生式規(guī)則表示法舉例——皮帶運輸系統(tǒng)

一條幾百至上千米的皮帶運輸線，需要多臺皮帶機串聯(lián)組成，每臺設(shè)備由電機控制箱和皮帶保護箱組成，每個部件有若干器件組成。此時，系統(tǒng)要研究設(shè)備與設(shè)備之間、設(shè)備與部件之間、部件與器件之間狀態(tài)關(guān)聯(lián)問題，這些問題都是由離散事件驅(qū)動的且是隨機的，如開機事件、關(guān)機事件、各種報警事件，所以稱皮帶運輸系統(tǒng)屬于離散事件系統(tǒng)。

本文著重討論皮帶運輸系統(tǒng)的停機問題，系統(tǒng)停機分為順停和逆停2種停機方式。順停是指從上游設(shè)備往下游設(shè)備依次停機，即1號設(shè)備停、2號設(shè)備?！钡阶詈笠慌_設(shè)備。每臺設(shè)備收到上游臨近設(shè)備順停機消息時要延時一個走帶時間，把皮帶上的貨物運完，保證自己空載停機。逆停是指當(dāng)整個系統(tǒng)中某一臺皮帶機設(shè)備發(fā)生故障時，此時這臺皮帶機及其上游設(shè)備執(zhí)行逆停操作(立即停機)，這臺皮帶機下游所有設(shè)備執(zhí)行順停操作。

分析整個停機過程，系統(tǒng)含有3個實體對象:①皮帶機狀態(tài)——運行、順停、逆停;②電機控制箱狀況——正常、故障;③皮帶保護箱狀況——正常、故障。當(dāng)電機控制箱狀況和皮帶保護箱狀況發(fā)生故障，則皮帶機狀態(tài)為逆停。當(dāng)上游鄰近皮帶機狀態(tài)逆停或順停，則該皮帶機狀態(tài)為順停。當(dāng)下游鄰近皮帶機狀態(tài)為逆停或順停，則該皮帶機狀態(tài)為逆停。

這里將自身皮帶機狀態(tài)表示為皮帶機狀態(tài)(i)，上游鄰近皮帶機狀態(tài)表示為皮帶機狀態(tài)(i-1)，下游鄰近皮帶機狀態(tài)表示為皮帶機狀態(tài)(i+1)。

“電機控制箱狀況”和“皮帶保護箱狀況”狀態(tài)值由“正?！弊?yōu)椤肮收稀笔怯筛鞣N傳感器消息獲得，屬于內(nèi)部隨機事件。鄰近皮帶機狀態(tài)改變消息，屬于外部隨機事件。

用離散事件系統(tǒng)定義的5元組D=(A，Sα，E，δ，SA0)描述。

A={皮帶機狀態(tài)，電機控制箱，皮帶保護箱};

Sα={{運行、逆停、順停}，{正常、故障}，{正常、故障}};

SA0={(皮帶機狀態(tài):運行)，(電機控制箱:正常)，(皮帶保護箱:正常)};

E={電機控制箱發(fā)生故障，皮帶保護箱發(fā)生故障，正常停機}=

δ={

if(電機控制箱狀況:故障)then(皮帶機狀態(tài)(i):逆停);

if(皮帶保護箱狀況:故障)then(皮帶機狀態(tài)(i):逆停);

if(皮帶機狀態(tài)(i):運行)&(皮帶機狀態(tài)(i+ 1):順停or逆停)then(皮帶機狀態(tài)(i):逆停);

if(皮帶機狀態(tài)(i):運行)&(皮帶機狀態(tài)(i-1):順停|逆停)then(皮帶機狀態(tài)(i):順停); }。

按照基于規(guī)則的系統(tǒng)設(shè)計方法，系統(tǒng)包含規(guī)則匹配單元和事件處理單元。規(guī)則匹配單元包括規(guī)則庫和工作內(nèi)存，事件處理單元包括外部事件和內(nèi)部事件的響應(yīng)和處理。對象狀態(tài)消息傳入規(guī)則匹配區(qū)中，首先更新工作內(nèi)存中存放的對象狀態(tài)消息，然后進行規(guī)則匹配，整個過程結(jié)構(gòu)如圖2所示。

圖2中，規(guī)則庫存放用于表示對象狀態(tài)轉(zhuǎn)換的規(guī)則;工作內(nèi)存存放對象的當(dāng)前狀態(tài)，為規(guī)則匹配提供依據(jù)。發(fā)送到規(guī)則匹配區(qū)的消息先更新工作內(nèi)存中對象狀態(tài)，再進行規(guī)則匹配。規(guī)則匹配過程是將規(guī)則與當(dāng)前工作內(nèi)存中的對象狀態(tài)進行比較。以上過程按照實體流圖法建模(實體流圖法是借鑒程序流程圖方法產(chǎn)生設(shè)計的)，其過程如圖3所示[8]。

對比圖2和圖3可以發(fā)現(xiàn)，產(chǎn)生式規(guī)則表示法系統(tǒng)邏輯由規(guī)則式描述，系統(tǒng)控制程序主要完成規(guī)則匹配和消息的傳遞，比一般實體流圖法的邏輯存在整個控制系統(tǒng)程序中，具有更好的可維護性和可操作性。系統(tǒng)需求變更，系統(tǒng)控制單元不變，只需改變規(guī)則庫。這樣將繁瑣的程序邏輯設(shè)計轉(zhuǎn)化為類自然語言描述的規(guī)則式，方便設(shè)計工作。

圖2 停機問題基于規(guī)則的系統(tǒng)結(jié)構(gòu)圖

圖3 實體流圖法系統(tǒng)結(jié)構(gòu)圖

2 規(guī)則庫的結(jié)構(gòu)錯誤檢測

2.1 錯誤分類

在實際應(yīng)用過程中，周期性地對規(guī)則庫進行調(diào)整，包括添加、刪除、修改操作，可能導(dǎo)致規(guī)則庫的結(jié)構(gòu)錯誤。因此在對規(guī)則庫進行修改后，有必要對規(guī)則系統(tǒng)進行有效驗證，以保證規(guī)則系統(tǒng)的完備性和一致性。同時，還需檢測會降低系統(tǒng)運行效率的冗余規(guī)則等。

典型的錯誤包括冗余、不一致、死結(jié)點、不可達結(jié)點和死循環(huán)[6]。

(1)冗余。一個規(guī)則系統(tǒng)中，如果2條規(guī)則的前提為包含關(guān)系，結(jié)論相同，則為冗余。

(2)不一致。也稱沖突或矛盾，如果在相同的前提下，可以推導(dǎo)出相互矛盾的結(jié)論，則稱該規(guī)則系統(tǒng)是不一致的。

(3)不完備。指規(guī)則庫對系統(tǒng)的刻畫不完整，可能是遺漏了部分規(guī)則，分2種情況:①死結(jié)點，實體只出現(xiàn)在結(jié)論集中，沒有出現(xiàn)在前提集中，且不是目標結(jié)論;②不可達結(jié)點，實體只出現(xiàn)在前提集，沒有出現(xiàn)在結(jié)論集中，并且不在輸入集中。

(4)死循環(huán)。在規(guī)則系統(tǒng)中，由一個前提出發(fā)，通過一系列的邏輯推理，又推導(dǎo)出該前提，使得推理不能正常結(jié)束。

2.2 檢測方法

(1)冗余。如果2條規(guī)則構(gòu)成冗余，有2個必要條件:2條規(guī)則的結(jié)論相同;2條規(guī)則的前提集合為包含關(guān)系。證明略，根據(jù)定義可得。

(2)沖突。2條規(guī)則是沖突的，當(dāng)且僅當(dāng):2條規(guī)則的結(jié)論相互沖突;2條規(guī)則的前提集合不沖突;任意結(jié)論不為對方的前提。

證明如下。

充分性:ri與rj的結(jié)論相沖突，如果ri和rj的條件集合不沖突，則在rj與rj的條件合集下，可同時引發(fā)ri與rj，使得出現(xiàn)不一致。

必要性:利用反證法可得。如果2條規(guī)則的結(jié)論不相沖突，則不會不一致;如果2條規(guī)則的前提集合相沖突，則不會同時出現(xiàn)在某一前提集下;如果一條件規(guī)則的結(jié)論是另一條規(guī)則的條件，事件的發(fā)生有先后順序，也不會同時出現(xiàn)。

(3)死循環(huán)。一組規(guī)則構(gòu)成死循環(huán)當(dāng)且僅當(dāng):構(gòu)成回路，即每條規(guī)則的結(jié)論都出現(xiàn)在另一條規(guī)則的前提中;該組的條件集合減去該組的結(jié)論集后，所得集合要么為空，要么不沖突。

證明如下。

充分性:設(shè)有規(guī)則集合{ri，…，rk}，構(gòu)成回路，條件集合減去結(jié)論集合后所得集合為C，且C內(nèi)元素不沖突。在ri成立的條件下，把ri的結(jié)論放到當(dāng)前的前題集合中，繼續(xù)匹配，則可以得到rj，…，rk。又rk的結(jié)論為ri的前提，ri再次成立，匹配不能正常結(jié)束。

必要性:如果{ri，…，rk}不構(gòu)成回路，則匹配可以正常結(jié)束，不會引起死循環(huán);如果條件集合減去結(jié)論集合得到結(jié)果集C，所得結(jié)果相沖突，假定ri與rj的前提部分出現(xiàn)在結(jié)果集C中，則規(guī)則ri與rj不會都匹配成功，推理可以正常結(jié)束。

(4)完備性。系統(tǒng)的完備性依賴于具體的應(yīng)用，假定有目標結(jié)論集p o，前提集p i。規(guī)則庫的結(jié)論集合Cres，規(guī)則庫的條件集合Ccon。

根據(jù)定義可得:Ccon-Cres-po則為死結(jié)點; Cres-Cres-p i則為不可達結(jié)論。

2.3 實例分析

限于篇幅，摘取如下規(guī)則庫片段，LRDL的語義見文獻[9]。

r1:[電機控制箱:正常]&[皮帶保護箱:正常]==[皮帶機狀態(tài):運行];

r2:[電機控制箱:故障]==[皮帶機狀態(tài):逆停];

r3:[皮帶保護箱:故障]==[皮帶機狀態(tài):逆停];

r4:[皮帶機狀態(tài):運行]&[皮帶機狀態(tài)(i+ 1):逆停|順停]==[皮帶機狀態(tài):逆停];

r5:[皮帶機狀態(tài):運行]&[皮帶機狀態(tài)(i-1):順停|逆停]==[皮帶機狀態(tài):順停];

r6:[皮帶機狀態(tài):順停]&[皮帶機狀態(tài)(i+ 1):運行]&[皮帶機狀態(tài)(i-1):順停]==[皮帶機狀態(tài):運行];

根據(jù)相關(guān)定義及定理，得到如下結(jié)論:

冗余:無

沖突:{r4，r5}，在前提集{[皮帶機狀態(tài)(i+ 1):逆停]，[皮帶機狀態(tài)(i-1):順停]}下，可能引起沖突。

不完備:無

死循環(huán):{r5，r6}在前提集{[皮帶機狀態(tài)(i+ 1):運行]，[皮帶機狀態(tài)(i-1):順停]}下，可能引起死循環(huán)。

上例是規(guī)則庫的第1個版本中的部分規(guī)則，經(jīng)邏輯驗證，存在結(jié)構(gòu)錯誤，經(jīng)過適當(dāng)修改，成功通過驗證。這也證實了規(guī)則庫與推理機的相互獨立性，給系統(tǒng)的維護帶來了方便。

3 結(jié)束語

本文研究的離散事件系統(tǒng)的系統(tǒng)結(jié)構(gòu)借鑒專家系統(tǒng)中基于規(guī)則系統(tǒng)架構(gòu)，采用產(chǎn)生式規(guī)則描述方法描述系統(tǒng)的事件發(fā)生和狀態(tài)轉(zhuǎn)移;并對得到的規(guī)則庫進行了有效的結(jié)構(gòu)驗證，保證了規(guī)則庫的內(nèi)部邏輯的正確性。對規(guī)則匹配的算法研究可以參考文獻[10]，至于規(guī)則庫刻畫的系統(tǒng)控制邏輯是否合理，有待進一步的仿真實驗。

[1] Ouidad K R.Interacting w ith reasoning in a MAS in tegrating a RBS[C]//Information and Communication Technologies，ICTTA 2006，Vol 2，2006:3001-3006.

[2] Campbell A S，Wainer G A.Applying DEVS modeling for discrete eventmultip lem odelcontrol ofa time varying plant [C]//W in ter Simulation Conference，2006:823-831.

[3] 韓江洪，鄭淑麗，陸 陽，等.離散事件控制系統(tǒng)規(guī)則化描述方法的研究[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2005，28 (9):1081-1084.

[4] 曲長征，于永利，金 偉，等.基于ExSpect的復(fù)雜離散事件動態(tài)系統(tǒng)建模[J].系統(tǒng)仿真學(xué)報，2005，17(12): 3011-3013.

[5] 孫 安，畢 翔，韓江洪，等.基于狀態(tài)轉(zhuǎn)換圖的LL語法快速分析方法[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版，2009，32 (7):1030-1033.

[6] 丁志軍，潘美芹，蔣昌俊，等.無回路規(guī)則系統(tǒng)的Petri網(wǎng)驗證方法[J].同濟大學(xué)學(xué)報:自然科學(xué)版，2007，35(2): 232-238.

[7] 宋新民，龍楊喜，賈志軍.基于仿真的故障診斷專家系統(tǒng)應(yīng)用研究[J].系統(tǒng)仿真學(xué)報，2006，18(4):1038-1040.

[8] 王維平，朱一凡，李 群，等.離散事件系統(tǒng)建模與仿真[M].北京:科學(xué)出版社，2007:25-57.

[9] 魏振春，韓江洪，陸 陽，等.一種基于規(guī)則的語言的公理主義[J].計算機工程與應(yīng)用，2008，44(20):86-88.

[10] 韓江洪，張亞瓊，魏振春，等.基于規(guī)則的離散事件系統(tǒng)建模與規(guī)則匹配研究[J].系統(tǒng)仿真學(xué)報，2008，20(6): 1394-1396，1419.