Research And Implementation Of Concurrent Probabilistic Planning With Utility Theory

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.PGraphplan is a sound planner based on Graphplan for probabilistic planning problems and it produces a contingent plan beginning with top-down dynamic programming. But it performs under the restriction of allowing only one non-noop action per time step. This restriction makes the algorithm gain lengthy planning and cost more time and space. The extension of PGraphplan can not breach this constrain. PGraphplan algorithm only consider probability information, and does not involve any state of the utility value of information. It is not easy to deal with the real world problem.For these problems, we proposed UC-PGraphplan in this paper. First, we expansion the classical plans by adding result nodes and propose a new concept of parallel valid trajectories and mutex information in UC-PGraphplan to improve planner's performance. As many contain all the valid trajectories to achieve at the same time step. UC-PGraphplan breaches the restriction"allows only one non-noop action per time step", and it can find the optimal plan. Second, we use the utility theory in the UC-PGraphplan, that all objectives can be accomplished with the greatest value of expected utility. Thus, it can enhance the quality of planning for the solution. The algorithm is more suited to solve real-world problems in the planning.Based on the algorithm proposed above, we have developed a new planer: UC -PGraphplan, which realizes handling parallel valid trajectories in probabilistic planning problems. Due to it can find the optimal plan, so UC-PGraphplan is more useful for actual problems and enlarge the application domains of the probabilistic planning.