王 冬 李景文 馮文全 朱 楠

(北京航空航天大學(xué) 電子信息工程學(xué)院，北京100191)

基于模型故障診斷方法使用系統(tǒng)的結(jié)構(gòu)和行為知識(shí)進(jìn)行診斷，是對(duì)傳統(tǒng)診斷方法的一個(gè)突破.最初的研究主要針對(duì)靜態(tài)系統(tǒng)基于模型的診斷，但現(xiàn)實(shí)中的系統(tǒng)往往是動(dòng)態(tài)運(yùn)行的，因此動(dòng)態(tài)系統(tǒng)基于模型的診斷得到了越來(lái)越多的關(guān)注.動(dòng)態(tài)系統(tǒng)中，輸入/輸出量及元件狀態(tài)隨時(shí)間變化，軌跡空間指數(shù)增長(zhǎng)，對(duì)推理機(jī)制都提出了挑戰(zhàn)［1］.實(shí)際的混合或連續(xù)動(dòng)態(tài)系統(tǒng)經(jīng)過(guò)離散化后可以使用離散事件系統(tǒng)(DES，Discrete-Event System)近似表達(dá)，每個(gè)時(shí)刻DES都可看作是瞬態(tài)的靜態(tài)系統(tǒng)，因此許多針對(duì)動(dòng)態(tài)系統(tǒng)診斷的研究都是基于系統(tǒng)可建模為DES的假設(shè).

DES基于模型診斷的方法主要包括［1］:診斷器和基于狀態(tài)/模擬的方法.診斷器［2］是M.Sam-path等人提出的用于判定動(dòng)態(tài)系統(tǒng)可診斷性的一種方法，用有限狀態(tài)自動(dòng)機(jī)表示對(duì)系統(tǒng)建模，然后根據(jù)該模型構(gòu)建全局診斷器.由于空間復(fù)雜度問(wèn)題，全局診斷器在實(shí)際大規(guī)模系統(tǒng)中一般不可行.為解決該問(wèn)題，文獻(xiàn)［3］提出了分散式診斷方法，基于分治法避免了對(duì)全局模型的計(jì)算.

基于狀態(tài)/模擬的方法通過(guò)檢驗(yàn)狀態(tài)一致性及狀態(tài)轉(zhuǎn)移一致性進(jìn)行診斷，是動(dòng)態(tài)系統(tǒng)診斷中被廣泛使用的一種方法，尤其是針對(duì)同步轉(zhuǎn)移系統(tǒng)［4］.基于狀態(tài)/模擬的方法最主要的問(wèn)題是置信狀態(tài)空間規(guī)模的增長(zhǎng).靜態(tài)系統(tǒng)診斷中狀態(tài)空間與系統(tǒng)元件個(gè)數(shù)是指數(shù)關(guān)系，而動(dòng)態(tài)系統(tǒng)需考慮系統(tǒng)隨時(shí)間的狀態(tài)變化軌跡，因此狀態(tài)空間大小與元件個(gè)數(shù)、時(shí)間是雙指數(shù)關(guān)系.為減小置信狀態(tài)空間，K-Best枚舉方法在每個(gè)時(shí)刻只考慮K個(gè)可能性最大的狀態(tài)［4-5］.當(dāng)系統(tǒng)復(fù)雜龐大或診斷周期長(zhǎng)時(shí)，這類(lèi)改進(jìn)方法的狀態(tài)更新仍是一項(xiàng)巨大工程.

本文提出一種結(jié)合粒子濾波和不確定圖的動(dòng)態(tài)系統(tǒng)診斷方法PF_LUG(Particle Filter＆Labeled Uncertainty Graph)，屬于基于狀態(tài)/模擬的方法.利用粒子在狀態(tài)空間的分布近似其概率，以及用不確定圖標(biāo)簽的反向匹配代替?zhèn)鹘y(tǒng)的正向軌跡枚舉，有效解決了由時(shí)間導(dǎo)致的計(jì)算量增長(zhǎng)問(wèn)題，將時(shí)間對(duì)復(fù)雜度的影響由指數(shù)運(yùn)算降為乘積運(yùn)算.

1 算法描述

粒子濾波(PF，Particle Filter)源于蒙特卡洛思想，通過(guò)從后驗(yàn)概率中抽取的隨機(jī)狀態(tài)粒子來(lái)近似表達(dá)其分布，是一種順序重要性采樣法.粒子濾波用于動(dòng)態(tài)系統(tǒng)診斷已有很多研究［6-7］，但大多數(shù)是針對(duì)用解析方程表示的故障模型.不確定圖［8］是對(duì)傳統(tǒng)規(guī)劃圖的改進(jìn)，增加了標(biāo)簽和轉(zhuǎn)移執(zhí)行結(jié)果層，使二維規(guī)劃圖也能夠描述不確定性.文獻(xiàn)［9-10］將粒子濾波方法用于基于不確定圖的conformant規(guī)劃求解，將不確定圖標(biāo)簽的內(nèi)容修改為包含該節(jié)點(diǎn)狀態(tài)的所有樣本的編號(hào)或名稱(chēng)，使用粒子在狀態(tài)空間的分布來(lái)近似概率，進(jìn)而對(duì)不同規(guī)劃解進(jìn)行評(píng)價(jià).

文獻(xiàn)［9-10］對(duì)conformant規(guī)劃的擴(kuò)展，使之與基于模型診斷有了許多相似之處，如狀態(tài)空間有限、初始狀態(tài)和動(dòng)作效果不確定、解是順序的、目標(biāo)是可實(shí)現(xiàn)的、狀態(tài)轉(zhuǎn)移是瞬時(shí)的等等.不確定圖可以看作是有限狀態(tài)機(jī)的另一種表示方式，其中的命題層、動(dòng)作層和結(jié)果層對(duì)應(yīng)診斷中的狀態(tài)、轉(zhuǎn)移條件和轉(zhuǎn)移結(jié)果.因此診斷中系統(tǒng)狀態(tài)的轉(zhuǎn)移過(guò)程可以使用不確定圖來(lái)描述.

圖1所示為一個(gè)用有限狀態(tài)機(jī)表示的系統(tǒng)，包含p1～p44個(gè)狀態(tài)，狀態(tài)轉(zhuǎn)移具有不確定性.例如初始狀態(tài)為p1且動(dòng)作a1發(fā)生時(shí)，以0.8的概率轉(zhuǎn)移到p3，0.2的概率轉(zhuǎn)移到p4.

圖1 用有限狀態(tài)機(jī)表示的系統(tǒng)

圖2用粒子個(gè)數(shù)為8的不確定圖描述該系統(tǒng).不確定圖按時(shí)間分層，每層又包含狀態(tài)層、動(dòng)作層、結(jié)果層3個(gè)子層(最終時(shí)刻對(duì)應(yīng)的層只有狀態(tài)層).該圖為只包含一個(gè)時(shí)間步長(zhǎng)的簡(jiǎn)化圖.P0和P1分別表示時(shí)刻0和時(shí)刻1系統(tǒng)可能的狀態(tài)，A0為時(shí)刻0可能發(fā)生的動(dòng)作，ε0為動(dòng)作的結(jié)果.標(biāo)簽記錄了處于該位置的粒子，用xi表示，1≤i≤N，N為總的粒子個(gè)數(shù).時(shí)刻0粒子均勻分布在4個(gè)狀態(tài)上，當(dāng)動(dòng)作a1，a2觸發(fā)狀態(tài)轉(zhuǎn)移時(shí)按轉(zhuǎn)移概率采樣粒子.最終P1各狀態(tài)的粒子分布情況反映了初始狀態(tài)及轉(zhuǎn)移的不確定性.

圖2 用粒子個(gè)數(shù)為8的不確定圖表示的系統(tǒng)

本文提出的PF_LUG算法基于上述不確定圖表示方法，并做如下修改:

1)若Ai包含可觀測(cè)動(dòng)作，則從圖中刪除不可能發(fā)生的轉(zhuǎn)移;

2)增加P*i+1層，表示由εi層直接得到的i+1時(shí)刻狀態(tài).進(jìn)行一致性檢驗(yàn)后刪除不滿足的狀態(tài)并對(duì)剩余狀態(tài)重采樣后得到Pi+1層;

算法分為兩個(gè)步驟:正向擴(kuò)展和反向搜索.

1.1 正向擴(kuò)展

按照不確定圖的擴(kuò)展方式進(jìn)行擴(kuò)展.如圖3所示，假設(shè)初始狀態(tài)未知，P0的粒子為均勻分布.A0中實(shí)際發(fā)生動(dòng)作為外部可觀測(cè)事件，假設(shè)a1發(fā)生，a2未發(fā)生.由于狀態(tài)轉(zhuǎn)移的不確定性，粒子被轉(zhuǎn)移到不同狀態(tài)上，形成下一時(shí)刻的分布P*1.進(jìn)行一致性檢驗(yàn)得到p4不滿足一致性，因此刪除該狀態(tài)及相關(guān)粒子，剩余粒子都分布在p3上.重采樣后處于p3的可能性被放大，8個(gè)粒子都分布在該狀態(tài)上.擴(kuò)展過(guò)程進(jìn)入時(shí)刻1.

1.2 反向搜索

標(biāo)簽使軌跡信息包含在粒子中，但由于實(shí)際觀測(cè)量判斷、一致性檢驗(yàn)刪除了部分不可能狀態(tài)，而重采樣造成的粒子更新使相同序號(hào)粒子在不同時(shí)刻所表示的意義改變.因此反向搜索要從同一時(shí)刻內(nèi)和不同時(shí)刻間兩方面分別進(jìn)行，即同一層內(nèi)按粒子序號(hào)搜索，不同層間按狀態(tài)搜索，同時(shí)根據(jù)t+1層的信息刪除t層不可能存在的轉(zhuǎn)移并更新節(jié)點(diǎn)標(biāo)簽.如圖4所示.

例如P2中只有p4滿足一致性，因此P*2中p2對(duì)應(yīng)的粒子x1～x7被刪除，φ0為無(wú)效轉(zhuǎn)移，時(shí)刻1到時(shí)刻2的狀態(tài)從p3轉(zhuǎn)移到p4，即粒子x8的軌跡.最終得到的軌跡有 3 個(gè):{p1，p3，p4}，{p2，p3，p4}，{p3，p3，p4}.

圖3 正向擴(kuò)展示意圖

圖4 反向搜索示意圖

1.3 PF_LUG算法

2 算法復(fù)雜度分析

在正向擴(kuò)展中，每個(gè)時(shí)刻需要遍歷3次狀態(tài)列表，分別進(jìn)行生成下一時(shí)刻可能狀態(tài)、一致性檢查和重采樣.狀態(tài)列表的大小受系統(tǒng)狀態(tài)空間大小mn(m為元件個(gè)數(shù)，n為元件模式個(gè)數(shù))及預(yù)設(shè)粒子個(gè)數(shù)p_num影響.當(dāng)粒子個(gè)數(shù)大于mn時(shí)，最壞情況是每個(gè)狀態(tài)平均分配到一定數(shù)目的粒子，這時(shí)狀態(tài)列表大小等于mn;當(dāng)粒子個(gè)數(shù)小于mn時(shí)，最壞情況是一個(gè)粒子表示一個(gè)狀態(tài)，其余狀態(tài)沒(méi)有粒子，狀態(tài)列表大小等于粒子個(gè)數(shù).因此狀態(tài)列表大小最多等于min(mn，p_num).正向擴(kuò)展的計(jì)算量為 t·3·min(mn，p_num)，t為從初始時(shí)刻init_time到current當(dāng)前時(shí)刻的步數(shù).

在反向搜索中，每個(gè)時(shí)刻遍歷一次狀態(tài)列表，以及各狀態(tài)orig列表中的所有粒子.由于在正向擴(kuò)展一致性檢查后，不能滿足一致性的狀態(tài)已被刪除，因此orig列表中總的粒子個(gè)數(shù)小于等于p_num.最壞情況是正向擴(kuò)展出的所有可能狀態(tài)都滿足一致性，即粒子全部保留.匹配pj需遍歷前一時(shí)刻狀態(tài)列表，計(jì)算量最壞為 min(mn，p_num).因此反向搜索的計(jì)算量為t·p_num·min(mn，p_num).

由此可得算法PF_LUG的復(fù)雜度為

傳統(tǒng)軌跡枚舉方法即馬爾科夫定位的復(fù)雜度為O(mnt).可見(jiàn)，算法PF_LUG有效解決了由時(shí)間導(dǎo)致的計(jì)算量增長(zhǎng)問(wèn)題，使時(shí)間對(duì)復(fù)雜度的影響由指數(shù)運(yùn)算降為乘積運(yùn)算.

3 仿真結(jié)果

對(duì)航天器供電系統(tǒng)中的供電控制單元進(jìn)行了仿真驗(yàn)證.該控制單元對(duì)輸入信號(hào)進(jìn)行直接輸出、熱備份電壓變換和冷備份電壓變換，并在部分輸出支路上用繼電器控制通斷.熱備份電壓轉(zhuǎn)換模塊的兩路電壓輸出通過(guò)一個(gè)選擇器，高電壓輸出;冷備份電壓轉(zhuǎn)換模塊由繼電器控制輸出哪一路電壓，如圖5、圖6所示.圖7為電壓轉(zhuǎn)換單元的有限狀態(tài)機(jī)，表1列出了5種狀態(tài)間所有可能轉(zhuǎn)移及概率.

系統(tǒng)包含9個(gè)元件，平均每個(gè)元件有5種工作模式，則狀態(tài)空間大小約為59，考慮時(shí)間步數(shù)的狀態(tài)空間為59t.仿真分別驗(yàn)證了預(yù)設(shè)參數(shù)(診斷解個(gè)數(shù)及粒子個(gè)數(shù))和時(shí)間步數(shù)對(duì)算法效率的影響.實(shí)驗(yàn)結(jié)果比較了K-Best枚舉方法和PF_LUG的運(yùn)行時(shí)間.其中K-Best枚舉方法利用沖突導(dǎo)向的最優(yōu)最先搜索得到各時(shí)刻的K個(gè)最優(yōu)解，并設(shè)置終止概率，當(dāng)候選狀態(tài)的概率低于該值則終止本次搜索.

圖5 供電控制單元

圖6 DC/DC模塊

圖7 電壓轉(zhuǎn)換單元有限狀態(tài)機(jī)

3.1 預(yù)設(shè)參數(shù)的影響

假設(shè)時(shí)間步數(shù)為4，改變K-Best的枚舉個(gè)數(shù)與PF_LUG中粒子個(gè)數(shù)，實(shí)驗(yàn)結(jié)果如表1所示.

表1 預(yù)設(shè)參數(shù)對(duì)算法性能的影響

40 20034 7000 36 12702

可以看出，K-Best枚舉在K值較小時(shí)速度較快，但隨參數(shù)K的增加，求解時(shí)間明顯變長(zhǎng).PF_LUG的計(jì)算時(shí)間與粒子個(gè)數(shù)有關(guān)，粒子數(shù)越多耗時(shí)越長(zhǎng)，但求得的診斷解個(gè)數(shù)不固定，原因有二:一是粒子個(gè)數(shù)不足以使全部小概率狀態(tài)體現(xiàn)在樣本中，二是多次重采樣使小概率事件被忽略.由于被忽略的都是小概率狀態(tài)，較少的粒子個(gè)數(shù)仍可以達(dá)到很好的診斷效果.

3.2 時(shí)間步數(shù)的影響

時(shí)間步數(shù)的變化范圍為［2，16］，K-Best枚舉中的參數(shù)K取3，5和7，PF_LUG中的粒子個(gè)數(shù)取1000，3000和5000.仿真結(jié)果如圖8、圖9所示，圖9為運(yùn)行時(shí)間限定在65000 ms內(nèi)的局部圖.

圖8 時(shí)間步數(shù)對(duì)算法性能的影響

圖9 時(shí)間步數(shù)對(duì)算法性能的影響(局部圖)

可以看出時(shí)間步數(shù)較小時(shí)，PF_LUG的耗時(shí)略多.但隨著時(shí)間步數(shù)的增加，K-Best枚舉的運(yùn)行時(shí)間指數(shù)增長(zhǎng)，且K值越大增長(zhǎng)越快.而PF_LUG運(yùn)行時(shí)間保持線性增長(zhǎng)，具有明顯優(yōu)勢(shì).

4 結(jié)束語(yǔ)

針對(duì)動(dòng)態(tài)系統(tǒng)基于模型診斷中狀態(tài)空間大小隨元件個(gè)數(shù)和時(shí)間雙指數(shù)增長(zhǎng)的問(wèn)題，提出了一種結(jié)合粒子濾波和不確定圖的動(dòng)態(tài)系統(tǒng)診斷方法PF_LUG.利用粒子在狀態(tài)空間的分布近似其概率，以及用不確定圖標(biāo)簽的反向匹配代替?zhèn)鹘y(tǒng)的正向軌跡枚舉，使每個(gè)時(shí)刻的計(jì)算復(fù)雜度只與粒子個(gè)數(shù)有關(guān).算法有效解決了由時(shí)間導(dǎo)致的計(jì)算量增長(zhǎng)問(wèn)題，使時(shí)間對(duì)復(fù)雜度的影響由指數(shù)運(yùn)算降為乘積運(yùn)算.仿真結(jié)果表明，相比K-Best枚舉方法，PF_LUG在診斷周期長(zhǎng)時(shí)有明顯優(yōu)勢(shì)，運(yùn)行時(shí)間相對(duì)診斷周期線性增長(zhǎng).

References)

［1］ Torta G，Torasso P.An on-line approach to the computation and presentation of preferred diagnosis for dynamic systems［J］.AI Communications，2007，20:93-116

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

［3］ Pencolé Y，Cordier M O.A formal framework for the decentralized diagnosis of large scale discrete event systems and its application to telecommunication networks［J］.Artificial Intelligence，2005，164(1/2):121-170

［4］ Kurien J，Nayak P.Back to the future for consistency-based trajectory tracking［C］//Proceedings of the 17th AAAI.Austin，Texas:AAAI Press，2000

［5］ Martin O，Ingham M，Williams B.Diagnosis as approximate belief state enumeration for probabilistic concurrent constraint automata［C］//Proceedings of the 20th AAAI.Pittsburgh，Pennsylvania:AAAI Press，2005

［6］ Marseguerra M，Zio E.Monte Carlo simulation for model-based fault diagnosis in dynamic system［J］.Reliability Engineering＆System Safety，2009，94:180-186

［7］ Li P，Kadirkamanathan V.Particle filtering based likelihood ratio approach to fault diagnosis in nonlinear stochastic systems［J］.Systems，Man，and Cybernetics，Part C:Applications and Reviews，IEEE Transactions on，2002，31(3):337-343

［8］ Bryce D，Kambhamptati S，Smith D.Planning graph heuristics for belief space search［J］.Journal of Artificial Intelligence Research，2006，26:35-99

［9］ Bryce D，Cushing W，Kambhamptati S.State agnostic planning graphs:deterministic，non-deterministic，and probabilistic planning［J］.Artificial Intelligence，2011，175:848-889

［10］ Bryce D，Scalable planning under uncertainty［D］.Downtown Phoenix:Department of Computer Science and Engineering，Arizona State University，2007