Probabilistic Motion Planning Under Temporal Tasks and Soft Constraints

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 works...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on automatic control 2018-12, Vol.63 (12), p.4051-4066
Main Authors: Guo, Meng, Zavlanos, Michael M.
Format: Article
Language:English
Subjects:
Chance-constrained optimization
Computer simulation
Cost analysis
linear temporal logic (LTL)
Markov chains
Markov decision process (MDP)
Motion planning
Multiple objective analysis
Optimization
Planning
Probabilistic logic
Robot control
Robot dynamics
Robot motion
Robots
Statistical analysis
Task analysis
Temporal logic
Trajectory analysis
Uncertainty
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9286
1558-2523
DOI:10.1109/TAC.2018.2799561