In Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems, pages 78-84, 1998.
The Prodigy system is based on bidirectional planning, which is a combination of goal-directed backward chaining with simulation of plan execution. Experiments have demonstrated that it is an efficient technique, a fair match to other successful planning systems. The question of completeness of bidirectional planning, however, has remained unanswered.
We show that Prodigy is not complete and discuss the advantages and drawbacks of its incompleteness. We then develop a complete bidirectional planner and compare it experimentally with Prodigy. We demonstrate that the complete planner is almost as efficient as Prodigy and solves a wider range of problems.