王 冬 李景文 馮文全 朱 楠

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

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

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

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

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

1 算法描述

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

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

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

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

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

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

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

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

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

算法分為兩個步驟:正向擴展和反向搜索.

1.1 正向擴展

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

1.2 反向搜索

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

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

圖3 正向擴展示意圖

圖4 反向搜索示意圖

1.3 PF_LUG算法

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

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

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

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

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

3 仿真結(jié)果

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

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

圖5 供電控制單元

圖6 DC/DC模塊

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

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

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

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

40 20034 7000 36 12702

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

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

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

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

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

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

4 結(jié)束語

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

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