TL;DR
This paper tackles the challenge of explaining the observed behavior of complex hybrid systems (systems with both discrete and continuous dynamics). They propose a novel approach that translates hybrid automaton models of these systems into the PDDL+ planning language, allowing off-the-shelf AI planners to find explanations. This planning-based method significantly outperforms traditional model-checking techniques in efficiency and ability to generate concrete trajectories.
What Problem Does This Paper Address?
Hybrid systems (HS) are ubiquitous in fields like robotics, chemical engineering, and automated manufacturing, exhibiting both discrete mode changes and continuous state evolution. Understanding why an HS behaves in a certain way, especially when faced with observed data, is crucial for debugging, verification, and building trust. The "Hybrid System Explanation" (HSE) problem aims to find a specific execution trace (a hybrid trajectory) of an HS that matches a given sequence of observations.
Traditional approaches to analyzing HS often rely on model checking (MC). While MC tools can verify safety properties, they often struggle to produce concrete counter-examples or trajectories, especially for complex systems. Some specialized tools can generate these, but they might make simplifying assumptions about system dynamics or only handle simpler cases. This paper addresses the gap by providing an efficient and practical method to generate these explanatory trajectories, bridging the divide between formal verification and AI planning.
Methods
The core of the paper's contribution lies in its novel mapping of hybrid automata (HA) to the PDDL+ planning language.
- Hybrid Automata (HA) Formulation: The authors first formalize the HSE problem using HA. They model the HS itself with one HA and create a "monitor automaton" that tracks the observed behavior. The parallel composition of these two HAs restricts the HS's trajectories to those consistent with the observations.
- Mapping to PDDL+: The key innovation is translating this network of HAs into a PDDL+ planning problem.
- State Variables: HA state variables (continuous) become PDDL+ numeric variables.
- Locations: HA discrete locations become PDDL+ Boolean state variables.
- Discrete Transitions: HA discrete transitions (guards and resets) are mapped to PDDL+ actions.
- Continuous Dynamics: HA continuous dynamics (flows) are mapped to PDDL+ processes.
- Observations: The monitor automaton's transitions are mapped to actions or, for a more efficient "greedy support," to PDDL+ events.
- Leveraging AI Planners: By converting the HSE problem into a PDDL+ instance, the authors can utilize powerful, off-the-shelf AI planners (specifically ENHSP with an HM R P heuristic) to find a plan. This plan, when interpreted back, represents a synchronized trajectory of the HS and the monitor, thus providing the explanation.
- Optimization: The HSE problem is framed as an optimization problem, aiming to find the "most suitable" explanation. The paper uses the number of discrete transitions in the explanation as a proxy for its quality, favoring shorter, more "eventful" trajectories.
Datasets
The paper evaluates its approach on three benchmark domains:
- Thermostat (constant dynamics): A standard hybrid automaton example with piece-wise constant dynamics.
- Platoon (linear dynamics): A benchmark for linear dynamics verification, involving a platoon of networked vehicles.
- Flight (nonlinear dynamics): A more complex domain modeling aircraft dynamics, as illustrated in Example 3.2 and Figure 3.
For each domain, they generated 10 trajectories using a simulator and then extracted observation sequences by sampling these trajectories at a fixed rate (1 second). The number of observations was varied from 2 to 100, creating different problem instances.
Key Insights and Ideas
- Planning as Explanation: The paper demonstrates that AI planning, traditionally used for goal-directed action sequences, can be effectively repurposed for explaining observed system behavior. This shifts the paradigm from "what should the system do?" to "what did the system do and why?".
- PDDL+ as a Unifying Language: PDDL+ proves to be a powerful formalism for bridging the gap between formal hybrid system modeling (HA) and symbolic AI planning. Its ability to handle both discrete and continuous aspects is key.
- Efficiency Gains: The planning-based approach offers a significant performance advantage over traditional model-checking methods, especially for larger and more complex systems. This is attributed to the scalability and heuristic guidance of modern AI planners.
- Greedy Support for Efficiency: Using "greedy supports" (where monitor transitions are triggered as soon as possible) for the monitor automaton leads to more efficient planning and still guarantees finding an explanation that is a prefix of a more general explanation.
Key Results
The empirical evaluation highlights the effectiveness of the proposed planning-based approach (HSE_P and HSE_Pe) compared to model-checking tools (DREACH and HYCOMP).
- Scalability: HSE_P and HSE_Pe significantly outperformed MC tools in terms of the number of problems solved within the given time and memory limits. HYCOMP struggled with non-constant dynamics, and DREACH faced issues with large state spaces.
- Performance: HSE_Pe (using greedy supports/events) was able to solve all tested problems across all domains, demonstrating superior scalability. HSE_P also showed good performance but was unable to solve the full suite of problems in linear and nonlinear domains.
- Quality of Solutions: The quality of solutions (measured by the length of the explanation) was comparable between HSE_P and HSE_Pe for thermostat and platoon. For the flight domain, HSE_P found slightly shorter explanations. MC tools produced plans of similar size to the best found by the planning approaches.
Limitations and Future Work
- Optimization Function: The paper uses a simple optimization function (minimizing discrete transitions). While effective, more sophisticated functions could be explored to capture different notions of "best" explanation.
- Greedy Support Completeness: While Theorem 3.7 shows that greedy supports yield explanations that are prefixes of general explanations, the practical implications of this approximation for all scenarios might warrant further investigation.
- PDDL+ Planner Limitations: The performance is still dependent on the capabilities of the underlying PDDL+ planner. Addressing limitations in planners for highly complex or non-linear dynamics remains an area for improvement.
- Future Work: The authors suggest exploring the combination of PDDL+ planning with model checking for falsification problems, which could be a promising avenue for future research. Further investigation into more complex optimization criteria for explanations is also implied.
Summary updated