Just-in-time synthesis for reactive motion planning with temporal logic

Abstract

The cost of the great expressivity of motion planning subject to temporal logic formulae is intractability. Recent advances in sampling-based methods seem to be only applicable to "low-level" control. The problem of realizing "high-level" controllers that satisfy a temporal logic specification does not readily admit approximations, unless the notion of correctness is relaxed as might be achieved with probabilistic variants of temporal logics. In this paper, we argue that not all possible environment (uncontrolled) behaviors need to be explicitly planned for, but rather short-time strategies can be generated online while maintaining global correctness. We achieve this by separating feasibility from controller synthesis, using metrics from the underlying continuous state space to ensure short-time strategies chained together provide globally correct behavior.

Additional details