A Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMMs Stanislav funiak 16. 412/6.834 Lecture, 15 March 2004 References Hofbaur, M. W, and Williams, B C(2002). Mode estimation of probabilistic hybrid systems. In: Hybrid Systems: Computation and Control Hscc 2002 Funiak, S, and Williams, B. C (2003 ). Multi-modal particle filtering for hybrid systems with autonomous mode transitions. In: DX-2003 SafeProcess 2003 Lerner, U.,R. Parr, D. Koller and G. Biswas(2000). Bayesian fault detection and diagnosis in dynamic systems. In: Proc. of the 17th National Conference on A I. pp 531-537. V. Pavlovic. J Rehg, T -J]. Cham, and K Murphy. A Dynamic Bayesian Network Approach to Figure Tracking Using Learned Dynamic Models. In Proc. ICCV 1999 H A P. Blom and Y. Bar-Shalom. The interacting multiple model algorithm for systems with Markovian switching coefficients. IEEE Transactions on Automatic Control, 33, 1988 Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 2004
16.412 / 6.834 Lecture, 15 March 2004 1 Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMMs Stanislav Funiak Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 2 References z Hofbaur, M. W., and Williams, B. C. (2002). Mode estimation of probabilistic hybrid systems. In: Hybrid Systems: Computation and Control, HSCC 2002. z Funiak, S., and Williams, B. C. (2003). Multi-modal particle filtering for hybrid systems with autonomous mode transitions. In: DX-2003, SafeProcess 2003. z Lerner, U., R. Parr, D. Koller and G. Biswas (2000). Bayesian fault detection and diagnosis in dynamic systems. In: Proc. of the 17th National Conference on A. I.. pp. 531-537. z V. Pavlovic. J. Rehg, T.-J. Cham, and K. Murphy. A Dynamic Bayesian Network Approach to Figure Tracking Using Learned Dynamic Models. In: Proc. ICCV, 1999. z H.A.P. Blom and Y. Bar-Shalom. The interacting multiple model algorithm for systems with Markovian switching coefficients. IEEE Transactions on Automatic Control, 33, 1988
A Hybrid Models Hidden markov model Dynamic systems p(x0) faile Process model is p(x,.) x=Ax,+ Br Measurement model i F,= Hx+r Applications: Applications: topological localization target tracking localization and mapping Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Outline Applications: fault diagnosis, visual tracking Switching linear Gaussian models exact filtering Probabilistic Hybrid Automata filtering Approximate Gaussian filtering with hybrid HMM models Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 2004
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 3 Hybrid Models Hidden Markov model on failed off p(x0) p(xt | xt-1) p(zt | xt ) Dynamic systems ? Applications: - target tracking - localization and mapping - … Applications: - topological localization Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 4 Outline z Applications: fault diagnosis, visual tracking z Switching linear Gaussian models + exact filtering z Probabilistic Hybrid Automata + filtering z Approximate Gaussian filtering with hybrid HMM models fx(t1)|z(t1)(x|z1) fx(t2)|z(t2)(x|z2) fx(t2)|z(t1),z(t2)(x|z1,z2) Z1 X x1 x2 Z1 Z2 Z1 Z2 X σ σ σ µ Process model is xt = Axt-1 + But-1 + qt-1 Measurement model is zt = Hxt-1 + rt Image adapted from Maybeck
A Scenario 1: Wheel monitoring for planetary rovers Continuous variables: linear and angular velocity o( Discrete variable: wheel failed (if any) D Normal trajectory and trajectories ith fault at each Courtesy NASA JPL Courtesy of Vandi verma. Used with permission Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 A Scenario 2: Diagnosing subtle faults [Haw 2002 Discrete variables: operational mode closed, open, stuck-closed, stuck-open) Continuous variables: CO2 flow, CO2& O2 conc./courtesy NASA JSC BIO-Plex plant growth chamber Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 2004
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 5 Scenario 1: Wheel monitoring for planetary rovers Discrete variable: wheel failed (if any) Continuous variables: linear and angular velocity Normal trajectory and trajectories with fault at each wheel Courtesy NASA JPL Courtesy of Vandi Verma. Used with permission. Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 6 Scenario 2: Diagnosing subtle faults [H&W 2002] Discrete variables: operational mode Continuous variables: CO2 flow, CO2 & O2 conc. {closed, open, stuck-closed, stuck-open} Courtesy NASA JSC
A Scenario 3: Visual pose tracking Discrete variables: type of movement Continuous variables: head, legs, and torso position Courtesy Pavlovic. J. Rehg, T.-J. Cham, and K. Murphy Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Scenarios 1-3: Common properties 1.Continuous dynamics 2. Finite set of behaviors, determines dynamics Continuous state hidden Noisy observations Need continuous statistical estimation Uncertainty in the model Need both System may switch Need to track discrete changes between behaviors Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 200
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 7 Scenario 3: Visual pose tracking Discrete variables: type of movement Continuous variables: head, legs, and torso position Courtesy Pavlovic. J. Rehg, T.-J. Cham, and K. Murphy Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 8 Scenarios 1-3: Common properties 1. Continuous dynamics 2. Finite set of behaviors, determines dynamics z Continuous state hidden z Noisy observations z Uncertainty in the model z System may switch between behaviors Need continuous statistical estimation Need to track discrete changes Need both
A Outline Applications: fault diagnosis, visual tracking Switching linear Gaussian models exact filtering Probabilistic Hybrid Automata filtering Approximate Gaussian filtering with hybrid HMM models Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Hybrid models- Desired properties u A A A3 CA State evolution Stochastic continuous evolution(uncertain model) Gaussian noise(for KF) Probabilistic discrete transitions Continuous observations, discrete and continuous actions Interaction of discrete and continuous state Discrete state affects continuous evolution Continuous state affects discrete evolution Large systems Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6412/6.834 Lecture,15 March2004
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 9 Outline z Applications: fault diagnosis, visual tracking z Switching linear Gaussian models + exact filtering z Probabilistic Hybrid Automata + filtering z Approximate Gaussian filtering with hybrid HMM models Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 10 Hybrid models – Desired properties z State evolution: Stochastic continuous evolution (uncertain model) Gaussian noise (for KF) Probabilistic discrete transitions Continuous observations, discrete and continuous actions z Interaction of discrete and continuous state: Discrete state affects continuous evolution Continuous state affects discrete evolution z Large systems 1 2 uc1 ud1 ud2 wc1 3 yc2 yc1 vs1 vs3 vo1 vo2 A A CA A vs2
A Graphical models revisited Actions Transition distribution P(x, ai,x,) Observation distribution Beliefs p(zx) p(x, ai,x Observations (Z1 Z2 p(21|x) observable Hidden States Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 11 Review: Hidden markov models Actions Beliefs Observations(Z) Ave States Discrete states actions and observations Transition observation p. written as tables Belief update P,(x)=p(,|x∑px|a,x) Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 2004
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 11 Graphical models revisited a1 b1 Z1 x1 b2 Z2 x2 ( | , ) j i i p x a x Actions Beliefs Observations States Observable Hidden ( | ) i i p z x Model: Transition distribution Observation distribution ( | ) i i p z x ( | , ) j i i p x a x Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 12 Review: Hidden Markov models z Discrete states, actions, and observations z Transition & observation p. written as tables a1 b1 Z1 x1 b2 Z2 x2 ( | , ) j i i p x a x Actions Beliefs Observations States Observable Hidden 7 11 5 9 77 Mass Ave Belief update:
A Review Linear models Kalman filter Actions States Acti Continuous states, actions and observations Linear(linearized) process and measurement model A x,+ Bu,+ qi z,=Hx, +r K,=C H(HC, H+R) 元=A1+B,元=x+K,(z,-H1) C,=ACHA+O C,=(I-K,)C Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Switching Linear Systems(SLDS) Discrete and continuous state Also known as jump Markov linear Gaussian model Actions Discrete states(modes) Beliefs Pr(d d r(d)=丌o P(r la, x,) Observations (Z, Continuous state p(zlx) Observable Hidden xu 1=A(duD),+b(dusu, Continuous (X1 +qn(d1+1) states y,=Hx, +r Discrete states d,bd( d2)
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 13 Review: Linear models, Kalman Filter z Continuous states, actions, and observations z Linear (linearized) process and measurement model a1 b1 Z1 x1 b2 Z2 x2 ( | , ) j i i p x a x Actions Beliefs Observations States Observable Hidden t t1 t1 t1 x Ax Bu q t t t z Hx r Belief update: Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 14 Switching Linear Systems (SLDS) z Discrete and continuous state z Also known as jump Markov linear Gaussian model a1 b1 Z1 x1 b2 Z2 x2 ( | , ) t 1 t p x a x Actions Beliefs Observations Continuous states Observable Hidden ( | ) t t p z x d1 d2 Discrete states Discrete states (modes): 0 0 1 Pr( ) Pr( | ) S d dt dt Continuous state: ( ) ( ) ( ) ( ) 0 0 0 1 1 1 1 1 x v d y Hx r q d x A d x B d u t t t t t t t t t t ( | ) p dt1 dt
A Example: Acrobatic robot tracking H failed a1,2,1,02 Pr(d,+Id, )0=0.+, 6r+noise A(ok) B2k +B2d+noise B(ok) 0995 gok) 02h1=2.w(01 011, 02s, 02s, a)+noise 0.005 a(failed) +0.d+noise 0 Bk+=fimo (01 ,01. ,024, 021, d7)+noise b(failed) 02xn=f2m(04, 018, 21, 02n, ) noise q(failed) Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Example cont'd The actuator works until t=20, then breaks t=18 A(ok) A(ok) A(ok)A(ok B(ok) B(ok) B(ok)B(ok) A(failed ok) q(ok) q(ok) B(failed) q(failed)
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 15 Example: Acrobatic robot tracking ok failed 0.005 0.995 1.0 µ µ T 1 2 1 2 T ,T ,T ,T f t noise f t noise t noise t noise k yes k k k k k yes k k k k k k k k k k ( , , , , ) ( , , , , ) 2, 1 2, 1, 1, 2, 2, 1, 1 1, 1, 1, 2, 2, 2, 1 2, 2, 1, 1 1, 1, T T T T T G T T T T T G T T T G T T T G f t noise f t noise t noise t noise k no k k k k k no k k k k k k k k k k ( , , , , ) ( , , , , ) 2, 1 2, 1, 1, 2, 2, 1, 1 1, 1, 1, 2, 2, 2, 1 2, 2, 1, 1 1, 1, T T T T T G T T T T T G T T T G T T T G A(ok) A( failed) B(ok) B( failed) q(ok) q( failed) Pr( | ) t 1 t d d , (0,0.01) 0 0 1 0 H r N » » » » ¼ º « « « « ¬ ª Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 16 Example cont’d z The actuator works until t=20, then breaks ok ok ok ok failed A(ok) B(ok) q(ok) A( failed) B( failed) q( failed) A(ok) B(ok) q(ok) A(ok) B(ok) q(ok) A(ok) B(ok) q(ok) t=17 t=18 t=19 t=20 … t=21
A What questions? Mode estimation Given a,z1.. azu estimate d, Application: fault diagnosis Continuous state estimation Given a,z,.azu estimate x, Application: tracking Hybrid state estimation Given a,z1..azy estimate x, d, Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Exact filtering for SLds Main ide Do estimation for each sequence of mode assignments Sum up the assignments that end in the same mode Each Gaussian has an associated weight(probability) Maths: p(x1,d,| ∑p(x,d1d1|a11a1z,) P(x1,d1…d1|a121a2z,) =p(x,|d1…d,a1z1a12,) p(d1…d1|a11-a-,) Probability of a mode seq Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 6. 412/6.834 Lecture, 15 March 200
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 17 What questions? z Mode estimation: Given a1z1 … at zt , estimate dt Application: fault diagnosis z Continuous state estimation Given a1z1 … at zt , estimate xt Application: tracking z Hybrid state estimation Given a1z1 … at zt , estimate xt , dt Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 18 Exact filtering for SLDS z Main idea: Do estimation for each sequence of mode assignments Sum up the assignments that end in the same mode Each Gaussian has an associated weight (probability) ok ok failed ok failed ok failed Maths: ( , ... | ... ) ( , | ... ) 1 1 ... 1 1 1 1 1 t t d d t t t t t t p x d d a z a z p x d a z a z t ¦ ( ... | ... ) ( | ... , ... ) ( , ... | ... ) 1 1 1 1 1 1 1 1 1 t t t t t t t t t t t p d d a z a z p x d d a z a z p x d d a z a z Continuous tracking Probability of a mode sequence
A Continuous tracking Back to our example: Know 1. Model A, B each each t 2. Observation t=17 t=18 t=19 t=20 Can do kalman filterin as before Se A(ok ( ok) A(ok) A(ok) B(ok) B(ok) B(ok) B(ok) a(failed) ok) q(ok) q(ok) q(ok) BAiled) ∧N Kalman filter: @ C(D P(x, d., a,za, z,)=N(o, C) Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16412/6.834 Lecture,15 March2004 Probability of a mode sequence(1/2) Challenge: Can we update p(d.,az.a, z,) efficiently? p(d1…d-1=0k.0k|a121…a1z1-) ok p(d1…d,=ok… ok failed 1, Prediction p(d1…d, d .d P(d, d.-,a, z independence a121…,a1z1)p(dn|d1) Discrete discrete transition probability
Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 19 Continuous tracking Back to our example: ok ok ok ok failed A(ok) B(ok) q(ok) A( failed) B( failed) q( failed) A(ok) B(ok) q(ok) A(ok) B(ok) q(ok) A(ok) B(ok) q(ok) t=17 t=18 t=19 … Know: 1. Model A,B each each t 2. Observations 3. Actions Can do Kalman filtering as before ( ) ( ) ˆ , i t i xt C Sequence (i) Kalman filter: ( | ... , ... ) (ˆ , ) ( ) ( ) 1 1 1 i t i p xt d dt a z atzt N xt C ( ) ˆ i t x (i) Ct ( ) 1 ˆ i t x t=20 Hybrid Mode Estimation and Gaussian Filtering with Hybrid HMM Models 16.412 / 6.834 Lecture, 15 March 2004 20 Probability of a mode sequence (1/2) Challenge: Can we update efficiently? ( ... | ... ) 1 t 1 1 t t p d d a z a z a1 b1 Z1 x1 b2 Z2 x2 ( | , ) t 1 t p x a x Actions Beliefs Observations Continuous states Observable Hidde n ( | ) t t p z x d1 d2 Discrete states ( | ) t 1 t p d d ok ok ok ok failed ( ... ... | ... ) 1 t1 1 1 t1 t1 p d d ok ok a z a z ( ... ... | ... ) 1 t 1 1 t t p d d ok ok failed a z a z 1. Prediction: ( | ... , ... ) ( ... | ... ) ( ... | ... ) 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 t t t t t t t t t t p d d d a z a z p d d a z a z p d d a z a z ( ... | ... ) ( | ) 1 t1 1 1 t1 t1 p dt dt1 p d d a z a z conditional probability independence discrete transition probability