2. Discrete Planning

This chapter provides introductory concepts that serve as an entry point into other parts of the book. The planning problems considered here are the simplest to describe because the state space will be finite in most cases. When it is not finite, it will at least be countably infinite (i.e., a unique integer may be assigned to every state). Therefore, no geometric models or differential equations will be needed to characterize the discrete planning problems. Furthermore, no forms of uncertainty will be considered, which avoids complications such as probability theory. All models are completely known and predictable.

There are three main parts to this chapter. Sections 2.1 and 2.2 define and present search methods for feasible planning, in which the only concern is to reach a goal state. The search methods will be used throughout the book in numerous other contexts, including motion planning in continuous state spaces. Following feasible planning, Section 2.3 addresses the problem of optimal planning. The principle of optimality, or the dynamic programming principle, [84] provides a key insight that greatly reduces the computation effort in many planning algorithms. The value-iteration method of dynamic programming is the main focus of Section 2.3. The relationship between Dijkstra's algorithm and value iteration is also discussed. Finally, Sections 2.4 and 2.5 describe logic-based representations of planning and methods that exploit these representations to make the problem easier to solve; material from these sections is not needed in later chapters.

Although this chapter addresses a form of planning, it encompasses what is sometimes referred to as problem solving. Throughout the history of artificial intelligence research, the distinction between problem solving [735] and planning has been rather elusive. The widely used textbook by Russell and Norvig [839] provides a representative, modern survey of the field of artificial intelligence. Two of its six main parts are termed ``problem-solving'' and ``planning''; however, their definitions are quite similar. The problem-solving part begins by stating, ``Problem solving agents decide what to do by finding sequences of actions that lead to desirable states'' ([839], p. 59). The planning part begins with, ``The task of coming up with a sequence of actions that will achieve a goal is called planning'' ([839], p. 375). Also, the STRIPS system [337] is widely considered as a seminal planning algorithm, and the ``PS'' part of its name stands for ``Problem Solver.'' Thus, problem solving and planning appear to be synonymous. Perhaps the term ``planning'' carries connotations of future time, whereas ``problem solving'' sounds somewhat more general. A problem-solving task might be to take evidence from a crime scene and piece together the actions taken by suspects. It might seem odd to call this a ``plan'' because it occurred in the past.

Since it is difficult to make clear distinctions between problem solving and planning, we will simply refer to both as planning. This also helps to keep with the theme of this book. Note, however, that some of the concepts apply to a broader set of problems than what is often meant by planning.