Abstraction based solution of complex attainability problems for decomposable continuous plants

The focus of the present paper is systems of nonlinear continuous sub-plants that share a common input but are otherwise coupled only through the specification of a control problem, possibly including state constraints. Examples include cart-pole systems and collision avoidance problems involving multiple vehicles. We propose a method that uses finite state models for solving highly complex continuous attainability problems. We first prove that finite state models, also called discrete abstractions, of the overall plant may be obtained as products of abstractions of sub-plants. The latter, which we call factors, may be determined quickly and concurrently. We also modify a state-of-the-art algorithm for the discrete, auxiliary attainability problems that arise, to work directly with the set of factors and prove that the asymptotic computational complexity of the modified algorithm matches that of the original one. In practice, the latter will often be much slower since the representation of the abstraction of the overall plant on a computer is likely to require an excessive amount of memory. Practicability of our method is demonstrated by successfully designing discrete controllers that globally stabilize decomposable nonlinear continuous plants whose overall finite state models would include millions of states and billions of transitions. Working with the factors instead, problem data fit into main memory of a customary personal computer, and computations take only minutes.