CDOFF: Fast-Forward Planning for Creating or Destroying Objects

Creating or destroying objects planning (CDOP) was put forward by Blum & Furst in 1995, and it hasn´t been solved very well until now. In this paper, an approach based on heuristic search is proposed to solve this problem. The concept of object component is presented for the first time. Based on this concept, Refined CDOGP algorithm is designed to minimize the number of nodes in the graph and save some storage space at the same time. Partial relaxed planning task could avoid some dead-end states. Based on the goal distances and the utilization of resource, a novel heuristic function is designed in this paper, and it will lead the search to the direction to a better valid plan. The whole plan process is named Creating or Destroying Objects Fast-Forward Planning (CDOFF). It is a very significative research, because it can be applied in many fields.