基于模型診斷研究進(jìn)展與展望

1、<p>　　基于模型診斷研究進(jìn)展與展望</p><p><b>　　摘要：</b></p><p>　　基于模型診斷方法是為了克服傳統(tǒng)診斷方法的嚴(yán)重缺陷而興起的新型智能診斷推理技術(shù)，是診斷理論和技術(shù)上的革命，對(duì)人工智能領(lǐng)域的研究起著重要的推動(dòng)作用。本文以一致性診斷和蘊(yùn)含診斷方法為代表，介紹了基于模型的靜態(tài)診斷相關(guān)技術(shù)和方法?；谀Ｐ偷碾x散事件診斷方法是靜態(tài)系

2、統(tǒng)診斷的延續(xù)，同時(shí)也是混成系統(tǒng)乃至純粹動(dòng)態(tài)系統(tǒng)模型診斷研究的基礎(chǔ)。本文綜述了離散事件系統(tǒng)模型診斷的建模及表示、可診斷性和相關(guān)診斷方法。介紹了若干有代表性的診斷系統(tǒng)，從系統(tǒng)建模、診斷方法、可診斷性判定、模型重構(gòu)及診斷應(yīng)用等方面展望了針對(duì)基于模型診斷領(lǐng)域中有待進(jìn)一步解決的問(wèn)題。</p><p>　　Abstract: Model-based diagnosis method is a new type of inte

3、lligent diagnostic reasoning technology, overcoming the shortcomings of traditional fault-diagnosis methods. Moreover, it is the revolution of diagnosis method both in theory and technology, and plays an important role i

4、n the research field of Artificial Intelligence. Using the methods of consistency-based diagnosis and diagnostic implication as representatives, this paper introduces the related technologies and methods of model-based d

5、</p><p>　　在20世紀(jì)60年代航天和軍工等高可靠性工程的迫切需求下，診斷迅速發(fā)展起來(lái)成為一門新興學(xué)科。特別是近二十年來(lái)，一些關(guān)鍵性現(xiàn)代化設(shè)備出現(xiàn)故障造成了重大損失。為避免這些嚴(yán)重災(zāi)難性事件的不斷發(fā)生，人們?cè)谠O(shè)備診斷上投入了大量的研究工作，分別在人工智能和自動(dòng)控制領(lǐng)域形成了診斷推理研究課題。經(jīng)過(guò)數(shù)十年的研究，已經(jīng)取得了許多研究成果，提出了諸多故障診斷方法，部分研究成果已經(jīng)應(yīng)用到實(shí)際中，及時(shí)發(fā)現(xiàn)故障并恢復(fù)，

6、避免了因故障造成的損失，并為進(jìn)一步改進(jìn)設(shè)備性能提供重要參考。</p><p>　　傳統(tǒng)的第一代診斷專家系統(tǒng)具有很強(qiáng)的設(shè)備依賴性，如何從專家那里獲取必要的診斷知識(shí)是維護(hù)、發(fā)展系統(tǒng)的瓶頸。基于模型診斷（Model-Based Diagnosis, MBD）是為了克服第一代診斷系統(tǒng)的嚴(yán)重缺陷而出現(xiàn)的智能診斷推理技術(shù)。不同于傳統(tǒng)的診斷方法，MBD使用設(shè)備的內(nèi)部結(jié)構(gòu)與行為的知識(shí)進(jìn)行診斷，被人工智能專家譽(yù)為診斷理論和技術(shù)上的

7、革命[1]。在IJCAI-99上，著名MBD專家Console和Dressler在其特邀報(bào)告中指出：MBD 對(duì)整個(gè)人工智能領(lǐng)域的研究起著重要推動(dòng)作用[2]。MBD專家Struss稱 MBD 是對(duì)人工智能的一個(gè)重要挑戰(zhàn)和檢驗(yàn)[3]。</p><p>　　MBD的研究受到了國(guó)內(nèi)外學(xué)者的重視，其應(yīng)用也越來(lái)越廣泛， 如電路故障查找、醫(yī)學(xué)診斷、大型VHDL程序的故障檢測(cè)與定位、大型通訊網(wǎng)絡(luò)故障診斷、電網(wǎng)故障診斷、汽車故障診

8、斷等。獲得美國(guó)宇航局獎(jiǎng)的Livingstone系統(tǒng)在沒(méi)有地面控制人員指揮的情況下自主診斷“深空一號(hào)”飛船的故障并發(fā)出更正指令。歐盟基金項(xiàng)目VMBD將MBD技術(shù)同時(shí)應(yīng)用于汽車制造和汽車駕駛，并做出商品化的汽車 MBD系統(tǒng)。</p><p>　　MBD的基本思想如圖1所示：由系統(tǒng)模型出發(fā)給出系統(tǒng)當(dāng)前的預(yù)測(cè)輸出值，然后與當(dāng)前的實(shí)際觀測(cè)值進(jìn)行比較，若兩者出現(xiàn)了差異，則說(shuō)明系統(tǒng)出現(xiàn)了故障；然后由差異出發(fā)，結(jié)合系統(tǒng)的模型進(jìn)行

9、推理給出系統(tǒng)可能的故障。</p><p>　　起初MBD的研究主要針對(duì)“靜態(tài)系統(tǒng)”，即系統(tǒng)停止運(yùn)行或者系統(tǒng)的某個(gè)運(yùn)行時(shí)間點(diǎn)的快照等，給出此時(shí)的故障診斷情況。隨著對(duì)在線診斷需求的出現(xiàn)，許多學(xué)者開展動(dòng)態(tài)系統(tǒng)MBD的研究。動(dòng)態(tài)系統(tǒng)MBD主要包括離散事件系統(tǒng)MBD、混成系統(tǒng)MBD和仍為開放性問(wèn)題的連續(xù)系統(tǒng)MBD。由于離散事件系統(tǒng)在各狀態(tài)中接近靜態(tài)系統(tǒng)[4]，而許多混成或者連續(xù)值的動(dòng)態(tài)系統(tǒng)通過(guò)抽象和近似以后，又可以使用離散

10、事件系統(tǒng)來(lái)表達(dá)，因此，離散事件系統(tǒng)MBD是靜態(tài)系統(tǒng)到連續(xù)系統(tǒng)MBD研究的橋梁[5]，受到越來(lái)越多學(xué)者的關(guān)注。</p><p><b>　　2 國(guó)際研究現(xiàn)狀</b></p><p>　　國(guó)外MBD方法的研究機(jī)構(gòu)主要集中在歐美。在靜態(tài)MBD方面：普林斯頓大學(xué)Sharad Malik教授領(lǐng)導(dǎo)的MBD方面研究小組在全球享有盛譽(yù)[6-8]；斯坦福研究所設(shè)有專門的診斷和驗(yàn)證中心，

11、在Dutertre研究員的帶領(lǐng)下已經(jīng)成為全世界MBD和驗(yàn)證的基地[9]；愛(ài)爾蘭都柏林大學(xué)Marques-Silva教授在SAT和MBD方面國(guó)際領(lǐng)先[10, 11]；加拿大多倫多大學(xué)Veneris教授領(lǐng)導(dǎo)的研究小組在MBD方面成果突出[12, 13]；在美國(guó)密歇根大學(xué)[14, 15]、華盛頓大學(xué)[16]和德國(guó)不來(lái)梅大學(xué)[17, 18]等也有相關(guān)的研究小組。</p><p>　　在實(shí)際應(yīng)用中，許多待診斷系統(tǒng)都是動(dòng)態(tài)系

12、統(tǒng)。動(dòng)態(tài)系統(tǒng)的典型特征是不確定性，因而其在建模、預(yù)測(cè)等方面比靜態(tài)系統(tǒng)MBD復(fù)雜得多，動(dòng)態(tài)系統(tǒng)診斷是對(duì)模型化特別是定性模型化以及推理機(jī)制的挑戰(zhàn)，至今仍是MBD有待解決的關(guān)鍵問(wèn)題。20世紀(jì)90年代中期Sampath等學(xué)者提出了用離散事件系統(tǒng)來(lái)解決或部分解決動(dòng)態(tài)系統(tǒng)診斷問(wèn)題[19, 20]，迅速成為MBD領(lǐng)域的一個(gè)熱點(diǎn)課題。最近幾年，在AIJ、JAIR、 AICom、 IJCAI、AAAI和ECAI等人工智能領(lǐng)域國(guó)際重要期刊及會(huì)議上，發(fā)表了許

13、多離散事件系統(tǒng)MBD的論文。另外，歐美一些國(guó)家從九十年代初期開始每年舉行一次診斷原理會(huì)議，其中有許多關(guān)于離散事件系統(tǒng)MBD的研究成果發(fā)表。</p><p>　　在離散事件系統(tǒng) MBD方面：美國(guó)密歇根大學(xué)Lafortune教授等從監(jiān)控理論研究離散可診斷性等問(wèn)題[21, 22]；法國(guó)雷恩大學(xué)Cordier教授等主要研究在線增量診斷及可診斷性問(wèn)題[23-28]；意大利布雷西亞大學(xué)Lamperti教授等研究主動(dòng)系統(tǒng)診斷問(wèn)

14、題[29-38]；加拿大多倫多大學(xué)Wonham教授等從全局一致性研究分布式診斷問(wèn)題[39, 40]；澳大利亞國(guó)立大學(xué)的一些學(xué)者也在研究增量診斷及可診斷性分析方法[41-47]。</p><p>　　基于模型診斷已應(yīng)用于很多領(lǐng)域。近幾年，除電路故障查找系統(tǒng)和醫(yī)學(xué)診斷系統(tǒng)外，MBD開始向更實(shí)用化的方向發(fā)展，如大型VHDL程序的故障檢測(cè)與定位、大型異步離散事件系統(tǒng)的診斷、網(wǎng)絡(luò)通訊故障診斷、汽車故障診斷、燃?xì)廨啓C(jī)監(jiān)控、W

15、eb故障監(jiān)控等。下面是MBD的幾個(gè)有代表性的應(yīng)用系統(tǒng)：</p><p><b>　?。?）DART</b></p><p>　　DART用一階邏輯語(yǔ)言描述設(shè)備，使用了獨(dú)立于設(shè)備的語(yǔ)言，在推理上使用了合取范式和推理規(guī)則，與歸結(jié)方法具有類似之處。在診斷推理過(guò)程中把假設(shè)產(chǎn)生和測(cè)試結(jié)合起來(lái)，以提高系統(tǒng)的效率。</p><p><b>　　（2

16、）GDE等系列</b></p><p>　　GDE使用了基于假設(shè)的真值維護(hù)系統(tǒng)作為其基礎(chǔ)的支持系統(tǒng)，通過(guò)使用極小沖突集來(lái)產(chǎn)生診斷。</p><p>　　最初的GDE系統(tǒng)是基于一致性的診斷，以后有很多擴(kuò)展，如Sherlock在GDE的基礎(chǔ)上加入了故障模型和統(tǒng)計(jì)信息，XDE則主要針對(duì)數(shù)字電路且將時(shí)間標(biāo)識(shí)集成到基于假設(shè)的真值維護(hù)系統(tǒng)中，SIDIA可用于診斷動(dòng)態(tài)系統(tǒng)，而FDE則使用基于

17、假設(shè)的真值維護(hù)系統(tǒng)，可看作GDE的一個(gè)簡(jiǎn)單實(shí)現(xiàn)，F(xiàn)DE-2則不必遵循觀測(cè)的時(shí)間順序而可以在任何階段插入測(cè)試點(diǎn)的觀測(cè)。</p><p>　?。?）LIVINGSTONE-2</p><p>　　由美國(guó)航天局NASA的埃姆斯研究中心和噴氣推進(jìn)實(shí)驗(yàn)室聯(lián)合推出的，第一個(gè)用于獨(dú)立控制宇宙飛船“深空一號(hào)”軟件包中的一部分，可自動(dòng)探測(cè)、診斷和排除故障，并可自行做出“決定”進(jìn)行故障恢復(fù)，使宇航飛行正常。這

18、種能力將使21世紀(jì)的航天器操作成本大為降低。由于該系統(tǒng)的特殊性，在設(shè)計(jì)時(shí)就考慮到了安全性、可維護(hù)性、最小化、可移植等要求。</p><p>　　（4）燃?xì)廨啓C(jī)診斷系統(tǒng)</p><p>　　是在進(jìn)行TIGER項(xiàng)目（歐聯(lián)體基金項(xiàng)目）的研究中產(chǎn)生的，是已商品化的系統(tǒng)，已有了廣泛的應(yīng)用。</p><p>　?。?）AUTOSTEVE</p><p>

19、　　已被福特和美洲虎使用的汽車診斷系統(tǒng)FMEA，能夠自動(dòng)生成失效模式及效應(yīng)分析。</p><p>　　除了上面提及的汽車診斷系統(tǒng)外，Mosterman等于1998年提出了診斷雪佛萊發(fā)動(dòng)機(jī)的方法，在VMBD項(xiàng)目進(jìn)行過(guò)程中設(shè)計(jì)出了RAZ’R，它是一個(gè)模型化和診斷的開發(fā)和運(yùn)行環(huán)境，已被保時(shí)捷和沃爾沃采用。VMBD項(xiàng)目的目標(biāo)就是將基于模型的診斷技術(shù)既應(yīng)用于在生產(chǎn)車間內(nèi)的汽車，又應(yīng)用于正在行駛的汽車。它是一個(gè)歐盟基金項(xiàng)目，

20、合作者包括汽車制造商、供應(yīng)商和大學(xué)。這一項(xiàng)目推動(dòng)了基于模型診斷的發(fā)展，它使得生產(chǎn)商和供應(yīng)商有機(jī)會(huì)來(lái)考察基于模型的診斷技術(shù)。</p><p>　　（6）電網(wǎng)故障診斷系統(tǒng)</p><p>　　意大利布雷西亞大學(xué)Lamperti教授等開發(fā)的電網(wǎng)故障診斷系統(tǒng)，將由斷路器、保護(hù)器、電線等構(gòu)成的大型電網(wǎng)抽象為一個(gè)離散事件的系統(tǒng)，根據(jù)各部件的內(nèi)在工作模式以及連接方式，使用基于模型的方法對(duì)網(wǎng)絡(luò)建模，通過(guò)匹

21、配所觀測(cè)到的現(xiàn)象來(lái)推斷網(wǎng)絡(luò)的行為給出故障的部件。已經(jīng)實(shí)現(xiàn)了一個(gè)較為通用的自動(dòng)診斷環(huán)境。</p><p>　?。?）大型通訊網(wǎng)絡(luò)故障診斷系統(tǒng)</p><p>　　法國(guó)雷恩大學(xué)Cordier教授等研究的大型通訊網(wǎng)絡(luò)的基于模型的故障診斷系統(tǒng)，將大型通訊網(wǎng)絡(luò)使用通訊自動(dòng)機(jī)建模，采用分散式方法、利用模塊獨(dú)立性等特點(diǎn)處理復(fù)雜度問(wèn)題。在MAGDA項(xiàng)目過(guò)程中實(shí)現(xiàn)了診斷工具如DDyp等，并基于SDH網(wǎng)絡(luò)等進(jìn)

22、行了測(cè)試。</p><p>　　此外，最近幾年，一些學(xué)者對(duì)基于模型診斷應(yīng)用到Web服務(wù)、工作流（Workflow）等進(jìn)行了研究，如歐盟項(xiàng)目WS-Diamond等。</p><p><b>　　3 國(guó)內(nèi)研究進(jìn)展</b></p><p>　　國(guó)內(nèi)MBD方法的研究團(tuán)隊(duì)主要包括：中山大學(xué)MBD小組，重點(diǎn)研究靜態(tài)系統(tǒng)的 MBD算法[48, 49]；吉林大

23、學(xué)的MBD研究組，從1998年開始MBD研究，側(cè)重靜態(tài)系統(tǒng)的MBD方法[50-59]，后續(xù)開展了不完備模型下動(dòng)態(tài)系統(tǒng)的MBD研究；此外，中國(guó)科學(xué)院軟件所[60, 61]，國(guó)防科技大學(xué)[62]等學(xué)者也給出了靜態(tài)系統(tǒng)的MBD算法；隨著對(duì)航天器自主生存能力要求的提高, 哈爾濱工業(yè)大學(xué)[63, 64]、北京航空航天大學(xué)[65-68]等高校學(xué)者也投入到了MBD研究中，給出了適合航天器的自主診斷算法；西南交通大學(xué)針對(duì)傳統(tǒng)專家系統(tǒng)不能滿足配電網(wǎng)故障診

24、斷的要求，對(duì)MBD方法進(jìn)行研究，給出配電網(wǎng)故障有效的診斷方法[69, 70]。</p><p>　　基于模型診斷方法受到了工業(yè)界的高度重視，從學(xué)術(shù)科研領(lǐng)域逐步走向?qū)嶋H研究與應(yīng)用。國(guó)際三大電子設(shè)計(jì)自動(dòng)化（Electronic Design Automation，EDA）公司Cadence、Synopsys和Mentor Graphics相繼研制出相關(guān)產(chǎn)品工具，如Encounter Diagnostics、Tetra

25、MAX、和YieldAssist等。遺憾的是，EDA領(lǐng)域有影響力的公司都來(lái)自美國(guó)，他們對(duì)核心技術(shù)的絕對(duì)壟斷嚴(yán)重制約了如我國(guó)這樣的發(fā)展中國(guó)家自主知識(shí)產(chǎn)權(quán)的芯片設(shè)計(jì)和創(chuàng)新。據(jù)國(guó)內(nèi)知名的“電子工程專輯”網(wǎng)站統(tǒng)計(jì)，國(guó)內(nèi)以中星微電子為代表的具有自主芯片設(shè)計(jì)能力的公司已超過(guò)600家，幾乎毫無(wú)選擇余地地購(gòu)買和使用上述三家公司的相關(guān)產(chǎn)品。MBD方法的研究及相關(guān)工具的研制，不僅是基礎(chǔ)理論研究的需要，也是提升我國(guó)芯片研發(fā)能力，增強(qiáng)國(guó)防實(shí)力的現(xiàn)實(shí)要求。<

26、;/p><p>　　4 國(guó)內(nèi)外研究進(jìn)展比較</p><p><b>　　4.1靜態(tài)系統(tǒng)診斷</b></p><p>　　根據(jù)對(duì)診斷結(jié)果邏輯約束強(qiáng)弱的不同，MBD可劃分為兩個(gè)基本流派：基于一致性的診斷[71-74](Consistency-Based Diagnosis, CBD)和基于溯因診斷[75, 76] (Abductive-Based Di

27、agnosis, ABD)。CBD僅要求所得候選診斷結(jié)果與系統(tǒng)模型、觀測(cè)在邏輯上相一致(即“不沖突”)即可；而ABD則不僅要求候選診斷結(jié)果與系統(tǒng)模型、觀測(cè)在邏輯上一致，還要求候選部件的(故障)行為必然能夠邏輯推出實(shí)際的(異常)觀測(cè)。顯然，ABD比CBD在邏輯約束上要求更強(qiáng)。相應(yīng)地，ABD 要求系統(tǒng)模型必須是完備的，即模型中包含了正常行為和所有可能的故障行為； 而CBD僅要求系統(tǒng)正常行為模型完備即可。由于ABD對(duì)診斷空間的限制太強(qiáng)， 即要

28、求所有觀測(cè)需要被診斷邏輯推出，這樣，如果待診斷系統(tǒng)的模型不完備，則可能丟失真正的解；而CBD對(duì)診斷空間的限制又太弱，即不要求任何觀測(cè)被診斷邏輯推出，這導(dǎo)致診斷空間中可能包含了大量的無(wú)用解。為此，人們趨向于研究如何將兩種方法比較、融合。 </p><p>　　4.1.1 基于溯因的診斷方法</p><p>　　Console和Torasso[77]將診斷看成是帶一致性約束的溯因問(wèn)題，并提出了

29、一個(gè)統(tǒng)一的定義，使得不同的邏輯定義都可在這一定義中進(jìn)行表示，并能夠進(jìn)行比較。通過(guò)比較，指出對(duì)于一個(gè)已知的領(lǐng)域或問(wèn)題，選擇哪一個(gè)邏輯定義更為合適。歐陽(yáng)丹彤等[78]在該定義的基礎(chǔ)上，研究了基于模型的中心診斷，并給出它的形式化診斷過(guò)程。 </p><p>　　因果關(guān)系知識(shí)是常識(shí)推理的一個(gè)重要部分。近幾年，許多學(xué)者將因果關(guān)系應(yīng)用于基于模型診斷領(lǐng)域，但這些研究工作僅僅針對(duì)簡(jiǎn)單因果理論。該理論有一定的局限性，因?yàn)樵谄渲兄挥?/p>

30、表示因果關(guān)系的信息。為此，姜云飛等[79]提出了廣義因果理論的概念，并研究了關(guān)于廣義因果理論的基于模型診斷與中心診斷的方法。歐陽(yáng)丹彤等[80]還利用溯因符號(hào)的概念擴(kuò)展了Console和Torasso描述文字對(duì)基于模型診斷的定義，并對(duì)能夠刻劃基于模型診斷空間的廣義因果理論上的基于模型中心診斷的診斷過(guò)程進(jìn)行了形式化，建立了其與本原蘊(yùn)涵/ 蘊(yùn)涵式的直接關(guān)系。該結(jié)果更具有一般性:一方面，得到的診斷不僅可以描述部件的正常或反常，還可描述部件的各種

31、故障行為方式；另一方面，當(dāng)需要被邏輯推出的觀測(cè)原子集取從空集到觀測(cè)全集一系列不同的觀測(cè)子集時(shí)，可得到從廣義因果理論上的從基于一致性診斷到溯因診斷等一系列診斷的計(jì)算方法。在實(shí)際應(yīng)用中，可使用我們的診斷方法，通過(guò)分析涉及表示每一觀測(cè)原子的那部分模型的完備性來(lái)適當(dāng)選擇需要被邏輯推出的觀測(cè)原子集，使得診斷空間不大，又不會(huì)丟失有用解。MBD中的模型總是假設(shè)基于系統(tǒng)的觀測(cè)和預(yù)測(cè)是準(zhǔn)確的，但在某些領(lǐng)域上此假設(shè)并</p><p>

32、;　　溯因診斷對(duì)診斷空間的限制太強(qiáng)，還要求所有觀測(cè)都必須被診斷邏輯推出，當(dāng)模型不完備時(shí)可能丟失有用解?；谝恢滦栽\斷對(duì)診斷空間的限制較弱，僅要求診斷與觀測(cè)一致。因此，許多學(xué)者對(duì)基于一致性的診斷方法進(jìn)行了研究，并結(jié)合一致性基本思想給出了利用BDD、SAT等進(jìn)行診斷的方法。</p><p>　　4.1.2 基于一致性的診斷方法</p><p>　　在靜態(tài)系統(tǒng)診斷中，常用基于一致性的方法來(lái)求解診

33、斷，診斷是分兩步進(jìn)行的，一是與領(lǐng)域有關(guān)的沖突識(shí)別，二是與領(lǐng)域無(wú)關(guān)的候選產(chǎn)生。Reiter[74]基于一致性方法首先基于一階邏輯推理求得沖突部件集合，然后根據(jù)所有沖突部件集合求得所有極小碰集得到候選診斷。De Kleer[71]等學(xué)者給出的基于一致性方法則利用基于假設(shè)的真值維護(hù)系統(tǒng)求出所有正的極小沖突及相應(yīng)的本原蘊(yùn)涵的方法求得所有候選診斷。后來(lái)，許多學(xué)者對(duì)Reiter給出的沖突集和碰集求解方法進(jìn)行了改進(jìn)。文獻(xiàn)[51]結(jié)合故障理論，給出了基

34、于一致性的最小正常診斷的概念，將系統(tǒng)描述限制在故障理論或在故障理論中擴(kuò)展有限的正常行為知識(shí)，進(jìn)而使用最小正常診斷刻畫基于一致性的診斷空間，縮小正常行為模型的最小反常診斷所產(chǎn)生的診斷空間；此外使用溯因刪除冗余解也是很重要的方法，文獻(xiàn)[50]還對(duì)溯因診斷和中心溯因診斷過(guò)程進(jìn)行刻畫，并將求中心溯因診斷過(guò)程刻畫為與領(lǐng)域有關(guān)的沖突識(shí)別及與領(lǐng)域無(wú)關(guān)的候選產(chǎn)生。</p><p>　　4.1.2.1 沖突識(shí)別</p>

35、<p>　　國(guó)內(nèi)外許多學(xué)者對(duì)診斷過(guò)程中沖突識(shí)別方法進(jìn)行了研究。De kleer首次提出沖突集的概念[82]，為基于一致性的診斷算法奠定了重要的基礎(chǔ)，隨后他又提出了一些沖突識(shí)別的方法以及一個(gè)廣為應(yīng)用且可用于計(jì)算極小沖突集的自動(dòng)推理引擎基于假設(shè)的真值維護(hù)系統(tǒng)[83]。后來(lái)，其他學(xué)者則使用定理機(jī)器證明的方法，如DART[72]等可以用作診斷過(guò)程中的沖突識(shí)別。Hou首先提出了CS-Tree方法[84]，然而，該極小沖突集計(jì)算方法依

36、賴于節(jié)點(diǎn)產(chǎn)生的順序，造成某些極小沖突集可能在計(jì)算過(guò)程中因剪枝而丟失，從而算法不完備。Han等[85]對(duì)Hou的方法進(jìn)行了改進(jìn)，提出了翻轉(zhuǎn)的CS-Tree方法(Inverse CS-Tree)和帶有標(biāo)識(shí)集的CS-Tree方法(CS-Tree with Mark Set)，此方法完備，但效率依然不高。</p><p>　　國(guó)內(nèi)學(xué)者也對(duì)于沖突識(shí)別方法進(jìn)行了研究。欒尚敏等[61]給出了在系統(tǒng)中利用系統(tǒng)結(jié)構(gòu)信息來(lái)求解所有極

37、小沖突集的方法；方敏[86]根據(jù)系統(tǒng)的結(jié)構(gòu)信息離線識(shí)別候選極小沖突集，然后根據(jù)測(cè)量數(shù)據(jù)和約束推理技術(shù)在線確定極小沖突集合簇。代樹武等[87]給出結(jié)合參數(shù)矩陣求解所有極小沖突集的方法，并且每次求解沖突集時(shí)僅調(diào)用一次元件模型知識(shí)。趙相福等[88]對(duì)產(chǎn)生所有極小沖突集的求解方法進(jìn)行過(guò)研究，給出CSSE-Tree方法和CSISE-Tree方法。</p><p>　　4.1.2.2 碰集求解</p><

38、p>　　現(xiàn)實(shí)和理論中的很多問(wèn)題都可以歸結(jié)為極小碰集的求解問(wèn)題，即求解與已知集合都有交的極小集合。例如：極小覆蓋集問(wèn)題、老師與課程問(wèn)題等。基于模型診斷中極小診斷就是求解所有極小沖突集的極小碰集。迄今為止，國(guó)內(nèi)外學(xué)者已對(duì)計(jì)算碰集的方法進(jìn)行了許多研究和改進(jìn)。在模型診斷中最早計(jì)算碰集的方法是由著名人工智能專家Reiter在1987年提出的HS-Tree求解碰集的方法[74]，在求解過(guò)程中加入剪枝策略和關(guān)閉策略，此種方法可能會(huì)丟失正確解。為

39、了保證極小碰集求解方法的完備性，Greiner等[89]對(duì)此方法進(jìn)行了改進(jìn)，給出了結(jié)合非循環(huán)圖的HS-DAG方法。此后，奧地利學(xué)者Wotawa等[90]也給出了基于Reiter碰集算法的改進(jìn)方法；歐陽(yáng)丹彤等[91]對(duì)Greiner給出的方法進(jìn)行了改進(jìn)，提出了NewHs-Tree方法，此方法在計(jì)算碰集時(shí)比HS-DAG方法搜索的結(jié)點(diǎn)數(shù)大大減少。趙相福等[92]給出了使用集合枚舉樹SE-tree形式化表達(dá)計(jì)算碰集的方法；馮文全等[66]學(xué)者在

40、此基礎(chǔ)上給出了結(jié)合二進(jìn)制標(biāo)簽改進(jìn)的碰集算法。陳曉梅等[93]給出了結(jié)合分支定界的集合枚舉樹碰集方法，通過(guò)將問(wèn)題分解成子問(wèn)題降低問(wèn)題的求</p><p>　　4.1.3 基于一致性擴(kuò)展診斷方法</p><p>　　在基于模型診斷推理方法中，診斷過(guò)程主要是分兩步進(jìn)行，首先是求得沖突部件集合，然后根據(jù)所有沖突部件集合求得所有極小碰集得到候選診斷。這兩部分求解復(fù)雜度都是指數(shù)級(jí)的，因此模型診斷的計(jì)算

41、復(fù)雜性相當(dāng)高。為避免對(duì)沖突集及其碰集的求解，許多學(xué)者基于一致性的診斷思想，給出了結(jié)合BDD、SAT、因果關(guān)系等完備診斷擴(kuò)展方法。</p><p>　　4.1.3.1 結(jié)合BDD的診斷方法</p><p>　　基于模型的不一致診斷方法是完備的，其診斷中的狀態(tài)空間的大小與診斷問(wèn)題規(guī)模的大小成指數(shù)關(guān)系。早期診斷方法采用顯式枚舉的方式來(lái)表示狀態(tài)空間，處理規(guī)模只能達(dá)到幾百萬(wàn)狀態(tài)的規(guī)模。為克服內(nèi)存空間

42、爆炸問(wèn)題，許多學(xué)者研究狀態(tài)空間的緊致隱含表示方法。1986年，Bryant提出了用二叉決策圖[95]（Binary Decision Diagram,BDD）把布爾函數(shù)表示成正則壓縮圖的方法，用BDD的運(yùn)算來(lái)表達(dá)狀態(tài)轉(zhuǎn)移關(guān)系。</p><p>　　基于BDD[96, 97] 的一致診斷方法主要通過(guò)對(duì)集成電路中潛在的錯(cuò)誤區(qū)域使用信號(hào)再綜合方法進(jìn)行診斷。如果綜合后的輸出行為一致，則當(dāng)前被診斷區(qū)域?yàn)殄e(cuò)誤區(qū)域；如果綜合后

43、的輸出行為不一致，則要繼續(xù)對(duì)集成電路中其它潛在區(qū)域進(jìn)行診斷，直至得到錯(cuò)誤區(qū)域結(jié)束。與基于模擬的方法相比，基于BDD的方法不需要使用錯(cuò)誤模型和測(cè)試向量，并且診斷解更準(zhǔn)確，容易擴(kuò)展到包含多錯(cuò)誤的情形。</p><p>　　然而，由于BDD本身信息表達(dá)能力的限制，在處理大規(guī)模集成電路時(shí)經(jīng)常導(dǎo)致內(nèi)存爆炸，因此很難應(yīng)用到大規(guī)模問(wèn)題的處理上。</p><p>　　4.1.3.2 結(jié)合SAT的診斷方法&

44、lt;/p><p>　　近年來(lái)，布爾可滿足性(Satisfiability, SAT)的研究取得了重要進(jìn)展，SAT 已經(jīng)成為解決諸多集成電路中一系列問(wèn)題的有力工具。目前學(xué)術(shù)和工業(yè)界的主流研究是采用主析取范式(Conjunctive Normal Formula, CNF)來(lái)描述集成電路系統(tǒng)，使用SAT求解器進(jìn)行不一致診斷推理。2011年第一屆SAT/SMT暑期學(xué)校在MIT舉行，Princeton University

45、教授Sharad Malik[7]作了基于SAT的設(shè)計(jì)錯(cuò)誤診斷方法的特邀報(bào)告。2012年第二屆SAT/SMT暑期學(xué)校在Trento University舉行，Stanford Research Institute研究員Bruno Dutertre[9]作了基于可滿足性模理論（Satisfiability Modulo Theories，SMT）的診斷方法的特邀報(bào)告。</p><p>　　Smith等[12]指出，

46、集成電路故障診斷與設(shè)計(jì)錯(cuò)誤診斷方法具有通用性，并將電路診斷任務(wù)轉(zhuǎn)換成SAT問(wèn)題，使用SAT求解器進(jìn)行多故障診斷。Jain等[98]提出使用 SAT 來(lái)提高設(shè)計(jì)錯(cuò)誤診斷的準(zhǔn)確性，通過(guò)一定的假設(shè)和對(duì)未知約束的建模對(duì)候選錯(cuò)誤源進(jìn)行篩選。Wotawa等[99-101]在MBD基礎(chǔ)上，給出了診斷設(shè)計(jì)錯(cuò)誤的系列方法。Suelflow等[18]借鑒MBD方法，利用不可滿足核進(jìn)行設(shè)計(jì)錯(cuò)誤診斷。Chen等[10]將設(shè)計(jì)錯(cuò)誤問(wèn)題形式化表示為MaxSAT問(wèn)題

47、，結(jié)合電路中時(shí)間空間信息對(duì)MaxSAT求解進(jìn)行優(yōu)化，進(jìn)一步提升了問(wèn)題的求解規(guī)模和效率。</p><p>　　國(guó)內(nèi)，張健等[102]給出了將診斷空間轉(zhuǎn)換為布爾公式和數(shù)學(xué)公式混合的中間形式，然后用標(biāo)志子句技術(shù)的求解器進(jìn)行診斷；陳榮等[103]提出了基于邏輯相容性診斷方法，先通過(guò)SAT求解得到系統(tǒng)對(duì)應(yīng)的沖突部件集，然后由沖突部件集獲取候選診斷。歐陽(yáng)丹彤等[58, 104]給出了結(jié)合SAT增量求解不一致診斷問(wèn)題，一次求解

48、一系列相似的不一致診斷問(wèn)題，不用對(duì)每一個(gè)子問(wèn)題分別求解，有效利用求解過(guò)程中信息。</p><p>　　4.1.3.3 基于拓?fù)潢P(guān)系的診斷方法</p><p>　　結(jié)合BDD和SAT的診斷方法，需要對(duì)元件的功能知識(shí)建模，且診斷復(fù)雜度較高。許多學(xué)者從元件拓?fù)潢P(guān)系角度出發(fā)，給出了不必對(duì)元件功能建模的系列擴(kuò)展一致性診斷方法。</p><p>　　張學(xué)農(nóng)等[105]給出了基于

49、值傳遞的診斷方法。在保證系統(tǒng)一致性的前提下， 盡可能假設(shè)系統(tǒng)元件正常，并根據(jù)系統(tǒng)當(dāng)前的輸入輸出進(jìn)行值傳遞推理。對(duì)于未進(jìn)行值傳遞推理的元件，如果通過(guò)推理確定元件的輸入輸出值與其正常行為描述不一致，則得到該元件故障元件。在此基礎(chǔ)上還給出了含故障模式的值傳遞診斷方法[106]，在值傳遞系統(tǒng)模型中加入描述系統(tǒng)元件的多種故障模式，并討論了得到的診斷結(jié)果與一致性診斷和溯因診斷之間的關(guān)系。</p><p>　　歐陽(yáng)丹彤等[10

50、7]學(xué)者給出了結(jié)合標(biāo)志傳播的診斷方法，此方法通過(guò)在系統(tǒng)中傳播輸出標(biāo)志，來(lái)判斷元件集合是否為系統(tǒng)的診斷，避免了求解是否為診斷時(shí)引起的NP-完全問(wèn)題；在此基礎(chǔ)上還給出一種基于因果關(guān)系求解所有極小診斷的新方法[52]，從而可直接求出所有的極小診斷，提高了診斷效率，并且不會(huì)丟失正確的解。還根據(jù)因果關(guān)系的思想提出了極小診斷組成原理和極小診斷元件個(gè)數(shù)原理，避免了非極小診斷的產(chǎn)生。</p><p>　　4.1.3.4 結(jié)合結(jié)構(gòu)

51、信息的診斷優(yōu)化方法</p><p>　　模型診斷中的模型形式化過(guò)程中，問(wèn)題的內(nèi)部結(jié)構(gòu)信息被丟棄。而在診斷求解過(guò)程中，內(nèi)部信號(hào)間的結(jié)構(gòu)信息對(duì)求解效率有較大影響，對(duì)此，研究人員對(duì)結(jié)合結(jié)構(gòu)信息的診斷方法進(jìn)行了研究。</p><p>　　歐陽(yáng)丹彤等[79]通過(guò)對(duì)模型結(jié)構(gòu)信息的研究，引入與結(jié)構(gòu)相關(guān)的定義信息和表示伴隨關(guān)系的信息，進(jìn)而可以減少候選診斷的數(shù)量；Fattach[108]和Wotawa [1

52、09]對(duì)模型的結(jié)構(gòu)進(jìn)行了分類，給出了樹型結(jié)構(gòu)系統(tǒng)的診斷方法；欒尚敏等[61]也給出了結(jié)合構(gòu)信息的基于模型的故障診斷方法；Marquis[110]和Haenni[111]通過(guò)計(jì)算模型信息得到結(jié)論，進(jìn)而求得系統(tǒng)診斷；李占山[112]等通過(guò)對(duì)模型結(jié)構(gòu)的研究，對(duì)診斷問(wèn)題進(jìn)行分解，并給出了分解的診斷算法；Viswanadham等[113]也將判定樹方法應(yīng)用于實(shí)際的診斷系統(tǒng)中。</p><p>　　在結(jié)合SAT是求解MBD方

53、法中，研究人員開始研究結(jié)合結(jié)構(gòu)特征提高診斷效率。DeOrio等[15]提出了將元件設(shè)計(jì)時(shí)學(xué)習(xí)的信息用于元件的故障診斷方法。Abdel-Khalek等[14]從有效利用觀測(cè)信息的角度，給出了在有限觀測(cè)下更高效的診斷方法。Ganai等[6]利用電路中元件輸出信號(hào)相關(guān)信息改進(jìn)了SAT求解器性能；Lu等[114]提出一種基于電路的SAT求解器，利用信號(hào)拓?fù)渑判蚝托盘?hào)間關(guān)系為SAT搜索過(guò)程提供有效的決策變量排序機(jī)制，從而使SAT求解效率得到一定程

54、度的提高。Mangassarian等[115]在基于SAT方法的基礎(chǔ)上給出利用統(tǒng)治關(guān)系進(jìn)行蘊(yùn)涵求解和反統(tǒng)治關(guān)系進(jìn)行蘊(yùn)涵求非解的方法，此方法在不影響診斷解完備情況下減少了SAT求解時(shí)的迭代次數(shù)。Chen等[11]給出了利用MaxSAT進(jìn)行診斷的方法，并在得到診斷解后，結(jié)合結(jié)構(gòu)特征計(jì)算相鄰診斷解。</p><p>　　Smith等[12]根據(jù)電路中元件間的統(tǒng)治關(guān)系，給出了求解診斷解的啟發(fā)式策略。Keng[13]和De

55、hbashi[17]根據(jù)診斷過(guò)程中產(chǎn)生的反例路徑，進(jìn)一步對(duì)診斷空間進(jìn)行約束，給出了提升診斷效率和準(zhǔn)確度的方法。Sharad Malik等[8]給出了結(jié)合MaxSAT和Backbone的診斷方法，利用MaxSAT計(jì)算可能發(fā)生的故障，基于Backbone的思想傳播信息，進(jìn)而減小問(wèn)題的求解規(guī)模。</p><p>　　4.2 離散事件系統(tǒng)診斷</p><p>　　由于現(xiàn)實(shí)中的系統(tǒng)往往是動(dòng)態(tài)運(yùn)行的，

56、自20世紀(jì)90年代，許多學(xué)者開展了動(dòng)態(tài)系統(tǒng)的基于模型診斷研究。Console和Dressler指出，動(dòng)態(tài)系統(tǒng)是對(duì)模型化特別是定性模型化以及推理機(jī)制的挑戰(zhàn)，動(dòng)態(tài)系統(tǒng)的診斷至今仍是基于模型診斷有待解決的問(wèn)題之一。而特別是最近幾年，離散事件動(dòng)態(tài)系統(tǒng)基于模型的故障診斷，受到越來(lái)越多學(xué)者的關(guān)注，在AIJ, JAIR, IJCAI, AAAI, ECAI等人工智能國(guó)際權(quán)威頂級(jí)雜志及會(huì)議上發(fā)表了許多離散事件系統(tǒng)基于模型診斷的論文。另外，歐美一些國(guó)家也

57、從九十年代初期開始每年舉行一次診斷原理會(huì)議 (DX)。</p><p>　　離散事件系統(tǒng)的基于模型診斷問(wèn)題主要包括建模與表示、離線的可診斷性判定以及在線的診斷。</p><p>　　4.2.1 建模與表示</p><p>　　建模主要是將待診斷的物理系統(tǒng)抽象為計(jì)算機(jī)能夠識(shí)別的符號(hào)化模型系統(tǒng)，是所有可診斷性方法及診斷方法的基礎(chǔ)。離散事件系統(tǒng)能夠描述同時(shí)具有動(dòng)態(tài)和靜態(tài)特

58、性的物理系統(tǒng)，并且能夠在某種抽象層次上描述連續(xù)系統(tǒng)。離散事件系統(tǒng)的表示方法主要有自動(dòng)機(jī)[5, 19, 20]、Petri網(wǎng)[116, 117]、進(jìn)程代數(shù)[118, 119]、貝葉斯網(wǎng)[120]等。 </p><p>　　由于物理系統(tǒng)特性的不同，建模的類型及其診斷方法具有多樣性。根據(jù)物理系統(tǒng)的特性，離散事件系統(tǒng)可以被分為一般離散事件系統(tǒng)[5]、模糊離散事件系統(tǒng)[121]、隨機(jī)離散事件系統(tǒng)等[122]；根據(jù)模型之

59、間的從屬關(guān)系[20]，離散事件系統(tǒng)可以被分為全局系統(tǒng)[19, 20]、分布式系統(tǒng)[123, 124]、分層系統(tǒng)[33, 125]以及分散式系統(tǒng)[26, 126]等；而按照物理系統(tǒng)到模型系統(tǒng)的對(duì)應(yīng)完備程度，可以分為完備系統(tǒng)[19, 20]和不完備系統(tǒng)[57]。 </p><p>　　4.2.1.1 基本模型</p><p>　　起初，離散事件系統(tǒng)模型用全局的基本模型表示[5]，如圖2所示。其

60、僅包括系統(tǒng)運(yùn)行的最基本要素：狀態(tài)、事件、狀態(tài)與事件之間的轉(zhuǎn)移關(guān)系以及初始狀態(tài)、終止?fàn)顟B(tài)。在基本模型中不包含其它各種系統(tǒng)特性。</p><p>　　圖2 離散事件系統(tǒng)模型</p><p>　　通常情況下，診斷方法起初建立在基本模型上，但是隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，行為的不斷復(fù)雜，特性的不斷增加，衍生出針對(duì)各種附加條件的建模方法。如在建模過(guò)程中，增加對(duì)一些特性的描述，或?qū)灸Ｐ瓦M(jìn)行分解以適應(yīng)

61、實(shí)際的診斷問(wèn)題。 </p><p>　　4.2.1.2 不完備模型</p><p>　　對(duì)于一個(gè)具有復(fù)雜行為并且處于復(fù)雜環(huán)境中的系統(tǒng)來(lái)說(shuō)，考慮全部可能發(fā)生的行為、預(yù)計(jì)所有可能的環(huán)境變化，并將其建模是不現(xiàn)實(shí)的。因此，使用不完備模型對(duì)這種復(fù)雜行為、復(fù)雜環(huán)境下的系統(tǒng)進(jìn)行描述。</p><p>　　Console等人提出了因果不完備模型中的診斷理論[76]，結(jié)合部件之

62、間的輸入輸出建立部件之間的因果關(guān)系，并結(jié)合非單調(diào)推理方法給出不完備模型下的診斷。趙相福等[57]提出了完備度概念，描述了未知行為與已知行為之間的比例，定量地描述了不完備系統(tǒng)的完備程度；給出了不完備同步積的概念，從行為不完備的角度給出了不完備模型的診斷方法，根據(jù)同步積的結(jié)果提取不完備模型的診斷路徑，討論了不同完備度對(duì)候選診斷路徑規(guī)模的影響。Kwong等[127]在文獻(xiàn)[57] 工作的基礎(chǔ)上討論不同完備度下候選診斷路徑的同步提取方法，提出了

63、得到不完備行為的方法，進(jìn)而擴(kuò)展不完備模型，并將未定義的不完備行為加入到不完備模型。Mayer等 [128]在文獻(xiàn)[57]工作基礎(chǔ)上，提出了不完備模型的診斷、模型改進(jìn)和故障修復(fù)方法。給出一種在去除完備模型假設(shè)后得到診斷結(jié)果的方法，并給出了對(duì)故障進(jìn)行修復(fù)的方法。歐陽(yáng)丹彤等[55]將不完備模型分為定義不完備和因果不完備。針對(duì)定義不完備，用在線觀測(cè)與模型共同約束的方法處理亂序觀測(cè)及未定義事件，得到可行的診斷軌跡。對(duì)因果關(guān)系不完備，給出利用因果圖

64、和部件關(guān)系解決分布式診斷中由于部件獨(dú)立建模而導(dǎo)致的</p><p>　　4.2.1.3 分布式模型</p><p>　　分布式模型由多個(gè)相對(duì)獨(dú)立的子模型構(gòu)成，應(yīng)用于大型多組件且組件間具有通訊行為的系統(tǒng)建模。組件被建模成狀態(tài)、事件集合獨(dú)立的子模型，子模型之間僅依賴通訊事件交互局部信息，不受其他子模型的控制和影響，且不存在全局統(tǒng)一的控制器。</p><p>　　Seng

65、upta [129]首先提出診斷的分布式模型，證明分布式模型上可診斷性的獨(dú)立性及傳遞性，并應(yīng)用到無(wú)線局域網(wǎng)的診斷問(wèn)題。</p><p>　　分布式模型也可以由全局模型分解[21]得到，當(dāng)全局模型過(guò)于龐大時(shí)，將關(guān)聯(lián)相對(duì)緊密的部件集合抽象為一個(gè)子模型，獨(dú)立于其他關(guān)聯(lián)松散的子模型，從而將全局模型分解為一組可以獨(dú)立決策的子模型。這組子模型是該全局模型的分布式模型。分布式模型的優(yōu)點(diǎn)在于子模型獨(dú)立決策，時(shí)間復(fù)雜度和空間復(fù)雜度

66、降低。但是由于子模型之間存在著相互關(guān)聯(lián)的行為，全局模型的分解可能忽略這些關(guān)聯(lián)行為，可能導(dǎo)致子模型信息的缺失。Pencolé等[130]在文獻(xiàn)[129]工作的基礎(chǔ)上提出了分布式模型中的同步方法，當(dāng)局部模型不能滿足診斷需要時(shí)，通過(guò)同步解決兩個(gè)子系統(tǒng)之間的協(xié)作。同步的兩個(gè)子模型可以互相控制彼此的行為，從而彌補(bǔ)全局模型分解造成的信息缺失。</p><p>　　Ribot等[131]分析等了分布式模型可診斷性的計(jì)

67、算和通訊成本，給出分布式模型中的通訊選擇方法，使通訊成本及可診斷性計(jì)算成本降低。</p><p>　　4.2.1.4 分散式模型</p><p>　　分散式模型是由全局模型分解后一些小規(guī)模子模型組成，每個(gè)子模型是獨(dú)立的，相互無(wú)通訊。并在全局上建立一個(gè)協(xié)調(diào)器，與各子模型通訊。</p><p>　　分散式模型最早是由Debou等[132]提出，模型中主要包括分散工作站、

68、中央?yún)f(xié)調(diào)器。觀測(cè)到的事件由分散的工作站進(jìn)行收集，隨后根據(jù)協(xié)議傳回到中央?yún)f(xié)調(diào)器并進(jìn)行處理，最后得到全局的診斷。</p><p>　　Pencolé等[126]提出的分散式模型將模型定義為多個(gè)獨(dú)立的子模型，每個(gè)子模型獨(dú)立進(jìn)行診斷。但是與文獻(xiàn)[132]不同的是，系統(tǒng)中沒(méi)有中央?yún)f(xié)調(diào)器，而是通過(guò)建立在子模型上的獨(dú)立控制器進(jìn)行診斷，觀測(cè)到的事件由分散的診斷器處理，得到局部診斷結(jié)果。該方法被應(yīng)用于通訊網(wǎng)絡(luò)上診斷問(wèn)題上

69、。</p><p>　　分散式模型中子模型之間不具有相互傳遞消息的功能，而是由局部診斷器或中央控制器進(jìn)行診斷工作。分散式模型的診斷方法與全局診斷方法相同，由于在分散式模型的診斷方法較小范圍內(nèi)進(jìn)行診斷，因此效率較高。但是存在的問(wèn)題是，當(dāng)局部模型不可診斷時(shí)，無(wú)論由中央控制器進(jìn)行處理，還是通過(guò)組合子模型的方法進(jìn)行處理，均會(huì)產(chǎn)生組合爆炸問(wèn)題。</p><p>　　4.2.1.5 分層模型</

70、p><p>　　分層模型對(duì)同一系統(tǒng)依據(jù)不同的抽象層次，以分層的形式進(jìn)行抽象描述。分層模型主要是基于對(duì)系統(tǒng)的部分組成部件的抽象表示來(lái)縮減系統(tǒng)的規(guī)模。該方法可以看作首先考慮系統(tǒng)整體，但此時(shí)的整體已經(jīng)是一個(gè)抽象的系統(tǒng)：其中的許多部件已經(jīng)被抽象為某個(gè)大的部件，因而整體系統(tǒng)由更少的抽象部件構(gòu)成，從而降低空間復(fù)雜度(當(dāng)然診斷推理時(shí)間復(fù)雜度也會(huì)相應(yīng)降低)。當(dāng)檢測(cè)到某一抽象部件反常而其余部分正常時(shí)，下一步的工作則僅僅考慮反常的抽象部

71、件即可而不必考慮全局的系統(tǒng)。當(dāng)然此時(shí)需要將該抽象部件進(jìn)一步細(xì)化以便求得更為精細(xì)的診斷結(jié)果。</p><p>　　Pencolé等[130]提出一種擴(kuò)展的診斷器方法，將通訊網(wǎng)絡(luò)的每一個(gè)物理結(jié)構(gòu)分支作為一個(gè)分層的層次；顯然，該方法強(qiáng)烈依賴于網(wǎng)絡(luò)的結(jié)構(gòu)特征。Su等[40]提出一種形式化的分層診斷方法，但缺乏具體可操作性。此外，Schullerus等[133]提出基于時(shí)間自動(dòng)機(jī)的分層診斷方法，其中每一較高的分層

72、層次都為一個(gè)時(shí)間自動(dòng)機(jī)，顯然，這種方法需要帶時(shí)間的系統(tǒng)模型，而時(shí)間信息可能會(huì)引起新的復(fù)雜性。Idghamishi等[134, 135]從控制工程領(lǐng)域的角度提出一種基于所謂“D-holon”概念的分層方法，其中每一層為一個(gè)D-holon，但沒(méi)有給出如何劃分產(chǎn)生好的D-holons 的方法。趙相福等[125]結(jié)合Lamperti 等人提出的“Silent Closure”概念，給出了一種如何分解系統(tǒng)的模型以產(chǎn)生好的D-holons的方法。&

73、lt;/p><p>　　4.2.2 可診斷性</p><p>　　可診斷性是判定離散事件系統(tǒng)的模型是否可診斷。模型可診斷能夠保證目標(biāo)系統(tǒng)在有效時(shí)間內(nèi)得到唯一且正確的診斷結(jié)果。</p><p>　　4.2.2.1 可診斷性判定方法</p><p>　　Lin等[136]首次討論了離散事件系統(tǒng)的可診斷性，并將可診斷性作為診斷問(wèn)題的基礎(chǔ)引入到離散事件系

74、統(tǒng)的診斷中。隨后Sampath等 [19, 20]給出利用診斷器的可診斷性判定方法。將診斷系統(tǒng)的有限狀態(tài)自動(dòng)機(jī)按照觀測(cè)事件編譯為一個(gè)診斷器，得到在每一個(gè)可觀測(cè)事件發(fā)生后系統(tǒng)當(dāng)前可能的狀態(tài)，并且用故障標(biāo)簽記錄之前已經(jīng)發(fā)生的全部故障事件，通過(guò)判斷診斷器中是否存在模糊環(huán)路及標(biāo)簽沖突來(lái)得到可診斷性結(jié)論。而且，診斷器在離線得到可診斷性結(jié)果時(shí)，還能夠根據(jù)在線觀測(cè)進(jìn)行診斷。該方法奠定了離散事件系統(tǒng)的可診斷性及診斷基礎(chǔ)，是經(jīng)典的可診斷性判定方法之一。&

75、lt;/p><p>　　上述可診斷性判定方法在時(shí)間復(fù)雜度上是雙指數(shù)級(jí)的，應(yīng)用于復(fù)雜行為系統(tǒng)時(shí)效率較低。因此，許多專家學(xué)者對(duì)其進(jìn)行了深入研究。Jiang等[137]在診斷器的基礎(chǔ)上，改進(jìn)了編譯方法，建立“雙模型”來(lái)判斷可診斷性。定義了“自同步”操作構(gòu)建診斷器，在自同步得到的同步積結(jié)果上，判斷模糊狀態(tài)及環(huán)路、計(jì)算故障標(biāo)簽沖突，得到可診斷性的結(jié)果。該方法時(shí)間復(fù)雜度是多項(xiàng)式級(jí)的，但是當(dāng)故障精確分類時(shí)，仍為指數(shù)級(jí)復(fù)雜度。Yoo

76、等[138]提出了對(duì)基于“雙模型”可診斷性判定方法的驗(yàn)證方法。Grastien等 [139]在基于“雙模型”方法上進(jìn)行了改進(jìn)，通過(guò)記錄每一個(gè)分支結(jié)構(gòu)，給出可觀測(cè)序列及對(duì)應(yīng)的故障集合來(lái)判定可診斷性。</p><p>　　與前述可診斷性方法不同，模式可診斷性[27]判斷的不是“事件”，而是“模式”，即判斷模型中的某一特定行為結(jié)構(gòu)是否能夠被診斷出來(lái)。目前模式可診斷性主要判定單故障、多故障，間歇性故障、重復(fù)故障以及故障修

77、復(fù)等模式。</p><p>　　模式可診斷判定方法首先在系統(tǒng)模型基礎(chǔ)上建立可觀測(cè)的“預(yù)診斷器”，并根據(jù)系統(tǒng)可能發(fā)生的故障選擇模式，最后通過(guò)“預(yù)診斷器”與模式的同步，得到系統(tǒng)的模式可診斷性。模式可診斷性的優(yōu)點(diǎn)在于主要處理觀測(cè)和故障事件，進(jìn)而簡(jiǎn)化系統(tǒng)模型。</p><p>　　4.2.2.2 分布式系統(tǒng)的可診斷性</p><p>　　Pencolé等[131]

78、討論了分布式離散事件系統(tǒng)的可診斷性，遵循可診斷性判定過(guò)程，得到局部的可診斷性，該可診斷性的結(jié)果僅被限制在子系統(tǒng)中，與其他子系統(tǒng)無(wú)關(guān)。當(dāng)子系統(tǒng)不可診斷時(shí)，對(duì)共享通訊事件的子系統(tǒng)進(jìn)行同步，在同步的結(jié)果上進(jìn)一步判定可診斷性。由于這種可診斷性需要更多的信息才能夠被判定，因此弱于局部的可診斷性。</p><p>　　[140]討論了分布式離散事件系統(tǒng)的模式可診斷性。在分布式系統(tǒng)上，進(jìn)行模式可診斷性的判定。在子系統(tǒng)上的判定方

79、法與全局判定方法相同，根據(jù)模式與“預(yù)診斷器”的同步，判定模式可診斷性。而當(dāng)子系統(tǒng)是模式不可診斷時(shí)，通過(guò)同步進(jìn)行模型的擴(kuò)展，得到較弱的可診斷性。</p><p>　　Qiu等[141]提出在分布式模型上通過(guò)雙模型判定可診斷性的方法。在子系統(tǒng)上建立局部雙樹，搜索是否存在著模糊環(huán)路及故障標(biāo)簽沖突，得到局部的可診斷性。而一旦子系統(tǒng)不可診斷，同樣通過(guò)同步來(lái)做進(jìn)一步可診斷性的判定。</p><p>　

80、　4.2.2.3 分散式系統(tǒng)的可診斷性</p><p>　　分散式系統(tǒng)的可診斷性主要分為[132]獨(dú)立可診斷、分散可診斷和集中可診斷。獨(dú)立可診斷是指每個(gè)工作站點(diǎn)都可以僅根據(jù)局部的觀測(cè)判定可診斷性。分散可診斷是指通過(guò)通訊遠(yuǎn)程傳輸局部觀測(cè)進(jìn)而判定可診斷性。集中可診斷是指通過(guò)中央診斷器處理所有局部觀測(cè)來(lái)得到可診斷性。</p><p>　　Qiu等[141]提出分散式系統(tǒng)中共可診斷性的判定方法，通

81、過(guò)同步自動(dòng)機(jī)判定系統(tǒng)中的每個(gè)故障是否可以被至少一個(gè)工作站點(diǎn)精確地診斷得出。被同步的三個(gè)自動(dòng)機(jī)分別為用來(lái)描述系統(tǒng)的所有行為的全局自動(dòng)機(jī)、用來(lái)描述系統(tǒng)中所有的正常行為的規(guī)范自動(dòng)機(jī)和通過(guò)向規(guī)范自動(dòng)機(jī)中添加額外的故障狀態(tài)和事件得到的擴(kuò)展規(guī)范自動(dòng)機(jī)。</p><p>　　Wang等[142]中提出驗(yàn)證共可診斷性的方法，通過(guò)同步兩類添加相應(yīng)故障標(biāo)簽后的全局自動(dòng)機(jī)進(jìn)行驗(yàn)證。其中一類自動(dòng)機(jī)描述系統(tǒng)中所有可能的行為，另一類自動(dòng)機(jī)描

82、述各個(gè)工作站點(diǎn)在相應(yīng)事件發(fā)生后的狀態(tài)。最近，該研究小組還在此方法基礎(chǔ)上，給出在動(dòng)態(tài)觀測(cè)下的共可診斷性判定方法[143]。</p><p>　　在文獻(xiàn)[142]工作基礎(chǔ)上，Moreira等 [144]提出了改進(jìn)的驗(yàn)證共可診斷性方法，在分散式模型中，通過(guò)對(duì)模型的化簡(jiǎn)提高分散式系統(tǒng)的可診斷性驗(yàn)證效率，該方法既可以應(yīng)用于分散式系統(tǒng)的聯(lián)合可診斷性，也可以用于全局可診斷性的驗(yàn)證。同時(shí)，該方法取消了對(duì)模型無(wú)不可觀測(cè)環(huán)和無(wú)限語(yǔ)言

83、的假設(shè)。 </p><p>　　4.2.2.4 基于可診斷性的模型重構(gòu)</p><p>　　基于可診斷性的模型重構(gòu)是通過(guò)對(duì)已有模型的分解和同步，從而提高可診斷性判定的效率或解決局部不可診斷問(wèn)題。</p><p>　　可診斷性模型重構(gòu)中模型分解是將全局模型根據(jù)模型結(jié)構(gòu)對(duì)事件集合進(jìn)行劃分，根據(jù)劃分后的事件子集將全局模型分解為適當(dāng)規(guī)模的子模型。同時(shí)根據(jù)子模型之間的聯(lián)系添加

84、通訊事件，作為子模型不可診斷時(shí)同步的依據(jù)。</p><p>　　可診斷性模型重構(gòu)中模型同步是在子模型不可診斷時(shí)，通過(guò)通訊事件同步兩個(gè)或多個(gè)子模型，得到較大模型的過(guò)程。同步操作通常根據(jù)通訊事件進(jìn)行兩個(gè)子系統(tǒng)狀態(tài)的同時(shí)轉(zhuǎn)移，而獨(dú)立部分的狀態(tài)獨(dú)立進(jìn)行轉(zhuǎn)移。由于子模型中通訊事件的關(guān)聯(lián)，使得同步后的模型行為更加完整，從而得到更精確的可診斷性結(jié)果。同步計(jì)算的復(fù)雜度隨著子模型的增加而呈指數(shù)級(jí)增加。在最壞情況下，子模型同步后的可

85、診斷性判定復(fù)雜度等同于全局模型下可診斷性判定復(fù)雜度。</p><p>　　許多學(xué)者對(duì)基于可診斷性的模型分解和同步的方法進(jìn)行了研究，Geng等[145]將一個(gè)全局模型分解為多個(gè)具有通訊事件的分布式子模型，并且驗(yàn)證子模型的可診斷性。在子模型不可診斷時(shí)，通過(guò)重新劃分模型，對(duì)可診斷性模型進(jìn)行重構(gòu)。Wan等[146]提出分布式模型中的同步優(yōu)化方法，在子模型不可診斷時(shí)，通過(guò)選擇計(jì)算和通訊成本最低的同步，來(lái)解決子模型局部不可診

86、斷問(wèn)題。</p><p>　　4.2.3 診斷方法</p><p>　　診斷方法是在離線建立的可診斷的模型中，根據(jù)在線觀測(cè)序列計(jì)算當(dāng)前系統(tǒng)是否存在故障的過(guò)程。離散事件系統(tǒng)診斷能夠在系統(tǒng)運(yùn)行的過(guò)程中進(jìn)行診斷，不需要系統(tǒng)停機(jī)，因此具有較高的診斷效率和應(yīng)用價(jià)值。并且，離散事件系統(tǒng)診斷結(jié)果得到的不僅是系統(tǒng)故障，還將給出系統(tǒng)故障行為的路徑，因此提供了更多的診斷信息。</p><p

87、>　　4.2.3.1 基本診斷方法</p><p>　　離散事件系統(tǒng)基于模型診斷主要包括診斷器、同步和搜索診斷方法。</p><p>　　基于診斷器方法[19]首先構(gòu)建帶有故障標(biāo)簽的自動(dòng)機(jī)，通過(guò)可觀測(cè)事件觸發(fā)自動(dòng)機(jī)的狀態(tài)進(jìn)而得到狀態(tài)序列，即系統(tǒng)實(shí)際的運(yùn)行過(guò)程。若系統(tǒng)可診斷，則在有限觀測(cè)序列之后系統(tǒng)將停止在某狀態(tài)，由該狀態(tài)的故障標(biāo)簽即可得到系統(tǒng)是否存在故障及相應(yīng)的具體故障。此方法的診斷

88、效率較高，若系統(tǒng)可診斷且在線觀測(cè)序列足夠長(zhǎng)，則可以在線性時(shí)間內(nèi)得到診斷結(jié)果。但由于構(gòu)建診斷器需指數(shù)級(jí)的時(shí)間和空間復(fù)雜度，不適合具有復(fù)雜行為的系統(tǒng)。</p><p>　　同步診斷方法[137]只構(gòu)建離線的系統(tǒng)模型，并將在線得到的觀測(cè)自動(dòng)機(jī)與離線模型進(jìn)行同步，進(jìn)而得到系統(tǒng)的全部候選診斷路徑。該方法可以處理系統(tǒng)中的時(shí)序不確定的觀測(cè)序列，但當(dāng)模型中的觀測(cè)重復(fù)較多時(shí)，候選診斷路徑數(shù)目將呈指數(shù)級(jí)增長(zhǎng)。因此，在基于同步的診斷方

89、法中，確定觀測(cè)時(shí)序是一項(xiàng)較為重要的研究?jī)?nèi)容。</p><p>　　基于搜索的方法由Lamperti 等[29]提出，通過(guò)在離線模型中搜索與觀測(cè)序列一致的路徑來(lái)得到診斷。該方法僅依賴系統(tǒng)模型和觀測(cè)序列，所需存儲(chǔ)空間相對(duì)較小。但當(dāng)模型中有效觀測(cè)事件不足時(shí)，得到的候選診斷路徑較多。</p><p>　　按照每次診斷產(chǎn)生所考慮的觀測(cè)信息，可將診斷方法分為后驗(yàn)診斷和增量診斷，其中后驗(yàn)診斷每次結(jié)果的產(chǎn)

90、生都需要考慮到當(dāng)前所有觀測(cè)序列及系統(tǒng)的整個(gè)模型。而增量診斷只需考慮前一次的診斷結(jié)果及新獲得的觀測(cè)序列[23, 24]。</p><p>　　按照每次診斷所考慮對(duì)象的角度，診斷方法又可以分為集中式、分散式、分布式及分層診斷。若每次診斷都要對(duì)整個(gè)系統(tǒng)進(jìn)行建模和診斷，則稱為集中式診斷方法。分散式診斷方法將全局模型按照某種方式分解為一些小規(guī)模的子模型，引入一個(gè)協(xié)調(diào)器協(xié)調(diào)各局部子模型，分別考慮各自的觀測(cè)序列進(jìn)而得到各自的局

91、部診斷結(jié)果。與分散式診斷不同的是，分布式診斷方法不需額外引入?yún)f(xié)調(diào)器，而是通過(guò)各子模型之間通訊來(lái)逐步得到最終的全局診斷。分層診斷方法先根據(jù)當(dāng)前層次模型得到可能的故障，然后根據(jù)各抽象層次之間的結(jié)構(gòu)選擇是否向上一層次傳播，進(jìn)而得到不同層次的局部故障或全局故障。</p><p>　　4.2.3.2 增量診斷方法</p><p>　　增量診斷是在已有診斷結(jié)果基礎(chǔ)上根據(jù)后續(xù)觀測(cè)進(jìn)行診斷的方法，避免了每

92、次都從初始狀態(tài)進(jìn)行診斷的冗余搜索，效率較高，但得到的診斷結(jié)果不完備。在窗口單觀測(cè)無(wú)回溯條件下的增量診斷方法，與連續(xù)系統(tǒng)診斷方法相同。</p><p>　　Cordier等 [23]最早給出增量診斷方法，主要根據(jù)在線的增量觀測(cè)與離線的自動(dòng)機(jī)鏈進(jìn)行診斷。首先，在每個(gè)觀測(cè)窗口到達(dá)時(shí)得到一個(gè)觀測(cè)序列。然后，在上次的診斷結(jié)果基礎(chǔ)上，結(jié)合觀測(cè)序列和當(dāng)前的自動(dòng)機(jī)鏈進(jìn)一步診斷。最后，將當(dāng)前觀測(cè)序列對(duì)應(yīng)的診斷結(jié)果與上次診斷結(jié)果合并

93、，得到增量診斷結(jié)果。</p><p>　　在增量診斷中兩個(gè)關(guān)鍵問(wèn)題[36]是觀測(cè)序列順序的正確性和適當(dāng)規(guī)模的自動(dòng)機(jī)鏈。如果觀測(cè)亂序且診斷無(wú)回溯，增量診斷將不斷回溯到初始狀態(tài)重新診斷，最壞情況下增量診斷將退化為全局診斷。自動(dòng)機(jī)鏈的規(guī)模是否適當(dāng)影響診斷效率，適當(dāng)規(guī)模自動(dòng)機(jī)鏈下增量診斷效率將有數(shù)量級(jí)上的提高。</p><p>　　對(duì)于觀測(cè)序列正確性問(wèn)題，趙相福等[57, 59]給出了利用代表觀測(cè)

94、時(shí)序的有向無(wú)環(huán)圖來(lái)保證觀測(cè)正確性的解決方案。首先，根據(jù)觀測(cè)的發(fā)出時(shí)間和到達(dá)時(shí)間，確定觀測(cè)窗口的大小。其次，根據(jù)窗口中觀測(cè)的時(shí)序，判斷窗口是否是一個(gè)合理的時(shí)間窗口，從而獲得合理的時(shí)間窗口的特性。最后，用有向無(wú)環(huán)圖及得到的連續(xù)窗口，得到正確的觀測(cè)序列。</p><p>　　4.2.3.3 不完備模型的診斷方法</p><p>　　不完備模型診斷方法主要有兩種，包括根據(jù)實(shí)際觀測(cè)自動(dòng)機(jī)與模型同步[

95、57]和根據(jù)實(shí)際觀測(cè)在模型中進(jìn)行搜索的方法[55]，兩種方法均由完備模型診斷方法擴(kuò)展而來(lái)。同步的方法在觀測(cè)時(shí)序不準(zhǔn)確時(shí)效率較高，而基于搜索的方法在觀測(cè)時(shí)序較為準(zhǔn)確時(shí)效率較高。</p><p>　　不完備模型下的同步診斷方法通過(guò)不完備同步系統(tǒng)離線建立的完備模型自動(dòng)機(jī)和在線得到的觀測(cè)自動(dòng)機(jī)進(jìn)行診斷。若同步時(shí)出現(xiàn)觀測(cè)與模型不匹配，則產(chǎn)生不完備行為。此時(shí)，將更多的路徑加入到觀測(cè)與模型的同步計(jì)算中，擴(kuò)展包含不完備行為的模型

96、，進(jìn)而提取診斷結(jié)果。在不同的完備度下，同步積的規(guī)模也不同。</p><p>　　基于搜索的診斷方法根據(jù)系統(tǒng)實(shí)際得到的觀測(cè)序列在完備模型中進(jìn)行搜索。若當(dāng)前模型中不能找到與觀測(cè)序列一致的軌跡，則根據(jù)模型中的時(shí)序關(guān)系，逐步對(duì)模型進(jìn)行放松直到與觀測(cè)匹配；若當(dāng)前的觀測(cè)中存在著未定義事件，則表示行為不完備，此時(shí)，將未定義事件根據(jù)與其他觀測(cè)事件的時(shí)序關(guān)系加入到不完備模型中，擴(kuò)展當(dāng)前不完備模型以得到診斷路徑。</p>

97、<p>　　5 發(fā)展趨勢(shì)與展望</p><p>　　（1）雖然現(xiàn)有自動(dòng)機(jī)、進(jìn)程代數(shù)、Petri網(wǎng)等方法可用于離散事件系統(tǒng)建模，但是建模復(fù)雜度較高。因而如何給出更高效的系統(tǒng)建模方法，并更好服務(wù)于診斷是值得進(jìn)一步研究與拓展的方向。</p><p>　　（2）增量診斷方法是一種高效的診斷方法，但由于自動(dòng)機(jī)鏈的定義比較嚴(yán)格，因此如何將全局模型分解為適當(dāng)規(guī)模的自動(dòng)機(jī)鏈，并且滿足在線觀

98、測(cè)窗口與自動(dòng)機(jī)鏈的匹配是一個(gè)值得研究的問(wèn)題；如何將增量診斷方法用于模型構(gòu)建、可診斷性判定等方法，仍有待進(jìn)一步研究。</p><p>　?。?）在待診斷系統(tǒng)規(guī)模較大時(shí)，可診斷性判定也隨之變得復(fù)雜，為了降低可診斷性判定的計(jì)算時(shí)間及空間，如何引入啟發(fā)式策略來(lái)提高可診斷性判定效率。另一方面，在基本保證可診斷性的前提下，如何根據(jù)模型結(jié)構(gòu)知識(shí)將全局模型分解為適當(dāng)規(guī)模的局部可診斷模型。若在分解后分布式模型中存在局部不可診斷，如

99、何同步和重構(gòu)解決局部模型中不可診斷。</p><p>　?。?）如何給出全局、分布式及分散式不完備模型的診斷及可診斷性判定方法，如何解決不完備模型的在線模型重構(gòu)問(wèn)題。</p><p><b>　　6 結(jié)束語(yǔ)</b></p><p>　　MBD方法的研究不僅包括基礎(chǔ)理論，更重要的是相關(guān)診斷工具的研制。MBD方法受到了國(guó)外工業(yè)界的高度重視，從學(xué)術(shù)