Prodigy bidirectional planning

Eugene Fink and Jim Blythe

Journal of Experimental and Theoretical Artificial Intelligence, 17(3), pages 161-200, 2005.


The Prodigy system is based on bidirectional planning, which is a combination of goal-directed reasoning with simulated execution. Researchers have implemented a series of planners that utilize this search strategy, and demonstrated that it is an efficient technique, a fair match to other successful planners; however, they have provided few formal results on the common principles underlying the developed algorithms.

We formalize bidirectional planning, elucidate some techniques for improving its efficiency, and show how different strategies for controlling search complexity give rise to different versions of Prodigy. In particular, we demonstrate that Prodigy is incomplete and discuss advantages and drawbacks of its incompleteness.  We then develop a complete bidirectional planner and compare it experimentally with Prodigy. We show that the complete planner is almost as fast as Prodigy and solves a wider range of problems.