TL;DR
This paper introduces novel data-driven techniques for reachability analysis of complex cyber-physical systems modeled using the Functional Mock-up Interface (FMI) standard. By leveraging dynamic sensitivity equations and sampling-based methods, the authors provide a way to compute guaranteed bounds on system behavior even for "black-box" models where internal dynamics are unknown, crucial for dependable digital twin applications.
What Problem Does This Paper Address?
Digital twins (DTs) are powerful tools for monitoring, optimizing, and controlling cyber-physical systems (CPS). However, their dependability hinges on the accuracy and trustworthiness of the underlying system models. In realistic scenarios, these models are often fragmented, with subsystems exported from different tools and encapsulated as "black-boxes" (e.g., FMI models). This lack of full model knowledge makes traditional formal analysis challenging. When system parameters are uncertain, reachability analysis is needed to compute bounds that enclose all possible system behaviors. This paper addresses the challenge of performing this crucial reachability analysis on these fragmented, black-box FMI models, especially when dealing with uncertainty in initial conditions.
Methods
The paper proposes two main data-driven techniques for reachability analysis of black-box FMI models:
- Dynamic Sensitivity-Based Reachability Analysis: This method leverages FMI's capability to retrieve partial derivatives. It solves dynamic sensitivity equations, which describe how a system's state changes in response to small perturbations in its initial conditions. By simulating these equations, the authors compute a scaling factor that, combined with a nominal trajectory, yields approximate reachable sets. This approach extends to coupled FMI models by composing their dynamic sensitivity equations.
- Sampling-Based Reachability Analysis: This technique involves partitioning the initial state space into smaller hyper-rectangles. For each partition, it estimates a Lipschitz constant (a measure of how much the system's output can change relative to input changes) by sampling trajectories. This estimated Lipschitz constant is then used to compute an approximate reachable set for that partition. The paper also discusses robust convex programs (RCPs) and their data-driven approximations (SCPs) for estimating these constants and providing probabilistic guarantees.
Both methods aim to provide probabilistic guarantees on the accuracy of the computed reachable sets.
Datasets
The paper does not introduce new datasets. Instead, it uses various benchmark systems for validation, including:
- Linear/Affine systems (stable, unstable, oscillator)
- Nonlinear systems: Van Der Pol system (2D and 4D), Rossler System (3D), Spring Pendulum, and a Biological Model. These systems are used to evaluate the accuracy and performance of the proposed algorithms against existing tools like Flow*.
Key Insights and Ideas
- Bridging the Black-Box Gap: The core innovation is enabling formal reachability analysis on FMI models without requiring full knowledge of their internal dynamics. This is crucial for leveraging existing, often proprietary, simulation models in safety-critical applications.
- Dynamic Sensitivity as a Powerful Tool: The dynamic sensitivity equations provide a more scalable and accurate way to estimate system dynamics and bounds compared to purely sampling-based methods, especially for higher-dimensional systems.
- Probabilistic Guarantees are Key: The methods provide probabilistic guarantees on the computed reachable sets, offering a quantifiable level of confidence in the analysis, which is essential for verification and safety assurance.
- Modularity is Essential: The approach is designed to handle coupled FMI models, reflecting the reality of complex system modeling where individual components are developed and simulated separately.
Key Results
- The proposed dynamic sensitivity-based approach demonstrated accurate and scalable reachability analysis for linear systems, outperforming sampling-based methods in terms of accuracy for higher dimensions.
- Both methods produced reasonably conservative reachable sets for nonlinear systems.
- The dynamic sensitivity approach generally offered a better accuracy/runtime trade-off for 2D systems compared to sampling-based methods.
- The sampling-based approach, while potentially slower, offers a flexible trade-off between accuracy and runtime cost and can provide probabilistic guarantees on containment.
- The authors' methods were compared to the model-based reachability tool Flow*, showing comparable results, with their methods being more conservative in some cases.
Limitations and Future Work
- Runtime Scalability: The runtime of the sampling-based algorithm can increase significantly with the number of samples, and the dynamic sensitivity approach's runtime increases rapidly with system dimension.
- Co-simulation Technique: The current co-simulation technique for building sensitivity equations relies on the Forward Euler method, which can introduce errors. Using more advanced numerical integration methods is suggested.
- Future Work:
- Extending the methods to monitor Signal Temporal Logic properties for black-box models.
- Applying the techniques to parametric black-box models to account for parameter uncertainty.
- Investigating the application of dynamic sensitivity to hybrid automata.
- Integrating the proposed methods with real-world data from physical assets for DT applications.
Summary updated