# Qualitative Analysis of POMDPs with Temporal Logic Specifications for Robotics Applications

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2014.

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

- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Pessimistic Iterative Planning with RNNs for Robust POMDPs](https://mlsanity.com/paper/2408.08770/) (2024)
- [Discrete-Event Controller Synthesis for Autonomous Systems with Deep-Learning Perception Components](https://mlsanity.com/paper/2202.03360/) (2022)
- [Reinforcement Learning under Partial Observability Guided by Learned Environment Models](https://mlsanity.com/paper/2206.11708/) (2022)
- [Compositional shield synthesis for safe reinforcement learning in partial observability](https://mlsanity.com/paper/2509.12085/) (2025)
- [Model-free Motion Planning of Autonomous Agents for Complex Tasks in Partially Observable Environments](https://mlsanity.com/paper/2305.00561/) (2023)
- [Control Synthesis in Partially Observable Environments for Complex Perception-Related Objectives](https://mlsanity.com/paper/2507.02942/) (2025)
- [Robustness Analysis of POMDP Policies to Observation Perturbations](https://mlsanity.com/paper/2604.21256/) (2026)
- [Ensuring Logic in the Fog: Sound POMDP Synthesis with LTL Objectives](https://mlsanity.com/paper/2605.12581/) (2026)

## Abstract (arXiv)

We consider partially observable Markov decision processes (POMDPs), that are a standard framework for robotics applications to model uncertainties present in the real world, with temporal logic specifications. All temporal logic specifications in linear-time temporal logic (LTL) can be expressed as parity objectives. We study the qualitative analysis problem for POMDPs with parity objectives that asks whether there is a controller (policy) to ensure that the objective holds with probability 1 (almost-surely). While the qualitative analysis of POMDPs with parity objectives is undecidable, recent results show that when restricted to finite-memory policies the problem is EXPTIME-complete. While the problem is intractable in theory, we present a practical approach to solve the qualitative analysis problem. We designed several heuristics to deal with the exponential complexity, and have used our implementation on a number of well-known POMDP examples for robotics applications. Our results provide the first practical approach to solve the qualitative analysis of robot motion planning with LTL properties in the presence of uncertainty.