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]
Outline Review of Diagnosis and Mode Estimation Generalizing mode estimation to Optimal CSPs Model-based Programming W/o State Mode Estimation as Trajectory Tracking Mode estimation is an Optimization Problem Given System variables X with domain Dx Mode variables Y with domain Dy System model p(X,Y): DxX D> True, False Observations Obs(X,Y): DxX Dy >True, Falsel Compute Leading Arg Max P(Y I Obs st.彐X∈Dx.WQX,Y)∧OBS(X,Y) is consistent
11 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 12 Mode Estimation is an Optimization Problem Given: System variables X with domain DX Mode variables Y with domain DY System model Ȍ(X,Y) : DX x DYo {True, False} Observations Obs(X,Y) : DX x DYo {True, False} Compute: Leading Arg Max P(Y | Obs ) Y DY s.t. X DX . Ȍ(X,Y) OBS(X,Y) is consistent
Generalize to Optimal CsP Constraint Satisfaction Problem CSP= variables X with domain Dx Constraint C(×):Dx→{True, False} Find X in Dxst. C(X)is True Optimal CSP OCSP=界 CSP is over variables Find Leading arg max gY) Y∈D staXE DY s.t. C(,Y)is True Outline Review of Diagnosis and Mode Estimation Generalizing mode estimation to Optimal csPs Model-based Programming w/o State Mode Estimation as Trajectory Tracking
13 Generalize to Optimal CSP Constraint Satisfaction Problem CSP = variables X with domain DX Constraint C(X): DX o {True,False} Find X in DX s.t. C(X) is True Optimal CSP OCSP= Decision variables Y with domain DY Utility function g(Y): DY o CSP is over variables Find Leading arg max g(Y) Y Dy s.t. X DY s.t. C(X,Y) is True 14 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
RMPL Model-based Program Titan Model-based Executive Control Program Generates target goal states Queries(hidden) states conditioned on state estimates Asserts(hidden) state System Model State estimates Track Tracks least likel cost goal states alve plant states Open 9 001-A Stuck Open Stuck Closed Observations Commands closed inflow= outflow= Plant Example: The model-based program sets engine s thrusting, and the deductive controller Mode Oxidizer tank Fuel tank Mode reconfiguration Estimation Deduces that Plans actions thrust is off. and to open the engine is healthy six valves Deduces that a valve failed-stuck closed Determines that valves on the backup engine will achieve thrust. and plans needed actions Mode reconfiguration ode estimation
System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller Observations Commands Plant Titan Model-based Executive State estimates State goals Mode Estimation Mode Reconfiguration Tracks likely plant states Tracks least cost goal states z Executes concurrently z Preempts z Queries (hidden) states z Asserts (hidden) state Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Generates target goal states conditioned on state estimates Example: The model-based program sets engine = thrusting, and the deductive controller . . . Determines that valves on the backup engine will achieve thrust, and plans needed actions. Deduces that a valve failed - stuck closed Plans actions to open six valves Oxidizer tank Oxidizer tank Fuel tank Fuel tank Deduces that thrust is off, and the engine is healthy Mode Estimation Mode Reconfiguration Mode Reconfiguration Mode Estimation
Mode estimation Mode reconfiguration Select a most likely set of Select a least cost set of component modes that are commandable component consistent with the model and modes that entail the current observations goal, and are consistent System Model State estimates Tracks Tracks least likel cost goal states plant states arg min P(Y Obs) rg max R(Y) s.t. P(X,Y)AO(m)is consistent s.t.P(X,Y) entails G(X,Y) ons PI S.t. Y(X, Y) is consistent RMPL Model-b/OpSat I-based Executive Control pro arg min f(x) s.t. C(x)is satisfiable get goal states D(x)is unsatisfiable state estimates Asserts (hic System Model State estiman State goals Track Tracks least likely cost goal states plant state arg min P(Y Obs) arg max R(Y) s.t. P(X,Y)AO(m)is consistent s.t.Y(X,Y) entails G(X,Y) ons Pl s.t. Y(.Y) is consistent
System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller Observations Commands Plant Titan Model-based Executive State estimates State goals Mode Estimation Mode Reconfiguration Tracks likely plant states Tracks least cost goal states z Executes concurrently z Preempts z Queries (hidden) states z Asserts (hidden) state Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Generates target goal states conditioned on state estimates Mode Reconfiguration: Select a least cost set of commandable component modes that entail the current goal, and are consistent Mode Estimation: Select a most likely set of component modes that are consistent with the model and observations arg min Pt (Y| Obs) s.t. Ȍ(X,Y) O(m’) is consistent arg max Rt (Y) s.t. Ȍ(X,Y) entails G(X,Y) s.t. Ȍ(X,Y) is consistent System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller Observations Commands Plant Titan Model-based Executive State estimates State goals Mode Estimation Mode Reconfiguration Tracks likely plant states Tracks least cost goal states z Executes concurrently z Preempts z Queries (hidden) states z Asserts (hidden) state Closed Valve Open Stuck open Stuck closed Open Close 0. 01 0. 01 0.01 0.01 inflow = outflow = 0 Generates target goal states conditioned on state estimates arg min Pt (Y| Obs) s.t. Ȍ(X,Y) O(m’) is consistent arg max Rt (Y) s.t. Ȍ(X,Y) entails G(X,Y) s.t. Ȍ(X,Y) is consistent OpSat: arg min f(x) s.t. C(x) is satisfiable D(x) is unsatisfiable
A Simple Concurrent State Model a device is described by a set of components communicating through shared variables A component has a set of modes and state variables Modes are mutually exclusive and collectively exhaustive All components include the unknown mode A mode has a vv=open→> v= stuck open→> probability Outflow= M,(inflow); Outflow =M,(inflow); Open state constraint open Stuck Closed closed lv= closed→> vlv= stuck closed→> Outflow =0: Outflow= 0 Unknown Simple Mode Estimation Find most likely modes consistent with observations Goal: Left engine on Observe no thrust 自点 Enumerate by decreasing prior probability Update by Bayes rule
19 Closed Open Stuck open Stuck closed Cost 5 Prob .9 A Simple Concurrent State Model A device is described by a set of components communicating through shared variables. A component has a set of modes and state variables. Modes are mutually exclusive and collectively exhaustive All components include the unknown mode. A mode has a: probability cost state constraint Vlv = closed => Outflow = 0; vlv=open => Outflow = Mz + (inflow); vlv=stuck open => Outflow = Mz + (inflow); vlv=stuck closed=> Outflow = 0; Unknown 20 Simple Mode Estimation Goal: Left engine on Observe “no thrust” Enumerate by decreasing prior probability. Update by Bayes rule. Find most likely modes consistent with observations