Constructing decidable hybrid systems with velocity bounds

Abstract

In this paper, the question of bi-similarity between hybrid systems and their discrete quotients is studied from a new point of view. We consider two classes of hybrid systems: piecewise affine hybrid systems on simplices and piecewise multi-affine systems on multi-dimensional rectangles. Given a fixed partition of the state space, we derive sufficient conditions on the values of the vector fields at the vertices of the polytopes, in order that the constructed hybrid system is bi-similar with its corresponding discrete quotient transition system. The results are based on the fact that affine vector fields on simplices and multi-affine vector fields on rectangles are uniquely determined by their values at the vertices. In this way, an interesting class of decidable hybrid systems is determined. The result is applied to a motion planning problem for planar robots.