Research And Implementation Of Probabilistic Planner Based On Mutex Constraint And Its Extended Algorithm

Now Intelligent Planning is a very hot branch in AI. Because of its wideapplication researchers pay much attention to planning technology. Especially,planning under uncertainty and incomplete has become the focal point studied. Invarious kinds of research approaches, because the probability method can describethe uncertain information ration relatively accurately, so study the probabilisticplanning that the operator has probabilistic outcome relatively strong superiority inmethod. Many researchers are in favor of this method and has produced a largeamount of algorithms on the basis of this. In the 2004 International PlanningCompetition that hold this year,list the probability domain in the project of thecontest for the first time. This indicates again that probabilistic planning is theimportant status of the research field in intelligent planning. Researchers in Intelligent Planning area develop some planners which solveuncertain and incomplete planning problem. Blum and Langford developprobabilistic GraphPlan(PGP). Experimental result indicates that PGP outperformsother planners which solve congeneric problem, such asBurdian,Weaver,MaxPlan. But PGP can only solve STRIP planning problem,planning problems with conditional effect action can't be solved by PGP. This text firstly analyses probabilistic planning research current situationfrom presentation methods, planning types, algorithm complexity, planninglanguage, sum up various kinds of theories and technology relevant to the studymethod of probabilistic planning, and introduces technique of dealing withconditional effect in classical and probabilistic planners respectively. Secondly thetext introduces main works by myself which include two sections. The first is toresearch and implement probabilistic planner based on mutex constraint. Thisplanner is improved from PGP, decreases the amount of nodes in the planninggraph and saves storage space. The second is to introduce algorithm of dealingwith probabilistic planning problem with conditional effect action. Finally the textclarifies the future work: implement the algorithm in the second section.