Abstract: Classical decision-theoretic planning methods assume that the probabilistic model of the domain is always accurate. Unfortunately, for lack of information, sometimes planning modeling experts can only obtain incomplete quantitative information, or even ordinal, qualitative information for modeling the uncertainty about the world transition. Recently, LAO* has been proved to be one of the most efficient planners for solving probabilistic planning problems. Two algorithms, namely rLAO* algorithm and qLAO* algorithm, are introduced to solve non-deterministic planning problems without complete information based on LAO*. Specifically, rLAO* algorithm can solve planning problems under uncertainty with incomplete quantitative information, and qLAO* algorithm can solve planning problems under uncertainty with qualitative information. Both these two algorithms are proved to be sound and complete. Both algorithms have been implemented in the framework of two un-deterministic planners “JLU-RLAO” and “JLU-QLAO”, and compared with LAO* using a lot of benchmark problems. Experimental results show that both systems inherit the merits of excellent performance of LAO* for solving planning problems under uncertainty. Because JLU-RLAO and JLU-QLAO planners can solve planning problems under uncertainty with incomplete information, they can be regarded as complementary planners to LAO*.