CHARDA: Causal Hybrid Automata Recovery via Dynamic Analysis
This work addresses the problem of automated model recovery for hybrid systems, which is incremental as it builds on existing techniques with new information-theoretic measures.
The authors tackled the problem of automatically learning hybrid automata from runtime behavior of dynamical systems, and CHARDA successfully discovered a reasonable over-approximation of a complex videogame character's behaviors and exactly learned the modes of simpler automata in an aircraft domain.
We propose and evaluate a new technique for learning hybrid automata automatically by observing the runtime behavior of a dynamical system. Working from a sequence of continuous state values and predicates about the environment, CHARDA recovers the distinct dynamic modes, learns a model for each mode from a given set of templates, and postulates causal guard conditions which trigger transitions between modes. Our main contribution is the use of information-theoretic measures (1)~as a cost function for data segmentation and model selection to penalize over-fitting and (2)~to determine the likely causes of each transition. CHARDA is easily extended with different classes of model templates, fitting methods, or predicates. In our experiments on a complex videogame character, CHARDA successfully discovers a reasonable over-approximation of the character's true behaviors. Our results also compare favorably against recent work in automatically learning probabilistic timed automata in an aircraft domain: CHARDA exactly learns the modes of these simpler automata.