Possibilistic Planning Using Possibilistic Decision Diagrams

The earlier studies have concentrate on the classical planning problems under the assumption of"Closed World", however, most of the practical problems don't meet such rigorous assumptions. Therefore, several researchers started to focus on the uncertainty planning problems, and certain achievements have been made on the research of probabilistic planning problems, yet, the transition probabilities for representing the effects of actions are not always available, especially in Artificial Intelligence applications where uncertainty is often ordinal, qualitative. Some researchers have advocated that possibilistic theory is more suitable for the problems unsolved by the probabilistic models or with the probabilistic information difficulty to get. They put forward the possibilistic planning problems in which the initial planning world state is partial known with graded preference. However, the possibilistic value iteration are often effective for small problems, typical AI planning problems fall prey to Bellman's curse of dimensionality: the size of the state space grows exponentially with the number of domain features.Meanwhile, the resolving methods of intelligence planning have a revolutionary change under the efforts of generations of researchers. The resolving methods coming from resolution theorem proving, to STRIPS methods, and converting planning problems to satisfiability problems and exploiting Model checking methods to solve planning problems. Especially, the last method has done a good job. In the 2000 Planning Competition, the planning system named MIPS(The Model Checking Integrated Planning System) making use of Binary Decision Diagrams to represent the states of planning problems, has expanded the search space effectively.In this paper, we introduced Possibilistic Decision Diagrams as a new decision diagrams to encode imprecise and vague information under uncertain environment on basis of possibility theory and decision diagrams theory. We prove that our Possibilistic Decision Diagrams can give a canonical representation of Possibilistic propositional formula. And we define the operations that can be applied on the Possibilistic Decision Diagrams: taking max,taking min and taking reverse. And we make use of the Possibilistic Decision Diagrams in our new algorithms called PPUPDDs to solve the possibilistic planning problems by constructing optimal possibilistic policies. We exploit the Possibilistic Decision Diagrams to represent the possibilistic value functions and possibilistic policies by capturing some regulations from the dynamic networks of action and utility to accomplish the possibilistic iteration algorithms which make our PPUPDDs algorithms outstanding for less storage space cost and less computational time cost. We run our PPUPDDs algorithms on Factory,Moat-Castle and Block possibilistic planning domain to obtain excellent performance.