Formalizing the PRODIGY Planning Algorithm

The PRODIGY project is primarily concerned with the integration of planning and learning. Members of the PRODIGY research group have developed many learning algorithms for improving planning efficiency and plan quality, and for automatically acquiring knowledge about the properties of planning domains. The details of the PRODIGY planning algorithm, however, have not been described in the literature. We present a formal description of the planning algorithm used in the current version of the PRODIGY system. The algorithm is based on an interesting combination of backward-chaining planning with simulation of plan execution. The backward-chainer selects goal-relevant operators and then the planner simulates the application of these operators to the current state of the world. The system can use different backward-chaining algorithms, two of which are presented in the paper.