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, called Rasputin, and compare it experimentally with Prodigy. We demonstrate that the new planner is almost as efficient as Prodigy and can solve more problems.