# Probabilistic Motion Planning under Temporal Tasks and Soft Constraints

arXiv: https://arxiv.org/abs/1706.05209 · HTML: https://mlsanity.com/paper/1706.05209/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2017.

## Built on by (most cited first, 9 of 9)

- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [C-MCTS: Safe Planning with Monte Carlo Tree Search](https://mlsanity.com/paper/2305.16209/) (2023)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [STL Robustness Risk over Discrete-Time Stochastic Processes](https://mlsanity.com/paper/2104.01503/) (2021)
- [Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications](https://mlsanity.com/paper/2311.17059/) (2023)
- [Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automata](https://mlsanity.com/paper/2101.10284/) (2021)
- [MULTIGAIN 2.0: MDP controller synthesis for multiple mean-payoff, LTL and steady-state constraints](https://mlsanity.com/paper/2305.16752/) (2023)
- [Scaling Learning based Policy Optimization for Temporal Logic Tasks by Controller Network Dropout](https://mlsanity.com/paper/2403.15826/) (2024)
- [LTLf Synthesis Under Unreliable Input](https://mlsanity.com/paper/2412.14728/) (2024)

## Abstract (arXiv)

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.