Research And Implementation Of Fast-Forward Planning For Creating Or Destroying Objects

Intelligent planning is an important branch of AI, and has been shown to be a hard problem. A fast planning method based on planning graph—Graphplan was put forward by Blum and Furst in 1995. It is the first time that using graph to solving planning problem, therefore it was considered to be a revolution in the planning field. Creating or Destroying Objects Graphplan is an planning system based on Graphplan. It could deal with the difficult problem that Graphplan hasn't solved. But CDOGP doesn't use the heuristic search in the plan searching algorithm. Fast-Forward planning system (FF) is a successful state-space search planner, which appeared in 2000's Planner Competition. It obtains heuristics via a relaxed planning graph to guide the enforced hill-climbing search strategy, but the operators in FF could not creating objects, and could not destroy objects, either, however, this kind of planning problem is widely existed in the real world.In this thesis, an approach based on forward state space search is proposed for the first time, and to some extent, it solves this difficult problem. The new method is named Fast-forward Planning for Creating or Destroying Objects (CDOFF). First of all, the concept of Object Component is presented for the first time. According to this concept, the objects in the initial set of objects are divided into two types. Secondly, Object Components Propositional Algorithms (OCP) proposed to decrease the number of nodes in the graph and save the store space, is an important composition of CDOFF. Thirdly, most of the existed heuristic function is only concerned to the goal distances, but the novel heuristic function, based on the goal distances and the utilization of resource, is designed in this thesis, and it will lead the search to the direction to a better valid plan.Based on the algorithm proposed above, we have developed a new planner by C programming language, CDOFF, which has been implemented to handle Creating or Destroying Objects planning problem. It is proved that it could deal with the CDOP problem by forward state space search method.