Research And Implementation Of Probabilistic Planning Algorithm With The Set Of Objects Dynamically Changing

Intelligent planning, especially uncertainty planning with probabilistic method and creating or deleting objects planning, is a popular domain in AI domains. Probabilistic planning quantificationally describes the uncertainty in real world, and it more fit to settle planning problems in real word, so it is concerned by many scholars. PGraphplan which is based on Graphplan is an excellent planner. PGraphplan produces a contingent plan beginning with top-down Dynamic programming based on Graphplan framework. But it performs under the restriction of allowing only one non-noop action per time step. This restriction makes the algorithm be less efficient than Graphplan. In planning, the increasing and decreasing of the objects abounds. So, the research on creating or deleting objects planning is more according with the environment and state of the word, and more fits to settle problems in real word. The planner CDOGP developed in 2005 is a very sound planner based on Graphplan. It presents idea of objects propositioned, which make objects be looked on propositions and easy to settle planning with set of objects dynamically changing. But in real word, common operator still exist uncertainty of action effect, even more the creating or deleting object operator. The complexity of CDO-operator is not represented in algorithm.For these problems of these two algorithms, this thesis presents new planning algorithm CDOPGP, namely probabilistic planning algorithm with the set of objects dynamically changing. We provide the concept branch of dynamical planning graph and branch probability. Based on these concepts, through permutation and combination of branch of goal proposition appearing in search, we implement parallel execute of action in probabilistic planning problem with the set of objects dynamically changing; and redefine the concept of mutually exclusive between propositions or actions or objects. It exerts effect and improves efficiency of algorithm; in addition, in this thesis, we import CDOP operator to probabilistic planning, successfully express the complexity of creating or deleting objects operator with probability, make probabilistic algorithm could settle a part of creating or deleting objects planning problems successfully.At last, based on the algorithm proposed above, we have developed a new probabilistic planning system with the set of objects dynamically changing which could settle parallel actions --CDOPGP. The experiment proves the system achieved the effect anticipatively, implement the parallel execute of actions, and find the maximal probability plan. It improves the efficient of probabilistic planner; make probabilistic planning more fit to settle the problems in real word.The new algorithm is more useful for actual problems in real word, and has upper theory research value. At the same time, the design of the CDOPGP planner, more broadens the application domain of probabilistic planning, and drives the development of probabilistic planning on the actually application side.