A complete bidirectional planner
Eugene Fink, Jim Blythe · 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, hasremainedunanswered. We show that PRODIGY is not complete and discuss the advantagesand 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. Introduction Newell and Simon invented means-ends analysis during their work on General Problem Solver, back in the early days of artificial intelligence. Their technique combined goaldirected reasoning with forward chaining from the initial state (Newell and Simon 1961). The authors of later planning systems (Fikes and Nilsson...