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.
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.
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.