Probabilistic Motion Planning Under Temporal Tasks and Soft Constraints

Journal Article (Journal Article)

This paper studies motion planning of a mobile robot under uncertainty. The control objective is to synthesize a finite-memory control policy, such that a high-level task specified as a linear temporal logic formula is satisfied with a desired high probability. Uncertainty is considered in the workspace properties, robot actions, and task outcomes, giving rise to a Markov decision process that models the proposed system. Different from most existing methods, we consider cost optimization both in the prefix and suffix of the system trajectory. We also analyze the potential tradeoff between reducing the mean total cost and maximizing the probability that the task is satisfied. The proposed solution is based on formulating two coupled linear programs, for the prefix and suffix, respectively, and combining them into a multiobjective optimization problem, which provides provable guarantees on the probabilistic satisfiability and the total cost optimality. We show that our method outperforms relevant approaches that employ Round-Robin policies in the trajectory suffix. Furthermore, we propose a new control synthesis algorithm to minimize the frequency of reaching a bad state when the probability of satisfying the tasks is zero, in which case, most existing methods return no solution. We validate the above-mentioned schemes via both numerical simulations and experimental studies.

Full Text

Duke Authors

Cited Authors

  • Guo, M; Zavlanos, MM

Published Date

  • December 1, 2018

Published In

Volume / Issue

  • 63 / 12

Start / End Page

  • 4051 - 4066

Electronic International Standard Serial Number (EISSN)

  • 1558-2523

International Standard Serial Number (ISSN)

  • 0018-9286

Digital Object Identifier (DOI)

  • 10.1109/TAC.2018.2799561

Citation Source

  • Scopus