Sampling-based Approximate Optimal Control Under Temporal Logic Constraints

J. Fu, I. Papusha, and U. Topcu

Abstract

We investigate a sampling-based method for optimal control of continuous-time and continuous-state (possibly nonlinear) systems under co-safe linear temporal logic specifications. We express the temporal logic specification as a deterministic, finite automaton (the specification automaton), and link the automaton’s discrete transitions to the continuous system state as it passes through specified regions. The optimal hybrid controller is characterized by a set of coupled partial differential equations. Because these equations are difficult to solve exactly in practice in all cases, we propose instead a sampling based technique to solve for an approximate controller through approximate value iteration. We adopt model reference adaptive search—an importance sampling optimization algorithm—to determine the mixing weights of the approximate value function expressed in a finite basis. Under mild technical assumptions, the algorithm converges, with probability one, to an optimal weight that ensures the satisfaction of temporal logic constraints, while minimizing an upper bound for the optimal cost. We demonstrate the correctness and efficiency of the method through numerical experiments, including temporal logic planning for a linear system, and a nonlinear mobile robot.

Citation

J. Fu, I. Papusha, and U. Topcu. “Sampling-based Approximate Optimal Control Under Temporal Logic Constraints,” ACM International Conference on Hybrid Systems: Computation and Control (HSCC), pp. 227–235, Pittsburgh, PA, April 18–20, 2017.