Model-based Programming and constraint-based hmms Brian c williams 16412J/6834J March 15th 2004 Image courtesy of JPL Brian C Williams, copyright Outline Review of Diagnosis and Mode Estimation Generalizing mode estimation to Optimal csPs Model-based Programming w/o State Mode Estimation as Trajectory Tracking
1 Image courtesy of JPL Model-based Programming and Constraint-based HMMs Brian C. Williams 16.412J/6.834J March 15th, 2004 Brian C. Williams, copyright 2000 2 Outline x Review of Diagnosis and Mode Estimation x Generalizing Mode Estimation to Optimal CSPs Model-based Programming w/o State Mode Estimation as Trajectory Tracking
Model-based Diagnosis a failure is a discrepancy between the model and observations of an artifact a diagnosis restores consistency 1. Enumerate candidates in order of likelihood 2. Test novel failures by suspending constraints and testing consistency 3. Symptoms in candidate identify conflicting modes 4. Conflicts prune remaining candidates Consistency-based Diagnosis Ando Orl G(0 AndI Out(=In1( AND In2 U() .ALL components have “ unknown mode EOr .U never assigned in C Diagnosis =Al=G, A2=U O1=G, O2=U, 03=G Model u(X,Y over system variables X and mode variables y Obs AsSignment toOcX∪Y Candidate C:: Assignment of modes to Y Diagnosis D A candidate such that D1^Obs∧甲(X,Y) is satisfiable
3 Model-based Diagnosis • A failure is a discrepancy between the model and observations of an artifact. • A diagnosis restores consistency. 1. Enumerate candidates in order of likelihood. 2. Test novel failures by suspending constraints and testing consistency. 3. Symptoms in candidate identify conflicting modes. 4. Conflicts prune remaining candidates. 4 Consistency-based Diagnosis And(i): G(i): Out(i) = In1(i) AND In2(i) U(i): Model: Ȍ(X,Y) over system variables X and mode variables Y Obs: Assignment to O X Y Candidate Ci : Assignment of modes to Y Diagnosis Di : A candidate such that Di Obs Ȍ(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. •U never assigned in C
Compact Encoding Kernel Diagnoses MI Kernel diagnosis A1-上10 {A2=U,M2=U} G12 MhZ Partial Diagnosis: A set of component modes P all of whose extensions are diagnoses Pi removes all symptoms Pi entails P(X,Y)A Obs (implicant) Kernel Diagnosis: A minimal partial diagnosis K Ki is a prime implicant of y(, Y)A Obs Diagnoses Found by Mapping Conflicts to Kernels 12 M3 Conflict: A set of component modes Ci that are inconsistent with the model and observations p(X,Y)A Obs entails not C Kernel Diagnosis: A minimal set of component modes Ki that eliminate all symptoms Ki is a prime impli Ki is a prime implicant of all(minimal)conflicts
5 ? 3 ? 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ? Kernel Diagnosis = {A2=U, M2=U} Compact Encoding: Kernel Diagnoses Partial Diagnosis: A set of component modes Pi all of whose extensions are diagnoses. • Pi removes all symptoms • Pi entails Ȍ(X,Y) Obs (implicant) Kernel Diagnosis: A minimal partial diagnosis Ki • Ki is a prime implicant of Ȍ(X,Y) Obs 6 Diagnoses Found by Mapping Conflicts to Kernels Conflict: A set of component modes Ci that are inconsistent with the model and observations. • Ȍ(X,Y) Obs entails not Ci Kernel Diagnosis: A minimal set of component modes Ki that eliminate all symptoms. • Ki is a prime implicant of Ȍ(X,Y) Obs • Ki is a prime implicant of all (minimal) conflicts M1 M2 A1 A B C D E 3 2 2 3 F G X Y Z 10 6 6 12 M3 A2 ? 3 ? 2 2 3 3 M1 M3 A1 A B C D E F G X Y Z 10 12 ?
Conflicts Map To Kernels by Minimal Set Covering Conflicts MI=U M2=U Al=U MI=U. M2=U Al=U A2=U M3=U MI=U M3=U A2=UMI=U Al=U MI=U Ml=U∧A2=U M2=U∧M3=U Ranking Diagnoses by Probability ()=p Assume Failure and Observation Independence y=vi∈C p(clx,=v Obs)=P(x,=v lc)p(c Obs) Bayes Rule P(X=V I c)estimated using Model normalization If previous Obs, c and 4 entails z=V Then p(z=v c)=1 If previous obs, c and entails x <> V Then p(z=V c)=0 If y consistent with all values for z Then p(x=v c)is based on priors E.g. uniform prior= 1/m for m possible values of x
7 A2=U M1=U A1=U M3=U A1=U, A2=U, M1=U, M3=U A1=U M1=U M2=U A1=U M1=U M1=U A2=U M2=U M3=U Conflicts Map To Kernels by Minimal Set Covering A1=U, M1=U , M2=U Conflicts 8 Ranking Diagnoses by Probability () ( ) i ij i ij yv c pc py v Assume Failure and Observation Independence P(xi =vij | c) estimated using Model: If previous Obs, c and Ȍ entails z = v Then p(z = v | c) = 1 If previous obs, c and Ȍ entails x <> v Then p(z = v | c) = 0 If Ȍ consistent with all values for z Then p(x = v | c) is based on priors E.g., uniform prior = 1/m for m possible values of x ( |)(| ) (| , ) ( ) i ij i ij i ij p x v c p c Obs p c x v Obs px v Bayes’ Rule Normalization
会 Diagnosis as conflict-directed MERS Best first search Increasin Cost Conflict 1 Infeasible Conflict 2 Feasible Enumerating Probable Candidates MERS Leading CandidateGenerate Based on priors Candidate Test Candidate Yes eep Consistent Extract Conflict Posterior p Yes No Done Below Threshold Sherlock: [de Kleer Williams]
9 Increasing Cost Feasible Infeasible Conflict 3 Conflict 2 Conflict 1 Diagnosis as Conflict-directed Best First Search 10 Enumerating Probable Candidates Generate Candidate Test Candidate Keep Consistent? Compute Posterior p Below Threshold? Extract Conflict Done Yes No Yes No Leading Candidate Based on Priors Sherlock: [de Kleer & Williams, 89]