  In this paper, we develop a Topological Approximate Dynamic Programming
(TADP) method for planningin stochastic systems modeled as Markov Decision
Processesto maximize the probability of satisfying high-level
systemspecifications expressed in Linear Temporal Logic (LTL). Ourmethod
includes two steps: First, we propose to decompose theplanning problem into a
sequence of sub-problems based on thetopological property of the task automaton
which is translatedfrom the LTL constraints. Second, we extend a
model-freeapproximate dynamic programming method for value iterationto solve,
in an order reverse to a causal dependency of valuefunctions, one for each
state in the task automaton. Particularly,we show that the complexity of the
TADP does not growpolynomially with the size of the product Markov
DecisionProcess (MDP). The correctness and efficiency of the algorithmare
demonstrated using a robotic motion planning example.
