Basic Plan-Generating Systems

notes by: Eyal Amir July 11, 1996

This is a summary of [Nilsson 80], plus a commentary from Nils Nilsson.

1 Basic Plan-Generating Systems

1.1 Robot Problem Solving

1.1.1 Assumptions • Goal of the form A(x) ∧ B(x).

• Initial and Intermediate of the form A(X) ∧ B(X).

• F-rule has the form (P,D,A) where P comes for Preconditions, D comes for Delete List and A comes for Add List. All are lists of literals, with variables quantified existentially.

• Matching is done between the State description, and the F-rule’s preconditions, using an mgu.

• STRIPS uses this formalism.

1.1.2 Buzzwords • CWA is used in STRIPS.

• The Frame Problem is avoided in STRIPS.

• F-rules are not effective in a world where chain reactions occur.

• STRIPS assumes that the components of the world are sufficiently decoupled.

• F-rules are good for normal behavior and are inaccurate for abnormal.

1.2 A Forward Production System

Forward search is feasible only if we are in a small search space, or if we have a well-informed evaluation function.

1.3 A Representation For Plans

• A Plan is a sequence of F-rules.

• Triangular Tables are used to keep additional information, analyze the execution of a plan.

• The i-th kernel is the list of facts needed to execute the plan from the i-th rule on. Useful for recovering from an unexpected situation.

• Maximum Matching Kernel is one way of using the kernel for recovering a plan. There is a pretty efficient algorithm for that.

1.4 A Backward Production System

• B-rules are used to regress the Goal state to the Initial State. One way of specifying B-ruls is to create them using F-rules.

• Regression is done for a Literal in the Goal, and then applied to the other parts of the Goal, using the same F-rule and the same instantiation of variables.

• Cases F u is a ground instance of an F-rule. Different instantiation completions are possible for a partially instantiated F-rule. Several mgu’s are available.

• Unachievable Goals can occur if

1. Regressing to F.

2. Internally Inconsistent State.

3. CWA implies inconsistency.

• Pruning nodes when either a node is Unachievable, or is identical to (or contains) one of its ancestors.

1.4.1 Interacting Goals

We might want to separate our goal into its distinct parts, and solve them one after the other (or even solve each one of them separately, and then hope to combine the solutions). But sometimes the components of a goal interact.

1.5 STRIPS

STRIPS is a planning system introduced by Fikes and Nilsson in 1971. It has many versions and is basically comprised of 3 parts:

1. A world model (mostly states).

2. Operators on worlds - F-rules.

3. Plan generator - sometimes GPS (see below), but there are others.

The following will describe STRIPS as it is described in [Nilsson 80], but the reader should note Nilsson’s remark in section 3.

STRIPS is based on the general strategy that most of the time, component goals do not interact. For special interactions, there are special handles.

• Splitting the Goal.

• Replacing a single-literal Goal with an F-rule and its Precond.

• Matching a Goal to the State.

• Applying the F-rule to the State.

1.5.1 Decisions By STRIPS

• Order of Components (the subgoals)

• Instantiation of variables (several mgu’s, several cases)

• What F-rule to choose when several are applicable

• Which leaf-node to expand next (heuristic in a graph search)

• Recursive Backtracking Strips (DFS)

1.5.2 GPS

GPS (General Problem Solver) was a preceding system to both SOAR and STRIPS. GPS is different than STRIPS in that it does not reduce the Goal, but rather performs a means-ends analysis. It requires a ’difference table’ to be specified for each application it is applied to.

GPS selects an F-rule and evaluates it as a “distance-reducer” between the goal and the current state. It would then do the process recursively for the F-rule’s precondition, and the distance between the outcome of applying the F-rule to the Goal.

Recursive STRIPS can be regarded as a special case of GPS, where differences between the State and the Goal are those components of the Goal unmatched by the State, and where all F-rules whose add list contains a literal L are considered relevant to reducing the difference L.

1.5.3 STRIPS can not...

It can not solve the register-swapping problem, because it will always delete one of the values in the attempt to first achieve one of the subgoals.

1.6 Deduction Systems Generating Robot Plans

1.6.1 Green’s Approach (Sit. Calculus 1)

It encounters the Frame Problem again. In Greens approach, the frame axioms should be mentioned explicitly (not applicable for large DBs). He uses resolution for refutation of the Goal.

ON(A, D, S0)

1.6.2 Kowalski’s Formulation (Sit. Calculus 2)

This formalization uses fluent names instead of fluent predicates (used in Green’s Approach). Thus we can quantify over fluents.

HOLDS(on(A, D), S0)

2 Advanced (1980’s point of view) Plan-Generating Systems

This section deals mostly with interacting subgoals.

2.1 RSTRIPS

RSTRIPTS is a modification of STRIPS, developed by Warren (1974) (later incorporated in Warren’s WARPLAN) and Waldinger (1977), that uses a goal regression mechanism for circumventing goal interaction problems.

It always keeps a list of Protected subgoals, and maintains it through the development of the plan. For a given point in the planning process, it checks if a desired F-rule violates some protections. There can be two cases:

• Protected subgoal reachieved - we are fine.

• Otherwise - regress the violator literal (the one that needs the violating F-rule) through the F-tule that created the Protected one, and put the regressed subgoal before that F-rule.

This way the Sussman anomaly for the Blocks-world is solved. In the Registers-swap case, we get to an Impossible goal, and the regression as explained above works as well.

2.2 DCOMP

DCOMP is based on Sacerdoti’s (1975,1977) and Tate’s (1976,1977) ideas for developing “nonlinear” plans.

The system creates a plan in two (and possibly three) stages. The first creates an AND-OR plan tree according to the goal, assuming that there are no interactions among the subgoals. The second tries to put some more ordering constraints on the plan to make it consistent with the interactions. If it was unable to do so, it takes the best plan (according to some measurements) and runs it through the third stage, in which it will try to add subplans that will amend the need for preconditions that were not satisfied in the second stage.

2.3 Hierarchical Planning (again - 1980’s-wise)

2.3.1 ABSTRIPS

A version of STRIPS, developed by Sacerdoti (1974), that works in several layers of details. It is comprised of a hierarchy graph for the literals, according to which the planning is done, and the planner for each stage (which is in this case STRIPS).

The following notations will be that level 1 is the lowest level (all the details), and level n is the highest level (least detailed). In a planning stage i literals that are in level < i will be transparent and will not be considered. That means that we actually remove these literals that are not considered from the Precondition and the Delete lists, for this stage. Then we apply the level planner on the basis of the plan generated in the level above (level i + 1). When we get to level 1, the plan generated there is the final one. If in any stage we can not construct an elaboration of the plan for the upper level, we backtrack and try to find a different solution in the preceding level.

The STRIPS planner has no problem using the above-level plan as the plan’s skeleton, because its way of work causes level i to find a solution for the (level i) preconditions of the inherited (level i + 1) F-rules.

One should notice that there might be inconsistencies in the states in the higher level plans (because we do not delete transparent literals), but they should be ignored in these plans.

2.3.2 Variations

One can take RSTRIPS or DCOMP, or any other planner that can incorporate an elaboration of a given plan, as the level planner instead of STRIPS in the above ABSTRIPS.

One special example of a variation is a Two-level hierarchical planner, where one can specify the Postponed literals in the exact F-rules, so that we get a better degree of accuracy, for some of the F-rules, some literals are unimportant for a upper-level planning, while for other F-rules, it is the most essential part. For example:

• putdown(x)

P &D : HOLDING(x)

A : ONT ABLE(x), CLEAR(x), HANDEMP T Y

• stack(x, y)

P &D : P -HOLDING(x), CLEAR(y) A : HANDEMP T Y, ON(x, y), CLEAR(x)

Here the preceding P means Postponed.

This system is based on Sacerdoti’s (1977) NOAH system, which combines hierarchical and nonlinear planning.

3 Conclusions

The main incentives behind the creation of STRIPS were the Frame Problem and the search problems involved with theorem proving.

When Sunil recently asked Nils Nilsson for his stance on STRIPS, he got the following (very enlightenning) reply

There are three aspects to STRIPS:

a) the STRIPS operator formalism (preconditions, delete list, and add list describing how a set of formulas is changed when an action modeled by the operator is applied and the conditions under which it can be applied),

b) the format for the world model and the goal conditions (predicate calculus formulas of various kinds) , and

c) the planning system itself that uses the world model, the goal, and the STRIPS operators to develop a plan.

Usually ”STRIPS” is used to refer to the planning system (c), but much of the theoretical material also deals with (a) and (b). And, the planning systems themselves vary greatly.

Here are some of the questions that must be asked about a, b, and c:

What kinds of formulas are allowed in the world model? Full FOPC?, Ground formulas? Ground literals? What kinds of formulas are allowed as goals? Performance and capabilities depend on what kinds of model and goals one assumes.

What kinds of formulas are allowed in the operators. Can the preconditions be full FOPC? If so, what is the role of existential variables when selecting bindings for the other variables in the operator? Are the operators to be considered ”operator schemas?” That is, are all variables in the operators ”schema variables?” If so, the precondition formula of an operator should be considered to be a family of ground formulas (rather than a quantified FOPC formula). Are ”wild card” variables allowed in the delete-list formulas? In backward planning, the precondition formula must be one of the kinds of formulas allowed to be a goal formula.

What kind of planning system is used? Forward planning only? Backward planning (using regression)? Must the variables in an operator be fully bound when applied? How are unbound variables treated by the regression procedure in backward planning. Is ”means-ends analysis” used? Is something like ”recursive STRIPS” used? Note that there is no single, agreed-upon STRIPS ”system.” There are many variations, and the properties of each are different!

These are some of the kinds of questions you should have in mind as you read the various STRIPS papers. Also, remember, that the faculty who ask questions about STRIPS on qual exams might not always realize that there are all these differences, so you should quickly remind them of the differences and inquire about what kind of STRIPS-like system they are asking about.

References

[Nilsson 80] Nils Nilsson, Principles of Artificial Intelligence, 1980, Ch.7, 275-319, Ch.8, 320-360.

This is /u/eyal/ongo/quals/planning.tex.