Homework 3.
Start [Feb 20, 2003]
Due  [March 6, 2003]

Question I
 I said that Graphplan will produce step-optimal solutions. We want
   to explore if this is actually the case. Consider the following
   example:

   We have empty init state, and Goal state is {P,Q}. We just have two 
actions in the domain

A1  Prec: none  Effects: P,W

A2  Prec: none  Effects: Q,~W

A. What is the optimal parallel plan for this problem? (note that W
has nothing to do with the goal--so we really don't care if it is true 
or false.

B. What is the plan that Graphplan will produce for this problem? Is
it optimal?

C. Is there an easy way of changing the action interference
   definition such that we could find optimal parallel plan with
Graphplan? (why is the obvious way of doing it not an easy way?)


Question II
 
--> Explain why a pair of conditions P,Q that are not mutex at level k
    will never be mutex at any level j that is greater than or equal
    to k

--> Explain whether graphplan detects every pair of mutex
    propositions. Try to give an example to support your answer. 


--> Standard graphplan finds step-optimal, but not length-optimal
   (i.e. optimal in the number of actions) plans. Is there an easy way 
   to change graphplan algorithm so it will find length-optimal plans?
   explain. 

Qn III

Consider the following problem. There are two actions: A1 and A2

A1: prec: p eff: q

A2 prec: r eff: ~q,w

We start with init state where p and r are true. 

**and our goals are q and w. 



III.a. Show how graphplan solves this problem--assuming that only
static interference relations are marked. No mutex propagation is
done.  Show all the steps in the graph construction, search and memo
finding. This is a really small problem. 


III.b. Now do this problem assuming that mutex propagation using the
normal rules of Graphplan is done. 

III.c. Comment on the relation between memoization and mutex
propagation as evidenced by parts a and b. 

Qn IV. 

For this problem, do the search on III.a. using EBL/DDB
memoization. Show all the steps, conflict sets etc. at each step. Show 
the memos (if any) learned. 

Qn V

For this problem, you will use the planning graph in the last level
III.b above.

V.a. Convert the planning graph into a CSP encoding (the problem is
small enough that you can write the entire encoding down). Show a solution
for this CSP encoding, and show how it corresponds to a plan.

V.b. Do V.a. but with SAT encoding.