1 Image courtesy of JPL Model-based Programming and Constraint-based HMMs Brian C. Williams 16.412J/6.834J March 15 th , 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 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 C i : Assignment of modes to Y ? Diagnosis D i : A candidate such that D i ? 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 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 P i all of whose extensions are diagnoses. ? P i removes all symptoms ?P i entails  (X,Y) ? Obs (implicant) Kernel Diagnosis: A minimal partial diagnosis K i ? K i is a prime implicant of  (X,Y) ? Obs 6 Diagnoses Found by Mapping Conflicts to Kernels Conflict: A set of component modes C i that are inconsistent with the model and observations. ?  (X,Y) ? Obs entails not C i Kernel Diagnosis: A minimal set of component modes K i that eliminate all symptoms. ?K i is a prime implicant of  (X,Y) ? Obs ?K i 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 ? 7 A2=U M1=U M3=UA1=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 () ( ) iij iij yv c pc py v ? ? Assume Failure and Observation Independence P(x i =v ij | 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 (|)(|) (| , ) () iij iij iij p xvcpcObs pc x v Obs px v Bayes’ Rule Normalization 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 Consistent?Keep Compute Posterior p Below Threshold? Extract Conflict Done Yes No Yes No Leading Candidate Based on Priors Sherlock: [de Kleer & Williams, 89] 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 D X ? Mode variables Y with domain D Y ? System model  (X,Y) : D X x D Y o {True, False} ? Observations Obs(X,Y) : D X x D Y o {True, False} Compute: ? Leading Arg Max P(Y | Obs ) Y ? D Y s.t.  X ? D X .  (X,Y) ? OBS(X,Y) is consistent 13 Generalize to Optimal CSP Constraint Satisfaction Problem CSP = <X, D X ,C> ? variables X with domain D X ? Constraint C(X): D X o {True,False} Find X in D X s.t. C(X) is True Optimal CSP OCSP= <Y, g, CSP> ? Decision variables Y with domain D Y ? Utility function g(Y): D Y o? ? CSP is over variables <X,Y> Find Leading arg max g(Y) Y ? D y s.t.  X ? D Y 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 System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller CommandsObservations Plant Titan Model-based Executive State goalsState estimates 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 Fuel tankOxidizer tank Deduces that thrust is off, and the engine is healthy Mode Estimation Mode Reconfiguration Mode Reconfiguration Mode Estimation System Model Control Program RMPL Model-based Program Control Sequencer Deductive Controller CommandsObservations Plant Titan Model-based Executive State goalsState estimates 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 P t (Y| Obs) s.t.  (X,Y) ? O(m’) is consistent arg max R t (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 CommandsObservations Plant Titan Model-based Executive State goalsState estimates 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 P t (Y| Obs) s.t.  (X,Y) ? O(m’) is consistent arg max R t (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 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 = M z + (inflow); vlv=stuck open => Outflow = M z + (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. 21 Simple Mode Reconfiguration Current state Enumerate by increasing immediate cost. Goal “nominal thrust” Find allowed states that entail goal. 22 Conflicts Focus MR Goal: Achieve Thrust A conflict, C, is an assignment to a subset of the control variables that entails the negation of the goal. 23 Goal: Achieve Thrust A conflict, C, is an assignment to a subset of the control variables that entails the negation of the goal. Conflicts Focus MR 24 Goal: Achieve Thrust A conflict, C, is an assignment to a subset of the control variables that entails the negation of the goal. Conflicts Focus MR 25 Goal: Achieve Thrust A conflict, C, is an assignment to a subset of the control variables that entails the negation of the goal. Conflicts Focus MR 26 Performance on Cassini Failure scenario MI time (Sparc 5 in sec) MR time (Sparc 5 in sec) MI time (est Sparc 5 sec) MR time (est Sparc 5 sec) EGA preaim 2.2 1.7 .07 .17 BPLVD 2.7 2.9 .18 .29 IRU 1.5 1.6 .02 .03 EGA burn 2.2 3.6 .08 .03 ACC 2.5 1.9 .04 .02 ME too hot 2.4 3.8 .18 .78 Acc low 5.5 6.1 .25 .05 Number of components: 80 Number of clauses: 11,101 27 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 28 Estimating Dynamic Systems Given sequence of commands and observations: 1. Infer current distribution of (most likely) states 2. Infer (most likely) trajectories S T X 0 X 1 X N-1 X N S T 29 Hidden Markov Model ? X, A, Z : Finite States, Actions & Observations ? T(x,a,x’): State transition function T: X x A o3(X) p(x’|a,x) ? O(x,z): Observation function O: X o3(Z) p(z|x) ? S(x): Initial state distribution S: 3(X) 30 Hidden Markov Models ? X = {Coin 1, Coin 2 } ? Z = {H,T} ? A = {} ? T, O, S: ? Observed sequence: h, t, h, h, h, h, t, h, t, t, h, h, h, h, h ? Hidden sequence: C 1 ,C 1 ,C 1 ,C 1 ,C 1 ,C 2 ,C 2 ,C 2 ,C 2 ,C 1 ,C 1 ,C 2 ,C 2 ,C 2 ,C 2 0.90.9 0.1 0.1 H (0.7) T (0.3) H (0.4) T (0.6) 0.5 0.5 31 HMM Belief Tracking 1) Initialization 2) Induction 1 () () i p xxS 1 1|| 1 (,) ( , ,) ( ) () (|, ) it jti t j jX ti ttt Ox z Tx a x p x px pz a p  dd  ao ?? | () ( | ,,) tt px px zaS PredictCorrect Normalize 32 Concurrent Probabilistic Constraint Automata Standby Engine Model Off Unknown Firing component modes… one per component … operating concurrently On Camera Model Off described by finite domain constraints on variables… (thrust = full) AND (power_in = nominal) (thrust = zero) AND (power_in = zero) (thrust = zero) AND (power_in = nominal) (power_in = zero) AND (shutter = closed) (power_in = nominal) AND (shutter = open) deterministic and probabilistic transitions off- cmd standby- cmd 0.01 0.01 standby- cmd fire- cmd turnon- cmd turnoff- cmd 0.01 0.01 cost/reward 0 v 0 v 2 kv 2 kv 0 v 20 v 0 v Comparison With Path Planning 1 ? Few variables ?O(10 4 )states ? Simple Action & Observation Models ? Hundreds of variables ?O(10 150 ) states (modes) ? Propositional Action & Observation Models How can we avoid enumerating the belief state? 34 Online Mode Estimation Left engine on Observe “no thrust” K-best Filtering: Enumerate by decreasing probability. Track distribution of reachable modes consistent with observations. Track most likely trajectories. 35 Online Mode Estimation Current S i ? S u i W j S O i+1 W k S i+1 Previous Observed Predicted 6 ? Find feasible next states, given current state distribution, commands and next state observations. U S i1 { ? W j ? U S i ?U S P i entails ) jk < jk § ? ¨ · 1 ? ?U 6 ?U 2 i1 where transition W j is specified by a conjunction of formulas ) jk ? next (< jk ) 36 3) Termination 4) Back tracking HMM Trajectory Tracking 1) Initialization 2) Induction 11 1 () ( | ) () 0 ii i i xpzx x GS 1 1|| 1 1|| () (,)max (, ,) ( ) () argmax (, ,) ( ) ti it j jit j jX ti j jit j jX xOxz Txax x xTxaxx GG \ G  dd  dd ao ?? > @ >@ 1|| * 1|| max ( ) arg max ( ) ti iX tti iX Px xx G G dd dd ** 11 () ttt xx 37 Probabilities for Mode Estimation () ( ) iij ii ij yv c cyvSS ? ? ? Initial state for each component is independent ? O(x i, z t ) estimated using model as before. ? Component transitions are independent, given previous state and action. ? T k (x j ,a j ,x ik ) = P(transition) * P(guard_satisfied) ? P(guard_satisfied) estimated from model (,,) (,, ) jji kjjik k Txax Txax ? 38 Enumerating Probable Transitions Generate Candidate Transition Test Target State Against Observations Consistent?Keep Compute Posterior P Using Bayes Rule Below Threshold? Extract Conflict Done Yes No Yes No Leading Candidate Transition Based on Predicted Next State Probability Livingstone: [Williams & Nayak, 97] For Each Component Identify Enabled Transitions And Their Probability Example Pump Valve Driver V1 V2 cmdin Flow v1 Flow v2 Cmdin=on & W vdu =nominal hung Cmdout=none off Cmdout=none on Cmdout=CmdIn W vdu =hang Cmdin=off & W vdu =nominal W vdu =hang VDU Cmdin=open & W valve =nominal stuck Flow=zero closed Flow=zero open Flow|Pressure Cmdin=close & W valve =nominal W valve =stick Valve W valve =stick W vdu P nom 0.999 hang 0.001 W valve P nom 0.997 stick 0.003 ? Valve Driver (VDU) commands valves ? Flow measured at each valve ? VDU may hang, valves may stick shut ? Wcaptures non-determinism of T(s,a,s’)C Multiple Spontaneous Valve Closures Tracking the Most Likely States Probability Time 0 VDU off 1 VDU on Turn on VDU 2 Valves Open Command valves VDU failed Valves Closed No Change 3 Observe flow=0 ? Start with known state(s) ? Track the most likely outcome(s) given observation ? Can be made very fast ? But most likely state may first appear (a priori) arbitrarily unlikely. Pump Valve Driver V1 V2 N-Stage Trajectory Tracking [Kurien & Nayak, 2000] ? Avoid committing to a small number of trajectories ? Build a structure that compactly represents all evolutions ? Generate additional trajectories in order as needed VDU OK Probability Open Valves Valves Open VDU Hung P=0.001 Temporal Conflicts: VDU OK in past V1 open, no V1 flow; VDU OK in past V2 open, no V2 flow; All Valves Stuck closed P=0.00001 time Start Pump ... Valves Closed Open Valves ... Current Conflicts: V1 open, no V1 flow; V2 open, no V2 flow Observe no flow. Graphical Model of Probabilistic Concurrent Constraint Automata Time t vdu W vdu off cmdin open closedv1 Flow v1 zero W v2 Flow v2 zero closed Time t+1 W v1 cmdout v2 none Pump Valve Driver V1 V2 cmdin Flow v1 Flow v2 Cmdin=on & W vdu =nominal hung Cmdout=none off Cmdout=none on Cmdout=CmdIn W vdu =hang Cmdin=off & W vdu =nominal W vdu =hang P(W vdu =nominal)=1-p P(W vdu =hang)= p Trajectory Tracking Framed as an Optimal CSP t=0 vdu W vdu off cmdin on closed v1 Flow v1 zero W v2 Flow v2 zero closed t=1 open zero zero t=2 high high W v1 cmdout v2 nom nom nom nom nom nom on open closed closed open open none on none none t=0 vdu W vdu off cmdin on closed v1 Flow v1 zero W v2 Flow v2 zero closed t=1 open t=2 none W v1 cmdout v2 none ? Assignments to W capture every system trajectory ? Probability of an assignment is defined to be 3 components 3 time P(W component,t ) ? Trajectories can be generated in prior probability order Focusing on Consistent Trajectories cmdin Flow v1 Flow v2 cmdout t=0 vdu W vdu off on closed v1 zero W v2 zero closed t=1 open zero zero t=2 high high W v1 v2 nom nom nom nom nom nom on open closed closed open open none on none none Observe: Flow v1 = zero noGood = {W vdu,0 =nom,W v1,1 =nom,W v1,0 =nom} Observe: Flow v2 =zero noGood = {W vdu,0 =nom,W v2,1 =nom,W v2,0 =nom} t=0 vdu W vdu off on closed v1 zero W v2 zero closed t=1 open zero zero t=2 zero zero W v1 v2 Hang nom nom nom nom nom Hung open closed closed closed closed none Hung none none Flow v2 Flow v1 cmdin cmdout t=0 t=1 t=2 vdu W vdu off on closed v1 zero W v2 zero closed open zero zero zero zero W v1 v2 nom nom nom nom Stick on open closed closed stuck stuck none on none none Flow v2 Flow v1 cmdin cmdout Stick CBFS zero zero ARC/Boeing Online Mode Estimation Demonstrations ? In-situ (e.g., Mars) propellant production ?testbedin 00. ? Integrated into 3T architecture ? Control of bioregenerative life support ? Flown on Deep Space One ? Deployed on interferometry testbed ? L2 integrated into IVHM architecture ? Experiment on X34 in ‘02 ? Experiment on X37 in ‘03 Jet Propulsion Lab NASA KSC NASA JSC NASA ARC/KSC/GRC Orbital Sciences 46 Model-based Programming ? To survive decades embedded systems orchestrate complex regulatory and immune systems. ? Future systems will be programmed with models, describing themselves and their environments. ? Runtime kernels will be agile, deducing and planning by solving optimization problems with propositional constraints. ? OpSat problems are solved efficiently by combining conflict-recognition and A* search to leap over leading inconsistent solutions. Images courtesy of NASA.