Managing non-determinism in symbolic robot motion planning and control

Abstract

We study the problem of designing control strategies for non-deterministic transitions systems enforcing the satisfaction of linear temporal logic (LTL) formulas over their set of states. We focus on finite transition systems with inputs, which are often encountered when solving motion planning problems by using discrete quotients induced by a given partition of the state space. Our approach solves the problem conservatively using LTL games, and consists of the following three steps: (1) the original transition system is transformed into a transition system on which an LTL game can be played, (2) a solution of the LTL game on the new transition system is obtained, and (3) an interface between this solution and the initial transition system is constructed. The correctness of the method is ensured by design. The advantages and conservativeness of our approach are discussed and illustrated by simple examples.