Approximate time-optimal control via approximate alternating simulations

Symbolic models of control systems have recently been used to synthesize controllers enforcing specifications given by temporal logics, regular languages, or automata. These specification mechanisms can be regarded as qualitative since they divide the set of trajectories into bad trajectories (those that should be eliminated by control) and good trajectories (those that need not be eliminated). In many situations, however, a quantitative specification, where each trajectory is assigned a cost, is more appropriate. As a first step towards the synthesis of controllers enforcing qualitative and quantitative specifications we investigate in this paper the use of symbolic models for time-optimal controller synthesis. Our results show that it is possible to obtain upper and lower bounds for the time to reach a desired target by an algorithmic analysis of the symbolic model. Moreover, we can also algorithmically synthesize a feedback controller enforcing the upper bound. All the algorithms have been implemented using Binary Decision Diagrams and are illustrated by some examples.