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