Research And Implementation Of Probabilistic Planning With Parallel Actions

Intelligent planning, especially uncertainty planning with probabilistic method, is a popular domain in AI domains. Probabilistic planning quantificationally describes the dynamic world, and gives contingent planning for uncertainty planning problems. More and more studies devote into researching probabilistic planning problems. 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.For this problem, we proposed PPGraphplan in this paper. In order to eliminate the restriction in Pgraphplan, we propose a new concept of parallel action set and give the algorithm for creating parallel action set too. We also use mutex information in PPGraphplan to improve planner's performance and find the shortest plan. PPGraphplan contains two phases: extending planning graph and extracting valid plan. We sign and propagate the information of mutex with planning graph in the first phase, and find optimal parallel action set instead of optimal action in the second phase using Dynamic programming. PPGraphplan breaches the restriction"allows only one non-noop action per time step", and it can find the optimal and shortest plan.Based on the algorithm proposed above, we have developed a new planer--PPGraphplan, which realizes handling parallel actions in probabilistic planning problems. Due to it can find the optimal and shortest plan, so PPGraphplan is more useful for actual problems and enlarge the application domains of the probabilistic planning.