Figure Planning Under The Framework Of The Decision-making Probabilistic Planning And Its Implementation

Now Intelligent Planning is a very hot branch in AI. Because of its wide application researchers pay much attention to planning technology. Especially, planning under uncertainty and incomplete has become the focal point studied. In various kinds of research approaches, because the probability method can describe the uncertain information ration relatively accurately, so study the probabilistic planning that the operator has probabilistic outcome relatively strong superiority in method. Many researchers are in favor of this method and has produced a large amount of algorithms on the basis of this. Because research approaches of the probabilistic planning and Markov decision processes are very similar again, so a lot of researchers have done a large amount of work in the combination between the two. In the 2004 International Planning Competition that hold this year,list the probability domain in the project of the contest for the first time. This indicates again that probabilistic planning is the important status of the research field in intelligent planning. This text analyses probabilistic planning research current situation from presentation methods,planning types,algorithm complexity,planning language, sum up various kinds of theories and technology relevant to the study method of probabilistic planning, announce the relation between probabilistic planning and Markov decision processes. Also apply the decision theory to probabilistic planning, define the probabilistic under utility model, put forward the corresponding algorithm DPG. We sets up the DPG algorithm structure above the probabilistic PlanGraph which have the rapidly propagating ability. Combing the Dynamic Programming, with forward search method, get a optimal planning solution in finite time step. We have realized this algorithm in C language and improved the complexity of the algorithm is in polynomial in finite time step. By the experimental result, we clarify every factor under utility model impact on optimum planning solution and DPG algorithm complexity. At last, we pointed out the merit of the algorithm: This is the extension to the probabilistic planning and the successful application of the MDPs.