Just scratching the surface: Partial exploration of initial values in reach-set computation

摘要

We suggest a method for significantly reducing the so-called wrapping effect, i.e., the accumulation of approximation errors incurred during reach-set computation of differential equations when repeatedly over-approximating intermediate reach sets by tractable computational representations of sets in the Rn. Our method can be implemented on top of any known reach-set computation method and generalizes bracketing systems [1] by being based on dimension-wise enclosures of the reach sets of appropriate lower-dimensional surfaces of the initial set selected due to monotonicity properties. Thus exploring just low-volume sub-sets rather than the entire initial and intermediate reach sets, accuracy is enhanced as the approximation error tends to be correlated with set volume. At the same time, the curse of dimensionality that set partitioning methods are prone to is avoided by resorting to a number of subsets linear in the problem dimension. Technically, we first conduct sensitivity analysis of the solution mapping with respect to initial states based on a simulation-based technique, and then determine subsets which are extracted from the boundary of the initial set for performing reachability analysis. We test our method by using it on top of the validated ODE solver VNODE-LP and demonstrate its effect by comparison with existing methods, using illustrative examples of non-linear dynamics.