A Causal Analysis Method for Concurrent Hybrid Automata

Michael W. Hofbaur, Franz WotawaAAAI 2006

Introduction

Modern autonomous systems, ranging from robotic explorers to complex chemical processing plants, are increasingly modeled as Concurrent Hybrid Automata (cHA). These systems combine discrete logic—such as mode switches and fault states—with continuous physical dynamics like flow rates and temperatures. A critical challenge in designing these systems is ensuring causal consistency: at any given time, the equations governing the system must have a valid assignment of inputs and outputs across all components.

In highly flexible or fault-tolerant systems, causality is not fixed. A component failure might necessitate a complete rerouting of signals or fluids, effectively turning a former "output" into an "input." Manually verifying every possible configuration is impossible as the state space grows exponentially with the number of components.

A micro-chemical plant undergoing reconfiguration due to component failures (marked with red X's), illustrating the dynamic nature of causality in hybrid systems.

Methodology: Diagnosis as a Solution

The authors propose a two-step framework to address the state-explosion problem by reframing causal analysis as a model-based diagnosis task.

1. Diagnosis-based Component Analysis

Instead of an exhaustive search, the method identifies valid input/output (I/O) relationships for individual components using a modified version of Reiter’s hitting-set algorithm. By treating potential output variables as "faulty components" in a diagnostic sense, the algorithm efficiently finds minimal sets of variables that can serve as outputs for any specific mode, ensuring mathematical solvability without checking every state combination.

2. Recursive Composition and Pruning

Once individual component causalities are established, they are composed incrementally. The process begins with a "World Automaton" ($A_0$), which defines the system's external boundary conditions. Components are then added one by one using a breadth-first search. A key innovation is the early detection and pruning of "incompatible" branches—paths where the combined equations of the components lead to a causal conflict.

The recursive composition process uses a tree-based search to combine component causalities, pruning incompatible branches early to avoid exploring invalid system states.

Key Results and Evaluation

The method was evaluated on a synthetic 8-component system with over 6,500 possible modes. The diagnosis-based approach successfully reduced this massive search space to just 288 unique causalities. Furthermore, by employing a connectivity-based heuristic for the composition order, the search only encountered 12 incompatible causalities before validating the entire system.

This efficiency allows designers to distinguish between strongly compatible systems (valid in all possible modes) and weakly compatible ones (valid only under specific configurations), providing a robust tool for verifying autonomous reconfiguration logic.

Conclusion and Future Directions

By treating causal analysis as a diagnostic problem, this research provides a scalable path for verifying complex hybrid systems. While the current heuristic for component ordering is effective, future work aims to reformulate the composition as a Constraint Satisfaction Problem (CSP) to further enhance robustness. Additionally, extending the framework from discrete-time difference equations to continuous-time ordinary differential equations remains a promising area for development.

Summary updated

BibTeX
@inproceedings{hofbaur2006causal,
  author = {Michael W. Hofbaur and Franz Wotawa},
  title = {{A Causal Analysis Method for Concurrent Hybrid Automata}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure