Homework 3.
Assigned [Sep 28, 2004]
Due [October 11th, 2004]

Qn I. Consider the planning problem from the first question of the
first homework  (reproduced below for your convenience)

-----------------------
operator O1
prec: P
Eff: R, ~S
 
operator O2
prec: Q
Eff: S
 
operator O3
prec: P
Eff: M
 
operator O4
prec: R,S
Eff: P,Q,R,S
 
operator O5
prec: R,S
Eff: P

The initial state is {P,Q} and the desired goals are {P,Q,R,S}
------------


I.A Draw the "relaxed planning graph" for this problem (relaxed
planning graph ignores negative interactions--ie, no mutexes). 

Mark a relaxed plan that supports the top level goals in this relaxed
planning graph. 

What is the heuristic value of the goal set {P,Q,R,S} in terms of

 i. Sum heuristic  ii. Level heuristic  iii. relaxed plan heuristic 

I.B. Now draw the standard mutex graph (as described in the text and
used by planning graph--don't need to use serial graph). With respect
to this standard graph, what is the heuristic cost of goal set
{P,Q,R,S} using SUM and Level heuristics? 

What is the value of the adjusted sum heuristic (recall that it is
equal to relaxed plan length + -ve interaction penalty). 



Qn II

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. 

II.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. 


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

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


Qn III

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

III.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.

III.b. Do II.a. but with SAT encoding of the planing graph.

III.c. (Added since I extended the deadline to 10/11 ;-)
   Do an "explanatory axiom" (or backward proof based) encoding
   of this problem (for the same length as the planning graph you used
   in the previous parts). Mark which constraints are similar, different,
   stronger etc. compared to III.b.