6.824 Artificial Intelligence, Fall 1993 Problem Set 8

Due: Beginning of class Wednesday, November 17

Problem 1. Consider rewrite rules such as the following.

(∗ x (+ y z)) → (+ (∗ x y) (∗ x z))
(+ (+ x y) z) → (+ x (+ y z))
x → (+ x (+ y (− y)))

Each rewrite rule specifies that an instance of the left hand side can be rewritten as an instance of the right hand side. For example, the first rule specifies that (∗ (f a) (+ c d)) can be rewritten to (+ (∗ (f a) c) (∗ (f a) d)). The last rule specifies that (f a) can be rewritten as (+ (f a) (+ (g b) (− (g b)))).

The above rules are only meant as an example — in this problem we consider the general concept of rewrite rules. Let R be a set of rewrite rules and let s and w be ground expressions (expressions that do not contain variables). Suppose that we use the following procedure to determine if there exists a way of rewriting s to w using rewrite rules in R using at most d rewriting steps.

Procedure to determine if s can be rewritten to w in d steps

1. If s is the same expression as w then return “yes”.

2. If d is 0 then fail.

3. Select (nondeterministically) a ground instance u → v of a rewrite rule in R.

4. If u does not equal s then fail.

5. If u equals s then return the value of a recursive call to the procedure on v, w and d − 1.

The above procedure operates on ground expressions (step 3 selects a ground instance of a rewrite rule). The general lifting transformation can be applied to this procedure. The following questions concern the differences between the ground procedure and the lifted procedure.

In the following questions we assume that at least one rule in the rule set R contains a variable and that there are n different rules in R.

In the ground procedure given above, how many ways are there of executing step 3? In the lifted version of the procedure, what is the maximum number of ways that the sequence of step 3 followed by step 4 can execute without failure? Consider a call to the lifted version of the procedure. As a function of n (the number of rules) and d (the allowed number of steps), give the maximum possible number of leaves in the search tree, i.e., the maximum number of times some recursive call to the procedure can fail at step 2.

Problem 2. This problem is on the lifted linear backward chaining planner. Consider the nonlinear planning procedure FIND-COMPLETION given below. This procedure takes a nonlinear plan β and searches for a completion.

Procedure for computing FIND-PLAN(Σ, Ω, c, h):

1. If Ω is a subset of Σ then return the empty plan.

2. Select an operator o_{i}.

3. If some element of the delete list of o_{i} is a member of Ω then fail.

4. If no element of the add list of o_{i} is a member of Ω then fail.

5. Let Ω′ be the weakest precondition of Ω with respect to o_{i}.

6. Let β be FIND-PLAN(Σ, Ω′, c − c(o_{i}), h)

7. Return the plan β; o_{i}.

For each of steps 1, 2, 3, 4 and 5 of the above procedure state whether that step is deterministic or nondeterministic in both the ground and the lifted version of the planner for the blocks world. Give a brief explanation of each answer. At least one answer is different when the planner is restricted to the blocks world than when we consider arbitrary STRIPS planning. Also, a step is considered to be nondeterministic if and only if there is more than one way of completeing the step without failing (the step has a nonfailing branching factor of at least two).

Prolem 3. Give a resolution proof that the following two clauses are unsatisfiable.

P (x, y) ∨ P (y, x)
¬P (x, y) ∨ ¬P (y, x)

Hint: consider the case where x equals y.

Problem 4. Give a polynomial time reduction of the STRIPS planning problem to resolution theorem proving. More specifically, given a set o_{1}, ⋯ o_{b} of STRIPS operators, a set Σ of initial propositions, and a set Γ of goal propositions, show how to construct, in time polynomial in the written length of the STRIPS problem, a set of clauses C such that one can derive the empty clause from C if and only if the given STRIPS problem has a solution. You should assume that the planning problem is ground, i.e., all propositions involved are simple proposition symbols.