（计算机软件与理论专业论文）基于值传递的故障诊断——模型、诊断和测试.pdf

中山走擘软件研究所 中山天擘博士学位论文 基于值传递的故障诊断 _ 模型、诊断和测试 专业：计算机软件与理论 博士生：张学农 指导老师：姜云飞教授 摘要 基于模型的诊断是由r e i t 科在| 9 8 7 年提出的一种基于逻辑推理的故 障诊断方法待诊断系统的行为可以通过系统的输入输出变量之间的对 应关系来描述由于其一般性和在许多领域的应用价值，基于模型的诊 断在人工智能领域被广泛关注 本文对基于模型的诊断的一些方面进行了研究，包括诊断模型的建 立，极小诊断的求解方法、诊断过程的重用诊断的分解和诊断的测试 等内容 本文的第4 章首先提出了一种基于值传递的系统模型，重新定义了 诊断，它与r e i t 盯的基于逻辑框架的诊断概念是等价的然后给出了快 速找到一个极小诊断的算法该算法不需要计算冲突集，并且在计算极 小诊断的同时给出一种合理的诊断解释 在上述基础上，第5 章提出了独立于系统输入输出的值传递路径的 概念，实现了值传递诊断过程的抽象，并根据等价路径对系统值传递路 径空问进行约简以约简的值传递路径空问作为一种新的系统描述给 张擘衣：基于值传递的故障诊断一模型、诊断和测试 出了一种故障诊断算法，对满足特定条件的系统，该算法多项式时间结 束同时本文给出了必要的证明和实验结果 第6 章对诊断问题的分解进行了研究，给出了候选诊断的分解与组 合定理在此基础上，提出了利用分步求解方法实现诊断分解的算法， 并对算法的正确性完备性和复杂性进行了证明实验结果表明分步求 解方法明显提高了舍多个输出的系统的诊断效率与利用变量假定倒化 值分解诊断问题的方法比较，本文的算法能提高效率并且扩大了适用范 围 最后，为找到故障系统的真实诊断，第7 章讨论了候选诊断和真实 诊断之间的关系，定义了诊断系统的可采纳性并证明基于一致性的诊断 是可采纳的在此基础上本文给出了一种基于一致性的诊断测试方法 在执行测试之后，所获得的关于真实诊断的信息是单调递增的，直到真 实诊断被包含在极小诊断集合中；一旦极小诊断集合包含真实诊断，所 有的测试都会支持真实诊断，而可能排除其它的候选诊断 关键词：故障诊断；基于模型的诊断；极小诊断；值传递；过程抽象； 诊断重用；诊断分解；分步推理；可采纳性；诊断测试 i v 中山大章软件研究所中山大学博士学位论走 f a u l td i a g n o s i sb a s e do nv a l u ep r o p a g a t i o n - - m o d e l ，d i a g n o s i sa n d t e s t m a j o r ：c o m p u t e r s o f t w a r ea n dt h e o r y n a m e ：z h a n gx u e n o n g s u p e r v i s o r ：j i a n g y u n f e i a b s t r a c t m o d e l - b a s e dd i a g n o s i si sa l li n t e r e s t i n gd i a g n o s t i cm e t h o db a s e do n l o g i c a lr e a s o n i n g ，w h i c hi sp r o p o s e db yr e i t e ri n1 9 8 7 i ta d d r e s s e st h e s y s t e m sw h o s en o m i n a lb e h a v i o r sc a l lb es p e c i f i e da sam a p p i n gf r o mt h e i r i n p u tv a r i a b l e st ot h e i ro u t p u tv a r i a b l e s d u et oi t sg e n e r a l i t ya n di t sd r a m a t i c i m p o r t a n c ei nm a n ya p p l i c a t i o nd o m a i n s ，m o d e l b a s e dd i a g n o s i sh a sb e e n r e c e i v i n gc o n s i d e r a b l ea t t e n t i o ni i lt h ef i e l do f a ir e s e a r c h i nt h i sp a p e r , s o m ea s p e c t so f m o d e l b a s e dd i a g n o s i sa r ed i s s c u s e d , s u c h a sd i a g n o s t i cm o d e l ，d i a g n o s i sa n di t sr e u s e ，d i a g n o s i sd e c o m p o s i t i o na n d t e s l i nc h a p t e r4 ，t h i sp a p e rf i r s tp r e s e n t sas y s t e mm o d e lb a s e do rv a l u e p r o p a g a t i o na n dr e d e f i n e s t h ed i a g n o s i s ，w h i c hi s e q u i v a l e n tt o r e i t e r s d e f i n i t i o n f u r t h e r m o r e ，a na l g o r i t h mf o rf i n d i n go n em i n i m a ld i a g n o s i si s b r o u g h to u t t h i sa l g o r i t h mn e e dn o tc o m p u t et h em i n i m a lc o n f l i c t sa n d p r o v i d e sar e a s o n a b l ei n t e r p r e t a t i o nf o r t h em i n i m a ld i a g n o s i s o nt h eb a s i so fa b o v ew o r k s ，c h a p t e r5d e f i n e st h ec o n c c p to fv a l u e p r o p a g a t i o nr o u t ef o ra b s t r a c t i n gt h ep r o c e s so fd i a g n o s i s ，a n dr e d u c e st h e r o u t es p a c eb yd e l e t i n ge q u i v a l e n c er o u t e s t h e n ，a na l g o r i t h mt od i a g n o s i n g v 张学农：基于值传连的故障诊断一模型诊断和测试 s y s t e mb a s e d0 1 1v a l u ep r o p a g a t i o n r o u t es p a c ei si n t r o d u c e d ，w h i c h t e r m i n a t e si np o l y n o m i a lt i m ef o rs o m es p e c i a ls y s t e m s ，b e s i d e s , t h e n e c e s s a r yp r o o f sa n de x p e r i m e n t a lr e s u l t sa r ea l s op r o p o s e di nt h i sp a p e r c h a p t e r6i n v e s t i g a t e st h ed e c o m p o s i t i o no fd i a g n o s i sp r o b l e m ，g i v e sa t h e o r e mf o rd e c o m p o s i t i o na n dc o m b i n a t i o no f t h ed i a g n o s i s o nt h eb a s i so f a b o v et h e o r e m , 柚a l g o r i t h mu s i n gg r a d u a la p p r o a c ht od e c o m p o s et h e d i a g n o s i sp r o b l e mi sp r o p o s e d b e s i d e s ，t h ec o r r e c t n e s s ，c o m p l e t e n e s sa n d c o m p l e x i t yo ft h ea l g o r i t h ma r cp r o v e di n t h i sp a p e r t h ee x p e r i m e n t a l r e s u l t si n d i c a t et h a to u ra l g o r i t h mc 锄e v i d e n t l yi m p r o v et h ee f f e c t i v e n e s so f d i a g n o s i n gm u l t i o u t p u ts y s t e m s c o m p a r i n gw i t ht h ea p p r o a c ho fd i a g n o s i s d e c o m p o s i t i o nb ya s s u m i n gi n s t a n t i a t i o n so f s o m ev a r i a b l e s ，o u ra l g o r i t h mi s m o r ee f f e c t i v ea n da p p l i e st om o r eg e n e r a ld i a g n o s i sp r o b l e m s f o rf i n d i n gt h ea c t u a ld i a g n o s i so ft h ef a u l t ys y s t e m ，c h a p t e r7 d i s c u s s e st h er e l a t i o n s h i pb e t w e e nt h ec a n d i d a t eo fd i a g n o s i sa n dt h es e to f t h ea c t u a lf a n 姆c o m p o n e n t s t h e n , w ed e f i n et h en o t i o no fa d o p t a b i l i t yo f t h ed i a g n o s t i cs y s t e ma n dp r o v et h a tt h ec o n s i s t e n c y - b a s e dd i a g n o s i si s a d o p t a b l e o nt h eb a s i so f t h ea b o v ew o r k s ，ad i a g n o s i st e s tm e t h o db a s e do n c o n s i s t e n c yi sp r o p o s e d a sr e s u l t so ft h i sc h a p t e r , t h eo b t a i n e di n f o r m a t i o n a b o u tt h ea c t u a ld i a g n o s i si sm o n o t o n o u s l yi n c r e a s e da f t e rt h ee x e c u t i o no f t h et e s t , u n t i lt h ea c t u a ld i a g n o s i si si n c l u d e di nt h es e to f m i n i m a ld i a g n o s e s ； o n c et h ea c t u a ld i a g n o s i si si n c l u d e di nt h es e to f m i n i m a ld i a g n o s e s ，i tw o u l d b ec o n f i r m e db ya n yt e s t sw h i c hm a yr e f u t eo t h e rd i a g n o s e s k e y w o r d s ：f a u l td i a g n o s i s ；m o d e l b a s e dd i a g n o s i s ；m i n i m a ld i a g n o s i s ； v a l u ep r o p a g a t i o n ；p r o c e s s a b s t r a c t i o n ；d i a g n o s i sr e u s e ；d i a g n o s i s d e c o m p o s i t i o n ；g r a d u a lr e a s o n i n g ；a d o p t a b i l i t y ；d i a g n o s i st e s t v 1 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师姜云飞 教授的指导下，独立进行研究工作所取得的成果除文中已经 注明引用的内容外，本论文不包含任何其他个人或集体已经 发表或撰写过的作品或成果对本文的研究作出重要贡献的 个人和集体，均已在文中以明确方式标明本人完全意识到本 声明的法律结果由本人承担 学位论文作者签名：；莒：髻移 日期：2 0 0 7 年1 2 月1 日 张擘农：甚一t - ( i 传- t 的故障1 争断一模型 诊断小r 剧试 学位论文使用授权声明 本人完全了解中山大学有关保留，使用学位论文的规定， 即：学校有权保留学位论文并向国家主管部门或其指定机构送 交论文的电子版和纸质版，有权将学位论文用于非赢利目的的 少量复制并允许论文进入学校图书馆、院系资料室被查阅，有 权将学位论文的内容编入有关数据库进行检索，可以采用复 印、缩印或其他方法保存学位论文 学位论文作者签名：1 ：云髻l 往 导师签名：，正飞厶 日期：2 0 0 7 年1 2 月f 日日期：2 0 0 7 年1 2 月日 中山走擘软件研究所中山大学博士学位论文 1 、前言 基于模型的诊断研究开始于七十年代中期。其开创性的工作是d e k l e e rj 的i n t e r 系统【i i 和b r o w na l 的w a t s o n 系统【2 1 到八十年代中 期这个领域热了起来，r e i t e rr 唧于1 9 8 7 年为基于模型的诊断提出了一 个漂亮的逻辑框架因其具有诸多优点及很高的实用价值，吸引了许多 研究者，到九十年代已经成为一个十分活跃的研究分支基于模型的诊 断对整个人工智能领域的研究起着重要推动作用一方面，人工智能领 域其它分支的许多研究成果可以在基于模型的诊断中得到有效的应用， 促进了这一分支的发展；另一方面，基于模型的诊断研究暴露了许多人 工智能技术中存在的问题，激发了人们对它们研究的热情 基于模型的诊断的主要思想【3 4 1 是：根据系统组成元件与元件之间 的连接建立起待诊断系统模型( 如结构、功能、行为) ，这种模型通常用一 阶逻辑语句来描述，根据系统的逻辑模型以及系统的输入，我们能通过逻 辑的推理理论推导出系统在正常情况下的预期行为，如果观测到的系统 实际行为与系统预斯行为有差异，就说明系统存在故障，利用逻辑的推 理理论，我们能够确定引发故障的元件集合 基于模型的诊断中有两个主要流派一个是基于一致性的诊断 ( c o n s i s t e n c y - b a s e dd i a g n o s i s ) 【3 】【5 】嘲另一个是溯因诊断似6 幽d 协 d i a g n o s i s ) 【s 1 【9 】【1 吼”1 前者把诊断概念建立在不正常工作的元件与观察结 果的相容性上，这相当于解释的弱概念，持这种观点的代表人物是d e k l r 和w i l l i a m s 后者的诊断概念要求由不正常工作的元件和诊断模型 可以逻辑地推出观察结果，这相当于解释的强概念，持这种观点的代表 人物是p o o l e c o n s o l el 和t o r a s s op 【1 2 】把诊断问题看成是带有一致性约 束的溯因问题他们提出了一个统一的定义，使得不同诊断的逻辑定义 都可以用这个统一的定义表示，并且可以把不同的定义加以比较在这 个统一定义下，基于一致性的诊断和溯因诊断仅仅是两个极端的情形 张学农：基于值传连的故障诊断一模型诊断和测试 基丁模型的诊断是一种全新的诊断方法，与传统的诊断方法有着重 要的区别因丽被h a m s c h e rw ，c o n s o l el ，d ck l c c rj 1 4 培人工智能专家 誉为诊断理论和诊断技术上的革命值得注意的是，模型是一个很广义 的概念，关于系统的结构模型称为模型，而关于系统的故障模型也可以 称为模型，但两者是截然不同的，后者的故障模型实际使用的还是基于 经验的知识，它描述的是系统的表现到它的故障结论( 不是通过系统描 述推理得到的，而是凭经验得到的) 的一个基于经验的推理模型，不是关 于系统本身结构知识的有一些学者将基于故障模型的诊断，如故障决 策树模型等也归到基于模型的诊断。本文所说的基于模型的诊断均特指 基于系统结构模型的诊断，这与国际上公认的基于模型的诊断的定义也 是相符的本文所讨论的模型都是关于系统结构知识的模型 基于经验的诊断系统使用的是经验知识，所谓经验知识，就是可以 根据系统的表现直接得出故障或可能故障的规则，这些规则是从经验中 得出的而基于模型的诊断系统使用的是关于模型本身的知识，它是通 过对模型的观察和预期输出的差异，并根据模型的内部结构和行为通过 计算和推理演算来判断那个部件或哪些部件是异常的 传统的诊断方法都是使用基于经验的诊断，这种诊断主要利用专家 对诊断对象的经验，对领域有极强的依赖性对一个对象适用的诊断系 统不能用在另外一个对象上 采用这种方法的计算机诊断系统主要有两类，一类是基于规则的诊 断系统( r u l e b a s e dd i a g n o s i ss y s t e m s ) ，另一类诊断系统使用判别树 ( d e c i s i o nt r e e ) 基于规则的诊断系统主要使用在专家系统中这种系统 把人类专家对诊断对象的诊断知识转换成产生式规则，规则的前提是诊 断对象的症状集合规则的结果是诊断的结论研制这种诊断系统的关 键问题是知识获取首先，人类专家需要经过长时间的积累才能获得诊 断领域的知识其次，如何把专家知识转换成计算机系统可用的产生式 规则也是一个大问题使用判别树的诊断系统首先把设备常见的故障和 2 中山大学软件研究所 中山大学博士学位论文 与之相连的症状组成( 故障，症状) 偶对，然后把这个偶对反过来，利用 症状为关键字，将其组织成树彤结构，以利用通过明显表现山的症状检 索出隐藏的故障这种方法的优点是简单，效率高但同样存在需要专 家经验、对领域有极强的依赖性等问题哪怕是对设备更换一个元件 也需要重新构造整个诊断判别树 早期的智能诊断是专家系统中关于人类疾病的诊断，美国斯坦福大 学的m y c i n 系统f 1 封是这类诊断系统的先驱和代表此后，人们又研制 了各种各样的诊断专家系统这类系统都是基于经验的诊断系统，系统 的知识库存贮的是专家关于诊断领域的知识，为研制这类系统，人们需 要把专家知识收集起来，转换成计算机能够使用的形式，诊断的输入信 息是病人的症状和化验结果，诊断的结果是指出待诊断对象可能患有的 某种疾病，并且给出治疗意见 基于模型诊断是智能诊断在思想上的一个大的突破，它的优点是： ( 1 ) 智能诊断是依赖知识的系统【1 4 胪1 6 i 堋，而基于经验的诊断仅 仅使用了专家的知识，缺乏对系统结构描述的知识这些知识在某些诊 断中占有十分重要的地位在缺乏这些知识的情况下。无论我们对基于 经验的诊断系统做何种改进，都不会对诊断系统的质量有显著的提高 因此，基于模型的诊断是提高诊断系统质量必须认真考虑的有效途径 ( 2 ) 基于经验的诊断类似于中医的诊断，而基于模型的诊断类似于 西医的诊断在中医的诊断中，医生的诊断全凭经验，不考虑人的身体 结构，不考虑人体各器官的功能和连接，因此也就无法像西医那样对病 人做手术治疗，例如换心、换肾等手术而对于电子、电器、软件产品 来说，这种诊断的思路是不适用的对电子、电器产品来说，诊断的目的 是找出有毛病的元件，然后更换这些元件，使系统恢复正常工作这类 诊断需要大量的关于系统结构的知识而模型就是对系统结构知识的描 述【 ( 3 ) 当前，电子、电器、软件等产品的更新换代的步伐非常迅速这 张学衣：基于值传逆的故障诊断一模型诊断和测试 类产品的生命周期一般都很短而基于经验的诊断主要依赖丁专家知识 专家知识的形成、总结和积累需要一个较长的过程等到专家知识积累 起来，再依据这些知识研制出诊断系统，它所要诊断的产品可能己经淘 汰了，或者已经过时了而基于模型的诊断可以在产品的设计阶段或生 产阶段根据系统的组成元件和元件之间的连接建立起系统模型。然后依 据模型研制计算机诊断系统诊断系统在目标设备出厂时可直接投入使 用且基于模型的诊断具有设备独立性，它把系统的推理内核与系统模 型分开，只要更换系统模型，就可以用于诊断另外一种设备 ( 4 ) 基于规则的诊断系统在诊断能力上是不完备的，即不能诊断所 有的故障，因为人类专家的诊断经验是不完备的，无论他怎样用心去积 累，也不可避免地会有遗漏的经验而对于基于模型的诊断来说，只要 从诊断模型推导出的预期的行为与实际观察到行为存在差别，就需要考 虑其诊断问题从这个意义上来说，只要是模型抽象得正确，就能够诊 断所有可能的故障 ( 5 ) 基于规则的诊断系统的另一个缺点是不能对诊断给出解释，而 基于模型的诊断却可以根据系统的组成元件和元件之间的连接对产生 的故障给出令人信服的解释 4 中山走擘软件研究所中山大孝博士学位论文 2 、基于模型的诊断概述 2 1 基于模型的诊断的形式定义 基于模型的诊断不仅用一阶逻辑来表示目标系统的结构和行为，还 用它来表示刻画特定诊断问题的观察集值得注意的是这里的模型是指 目标系统的表示。而不是指逻辑上的关于一组公式的可满足的解释这 种基于逻辑的方法的一个前提条件是，模型能够正确描述目标系统的结 构和行为，或者故障的因果关系从逻辑的角度上，可以将“诊断”认为 是对所观察到的行为的一种“解释”，目前主要有两大类关于这种“解释” 的概念，一类是基于逻辑一致性的概念( 基于一致性的诊断) ，一类是溯 因的概念( 溯因诊断) 基于一致性的诊断是由r e i t e rr 【3 】于1 9 8 7 年首次提出的该方法 用一阶逻辑语句的集合s d 表示目标系统的描述，s d 包含了刻画系统元 件间的连接关系的公理集和描述每一个元件行为的公理集用谓词a t ( c ) 表示元件c 是异常的，那么对于正常元件c ，用蕴含式- a t ( c ) - - ) o u t p u t = ， ( i n p u t s ) 来表示元件c 的正常行为用观察集翻臁示系统的观测在假 定所有的元件都正常工作的情况下，如果o b s 与s d 不一致，就意味着观 察行为与预期行为之间有差异一个诊断就是这样的一个关于元件的集 合a ，在该集合内的元件是异常的，而其他元件都是正常的情况下，观察 o b s 和系统描述s d 是一致的设系统的所有元件的集合为c o m p s , d e k l e e rj ，m a c k w o r t ha k ，r e i t e rr 【1 8 1 给出了基于一致性的诊断的形式 化描述 定义2 1 ：基于一致性的诊断 设c o m p s , 关于( s d ，c o m p s , 研的基于一致性的诊断为 d ( ，c o m p s - ) 2 口6 ( c ) icc a ) u 1a b ( c ) lc c o m p s 一) ，使得 张学农：基于值传递的故障诊断一模型诊断和测试 u o b s u d ( & c o m p s - a ) l 是一致的 溯因推理是指在某个域给定的事件集合中产生一个解释的过程溯 因诊断起源于一个基于疾病和征状的因果模型的医疗诊断方法将这种 方法推广到基于逻辑公式的器件的诊断上后，模型7 就是指包含了那些 描述故障因果关系的公理故障对应于一个特定的表征或假设的集合 p o o l ed ，g o e b e lr ，a l e l i u n a sr s l 并l l p o o l ed 唧首先给出了溯因诊断的 定义 定义2 2 ：溯因诊断 设f 是一个极小的关于故障原因的假设集合，丁是系统的模型，o b s 是观察集称e 是一个溯因诊断，当且仅当e u t 是一致的，且及j 外 o b s 为了将基于一致性的诊断和溯因诊断统一起来，将故障产生原因的 假设集也用非正常部件的集合表示，模型用如表示，d ek l e e rj ， m a c k w o r t ha k ，r e i t e rr i l g l 对溯因诊断给出了新的定义 定义2 3 ：溯因诊断 设a c _ c o m p s , 关t - ( s d ，c o m p s , o b s ) 的溯因诊断为d ( c o m p s - a ) ， 使得s z x ) d ( a ，c d i 路) ) 是一致的，且s d u d ( a , c o m p s - a ) o b s c o n s o l el ，t o r a s s op 将定义2 1 和定义2 3 统一起来，建立了一 个基于模型的诊断的定义谱系 定义2 4 ：基于模型的诊断 设o c o b s , a c c o m p s , 称d ( c d 岈怔) 为关于( s d , c o m p s , 中山大学软件研究所中山大学博士擘住论文 o b s ) 的基丁模型的诊断，当且仪当 ( 1 ) o b s u d ( c o m p s - a ) 是一致的 ( 2 ) s du d ( & c o m p s - a ) 0 从以上定义可以看出，当0 从。到d 啵化时，可得到从基于一致性 诊断到溯因诊断一系列不同的逻辑定义由此可见，溯因诊断对诊断空 间的限制最强，即要求所有观测被逻辑推出。而基于一致性的诊断限制 最弱，即不要求任何观测被逻辑推出p r e i s tc 【。卵也对一致性的诊断和 溯因诊断进行了研究 2 2 基于模型的诊断的示例 我们介绍两个在诊断领域经常采用的具有代表性的示例介绍基于模 型的诊断在本文的其它章节中，仍然采用这两个示例进行说明一个 示例是p o l y b o x 系统，变量取值范围是无限的，元件的功能可以用简单代 数方程来表示另一个是全加器，变量取值范围是有限的，元件完成的 是逻辑运算 2 2 1p o i r b o x 系统 图2 1 给出了p o t y b o x 系统的诊断例子其中m 1 、m 2 和m 3 是乘法 器，彳和a 2 是加法器 系统的元件集合c o m p s = a 1 ，a 2 ，m 1 ，m 2 ，m 3 系统的描述s d 由下列一阶逻辑语句组成： ( 1 ) 描述乘法和加法功能的语句，例如 a d d ( x ) a - - , a b ( x ) - o u t ( x ) = i n l ( x ) + i n 2 ( x ) 等 ( 2 ) 描述各元件属性的语句，例如 a d d ( a nm u l t i ( m 1 ) 等 ( 3 ) 描述各元件之间互相连接的语句，例如 张学衣：基于值传递的故障诊断一模型诊断和测试 o u t ( m 1 ) = i n l 叫no u t ( m 2 ) = i n 2 似，) 等 此外，还包括对输入、输出的限制语句以及布尔代数的公理 图2 1 、p l o y b o x 系统 f i g2 ip o l y b o xs y s t e m 设系统输入为a = 3 ，c = 3 ，e = 3 ，b = 2 ，d = 2 ，f = 2 ，系统输出为g = 1 0 ， 月1 2 极小诊断有4 个：d ( m ， ，( a 1 ，a 2 ，m 2 ，m ，) ) d ( 臼j ) ， m 1 ，a 2 ， m 2 ， 埘) ) d ( m 2 ，a 2 ，即j ，m 1 ，加) ) d ( m 2 ，协 ， a t ，彳五刎 ) 2 2 2 全加器 图2 2 给出了全加器的诊断例子其中朋和x 2 是异或门，4 ，和 a 2 是与门，0 是或门 系统的元件集合c o m p s = - 似，一2 ，x i ，x 2 ，o i 系统的描述s d 由下列一阶逻辑语句组成： ( 1 ) 描述异或门、与门和或门功能的语句，例如 a n d ( x ) - a b ( x ) - - o u t ( x ) = a n d ( i n l ( x ) i n 2 ( x ) ) 等 ( 2 ) 描述各元件属性的语句，例如 a n d ( a 1 ) ，x o r g ( x o 等 ( 3 ) 描述各元件之间互相连接的语句，例如 o u t ( x 1 ) = i n i 刁，o u t ( x 1 ) = i n 2 ( x 2 ) 等 3 2 3 2 3 2 中山大学软件研究所中山大学博士学住论文 此外还包括对输入、输m 的限制语句以及布尔代数的公理 l 0 图2 2 、全加器 f i g2 2f u l la d d e r 1 【0 】 这个系统在观测a = i ，b = l ，c - - - - o 和，= o ，仔= l 之下，有4 个基于一 致性的极小诊断：烈艘) ，似，彳z2 ( 1 ，d j ) ) z ) ( x l ，a l ， 船，a 2 ，d ，) ) ， d ( 朋，a 2 ，即j ，x 2 , 叫) ) ，d ( x l ，0 1 ，似j ，x 2 ，彳2 ) ) 2 3 诊断空间的刻画与诊断的计算 2 3 1 基于一致性的极小诊断 由于可能存在2 1 c o p m s l 个诊断，有必要寻找一种能紧致刻画诊断空间 的方法r e i t e rr 【3 1 提出了一种基于逻辑一致性的方法，称为基于一致性 的极小诊断 定义2 5 ：基于一致性的极小诊断 设a c _ c o m p s , 关于( s d ，c o m p s , o b s ) 的基于一致性的极小诊断 为一极小集合d ( c o m p s - ) ，使得衄t o o b s u d ( a , c o m p s - a ) 捏z - - 致的 根据极小诊断的定义，容易得出求极小诊断的朴素方法：先系统地 产生系统元件集合c d m 路的所有子集墨然后测试肋uo b su - , a b ( c ) 9 张学衣：基于值传递的故障诊断一模型，诊断和测试 ic e c o m p s - s 的一致性但是，随着系统元件数量的增加，系统的所有 子集数量会以指数增加，而且要判断一个逻辑语句集合是否致也是困 难的因此，r e i t e rr 采用冲突集例的概念来计算诊断诊断的过程可分 为两步：( 1 ) 产生所有的极小冲突集；( 2 ) 求极小冲突集的极小碰集而得到 极小诊断 定义2 6 ：( 极小) 冲突集 系统( s d ，c o m p s , o b s ) 的( 极小) 冲突集是一个( 极小) 集合 c l ，c 2 ， c x ，满足s d uo b s u - - a b ( c o ，t “c x ) 是不一致的 定义2 7 ：( 极小) 碰集 设c 是一个集合簇，c 的( 极小) 碰集( h i t t i n gs e t ) 是一个( 极小) 集合 u s c s ，使得对所有s c 满足n s o 定理2 1 设d 是系统元件集合c o m p s 的子集，则d 是系统( 趿c o m p s , o b s ) 的极小诊断当且仅当d 是( 肋，c o m p s , o b s ) 的极小冲突集簇的极小碰 集 从基于一致性的诊断和基于一致性的极小诊断的定义容易得出如 下结论： 命题2 1 若d ( ，c o m p s - a ) , 是- - 个基于一致性的诊断，则一定存在一个基于 一致性的极小诊断d ( a ，c o m p s - a ) ，使得a 7 c a 如果上述命题反过来也成立，那么使用基于一致性的极小诊断就可 l o 中山尢学软件研究所中山大学博士学位论文 以紧致地刻画整个基丁一致性的诊断空间 假设2 1 ：( 极小诊断假设) 设d ( ：c o m p s - a 3 是基于一致性的极小诊断，且，c a c c o m p s , 那么d ( ，c o m p s - a ) 是一个基于一致性的诊断 但是，d ek l c e rj ，m a c k w o r t ha k ，r e i t e rr 【1 8 1 指出上述假设并不总 是成立，并给出了极小诊断假设成立的条件 定理2 2 如果( 舳，c o m p s , o b s ) 的所有极小冲突都为正冲突，则极小诊断假 设成立 基于一致性的极小诊断在一般情形下不能刻画基于一致性的诊断 空间为解决这一问题，r a i m a n0 唧】提出了基本诊断但是，只有当 s i x j o b s 为h o m j 哩论时。基本诊断才能刻画基于一致性的诊断空间随后， d ek l e e rj 。m a c k w o r t ha k ，r e i t e rr 【1 8 】提出了基于一致性的中心诊断 来刻画基于一致性的诊断空间 2 3 2 基于一致性的中心诊断 假设一个系统由3 个元件c 1 。c 2 和a 组成并假设我们得到了如 下两个诊断：a b ( c 1 ) a b ( c 2 ) a a b ( c 3 ) ，a b ( c 1 ) a a b ( c 2 ) - - , a b ( c 3 ) 这可以 解释成a 和凹故障，而。可能故障也可能无故障因此，上述两个诊 断可以表示成a b ( c 1 ) a a b ( c 2 ) 为此，d e k l e e rj ，m a c k w o r t h a k ，r e i t e r r i t s l 提出了部分诊断的概 念提供了一种刻画所有诊断的方法 张学农：基于值传递的故障诊断一模型诊断和刹试 定义2 8 ：覆盖 称文字的合取式c 覆盖另一文字合取式d ，当且仅当c 的每个文字 都在d 巾出现 定义2 9 ：基于一致性的部分诊断 ( s d ，c o m p s , o b s ) 的一个基于一致性的部分诊断是一可满足的口6 文字的合取式尸 使得对任意被p 覆盖的可满足的西文字的合取式q ， s d u o b s u q ) 是一致的 命题2 2 设p 是( s d ，c o m p s , d j 哟的一个基于一致性的部分诊断，s 是p 中 提到的所有元件的集合，那么p 4 ( c ) ，其中c e c o m p s - s , 是( 肋0 c o m p s , o b s ) 的- - 个基于一致性的诊断，其中每一个彳( c ) 是a b ( c ) 或 吲6 ( c ) 定义2 1 0 ：基于一致性的中心诊断 基于一致性的中心诊断是具有如下性质的基于一致性的部分诊断 能覆盖它的唯一的基于一致性的部分诊断是其本身 定理2 3 d ( ，c o m p s - a ) 是一个基于一致性的诊断，当且仅当存在一个基于 一致性的中心诊断来覆盖它 上述定理说明，在一般情况下，使用基于一致性的中心诊断可以紧 致地刻画基于一致性的诊断空间如何计算基于一致性的中心诊断呢? 这要用到本原蕴涵蕴涵式的概念 中山大学软件研究所中山大学博士擘住论文 定义2 1 1 ：本原蕴涵 设三是命题公式的集合，称一可满足的基文字合取式7 ( a p 不含互 补对的文字的合取式) 是三的一个蕴涵当且仅当，7 能推出三中的每个 语句称，7 是三的一个本原蕴涵当且仅当能覆盖，7 的唯一的三的蕴涵 是刀本身 定义2 1 2 ：本原蕴涵式 设三是命题公式的集合，称基文字的析取式c 为三的蕴涵式，当且 仅当三能推出c 称c 为三的本原蕴涵式，当且仅当不存在c 的真子句 c ：使得c 为三的蕴涵式 定理2 4 ( s d ，c o m p s , o b s ) 的基于一致性的部分诊断是( 肋0c o m p s , o s s ) 的所有极小冲突的蕴涵 定理2 5 ( s d ，c o m p s , o s s ) 的基于一致性的中心诊断是( s d ，c o m p s , o s s ) 的所有极小冲突的本原蕴涵 2 3 3 溯因诊断 与基于一致性的诊断类似，也可以采用中心溯因诊断【1 町紧致地刻 画溯因诊断空间 定义2 1 3 ：部分溯因诊断 ( s d ，c o m p s , o b s ) 的部分溯因诊断为一可满足的d ( a 1 ，a 2 ) ，使得 对每一被d ( a i ，2 ) 覆盖的可满足的d ( a i ，, x 2 3 ，都有肋u d ( l 2 是一致的，且u d ( a 1 ，a 2 ) ) o b s 张学农：基于值传递的故障诊断一模型诊断和测试 定义2 1 4 ：中心溯因诊断 中心溯因诊断是具有如下性质的部分溯因诊断：能覆盖它的唯一的 部分溯因诊断是其本身 定理2 6 d ( c o m p s - a ) 是一个溯因诊断，当且仅当存在一个中心溯因诊断 来覆盖它 定理2 7 设s d ，0 为有限集合，表示输入，0 表示输出，u d = o b s d ( a i 。 a 2 ) 为关于( c o m p s , o b s ) 的中心溯因诊断，当且仅当i ) ( a i ，t a ) 为 7 s d m - - o i 拘本原蕴涵，其中1 7 是( 肋，c o m p s , o b s ) 的所有极小冲 突的合取式 2 4 基于模型的诊断的研究课题 2 4 1 模型的构建 模型的构建是基于模型诊断的基础r e i t e r 的工作为基于模型的诊断 提供了一个形式化框架，为基于模型的诊断奠定了坚实的理论基础其 经典模型p 墚用一阶逻辑表示系统。描述系统的组成和行为 2 0 世纪8 0 年代，很多研究者循着r e i t e r 的方向开展研究工作，取得很 多有用的研究结果f 1 8 】【2 2 2 1 1 矧，推动了基于模型诊断的发展但是，人们 也很快发现，基于模型诊断的计算复杂性与待诊断系统的元件数量有极 为密切的关系当系统较为复杂、元件数量很多时，诊断计算的复杂性急 剧上升，导致诊断无法进行为减少诊断计算复杂性，人们自然地想到 把系统分成若干个组，先按组做出诊断，然后对确定的组再诊断到元件 c h i t t a r ol ，r a n o nr t 2 4 j 指, w , ，上述简单的抽象方式对诊断效率的改 进并不是总有作用，有时甚至是起反作用于是他们提出分级结构抽象 中山太擘软件研究所中山太学博士擘位论文 的思想，提出了多错误分层诊断模型他们把s d 细分为c d 加h b d ，其 中c d 表示结构描述，描述系统元件间的连接关系；b d 表示行为描述，描 述元件在各种状态下的行为，包括正常状态和各种不同的异常状态经 典模型中的正常和异常两种状态只是多错误分层诊断模型中状态的特例 其核心是给出构建诊断模型中关于抽象过程的概念，然后把简单的诊断 模型抽象问题转换为在多个抽象诊断模型中选取最优诊断模型的问题， 给出了判断诊断模型优劣的准则，并给出自动产生最优诊断模型的算法 s a c h c n b a c h c rm ，s t r u s sp 【2 5 1 认为之所以效率太低，是源于描述实际 系统的模型过细，未能抓住系统本身的特点。不适应诊断的要求这种 过细的模型，不但降低了系统的效率，实际上很多描述也无必要他们 提出在系统参量的关系约束框架的基础上。依据系统的输入和观察到的 输出，以及系统的诊断任务，重新对实际系统进行定量抽象这种抽象 在能够描述系统行为的情况和满足任务要求的前提下。应尽可能地粗 这种方法在系统的定量描述和定性描述之间架起桥梁。可以在不考虑抽 象级别的情况下表达元件间的行为知识s a c h b a c h e r 和s t r u s s 等把他们 的方法用在欧洲汽车生产和供应公司的一个汽车引擎的故障诊断中，诊 断效率得到