6.824 Artificial Intelligence, Fall 1993 Problem Set 7

Due: Beginning of class Wednesday, November 10

Problem 1. Consider a graph search problem in which each node is a non-negative integer. Consider the following operations on numbers, viewed as operators in a graph search problem.

• D (for “Double”) D(n) is 2n.

• H (for “Half”) H(n) is ⌊\frac{n}{2}⌋.

• S (for “Successor”) S(n) is n + 1.

• E (for “make-Even”) If n is odd then E(n) is n − 1, else E(n), is n.

The plan (sequence of operations) H; E; D; E maps the number 11 to the number 8 (H(11) = 5; E(5) = 4; D(4) = 8; and E(8) = 8).

Consider the following propositions about numbers.

• The proposition Even is true of a node n just in case n is even.

• The proposition Odd is true of a node n just in case n is Odd.

• The proposition One-Two is true of a number n just in case the prime factorization of n contains a single factor of 2. For example One-Two(6) is true but One-Two(12) is false.

Each operator can be applied at any node. In the following table each operator has been assigned an empty prerequisite list. Make a copy of this table with the add lists and delete lists filled in. Each add list and delete list should be a subset of the propositions Even, Odd, and One-Two. The delete lists should be as small as possible and the add lists as large as possible so that the operator specification holds of the actual operators.

Operator  Prerequisite List  Delete List  Add List
D ∅
H ∅

S ∅ E ∅

In the following table each operator has been assigned prerequisites. Make a copy of this table with minimal delete lists and maximal add lists inserted.

Operator  Prerequisite List  Delete List  Add List

D Odd H ∅ S Even E ∅

Problem 2. GPS was developed in the late 50’s by Simon and Newell as a model of human problem solving. The GPS procedure for STRIPS planning is given below. To find a plan α such that Σ → [α]Ω do the following:

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

2. Nondeterministically select some operator o_{i} such that some proposition on the add list of o_{i} is a member of Ω but not a member of Σ

3. Let Ω′ be the prerequisites of o_{i}.

4. Recursively find a plan β such that Σ → [β]Ω′.

5. Let Σ′ be the result of running the program β; o_{i} from start state Σ, i.e., Σ′ is the largest set of propositions such that Σ → [β; o_{i}]Σ′.

6. Recursively find a plan γ such that Σ′ → [γ]Ω.

7. Return the procedure β; o_{i}; γ.

Step 2 of the above procedure is non-deterministic. This allows for many different possible executions. An implementation of this procedure would have to search the space of all possible executions.

Give an example of a planning problem for which there exists a plan that solves the problem but where GPS can not find a solution.

Problem 3. Consider the following forward chaining partial order planner. The difference between the planner given below and the one given in the notes is step 4. Deterministic selections are not backtracked and do not correspond to branches in the search tree. Nondeterministic selections on the other hand are backtracked and do correspond to branches in the search tree.

The Procedure FIND-COMPLETION(β c)

1. If the nonlinear plan β is order inconsistent, or the total cost of the steps in β is greater than c, then fail.

2. If the nonlinear plan β is complete then return β.

3. If there is a causal link s\underrightarrow{P}w in β and a threat v to this link in the symbol table such that β does not contain either v < s or v > w, then nondeterministically return one of the following.

     (a) FIND-COMPLETION(β + (v < s), c)
     (b) FIND-COMPLETION(β + (v > w), c)

4. If none of the above cases apply then nondeterministically do one of the following.

(a) Nondeterministically select an operator o from the allowed set of operations such that for each prerequisite P of o there exists a step name s that adds P. Create a new entry w in the symbol table that maps a new step name to the operator o. Let β′ be the plan that results from adding the step w

and adding a causal link s\underrightarrow{P}w for each prerequisite P of w. Return the

         plan FIND-COMPLETION(β′, c).

(b) Deterministically select a prerequisite P of the step FINISH such that β

does not contain any causal link of the form s\underrightarrow{P}FINISH but where some step in β adds P. Nondeterministically select some step name s in the symbol table such that s adds P and return the plan

                       FIND-COMPLETION(β + s\underrightarrow{P}FINISH, c).

part a. Is the above planner sound, i.e., will it only return correct solutions. Explain your answer.

part b. Is the above planner complete, i.e., will it find a solution whenever a solution exits. Explain your answer.

part c. Show that the above planner is not systematic, i.e., give a linear plan that is a topological sort of two different nonlinear plans generated down two different branches of the search generated by the above procedure.

part d. Explain why the linear version of the forward chaining planner, and the the backward chaining version of the nonlinear planner, are both systematic in the sense that no two branches of the search tree can generate the same plan.