Classical decision-theoretic planning methods assume that the probabilistic model of the domain is always accurate. We present two algorithms rLAO* and qLAO* in this paper. rLAO* and qLAO* can solve uncertainty Markov decision problems and qualitative Markov decision problems respectively. We prove that given an admissible heuristic function, both rLAO* and qLAO* can find an optimal solution. Experimental results also show that rLAO* and qLAO* inherit the merits of excellent performance of LAO* for solving uncertainty problems.