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.


Planning - Table of Contents

 © Charles F. Schmidt