Flowpipe approximation and clustering in space-time

In this paper, we present an approximation of the set of reachable states, called flowpipe, for a continuous system with affine dynamics. Our approach is based on a representation we call flowpipe sampling, which consists of a set of continuous, interval-valued functions over time. A flowpipe sampling attributes to each time point a polyhedral enclosure of the set of states reachable at that time point, and is capable of representing a nonconvex enclosure of a non-convex flowpipe. The use of flowpipe samplings allows us to represent and approximate the nonconvex flowpipe efficiently. In particular, we can measure the error incurred by the initial approximation and by further processing such as simplification and convexification. A flowpipe sampling can be efficiently translated into a set of convex polyhedra in a way that minimizes the number of convex sets for a given error bound. When applying flowpipe approximation for the reachability of hybrid systems, a reduction in the number of convex sets spawned by each image computation can lead to drastic performance improvements.