Probabilistic Motion Planning Under Temporal Tasks and Soft Constraints

DOI10.1109/TAC.2018.2799561MaRDI QIDQ4562786zbMATH OpenOpenAlexFDO

Authors Meng Guo, Michael M. Zavlanos

Publication date 18 December 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.05209

Mathematics Subject Classification ID

Temporal logic (03B44) Specification and verification (program logics, model checking, etc.) (68Q60) Stochastic programming (90C15) Markov and semi-Markov decision processes (90C40)

Abstract: 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 (LTL) 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 (MDP) 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 trade-off 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 multi-objective 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 schemes via both numerical simulations and experimental studies.

Recommendations

• Optimal Probabilistic Motion Planning With Potential Infeasible LTL Constraints
• Iterative temporal motion planning for hybrid systems in partially unknown environments
• Chance-Constrained Multilayered Sampling-Based Path Planning for Temporal Logic-Based Missions
• Motion planning under uncertainty for robotic tasks with long time horizons
• Learning-Based Probabilistic LTL Motion Planning With Environment and Motion Uncertainties
• Path Planning among Movable Obstacles: A Probabilistically Complete Approach
• Temporal logic motion planning for dynamic robots
• Cross-entropy temporal logic motion planning
• Motion planning among time dependent obstacles
• Motion Planning for Continuous-Time Stochastic Processes: A Dynamic Programming Approach

Cited in

(7)

• Multi-objective optimization of long-run average and total rewards
• Probabilistic constraint tightening techniques for trajectory planning with predictive control
• On soft predicates in subdivision motion planning
• Temporal logic motion planning using POMDPs with parity objectives
• Chance-constrained Static Schedules for Temporally Probabilistic Plans
• Optimal deterministic controller synthesis from steady-state distributions
• MULTIGAIN 2.0: MDP controller synthesis for multiple mean-payoff, LTL and steady-state constraints

This page was built for publication: Probabilistic Motion Planning Under Temporal Tasks and Soft Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4562786)