Analysis And Implement Of Meta-operators

Planning is one of the important topics in Artificial Intelligence domain. It is a process of selecting and arranging given actions such that the execution of actions in sequence can achieve the goal state. Due to the combination explosion problem, planning is hard to solve in that planners usually produce a huge searching space when a plan is generated. So there are a variety of planning methods featured as heuristic searching, hierachical planning or logical reasoning. Also planners adopt some optimization techniques to speedup the computation and to impove the plan quality.Meta-operator is such a technique for improving plan computation. In most of the planning problems, some actions have a close correspondence because they occur in pairs in the solution. Meta-operators describe compositions of actions, the idea behind meta-planning is to plan at the level of composite actions, which can reduce the searching path for a plan and thus improve planning performance.In this thesis, we propose an approach on generating meta-operators on the basis of Graphplan algorithm. The idea is to analyze possible relations such as cause, restriction and opposition relationship between operators, and thus yield effective meta-operators. Our algorithm consists of pre-processing, combination and generation. The combination coming as the important part shows the principles of combining operators. With the input meta-operators, we can use a Graphplan planner to perform meta planning.The experimental results reveal that our algorithm enhances the Graphplan algorithm for some classical planning problems like Blocks World. The improvement in planning performance apparantly increases with the size of planning problems.