Research And Implementation Of Parallel Plan Via Forward State Space Search

Intelligence Planning has been an active research and applications field concerned with action and plan representation, plan synthesis and reasoning, analysis of planning algorithms, plan execution and so on. Specially, planning approach based on state space search is a popular domain in the field, FF with forward state space search and AltAlt with regression state space search are the representations of this approach. But they perform under the restriction of allowing only one non-noop action per time step. This restriction makes the lengthy planning that algorithm gain and the plan gained didn't satisfy the requirement of realistic application field. For solving parallel plan, the approach based on state space search still faces the problem of exponential branching factor. AltAlt-p planner with regression state space search breaks these restrictions, but it is too strict to keep the branches that contain the plan solutions and then loss the chances gained approximate optimal plan solutions.For these problems, the parallel planning algorithm based on forward state space search was proposed. We implement the planning algorithm by proposing two new concepts: independent action and interaction between two actions. The approach not only makes up, a certain extent, the drawbacks of FF's in completeness, but also finds a standoff between completeness and optimality. The algorithm takes use of relaxed GraphPlan and improves the quality of plan solution, and then finds shorter plan solutions. So it fits into the requirement of realistic application field.Based on the algorithm proposed above, we have developed a new planner by C programming language, PPFF, which has been implemented to handle parallel actions in planning problems. Due to it can find the approximate optimal and shortest plan and improve the plan quality, so PPFF is more useful for actual problems and enlarge the application domains of the planning.