麻省理工学院：《自制决策制造原则》英文版 Conflict-directed Diagnosis

Conflict-directed Diagnosis Brian c。 WIllams 1641013 November 5th 2003 CourtesyofNasa/jpl-calTech.http://www.jpl.nasagov

10/03/03 copyright Brian Williams, 2003 1 Courtesy of NASA/JPL-Caltech. http://www.jpl.nasa.gov. Conflict-directed Diagnosis Brian C. Williams 16.410-13 November 5th 2003 Brian C. Williams, copyright 2000

WORLD observations Plant actions sense act Diagnostic Agent AGENT Monitors diagnoses Repairs avoids Probes and tests Symptom-directed 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 2 sense P(s) WORLD observations actions AGENT Diagnostic Agent: • Monitors & Diagnoses • Repairs & Avoids • Probes and Tests Plant act Symptom-directed

Consistency-based Diagnosis And( Orl G() LE O Andl Out(=In1( AND In20 l11 U0) ALL components have Or3 unknown mode”U, Whose assignment is never mentioned inC Diagnosis=AlG, A2=U 01=G, 02=U, 03=G Obs Assignment to O Candidate C;: Assignment of modes to X Diagnosis D;: A candidate such that DA Obs A c(X,Y) is satisfiable 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 3 Consistency-based Diagnosis And(i): ƒ G(i): Out(i) = In1(i) AND In2(i) ƒ U(i): ƒ Obs: Assignment to O ƒ Candidate Ci: Assignment of modes to X ƒ Diagnosis Di : A candidate such that Di š Obs š C(X,Y) is satisfiable. 1 1 1 1 0 Or1 Or3 And1 A B C D E F G X Y Z 0 1 Diagnosis = {A1=G, A2=U O1=G, O2=U, O3=G} ALL components have “unknown Mode” U, Whose assignment is never mentioned in C

Out line Diagnosis as Learning from symptoms and Conflicts Conflict learning Single-fault diagnosis Multiple-fault diagnosis 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 4 Outline ƒ Diagnosis as Learning from symptoms and Conflicts ƒ Conflict learning ƒ Single-fault diagnosis ƒ Multiple-fault diagnosis

Learning Conflicts From Symptoms Orl 11110 B 1Am人E0 Or2 And3 G eOr Symptom F is observed o, but should be 1 if ol, o2 and al are okay Conflict: Al=G, ol=G, 02=G is inconsistent At least al=0. o1=0. or 02=U 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 5 Or1 Or2 And1 A B C D E 1 1 1 1 F G X Y Z Symptom: F is observed 0, but should be 1 if O1, O2 and A1 are okay. Conflict: {A1=G, O1=G, O2=G} is inconsistent F 0 1 1 1 ĺAt least A1=U, O1=U, or O2=U Learning Conflicts From Symptoms 0 Or3 And3

Find Symptom Using Unit Propagation true false false true C2: pv-t CI:rvg VR procedure propagate(c) ∥ C is a clause if all literals in C are false except l, and I is unassigned then assign true to and record c as a support for l and for each clause C mentioning not I propagate(C) end propagate 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 6 r q p C2: ¬ p ›¬ t true false true t false procedure propagate ( C) // C is a clause if all literals in C are false except l, and l is unassigned then assign true to l and record C as a support for l and for each clause C’ mentioning “not l”, propagate (C’ ) end propagate C1 : ¬r › q ›p Find Symptom Using Unit Propagation

Find Symptom Using Unit Propagation 0=C A=1 (F=1)y-(F=0) (O1=G)v-(A=1)vX-1+X=1 F=1 F A=G→+A1=0X-1)Y-Y=1)VF=1 (02=G)-(B=1)Y=1+y=1 02=G B=1 10/03/03 copyright Brian Williams, 2003 7

10/03/03 copyright Brian Williams, 2003 7 Find Symptom Using Unit Propagation ™(O1=G) › ™(A=1) › X=1 ™(A1=G) › ™(X=1) › ™(Y=1) › F=1 ™(O2=G) › ™(B=1) › Y=1 O1=G ™(F=1) › ™(F=0) O2=G B=1 A=1 X=1 Y=1 A1=G F=1 F=1

Find Symptom Using Unit Propagation A=1 true 0=C A=1 (F=1)y-(F=0) (O1=G)v-(A=1)vX-1+X=1 true F=1 F=1 AIG+(Al=G)V(X-1)V=(Y=I)VF=1 F=l (02=G)-(B=1)Y=1+y=1 true 02=G B=1 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 8 Find Symptom Using Unit Propagation ™(O1=G) › ™(A=1) › X=1 ™(A1=G) › ™(X=1) › ™(Y=1) › F=1 ™(O2=G) › ™(B=1) › Y=1 ™(F=1) › ™(F=0) B=1 O1=G B=1 true O2=G A=1 A=1 true X=1 Y=1 A1=G F=1 F=1 F=1 true

Find Symptom Using Unit Propagation O1=G A= A true true 01=GA= (F=1)y-(F=0) 01=G-(A=1)VX=1+X= true F=1 F=1 Al=G M=→Al=Gy(Xy-(x)PF true (02=G)-(B=1)Y=1+y=1 true true 02=GB= 02=G 10/03/03 copyright Brian Williams, 2003

10/03/03 copyright Brian Williams, 2003 9 Find Symptom Using Unit Propagation ™(O1=G) › ™(A=1) › X=1 ™(A1=G) › ™(X=1) › ™(Y=1) › F=1 ™(O2=G) › ™(B=1) › Y=1 ™(F=1) › ™(F=0) O1=G B=1 O1=G true B=1 true O2=G O2=G true A=1 A=1 true X=1 Y=1 A1=G A1=G true F=1 F=1 F=1 true

Find Symptom Using Unit Propagation O1=G A= A true true 01=GA= (F=1)y-(F=0) true 01=G)-(A=1)VX=1+X=1 true F=1 F=1 M=→Al=Gy(X=y(x)VPF true true (02=G)V-(B=1)Y=1+y=1 true true 02=GB= O2=G 10/03/03 copyright Brian Williams, 2003 10

10/03/03 copyright Brian Williams, 2003 10 Find Symptom Using Unit Propagation ™(O1=G) › ™(A=1) › X=1 ™(A1=G) › ™(X=1) › ™(Y=1) › F=1 ™(O2=G) › ™(B=1) › Y=1 ™(F=1) › ™(F=0) O1=G B=1 O1=G true B=1 true O2=G O2=G true A=1 A=1 true X=1 true Y=1 true A1=G A1=G true F=1 F=1 F=1 true