Directions in planning: Understanding the flow of time in planning. Dissertation, available at http://www.cs.pdx.edu/ bart/papers.html

Since the notion of general purpose planning became one of the touchstones of artificial intelligence, surprisingly little improvement has been made in the efficiency of 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 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