Planning as search: a quantitative approach

Reviewer: Mohamed E. El-Hawary

That the state of knowledge in various subfields of artificial intelligence has advanced from qualitative statements to quantitative results is exemplified by the body of results concerning the performance of heuristic search algorithms. The field of planning, however, remains at the qualitative stage. Ideally, this field focuses on problem solving in a real-world environment, where the manager may not have complete information about the world or be able to completely predict the effects of its actions. In such a situation, the manager performs several iterations of planning, executing, and then replanning a solution, based on its perceived result. Most literature on planning, however, deals with problem solving in a world of perfect information and prediction. While heuristic search uses knowledge sources such as heuristic evaluation functions, planning tends to make use of such knowledge as subgoals, macro-operators, and abstraction spaces. Arguing that planning can be considered as an extension of heuristic search, Korf examines each of these knowledge sources in turn and presents them in a unified framework. In each case he defines the knowledge in terms of a problem space and explains how, and to what extent, the knowledge reduces search in that space. He states that his paper takes the first steps in the quantitative analysis of problem-solving performance using these sources of knowledge. Korf identifies a measure called the subgoal distance as the parameter that, along with the branching factor, determines the time complexity of a search using subgoals. He explores independent, serializable, and nonserializable subgoals in turn and has found that independent subgoals divide the branching factor of a problem, serializable subgoals reduce the branching factor by ruling out certain operators, and solving nonserializable subgoals may reduce the distance to the main goal. Solving nonserializable subgoals may be worthwhile even in cases where the distance to the goal is not reduced, if the problem solver has macro-operators available that will achieve the goal from those subgoals. In the special case of serially decomposable problems, exponentially increasing numbers of initial states can be solved by storing only logarithmically more macro-operators. In the more general case of single-goal problems, a network of macros gives a multiplicative trade-off between search time and storage space. This concept can be extended into a central hub approach to handle arbitrary initial and goal states, but the penalty here is that solution lengths become proportional to the problem diameter, rather than to the distance between initial and goal states. A more highly connected macro-network to deal with the general problem of arbitrary pairs of initial and goal states results in an abstract problem space. The author found that for a single level of abstraction, the optimal size for an abstract space is the square root of the size of the base space; this choice reduces search time from linear in the size of the space to the square root of the size of the space. For multiple levels of abstraction, he found that the optimal hierarchy has a logarithmic number of levels with a constant ratio between their sizes; this hierarchy reduces search time from linear in the number of states in the problem space to logarithmic. Abstraction hierarchies can reduce exponential complexity to linear complexity because the number of states is often exponential in the problem size.

Reviewer: Jaak Tepandi

This paper presents a thesis that planning can be viewed as a problem-solving search that uses subgoals, macro operators, and abstraction as knowledge sources. The author quantifies problem-solving performance using these sources of knowledge and concludes that (1) subgoal distance may be characterized as a fundamental measure of problem difficulty, (2) macro operators provide a multiplicative time-space tradeoff, and (3) abstract hierarchies can reduce exponential problems to linear complexity. The results are interesting. The presentation is clear and sufficiently precise with useful examples and a minimal number of formulas. I enjoyed the elegant transitions from one subject to another which provide a deeper insight into the relationships between, for example, macros and abstraction. It is difficult to evaluate the usefulness of this thesis. Are there no more knowledge sources for planning—even if we view it as pure problem-solving search__?__ What happens if we switch from toy problems, such as Rubik's Cube and the eight puzzle, to planning in realistic domains__?__ The results seem applicable to problem-solving search in general, and anyone interested in planning, search, or abstraction should find this paper worth reading.