Example of NonLinear Planning
|
Planning is
a process that involves making a great many decisions. And, the
planner typically can not know the effect that any particular
decision will have on the plan. Consequently, decisions may need
to be withdrawn and different decisions made in order to succeed
in the creation of a viable plan.
The decision
of how to decompose a problem or goal into subproblems is explicit
in all of the planning algorithms that we have considered. But
if we examine the planning process a bit more analytically it
will become apparent that there are many additional decisions
that must be made once a decomposition has been chosen. A list
of some of the decisions that are made during the planning process
include:
- a choice of which decomposition
to use to solve the problem;
- a choice of the order in which
to plan the solution of the unsolved subproblems;
- a choice of which objects in
the domain to bind to the actions chosen for use in solving the
problem;
- a choice of the order in which
to execute the actions of the plan
When one decision affects another
decision we say that the decisions are dependent. Or equivalently,
we say that one decision constrains another. If one decision
has no effect on another decision, then we say the decisions
are independent. For example, if I decide to drink
a glass of wine and there is no wine opened, then I must
decide to open a bottle of wine. In this case to
open a bottle of wine is a decision that is dependent
on the decision to drink a glass of wine. Note
that (for some) the dependency is logically asymmetrical. That
is, the decision to open a bottle of wine could have been made,
for whatever reason, and this decision would not have necessitated
drinking some of the wine. (I could, for example, let my friends
drink it all and not partake myself.) But dependencies among
subproblems need not always be asymmetric. Perhaps, after we
have all been sated on some good wine, we decide to make some
coffee. For this both water and ground coffee are required. There
is a strong dependency here, and this dependency is symmetric.
Whether I choose to solve the problem of obtaining water or obtaining
coffee first will probably have no effect on either task. Finally,
the choice of music to listen to will probably be a choice that
can be made independently of the choices involved in having wine
or coffee.
Another way
to think about these issues of dependencies that arise in planning
decisions is to see that one decision may commit one to
making other decisions and to making them in a particular way.
What researchers began to explore was the possibility of defining
a planning method that deferred the making of commitments as
long as possible. This was referred to as Least Commitment
Planning. The idea is not to make any decisions until the
planning process forces the decision. If a decision is made prior
to such forcing, one may make the wrong decision and have to
retract it and make another. But if the decision can be deferred
until one is forced to make it, then presumably the decisions
on which the decision depends will have already been made
they are the forcing decisions. And if a decision is not forced,
then in the best case, this decision is independent of all others
and will not affect them. Or, in the worst case, other decisions
depend on it but not conversely. Thus, Least Commitment Planning,
doesn't guarantee a solution to the problems inherent in planning
(after all. planning is an intractable problem) but it may often
simplify the planning process.
|
|
The figure to the right illustrates one kind
of Least Commitment Planning that was explored. Again
a simple blocks problem serves as the example problem. This example
problem is illustrated at the top of the figure. In this example,
the decision that is deferred is that of ordering the
execution of the plan. Recall that in STRIPS the execution order
was linearly related to the planning order. Consequently, the
order of planning forced the planner to choose a particular execution
ordering. In NOAH, the name given to the planning system considered
here; the planning order and execution order are not necessarily
linearly related thus, the reference to this planning as
non linear planning.
Note that in order
to defer decisions the planner must maintain a global
view of the plan as it evolves. While planning, STRIPS enjoyed
no such global view. The stack served as the representation used
to control planning. When the plan was represented as a Triangle
Table STRIPS created what we might call a global view of the
plan. The Triangle Table was a data structure that allowed a
process to determine whether or not one action depended on another.
If the cell in the column of operator i-k and in the row
of operator i contained an entry, then operator i
depended on operator i-k. And, operator i-k had
to be executed prior to operator i in order for the plan
to be viable.
NOAH maintains
information about the evolving plan in a data structure that
is illustrated in this figure as a graph with different types
of nodes. The yellow node is referred to as a split and
the blue node as a join. The graph is used to represent
the partial order of the actions of the plan as it evolves during
the planning process. The split node indicates that the
nodes connected to it are unordered. The join node indicates
that the nodes connected to it are ordered.
The figure
is divided into Levels. These are simply used to convey the steps
in the planning process. At Level 1, shown at the top of the
figure, there is a single "action node" that simply
asserts that the goal is to be achieved. There is no action that
directly achieves this goal. Consequently, at Level 2 the goal
is decomposed into two separate actions. Note that a split
node points to each of these two action nodes. This indicates
that at this stage in the planning no decision has been made
concerning the ordering of these actions. Rather, the default
decision chosen by NOAH is to leave them unordered a decision
that represents the least commitment that can be made concerning
the ordering decision.
At Level 3
the actions of Put A on B and Put B on C are identified.
The green nodes represent a precondition for the associated action
that is true in the initial state, S0. The red rectangular nodes represent
a precondition for the associated action that is false in the
initial state, S0. Note that at this point the subproblems
are only ordered with respect to the action.
Since two actions
have now been chosen it is possible that these actions must be
ordered. This is determined through the use of predicates that
are referred to as Critics. For example, if a true precondition
for an action, say Put B on C is made false by the outcome
of another action, say Put A on B; then the critic that
tests for this condition has identified a conflict due to the
dependency between these actions. The conflict can be resolved
if Put A on B is done before Put B on C .
|
|
|
Note that Level
3 is repeated with the annotation (after criticism) and now these
two actions have been ordered since the criticism has forced
the planner to make this decision in order to insure the correctness
of the evolving plan. The rest of the graph illustrates the continuation
of this cycle of introducing actions and subproblems, critiquing
the plan, and resolving any conflicts that have been detected.
In this example,
we have focused only on the ordering decision. The idea of using
critics to examine the evolving plan can be extended to other
decisions. For example, a Use Existing Objects Critic
can be defined. For example, if I need to open two bottles of
wine then I can do this with either the same wine opener or with
a different opener. If during planning two different openers
had been chosen, then the Use Existing Objects Critic would
recognize this decision. Then, the decision could be revised
so that only one opener is used; thus simplifying the plan.
Additional
Critics can be defined. However, note that the evolving plan
is critiqued at each Level. And, this critiquing process itself
can be computationally intensive. For example, the critic that
tests for the interaction of actions examines all of the outcomes
of an action against all of the preconditions of another action
for all pairs of actions that are not currently ordered with
respect to each other. A cloase examination of an abstraction
of both the Linear and NonLinear algorithms
reveals that both algorithms are computationally intensive.
|
|
|
