# Optimal Probabilistic Motion Planning with Potential Infeasible LTL Constraints

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2020.

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

- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2411.00205/) (2024)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [Probabilistic Planning with Partially Ordered Preferences over Temporal Goals](https://mlsanity.com/paper/2209.12267/) (2022)
- [Exploiting Hybrid Policy in Reinforcement Learning for Interpretable Temporal Logic Manipulation](https://mlsanity.com/paper/2412.20338/) (2024)
- [Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automata](https://mlsanity.com/paper/2101.10284/) (2021)
- [Model-free Motion Planning of Autonomous Agents for Complex Tasks in Partially Observable Environments](https://mlsanity.com/paper/2305.00561/) (2023)
- [Preference-Based Planning in Stochastic Environments: From Partially-Ordered Temporal Goals to Most Preferred Policies](https://mlsanity.com/paper/2403.18212/) (2024)
- [Near-Optimal Reinforcement Learning for Constrained Recurrence Objectives](https://mlsanity.com/paper/2511.19849/) (2025)
- [Reinforcement learning with timed constraints for robotics motion planning](https://mlsanity.com/paper/2601.00087/) (2025)

## Abstract (arXiv)

This paper studies optimal motion planning subject to motion and environment uncertainties. By modeling the system as a probabilistic labeled Markov decision process (PL-MDP), the control objective is to synthesize a finite-memory policy, under which the agent satisfies complex high-level tasks expressed as linear temporal logic (LTL) with desired satisfaction probability. In particular, the cost optimization of the trajectory that satisfies infinite horizon tasks is considered, and the trade-off between reducing the expected mean cost and maximizing the probability of task satisfaction is analyzed. Instead of using traditional Rabin automata, the LTL formulas are converted to limit-deterministic B"uchi automata (LDBA) with a reachability acceptance condition and a compact graph structure. The novelty of this work lies in considering the cases where LTL specifications can be potentially infeasible and developing a relaxed product MDP between PL-MDP and LDBA. The relaxed product MDP allows the agent to revise its motion plan whenever the task is not fully feasible and quantify the revised plan's violation measurement. A multi-objective optimization problem is then formulated to jointly consider the probability of task satisfaction, the violation with respect to original task constraints, and the implementation cost of the policy execution. The formulated problem can be solved via coupled linear programs. To the best of our knowledge, this work first bridges the gap between probabilistic planning revision of potential infeasible LTL specifications and optimal control synthesis of both plan prefix and plan suffix of the trajectory over the infinite horizons. Experimental results are provided to demonstrate the effectiveness of the proposed framework.