Since the notion of generative planning became one of the touchstones of artificial intelligence, surprisingly little improvement has been made in the efficiency of generative planning algorithms. Efficient high-speed search is essential to most planning algorithms proposed to date: this can only be achieved if the search algorithms used are based on a solid understanding of the search space. The concept of search directionality-searching temporally or causally forward or backward-has been quite important to designers of generative planning algorithms. Nonetheless, this concept appears to be poorly understood.
Through a series of constructions and experiments, it is shown here that successful planners must be capable of both forward chaining and backward chaining behavior, and that understanding directionality issues in planning is a necessary precursor to the construction of efficient planners.
This work begins by discussing some of the underpinnings of directionality in planning: the physical, psychological, and computational temporal arrows that directionally orient planning problems. A previously unappreciated property of directionality in planning is then described, namely that the direction of planning problems is not a fundamental property of the standard formalism. Planning problems can be reversed, allowing a planner to search in the opposite of its normal direction without a change in planning algorithm. Next, a novel technique is described for determining the directional behavior of existing planners, and experimental results using an implementation of this technique are reported. This analysis of planner direction can be used to better understand the search strategy used in modern planning algorithms such as satisfiability-based planning. Finally, some consequences and extensions of the results are given.
Together, these results shed new light on the construction of generative planning algorithms using high-speed search, and thus move us closer to making generative planning practical for real problems.