Problem set 1
Assigned: [Feb 10, 2008]
Due: [Feb 26, 2008]

I. Consider the following problem:

Operator O1
eff: for all x If P1(x) then Q(x)
      for all x If P2(x) then Q(x)
     for all y If R(y)  then W(y)
     for all u If M(u) then ~Q(u)
     for all u If N(u) then ~Q(u)


Operator O2
  forall x if J(x) then W(x)

Init state: P1(a),J(a) [Remember--init state is
complete. So we only specify things that are true; the rest are false]

Goals: there exists x  Q(x) ^  W(x)

I.1. Assuming there are two objects, a and b in the domain, write
down the set of "ground STRIPS operators" that correspond to O1. 

I.2. Using the lifted action representation, show how a regression
planner solves this problem. Did you learn anything interesting about
how regression will change in the presence of conditional and
quantified effects? (Pay special attention to which goals O1 is being
used to support in which branch; make sure you don't skip any possible
branches...) 

I.3. Show how a partial order planner solves this problem.


==================
Qn II. 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}
------------


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

II.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 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, you will use the planning graph in the last level
III.b above.

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

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

IV.c.
   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 IV.b.


----------------------------------------------------------