Consider the following "artificial" planning domain, which
contains the (artificial) operators described below:
 
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}

You can think of the boolean state variables as propositions. A
literal is a proposition or its negation. 

1.a. Assuming that the state variables are all those that are named in
the init state, goal state and action descriptions, what is the size
of the state space?  What is the size of search space in which the
progression and regression planners search? (Hint: Progression should
be easy. For regression, notice that for this type of problem, a
regression state is a "conjunctive" formula over literals. So you just
need to figure out how many conjunctive formulas are there).


1.b. Show the first level of the search tree generated by progression
search. Also show the branch that leads to the goal state. 


1.c. Show first level of the search tree generated by regression
search. Also show the branch that leads to the initial state.

1.d removed

1.e.  Draw the "relaxed planning graph" for this problem (relaxed
planning graph ignores negative interactions--ie, no mutexes). Draw it
until it levels off. 

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

1.g. 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
 iv. perfect heuristic (the problem is small enough that you should
 know what the perfect heuristic value is here).


1.h.[**ONLY if we do Mutex Propagation] (Only if we do mutex propagation in class)
Copy the planning graph above and mark mutexes on it With respect to
this standard graph, what is the heuristic cost of goal set {P,Q,R,S}
using SUM and Level heuristics?