ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



̻ģ͵* 
ŷͮ1Ʒ2 
ժҪȻԻģ͵ϴһϵвͬ߼,ҵǴһͳһĳ,Ĳͬ.ڸö˻ģ͵ϵĸ.̻ͨģ͵Ϲ,֤˻ģ͵뱾ԭ̺/̺ʽֱӹϵ,Ӷ۽ATMS(assumption-based truth maintenance system)㷨ϵ.һָ,ԻһϵĿ̻Ŀ̻һ.
ؼʡģ͵,ģ͵,ԭ̺/̺ʽ.
ͼšTP18
Characterizing Kernel Model-based Diagnosis 
OU-YANG Dan-tong1JIANG Yun-fei2 
AbstractAlthough there is a spectrum of different logical definitions of model-based diagnosis, fortunately, there exists a unified abstract definition which generalizes the definitions proposed in the past. Based on this definition, the concept of kernel model-based diagnosis is proposed. Then by characterizing the process of kernel model-based diagnosis, the direct relationship between it and the prime implicants/implicates is also demonstrated. Therefore, the theoretical results in this paper can be linked with algorithms such as the ATMS (assumption-based truth maintenance system). Furthermore, it is pointed out that the characterization of kernel consistency-based diagnosis is only a special case of the characterization in this paper.
Key wordsModel-based diagnosis, kernel model-based diagnosis, prime implicant/implicate.
ʹôͳרϵͳϵͳھ豸,δרȡҪ֪ʶάͷչЩϵͳƿ.ģ͵һµAI,Կ˷ͳȱ.
ģ͵ϿԿ֪жԹ۲켯͡Explanations)Ĺ.,ٴͬĹڡ͡߼.һǽ͵.,һϽһ۲m,mһ,μף14.һǽ͵ǿ.,һϽһ۲m,߼Ƴm,μף5,6.Ȼ,߼ƳһҪǿö.ôһ۲켯,ӦѡЩ۲뱻߼Ƴأһĵط.Ҫ߼ƳĹ۲ӼĲͬѡ˻ģϵĲͬ߼.,ף7ΪеĹ۲뱻߼Ƴף8,9Ϊһֻй۲һ¼,Ҫκι۲챻߼Ƴ.
Console LTorasso P10ݷгֵĻģϵĲͬ߼,һͳһĶ.ļڸö,һܹ̻ģϿռĻģ͵ϵĸ,Ϲ̽˿̻.ÿ̻֤˻ģ͵뱾ԭ̺/̺ʽֱӹϵ,ӶʹATMS11(assumption-based truth maintenance system)㷨,ǵ۽ʵϵ.
1ģ͵
1. ģ͵DPһԪ顴SD,COMPS,CXT,OBS,SDΪϵͳ,һļ;COMPSΪϵͳɲ,һ޵ĳ;CXTΪʾݵĻԭӼ;OBSΪ͵Ĺ۲켯ĻԭӼ.
CXTOBSÿһԭf(a)ĺΪڲfĹ۲ֵΪa.
2. ֪һDPSD,COMPS,CXT,OBS,ӦDPAPһԪ顴SD,COMPS,CXT,,,ЦOBS,{f(x)f(y)OBS,fÿһyֵx}.
һԪνABζšabnormal ,cCOMPSʱ,AB(c)Ϊ.
3. ֪Cp,Cn,D(Cp,Cn):AB(c)ݡģۡAB(c).
4. ֪һDPԼӦDPAP綨2,D(,COMPS)ΪDPһģ͵,ҽ
1D(,COMPS)߼Ƴ,ÿһmʦ,SDCXT{D(,COMPS)}m.
2D(,COMPS)릷һ,SDCXT{D(,COMPS)}Ȧ.
ԭ,ΪOBSһӼ.OBS{O1,...,On},OBS,{O11,...,O1r}.áOBSʾ{O1...šOn},ʾ{O11...šO1r}.
ɶ4ѵõ¶.
1. ֪DPAP,ڹDPĻģ͵,SDCXTOBSǿ,SDCXTȡOBSҲǿ,ر,SDCXTȡҲǿ.
2̻ģ͵
2.1ģ͵
5. һЩֵĺȡʽCһЩֵĺȡʽDҽCÿһֶD.
6. ֪DPAP,DPĻģ͵ĲΪһD(1,2),ʹöÿһD(1,2)ǵĿD(1,2),:1 SDCXTȦ{D(1,2)}һ,2 ٦,SDCXT{D(1,2)}+ע,SDCXT{D(1,2䣩}ȦһµȼSDCXT{D(1,2䣩}OBS㣩.
һԲ벿Ǹö.ǰ൱ڸÿȡ.൱ڸÿȡOBS.ɸöֱӵõ.
1. ֪DP,DPÿһģ͵Ĳ϶ǹDPĻһԵĲ..
7. ģ͵ǾʵĻģ͵Ĳ:ܸΨһĻģ͵ĲϾ.
ѵó½:D(,COMPS)Ϊһģ͵,ҽһģ͵.Ҳ˵,ʹûģ͵ϿԿ̻ģ͵Ͽռ.ô,μģ͵?ڴ֮ǰ,Ȼعһ뱾صһЩ.
8. ABΪAB(c)AB(c),cCOMPS.ABӾΪABֵȡʽ.
9. ڡSD,COMPS,CXT,OBSһͻǴSDCXTOBSƳһABӾ.һͻΪС,ҽóͻһӾ䶼һͻ.
10. 覲⹫ʽļ,һĻֺȡʽ(Եֵĺȡʽ)Ǧһ̺(Implicant)ҽƳеÿһ.ơǦһԭ̺(Prime Implicant)ҽܸǡǵΨһĦ̺ǡǱ.
11. 覲⹫ʽļ,ƻֵȡʽCΪ̺ʽ(Implicate)ҽƳC.CΪıԭ̺ʽ(Prime Implicate)ҽCӾC,ʹCΪ̺ʽ.
212(̻һԵ). ڡSD,COMPS,CXT,OBSĻһԵSDCXTOBSСͻıԭ̺.
2.2̻ģ͵
2.12ݡDPĻһԲǹDPСͻ̺. 
,áǱʾSDCXTOBSABӾʽıԭ̺ʽĺȡʽ,硫D(i1,j1)...ġD(im,jm),ÿһD(ip,jp),SDCXTOBSD(ip,jp);æʾSDCXTȡABӾʽıԭ̺ʽĺȡʽ,硫D(l1,k1)...ġD(ln,kn),ÿһD(lq,kq),SDCXTȡD(lq,kq),ر,,false.
3̻ģ͵ϣ. ֪DPAP,ΪSDCXTOBSABӾʽıԭ̺ʽ(DPСͻ)ĺȡʽ,ΪSDCXTȡABӾʽıԭ̺ʽĺȡʽ,D(1,2)ΪDPһģ͵,ҽD(1,2)Ϊǡġһԭ̺.
֤:Ҫ.D(1,2)ǹDPһģ͵.֤D(1,2)ǡġ.1֪,D(1,2)ҲǹDPĻһԲ.,2,D(1,2).֤D(1,2),÷֤.Ȼ,ԡеһD(lp,kp),D(1,2)D(lp,kp).D(1,2)ǻģ͵֪,D(1,2)Ϊģ͵Ĳ.ɶ6֪,SDCXT{D(1,2)},SDCXTȡD(1,2).˵,D(1,2)ΪSDCXTȡһ̺ʽ.,һĳһԭ̺ʽ(lq,kq),ʹáD(lq,kq)ΪD(1,2)ȡʽ.༴дĳһD(lq,kq),ʹD(lq,kq)ΪD(1,2)Ӻȡʽ.ȻD(1,2)D(lq,kq).ĶڡһD(lp,kp),D(1,2)D(lp,kp)ì.ԭD(1,2),D(1,2).,D(1,2)ǡġ.ڼһD(1,2),D(1,2)ǡǡġ̺,D(1,2)ǡġ.D(1,2)Ǽ2֪,D(1,2)ǹDPĻһԲ.ɶ6֪,SDCXT{D(1,2)}OBSǿ.ΪSDCXTȡ,,SDCXT{},D(1,2),SDCXT{D(1,2)}.,ɶ6֪,D(1,2)ǻģ͵Ĳ.Ϊ˻ģ͵D(1,2),,D(1,2)D(1,2).˵,D(1,2)ǡǡġıԭ̺.
.D(1,2)ǡǡġһԭ̺.֤֪,һǻģ͵Ĳ.һD(1,2),D(1,2)ǻģ͵Ĳ,ôɱҪԲ֤֪,D(1,2)һǡǡġ̺.Ϊˡǡġıԭ̺,,D(1,2)D(1,2).˵,D(1,2)ǻģ͵.
Կ,öŵ:1 ģ͵ϵĹطΪйصĳͻʶ޹صĺѡ.2 ȡʱ,ֱӵõף12жԻһϵĿ̻,˵,Ǹöһ.ֱϿ,ģ͵ڻһϸСĿAB,֤OBSһ,߼Ƴ.,ʵӦ,ǿȴӡǼĻһϿռ,Ȼͨ豻߼ƳĹ۲Ŀ󦷣,ڸϸСĿAB,ԱҳõĽ.3 Ҫ,֤˻ģ͵뱾ԭ̺ͱԭ̺ʽֱӹϵ,Ӷǵ۽ATMS㷨ϵ.
3ʵ
һͱļΪģ.òΪʽcorrectholedӦڡABoil-cupABoil-cup,ģSD¹ʽ
holed(oil-cup)oil-below-car(present)
holed(oil-cup)oil-level(low)
correct(oil-cup)oil-level(normal)
oil-level(low)engine(on)engine-temperature(high)
oil-level(normal)engine(on)engine-temperature(normal)
濼.DP=SD,COMPS,CXT,OBS.COMPS={oil-cup},OBS={oil-below-car(present)},CXT={engine(on)}.DPӦAP=SD,COMPS,CXT,,,Ц={oil-below-car(absent)}.
ģ걸ģ걸ָÿһ۲ԭSDУ,ȡ={oil-below-car(present)}.Ӧö3,1Ϊholed(oil-cup)correct(oil-cup),Ϊholed(oil-cup).2ǡġıԭ̺Ϊholed(oil-cup).,ģ͵Ϊholed(oil-cup).һǺ.Ϊoil-below-car(present)ԭ걸ģ,holed(oil-cup)oil-below-car(present)Ψһԭ.
ģǲ걸,holed(oil-cup)oil-below-car(present)Ψһԭ,벿oil-cup״̬صĶԭܵoil-below-car(present),ʱ,ֻΨһholed(oil-cup)Ͳ.,ʱȡ,,ɴӡcorrect(oil-cup)holed(oil-cup),ȻǺ.
4ᡡ
 һܹ̻ģϿռĻģ͵ϵĸ,Իģ͵Ϲ̽˿̻.ǽϹطΪйصĳͻʶ޹صĺѡ,֤˻ģ͵뱾ԭ̺/̺ʽֱӹϵ,Ӷǵ۽ʵϵ.
оõȻѧ͹ҽίʿ.
߽ܣŷͮ,Ů,1968,ʿ,ʦ,ҪоΪģ͵,֤.
Ʒ,1945,,ʿʦ,ҪоΪԶ,ģ͵ϼ滮.
ͨѶϵˣŷͮ, 130023,ִѧѧϵ
1997-12-01յԭ,1998-01-23յ޸ĸ
ߵλŷִͮѧѧϵ130023
Ʒɡɽѧݡ510275
E-mail: jutao@mail.interflow.com.cn
ο
1Davis R. Diagnostic reasoning based on structure and behavior. Artificial Intelligence, 1984,24(1-3):347410
2Genesereth M R. The use of design descriptions in automated diagnosis. Artiicial Intelligence, 1984,24(1-3):411436
3Reter R. A theory of diagnosis from first principles. Artificial Intelligence, 1987,32(1):5796
4de Kleer J, Williams B C. Diagnosing multiple faults. Artificial Intelligence, 1987,32(1):97130
5Poole D, Goebel R, Aleliunas R. THEORIST: a logical reasoning system for defaults and diagnosis. In: Cercone M, Calla G MC eds. The Knowledge Frontier. New York: Springer Verlag, 1987. 331352
6Console L,DuprD T, Torasso P. A theory of diagnosis for incomplete causal models. In: Sridharan N S ed. Proceed-ings of the 11th International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan-Kaufmann Publishers, 1989. 13111317
7Poole D. Normality and faults in logic-based diagnosis. In: Sridharan N S ed. Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan-Kaufmann Publishers, 1989. 13041310
8de Kleer J, Williams B C. Diagnosis with behavioral modes. In: Sridharan N S ed. Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan-Kaufmann Publishers, 1989. 13241330
9Struss P, Dressler O. Physical negationintegrating fault models into the generl diagnostic engine. In: Sridharan N S ed. Proceedings of the 11th International Joint Conference on Artificial Intelligence. San Mateo, CA: Morgan-Kaufmann Publishers, 1989. 13181323
10Console L, Torasso P. A spectrum of logical definitions of model-based diagnosis. Computational Intelligence, 1991,7(3):133141
11de Kleer J. An assumption-based tms. Artificial Intelligence, 1986,
28(2):127162
12de Kleer J, Mackworth A K, Reiter R. Characterizing diagnosis and systems. Artificial Intelligence, 1992,56(2-3):197222
1997-12-01յԭ,1998-01-23յ޸ĸ 
