基于粒子滤波和不确定图的动态系统诊断方法

王 冬 李景文 冯文全 朱 楠

(北京航空航天大学 电子信息工程学院，北京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