Research And Implementation Of Probabilistic Planning For Creating Or Destroying Objects

The research on the Intelligence Planning has become a popular domain in AI. Especially in 1995 Blum and J. Langford presented the Fast Planning Through Planning Graph Analysis (Graphplan) which extremely promotes the development of the Intelligence Planning. Many planners afterwards are on the base of Graphplan, for example the PGraphplan proposed in 1999 applied the Graphplan to the probabilistic planning problems. But the objects in PGraphplan are still static, that is to say the actions in the planning problems can neither create nor destroy objects. There is a problem that the actions in the plan can neither create nor destroy objects which was proposed at a international conference early in 1995. That problem was partly solved until Wen-xiang GU and his students proposed the planning system CDOGP. But the planning problems in CDOGP are still determined and the planner can't solve the undetermined planning problems or planning problems with probability.For the problem in intelligent planning, we extend CDOGP to handle the probabilistic planning problems based on the creating or deleting objects. First of all we redefined the exclusion relations because of the actions'undetermination in probabilistic planning. We add the exclusion relations between object propositions in our paper. Then we propose the concept of concurrent action set which allowed multiple actions executing in parallel. We give the algorithm to create the concurrent action set and make up the drawbacks in classical probabilistic planning that only one action can be executed at a time step. After that we adopt the thought of transforming the objects to propositions to deal with the problems and the dynamic objects in planning problems can be treated. Finally,we developed the planner PCDOGP by C programming language and achieved the expected effect. The planner PCDOGP can solve the probabilistic planning problems for creating or destroying objects quickly and the actions in plan can be executed in parallel.In the paper, based on the algorithm proposed above, we have developed a new probabilistic planning system which could create or destroy objects—PCDOGP. The experiment proves our algorithm is effective indeed. Consequently we can solve the planning problems quickly and reduce the length of the solution.