1Mining Hybrid Models from DataClaire J. TomlinHamsa Balakrishnan, Inseok HwangDepartment of Aeronautics and AstronauticsDepartment of Electrical EngineeringStanford UniversityMay 2005Background and Outline• Tools for the analysis and control of hybrid systems– Reachable set calculations– Approximation algorithms for trajectory optimization in hybrid systems• This talk: identifying hybrid models from data2ETMS/UAV flight data4400 4600 4800 5000 5200 5400 5600−4600−4400−4200−4000−3800−3600−3400−3200x [in m.]3000 4000 5000 6000 7000 8000 9000−7500−7000−6500−6000−5500−5000−4500−4000−3500−30004800 5000 5200 5400 5600 5800 6000−4300−4200−4100−4000−3900−3800−3700−3600−3500−3400−3300−3200[UAV data with Teo and Jang; ETMS data from McNally (Ames)] ETMS data with synthesized flight[with Alex Bayen, Pascal Grieder]3[Dsh]p-d/ [Dsh]a-pTime [hrs][Courtesy Dali Ma, Stanford University][Rousset, et al., Genes Dev 15 658-71, 2001]proximal distalDrosophila wing epithelium: Dsh protein[Amonlirdviman, Khare, Tree, Chen, Axelrod, Tomlin Science ’05]Hybrid System Model4Continuous state parameters:ModeTransition matrix:Stochastic Linear Hybrid SystemWe assume that  Measurement matrices C are known System has a minimum (known) dwell time, Td in each mode Typical system behavior is manifested in the available data sets Mode transitions are independent of the continuous state Mode transitions are probabilistic and MarkovianAssumptions on system behavior5Maximum Likelihood Hybrid ModelSwitching pointsLabels (modes)l1= 2 l2 = 1 l3= 2lNs= 1s1= 1s2 s3 sNsTt• Data sequence• discrete modes• segmentsContinuous model ; Discrete modelMaximum Likelihood ModelGiven the continuous output of the system we would like to compute the maximum likelihood hybrid system model.where is the likelihood function we would like to maximize6Assume an initial continuous model (Θ(0)) and an initial discrete model (D(0)).iterateStep 1: Find the globally optimal segmentation points (S) and their labels (L) assuming the model parameters of the current iteration (k). Update switching matrix, M. This gives us the maximum likelihood model D(k+1).Step 2: Fit maximum likelihood models into the segmented time sequences, i.e., for the computed {S,L}, fit the best Θ(k+1).until convergence to a local maximumParameter Inference Algorithmwhere• Reflects how well model tracks the continuous state• Easy to compute (Kalman filter recursions) Likelihood function7• Finding the optimal segmentation is potentially intractableSl2= 2l1 = 1lN= 2l3= 1Ss1=1s2 s3 sNTtSl2= 2l1 = 1 l3= 1lN= 1Ss1=1 s2 s3 sNTtO(NT) possible segmentations!Sl1= 2 l2 = 1 l3= 2lN= 1Ss1=1 s2 s3 sNTtOptimal SegmentationFinding optimal segmentation is potentially intractable (O(NT))Let max. derived by dividing into n parts t1 bl = LastModen-1(b-1)Tsn-1iMliStep 1: Optimal segmentation8Using this, we can find the best segmentation as the one that achieves with complexity O(NT3)Dynamic Programming Algorithm• For the optimal segmentation determined in Step 1, we fit the best continuous parameters for each mode, by maximizingwhere Z is the “complete” data, i.e., both the observed variables (Y) and the state variables xk, k=1…n. l1= 3 l2 = 1 l3= 2s1=1 s2 s3tMode 3 is best fit to Y1:s -12Mode 2 is best fit to Ys:s -134Step 2: Fitting the best continuous model9Proposed algorithm local maximum need initial conditionsWe know system stays in a mode for at least TdWe estimate the number of discrete modes in the system (N), the initial segmentation, and the initial continuous model. EstimateActual Measurementy1yTdbest model for mode 1Initialization• Models for Motion Capture (Li et al.)• Time Series Analysis (Shumway and Stoffer)• Hybrid Estimation Algorithms (Bar-Shalom, Blom et al.)• Observability and Identifiability of Hybrid Systems (Vidal, Soatto, Sastry, Bemporad et al., Balluchi et al.) • System Identification/ Subspace Identification Methods (Ljung, De Moor, Van Overschee, Vidal, Ma)• Dynamic Textures (Soatto et al.)Related Work104800 5000 5200 5400 5600 5800 6000−4300−4200−4100−4000−3900−3800−3700−3600−3500−3400−3300−3200xpos (in m)ypos (in m)Aircraft 1: Evader (autopilot running CSPA*algorithm)Aircraft 2: Blunderer*CSPA: Closely Spaced Parallel ApproachesDragonFly Dual Aircraft Test4800 5000 5200 5400 5600 5800 6000−4200−4100−4000−3900−3800−3700−3600−3500−3400−3300 Dual Aircraft Test Data − TrajectoriesTraining data for A/c 1A/c 1, Mode 1A/c 1, Mode 3A/c 1, Mode 2Training data for A/c 2Aircraft 2, Mode 1Aircraft 2, Mode 2Aircraft 2, Mode 3Aircraft 2, Mode 4xpos (in m.)ypos (in m.) Aircraft 1 (Evader) Aircraft 2 (Blunderer) t=18 s. t = 20 s. t = 39 s. Results110 10 20 30 40 50 6000.511.522.533.544.55timemodeInferred mode transition sequence: Dual Vehicle Flight Test DataAircraft 1Aircraft 2true autopilot command (to A/c 1) 4800 5000 5200 5400 5600 5800 6000−4200−4100−4000−3900−3800−3700−3600−3500−3400−3300Application of Proposed Algorithm to Dual Aircraft Test Data − TrajectoriesTraining data for A/c 1A/c 1, Mode 1A/c 1, Mode 3A/c 1, Mode 2Training data for A/c 2Aircraft 2, Mode 1Aircraft 2, Mode 2Aircraft 2, Mode 3Aircraft 2, Mode 4xpos (in m.)ypos (in m.) Aircraft 1 (Evader) Aircraft 2 (Blunderer) t=18 s. t = 20 s. t = 39 s. startManual pilotParallel localizer trackinga/c 2 blundersa/c 1 autopilot (evasive maneuver)a/c 2 ends blunderManual pilot takes over a/c 1Manual pilot takes over a/c 2Validation4400 4600 4800 5000 5200 5400 5600−4600−4400−4200−4000−3800−3600−3400−3200xposn [m.]yposn [m.]Hybrid Model Identification for Hold PatternPosition 4400 4600 4800 5000 5200 5400 5600−4600−4400−4200−4000−3800−3600−3400−3200xpos [in m.]ypos [in m.]Holding Pattern Data123000 4000 5000 6000 7000 8000 9000−7500−7000−6500−6000−5500−5000−4500−4000−3500−3000Raw Trajectory Data for Tracking0 100 200 300 400 500 600 70011.11.21.31.41.51.61.71.81.92Mode Estimates from Tracking Hold Patterns after model identificationtimemodehold pattern begins hold pattern begins hold pattern ends hold pattern ends 3000 4000 5000 6000 7000 8000 9000−7500−7000−6500−6000−5500−5000−4500−4000−3500−3000Hold Patterns after Model Identification and Tracking (using IMM)xpos [m.]ypos [m.]Track dataHybrid