TL;DR
This paper introduces a novel method for computing over- and under-approximations of reachable states for systems with perturbed delay differential equations (DDEs). By leveraging the "homeomorphism property" of system solutions, they enable efficient reachability analysis on the boundaries of initial state sets, extending existing ODE techniques to DDEs and offering robust safety verification capabilities.
What Problem Does This Paper Address?
Verifying the safety of complex dynamical systems is crucial, especially when these systems involve time delays, which are common in networked and physical systems. Delay Differential Equations (DDEs) are the standard mathematical tools for modeling such systems. However, performing reachability analysis (determining all possible states a system can reach) for DDEs is significantly more challenging than for Ordinary Differential Equations (ODEs). Existing methods for DDEs primarily focus on over-approximating reachable sets, leaving the problem of under-approximation (which is vital for proving robust unsafety) largely unaddressed. This paper tackles this gap by developing methods for both over- and under-approximating reachable sets for DDEs with time-varying Lipschitz perturbations, a more general class than previously studied.
Methods
The core contribution lies in extending the "boundary reachability analysis" method, previously successful for ODEs, to a specific class of perturbed DDEs. This class is characterized by solutions exhibiting a "local homeomorphism property" with respect to initial states. This property is guaranteed by imposing a constraint on the time-lag term ($\tau$) of the DDE, derived through sensitivity analysis to ensure the system's dynamics are strictly diagonally dominant.
The key steps involve:
- Deriving a Time-Lag Constraint: A novel constraint on $\tau$ is derived (Theorem 1) that ensures the homeomorphism property. This constraint is shown to be less conservative than previous methods by avoiding dependency on the system's dimension.
- Boundary Reachability Analysis: Leveraging the homeomorphism property, the paper demonstrates that computing reach sets for the entire initial state set can be reduced to analyzing only the boundary of the initial set. This significantly reduces computational complexity.
- Over- and Under-Approximation:
- Over-approximation: Computed by applying existing reachability analysis methods to the boundary of the initial set. This provides a guaranteed enclosure of the reachable states, useful for robust safety verification.
- Under-approximation: Computed by excluding certain regions from the over-approximated boundary reach set. This provides a guaranteed subset of states that are not reachable, useful for robustly proving unsafe conditions.
The paper also establishes theoretical results (Lemmas 1-3, Theorems 2-3) proving the compactness of reach sets and the relationship between boundary trajectories and the computed reach sets.
Datasets
Not discussed in the paper. The paper focuses on theoretical development and demonstrates its approach using synthetic examples.
Key Insights and Ideas
- Homeomorphism Property is Key: The paper highlights that the "homeomorphism property" of DDE solutions is the critical enabler for extending boundary reachability analysis. This property ensures that the topological structure of the initial set is preserved in the reachable set, allowing boundary analysis to be sufficient.
- Reduced Conservatism in Time-Lag Constraint: The new constraint on the time-lag term ($\tau$) is a significant improvement. By avoiding dependence on system dimension, it allows for larger time delays while still guaranteeing the desired properties, making the method applicable to a wider range of systems.
- Boundary Analysis for DDEs: The core insight is that for this specific class of DDEs, analyzing the boundary of the initial state set is sufficient to compute both over- and under-approximations of the full reachable set. This drastically reduces the computational burden compared to analyzing the entire initial state volume.
- Robust Safety and Unsafety Verification: The paper clearly articulates the utility of over-approximations for proving robust safety (the system will never enter an unsafe region, regardless of perturbations) and under-approximations for proving robust unsafety (the system will eventually enter an unsafe region, regardless of perturbations).
Key Results
The paper presents a method for computing over- and under-approximations of reachable sets for perturbed DDEs. The effectiveness of the approach is demonstrated through three examples:
- Example 1 (2D system): Showcased robust safety verification (system does not intersect unsafe set) and robust unsafety verification (system intersects unsafe set). Computation time: 15.53 seconds.
- Example 2 (2D system): Illustrated the computed over-approximation being contained within the viable domain. The computed under-approximation tended to become empty with increasing time horizon. Computation time: 320.56 seconds.
- Example 3 (7D system): Demonstrated the method on a higher-dimensional system using interval representations for simplicity and efficiency. Computation time: 130.21 seconds.
The paper also shows that the derived constraint on $\tau$ is less conservative than previous methods, allowing for larger time delays.
Limitations and Future Work
- Limited Class of DDEs: The method is applicable to DDEs exhibiting the local homeomorphism property, which is guaranteed by a specific constraint on the time-lag term and sensitivity matrices. Extending the method to DDEs that do not satisfy this property remains an open problem.
- Conservativeness of Over-Approximations: While the method reduces computational burden, the computed over-approximations can still be conservative, especially for longer time horizons. The paper suggests that partitioning the initial set's boundary can help mitigate this.
- Under-Approximation Behavior: For longer time horizons, the computed under-approximations can become empty, limiting their utility in some scenarios.
- Future Work: The authors suggest exploring how to derive bounds for invertible sensitivity matrices that are not necessarily strictly diagonally dominant, which could potentially relax the constraints on $\tau$. They also hint at further improvements by partitioning the initial set's boundary to reduce wrapping effects and improve accuracy.
Summary updated