CHARDA: Causal Hybrid Automata Recovery via Dynamic Analysis

Adam Summerville, Joseph C. Osborn, Michael MateasIJCAI 2017 · DOI

TL;DR

This paper introduces CHARDA, a novel method for automatically learning "hybrid automata" – models that combine discrete states with continuous dynamics – from observed system behavior. CHARDA excels at identifying distinct operating modes and learning causal guard conditions that trigger transitions between them, offering a powerful way to abstract complex systems for analysis and planning.

What Problem Does This Paper Address?

Understanding and controlling complex dynamical systems is a fundamental challenge in many fields, from robotics to game AI. Hybrid automata (HAs) offer a powerful modeling framework by integrating discrete logic with continuous variables, making them suitable for systems with distinct behaviors that change over time. However, manually creating accurate HA models is labor-intensive and error-prone. This paper addresses the gap of automatically learning these complex HA models from observed data, aiming to create abstractions that are useful for human analysis and automated planning, especially in domains with intricate, non-physical dynamics like video games.

Methods

CHARDA employs a two-phase approach:

  • Mode Identification: This phase uses a dynamic programming approach, similar to segmented least squares, to identify distinct "modes" of system behavior. It segments the observed data into intervals where the system's dynamics are relatively consistent. A key innovation here is the use of information-theoretic measures (like BIC and MDL) as a principled penalty function for model complexity. This penalty helps CHARDA balance fitting the data well with keeping the model simple, preventing overfitting and guiding the segmentation process. It also allows for merging segments if it leads to a more optimal overall model.
  • Causal Guard Learning: Once modes are identified, CHARDA learns the "guard conditions" that trigger transitions between them. It prioritizes learning causal guards, meaning it tries to identify predicates about the system's state or environment that directly cause a transition, rather than just being correlated with it. This is achieved by using Normalized Pointwise Mutual Information (NPMI) to measure the causal strength between observed predicates and mode transitions. Exogenous (external) causes like player inputs or collisions are given higher priority than endogenous (internal) ones.

Datasets

  • Super Mario Bros. (SMB) Domain: The primary novel domain used for evaluation. The authors used a trace of a character's behavior in SMB, which presents challenges like non-physical dynamics and rapid mode changes.
  • Aircraft Tracking Domain: Used for comparison with existing work. The paper mentions two scenarios: "Lawnmower" (a structured flight pattern) and "Random" (a more unpredictable pattern).

Key Insights and Ideas

  • Information Theory for Model Selection: Using BIC and MDL as penalty functions for segmentation is a principled way to balance model complexity and data fit, leading to more robust mode identification than simpler methods.
  • Causality over Correlation: Prioritizing the learning of causal guard conditions is crucial for creating models that are not only descriptive but also predictive and understandable. This is a significant step beyond simply finding correlations.
  • Domain Flexibility: CHARDA's framework is designed to be extensible, allowing for different model templates, fitting methods, and predicate sets, making it adaptable to various dynamical systems.
  • Games as a Rich Domain: Video games offer a unique testing ground for learning algorithms, bridging the gap between synthetic data and real-world cyber-physical systems, and providing valuable insights into complex agent behaviors.

Key Results

  • Videogame Domain: CHARDA successfully discovered a reasonable over-approximation of a complex videogame character's true behaviors, identifying distinct modes and transition guards.
  • Aircraft Domain: CHARDA's segmentation performance favorably compared to existing probabilistic timed automata learning methods, and it exactly learned the modes of simpler automata in this domain.
  • Mode Merging Trade-off: While CHARDA's mode identification and merging improved overall model accuracy, it sometimes over-merged distinct but similar modes (e.g., different jump types in Mario), leading to a more abstract but less detailed model. MDL penalty tended to produce more faithful models than BIC in the Mario domain.

Limitations and Future Work

  • Over-Merging of Modes: A significant limitation acknowledged is the tendency for CHARDA to over-merge similar but distinct modes, leading to a loss of detail in the learned automaton. Future work aims to find better principled ways to learn these similar modes or incorporate techniques like Chinese Restaurant Processes or Forget-Me-Not Process for mode assignment.
  • Guard Condition Granularity: The learned guard conditions are currently limited to conjunctions of predefined predicates. Future work could explore learning more complex guards, including linear inequalities or disjunctions, and incorporating experimentation to refine models and test hypothesized guards.
  • Non-Determinism Resolution: The current approach has limitations in resolving non-deterministic transitions, which is an area for future exploration.
  • Comparison to Existing Work: While CHARDA outperforms some existing methods, direct comparison is sometimes limited by differing assumptions (e.g., requiring prior knowledge of the number of modes).

Summary updated

BibTeX
@inproceedings{summerville2017charda,
  author = {Adam Summerville and Joseph C. Osborn and Michael Mateas},
  title = {{CHARDA: Causal Hybrid Automata Recovery via Dynamic Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/390},
}
Figure