REACHABILITY ANALYSIS OF DYNAMICAL-SYSTEMS HAVING PIECEWISE-CONSTANT DERIVATIVES

In this paper we consider a class of hybrid systems, namely dynamical systems with piecewise-constant derivatives (PCD systems). Such systems consist of a partition of the Euclidean space into a finite set of polyhedral sets (regions). Within each region the dynamics is defined by a constant vector field, hence discrete transitions occur only on the boundaries between regions when the trajectories change their direction. With respect to such systems we investigate the reachability question: Given an effective description of the systems and of two polyhedral subsets P and Q of the state-space, is there a trajectory starting at some x is an element of P and reaching some point in Q? Our main results are a decision procedure for two-dimensional systems, and an undecidability result for three or more dimensions.