Prodigy bidirectional planning
Journal of
Experimental and Theoretical Artificial Intelligence, 17(3), pages
161-200, 2005.
Abstract
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.