Introduction to Planning

Planning and Problem Solving

   As we will see, many of the same issues addressed in problem solving research arise in planning research. However, the term 'planning' is typically used in AI when the problem is a "real-world" problem. The scare quotes surround "real-world" because many of the examples in the planning literature are based on block-stacking problems. Stacking blocks is perhaps a real-world problem prior to the age of four, but most of us don't spend much time stacking blocks in our respective "real-worlds".

   It is very difficult and usually impossible to solve real "real-world" problems using the method of state space search. State Space Search has two properties which contribute to this difficulty. State Space Search requires complete description of the states searched and requires the search to be carried out locally.

   Completely describing each state that is expanded during a search can be computationally expensive when real world problems are involved. In puzzle problems such as the 15 puzzle, the total information about a current state can be represented using 16 atomic expressions that declare the occupancy status of each location together with an invariant set of expressions that describe the contiguity structure of the locations. This is a relatively small number of expressions. Compare this to the number of expressions required to represent something as mundane as the room in which you are currently located. The method of problem reduction operates on descriptions of "problem states." These problem states are partial rather than complete descriptions of a state of the world. Some variant of the method of problem reduction is used in most of the planning research that we will encounter.

   The local property of state space search refers to the fact that search can proceed only by expanding states that are directly reachable from the current state. Many of the examples of problem reduction that will be examined allow for the generation of so-called "island states." An island state (or really a partial state) is a state through which the planner believes the solution must pass. For example, to attend a particular rock concert, the planner may believe that a ticket to this concert will be required. Put another way, this is a belief that the solution path will involve passing through at least one state in which the planner possesses a ticket to the concert. The significance of island states can be appreciated if we consider the combinatorics of orderings of actions. If a solution to a problem requires only 7 actions, then there are potentially 7! or 5,040 possible orderings of these actions. However, if one of these actions must occur as the fourth action and we know which action must occur in this position then there are now only 2(3!) or 12 possible orderings to consider. The ability to introduce information about partial states that aren't directly reachable from a current state allows problem reduction methods to escape the limitations of the local property of state space search.

A Planning Paradigm

   Planning is a ubiquitous aspect of our mental lives. The initial AI research on planning adopted some strong assumptions in order to begin to computationally investigate planning. These assumptions are listed below.

Assumptions of the "Standard" AI Planning Paradigm

  • There is a single causal agent and this agent is the planner;
    • Representing and reasoning about several causal sources; entities that can affect change in the world, greatly complicates planning; and perhaps necessitates that planning take a different form. Research began with this simpler and more tractable situation where only the planner can affect the world. Thus, the planner has complete control over the changes that occur.
  • The planner is given a well-defined goal which remains fixed over the course of planning;
    • The expressions that describe the goal are crucially involved in the planning process. If these are ill-defined the planning is impossible. And, since the choice of actions is dictated by the goal, if the goal changes then all of these decisions must be revisited and potentially revised.
  • The planner is assumed to have functionally complete and accurate knowledge of the starting situation;
    • Note the term 'functionally complete.' The planner needs to know everything necessary to create a plan that will be successful. This may include very little knowledge of the starting situation or a great deal. Deciding what needs to be known is part of what can make planning difficult. And, if the functionally important knowledge is not accurate, then the planner can't be sure that the plan created will be successful.
  • The planner is assumed to possess the knowledge required to accurately model the world;
    • Without this requirement there is no guarantee that the plan created will be successful.
  • The planner is assumed to possess the resources (time and memory) required to use this model to reason about the possible worlds associated with the different courses of action that might be pursued.
    • Planning is, in general, an intractable problem. And, if the world is complex then modeling the world may also be intractable. This assumption is simply a warning to restrict the research to tractable planning domains.

   Researchers have begun to investigate computational models of planning in which one or more of these assumptions is violated. We will focus on the early planning research that was developed around the "Standard" AI Planning Paradigm. We begin with an example that illustrates the way in which GPS (General Problem Solver) implemented a version of problem reduction search that Newell and Simon termed Means-Ends Analysis. Next we introduce the distinction between Linear and NonLinear planners and illustrate this distinction by examining the STRIPs Planner and NOAH, a nonlinear planner

GPS
 © Charles F. Schmidt

Planning - Table of Contents