Learning-based Planning with Temporal Logic Constraints

The goal is a model-free reinforcement learning method for stochastic planning under temporal logic constraints — so that a robot can be given a high-level task and return a policy that provably satisfies it.

Pipeline from temporal-logic specification to feedback policy with satisfaction guarantee — From specification to policy: the task formula is translated into an automaton, composed with the stochastic system, and solved with topological approximate dynamic programming.

Chance-constrained planning. We translate specifications expressed in a subclass of Probabilistic Computational Tree Logic (PCTL) into chance constraints, and devise a variant of approximate dynamic programming — approximate value iteration — that solves for the optimal policy while guaranteeing satisfaction of the PCTL formula.

Topological approximate dynamic programming. For syntactically co-safe LTL tasks, we maximize the probability of satisfaction while addressing the sparse-reward problem in two steps: decompose the planning problem into a sequence of sub-problems using the topological structure of the task automaton, then solve one value function per automaton state in reverse causal order. The run time does not grow exponentially with the size of the specification.

Approximate value function surface — Value function approximation, the task automaton, the resulting trajectory, and convergence of the approximation error.

Task automaton translated from an scLTL formula — Value function approximation, the task automaton, the resulting trajectory, and convergence of the approximation error.

Outcomes

Li, L., & Fu, J. (2019). Topological approximate dynamic programming under temporal logic constraints. 2019 IEEE 58th Conference on Decision and Control (CDC), 5330–5337. https://doi.org/10.1109/CDC40024.2019.9029959
Li, L., & Fu, J. (2019). Approximate dynamic programming with probabilistic temporal logic constraints. 2019 American Control Conference (ACC), 1696–1703. https://doi.org/10.23919/ACC.2019.8815215