  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.
