Automated synthesis of low-rank control systems from sc-LTL specifications using tensor-train decompositions

Correct-by-design automated construction of control systems has attracted a tremendous amount of attention. However, most existing algorithms for automated construction suffer from the curse of dimensionality, i.e., their run time scales exponentially with increasing dimensionality of the state space. As a result, typically, systems with only a few degrees of freedom are considered. In this paper, we propose a novel algorithm based on the tensor-train decomposition that solves stochastic optimal control problems with syntactically co-safe linear temporal logic specifications. We show that, under certain conditions, the run time of the proposed algorithm scales polynomially with the dimensionality of the state space and the rank of the optimal cost-to-go function. We demonstrate the algorithm in a six-dimensional problem instance involving a simple airplane model. In this example, the proposed algorithm provides up to four orders of computational savings when compared to the standard value iteration algorithm.