Polynomial-Time Probabilistic Controllability Analysis of Discrete-Time Piecewise Affine Systems

This paper proposes a probabilistic approach to the controllability analysis for discrete-time piecewise affine (PWA) systems. Three kinds of randomized algorithms, which are based on random sampling of the mode sequence and/or the initial state, for determining with a probabilistic accuracy if the system is controllable are presented: a positive one-sided error algorithm, a negative one-sided error algorithm, and a two-sided error algorithm. It is proven that these are polynomial-time algorithms with respect to several variables of the problem. It is also shown with some examples, for which it is hopeless to check the controllability in a deterministic way, that these algorithms are efficient.