Improved HSSE-tree method based on binary label
-
摘要: 随着对航天器自主生存能力要求的提高,基于模型的故障诊断成为国内外的研究热点.计算全体极小碰集是基于模型的故障诊断中的关键步骤,以HSSE-tree算法为基础,结合二进制位标记,提出一种HSSE-tree的高效改进算法——Binary-label HSSE.改进算法采用二进制位标记来代替实际节点元素,并采用了有效的剪枝策略及节点扩展方式,避免了HSSE-tree算法中存在的节点个数及超集个数随着问题规模增大而产生的爆炸式增长的问题;此外,改进算法采用二进制位运算,避免了判断碰集及判断是否超集时的元素遍历,使算法的运行时间进一步减少.仿真结果表明,与HSSE-tree算法相比,改进算法的消耗时间及占用内存均有了大规模减少.这为航天器系统的故障诊断及实时诊断提供了理论依据和应用基础.Abstract: Because of the increase of the demand for the autonomy of spacecrafts, model-based diagnosis has been a hot research spot both at home and abroad. Computing all minimal hitting sets is a key step of model-based diagnosis. An effectively improved method of HSSE-tree called Binary-label HSSE based on HSSE-tree and combining binary labels was put forward. The improved method used binary digits to mark the real elements of the nodes, and used effectively pruning and expanding strategies, to avoid the main problem of HSSE-tree, the explosive growth of the expanded nodes and supersets along with the dimension of the problems. Additionally, computing between binary digits can avoid the traverse of every element in a node when judging whether the node is a minimal hitting set (MHS), which also contributes to the significant decrease of the run time. Simulation results show the improved method costs much less space and time than the HSSE-tree method, which provides both theoretical and applicative foundation for fault diagnosis and Real-time diagnosis of spacecraft system.
-
Key words:
- minimal hitting set /
- model-based diagnosis /
- binary label
-
[1] Hayden S,Sweet A,Shulman S.Lessons learned in the livingstone 2 on earth observing one flight experiment [C]//Proc AIAA 1st Intelligent Systems Tech Conf.Arlington,Virginia:Infotech@Aerospace,2005:1-15 [2] Narasimhan S,Brownston L.HyDE-a general framework for stochastic and hybrid model-based diagnosis [C]//Proc of the 18th Int Workshop on Principles of Diagnosis.Nashville:TN,2007:162-169 [3] Hamscher W C.Modeling digital circuits for troubleshooting[J].ArtificialIntelligence,1991,51(13):223-272 [4] 赵相福.基于模型诊断中的关键算法研究 [D].长春:吉林大学计算机科学与技术学院,2006 Zhao Xiangfu.Research on key algorithms in model-based diagnosis [D].Changchun:College of Computer Science and Technology,Jilin University,2006(in Chinese) [5] Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-96 [6] Franz Wotawa.A variant of Reiter-s hitting-set algorithm[J].Information Processing Letters,2001,79(1):45-51 [7] 姜云飞,林笠.用布尔代数方法计算最小碰集[J].计算机学报,2003,26(8):919-924 Jiang Yunfei,Lin Li.The computation of hitting sets with boolean formulas[J].Chinese Journal of Computers,2003,26(8):919-924(in Chinese) [8] Rymon R.Search through systematic set enumeration [C]//Proceedings of the 3rd International Conference on Principles ofKnowledge Representation and Reasoning.Cambridge,MA:Morgan Kaufmann,1992,539-550 [9] 陈晓梅,孟晓风,乔仁晓.基于BNB-HSSE计算全体碰集的方法[J].仪器仪表学报,2010,31(1):61-67 Chen Xiaomei,Meng Xiaofeng,Qiao Renxiao.Method of computing all minimal hitting set based on BNB-HSSE[J].Chinese Journal of Science Instrument,2010,31(1):61-67(in Chinese)
点击查看大图
计量
- 文章访问数: 1651
- HTML全文浏览量: 118
- PDF下载量: 605
- 被引次数: 0