Robust obstacle avoidance for constrained linear discrete time systems: A set-theoretic approach

This paper considers the robust obstacle avoidance problem for constrained linear discrete time systems from the set-theoretic point of view. A simpler problem of avoiding a single convex obstacle is considered initially and it is demonstrated that, even for the simple linear-convex setting, the convexity of the capture region is not, in general case, preserved. The resulting non-convexity of the capture region implies that the exact, dynamic programming based, algorithmic procedure is computationally extremely demanding and, potentially, prohibitively hard. The inherent computational complexity is tackled by considering an algorithmic procedure that yields inner and outer convex approximations of the exact non-convex capture sets. Additionally, a more complicated problem of avoiding multiple convex obstacles is treated by introducing the concept of the interaction of obstacles. The distinction between interacting and non-interacting obstacles is induced from geometric properties of the avoidance region and can be utilized, in a dynamic programming fashion, for the simplification of underlying set computations. Some simple, telling, examples illustrate a set of hidden phenomena such as strong disconnectedness of the global avoidance region.