Computing Distances between Reach Flowpipes
Preprint
Abstract
We investigate quantifying the difference between two hybrid dynamical systems under noise and initial-state uncertainty. While the set of traces for these systems is infinite, it is possible to symbolically approximate trace sets using \emph{reachpipes} that compute upper and lower bounds on the evolution of the reachable sets with time. We estimate distances between corresponding sets of trajectories of two systems in terms of distances between the reachpipes. In case of two individual traces, the Skorokhod distance has been proposed as a robust and efficient notion of distance which captures both value and timing distortions. In this paper, we extend the computation of the Skorokhod distance to reachpipes, and provide algorithms to compute upper and lower bounds on the distance between two sets of traces. Our algorithms use new geometric insights that are used to compute the worst-case and best-case distances between two polyhedral sets evolving with time.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Quantifying Conformance Using the Skorokhod Metric2015
- WiP abstract: Conformance testing as falsification for cyber-physical systems2014
- SpaceEx: Scalable Verification of Hybrid Systems2011
- A Policy Iteration Technique for Time Elapse over Template PolyhedraLecture Notes in Computer Science, 2008
- Zonotope/Hyperplane Intersection for Hybrid Systems Reachability AnalysisLecture Notes in Computer Science, 2008
- Reachability Analysis of Large-Scale Affine Systems Using Low-Dimensional PolytopesLecture Notes in Computer Science, 2006
- Efficient Computation of Reachable Sets of Linear Time-Invariant Systems with Inputs2006
- Reachability of Uncertain Linear Systems Using Zonotopes2005
- Toward an Approximation Theory for Computerised Control2002
- How good are convex hull algorithms?Computational Geometry, 1997