Research On Presentation And Solution Of Possibilistic Planning Problems

Planning research have been centralizing in classical planning problems based on the assumptions that actions are deterministic, the initial state is known and the goal is defined by a set of final states for earlier years. However, most practical problems do not satisfy these conditions of complete and deterministic information. Therefore, many researchers have been taking up with the study of uncertainty planning. Most research on it are centralised in probabilistic planning based on MDP models and dynamic programming or state-space search methods. But transition probabilities for the representation of the effects of actions are not available easily, especially in AI applications where uncertainty is often ordinal, qualitative. A few researchers have advanced the qualitative view of decision making and qualitative versions of decision theory. And yet some researchers think possibility that the uncertainty on states and effects of actions represented by possibility distributions is more adequate to cases in which problems can not be resolved by probability model or the probabilities are not available, not reliable, or hard to obtain.We introduce a possibilistic planning presentation approach based on PDDL (Planning Domain Definition Language)named Poss-PDDL, and provide an algorithm resolving possibilistic planning problems represented by Poss-PDDL based on Graphplan and qualitative utility theory in the framework of potheory, where both preferences and uncertainty are qualitative. We also design and develop possibilistic planning problem solver——Poss-Graphplan. Poss-PDDL is more universal and normal for PDDL has been the criteria plan domain definition language. As the uncertainty on states and effects of actions represented by possibility distributions is well-suitable for cases in which the probabilities are not available, not reliable, or hard to obtain, our approach is more fit for solving uncertain planning problems. The experiments show that our algorithm has excellent performance in terms of solving ability and efficiency.