基于粒子濾波和不確定圖的動態系統診斷方法

王 冬 李景文 馮文全 朱 楠

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

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

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

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

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

1 算法描述

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

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

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

圖1 用有限狀態機表示的系統

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

圖2 用粒子個數為8的不確定圖表示的系統

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

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

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

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

1.1 正向擴展

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

1.2 反向搜索

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

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

圖3 正向擴展示意圖

圖4 反向搜索示意圖

1.3 PF_LUG算法

2 算法復雜度分析

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

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

由此可得算法PF_LUG的復雜度為

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

3 仿真結果

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

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

圖5 供電控制單元

圖6 DC/DC模塊

圖7 電壓轉換單元有限狀態機

3.1 預設參數的影響

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

表1 預設參數對算法性能的影響

40 20034 7000 36 12702

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

3.2 時間步數的影響

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

圖8 時間步數對算法性能的影響

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

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

4 結束語

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

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