|
The figure
to the right provides an example of some of the features of Means-Ends
Analysis as it was employed in GPS. The example problem that
we consider is to 'go from your house in New Brunswick to
your Aunt's House in Los Angeles.' GPS required knowledge
about the problem domain. This knowledge was represented in a
Difference-Operator Table. This table provides the knowledge
needed to decompose a problem into subproblems. An example of
such a table is shown in the top portion of the figure.
The basic idea
that underlies Means-Ends Analysis is that the planner has the
ability to compare two problem states and determine one or more
ways in which these problem states differ from each other. (These
problem states are thought of as partial state descriptions.
Even though partial, note that if we think of these problem states
as a set of descriptions, then there are a great
many ways in which to construct differences. Let Dif
be the union of the descriptions of the problem states
with their intersection removed. Then, the number of possible
descriptions of the way in which these problem states differ
is approximated by the power set of Dif.. )
The rows of this example table lists a way in which two problem
states might differ. The labels at the top of the columns list
an operator (action) that can reduce the difference. And, the
labels at the bottom of the columns list the partial state description
that must be satisfied in order for the operator to be applied.
For example the top row lists the possibility that the two states
are more than 1000 miles apart. For this difference only the
first column is "Xed" indicating that only the
operator associated with column one, 'use airplane' is
considered appropriate to this difference. And, at the bottom
of this column is listed the precondition associated with this
operator; namely, to 'be at airport.'
|
|
|
The remainder of this figure illustrates
a "trace" of the recursive application of the Means
End Analysis procedure. Note the "problem state names"
depicted in the lower part of the figure. These are Sstart,
Sa, ... , Sg, Sgoal. This alphabetical listing mirrors the
order in which they were generated in the planning phase. Note
that this is quite different from the execution ordering depicted
by their location on the dotted red line. For example, Sa is
the first intermediate problem state considered but it occurs
in the middle of the time line that represents the order in which
the actions must be executed.
A careful study
of the trace reveals the way in which this procedure can introduce
"island states."
|
