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?

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


[Nov 24, 2005] These parts are *optional* and were added after the
class of Nov 23.


1.h.(*optional*) Copy the planning graph above and mark mutexes on it
(as described in the text and in the class of [Nov 23 2005]) With
respect to this standard graph, what is the heuristic cost of goal set
{P,Q,R,S} using SUM and Level heuristics?


Qn 2. Planning under uncertainty and incomplete information


Consider a domain with three literals, P, Q and  R. 

Suppose in the initial state, we only know that either P or Q is true
(not both).  Our goal is to make Q true.

Consider the following three actions with conditional effects:

A1: P=> [Q V R]
A11:P=> [Q V ~R]
A2: R=> Q
 
[Assume that the disjunction is exclusive--that is the effect Q V R
means either Q or R will be true--not both]

1. What is the size of the belief space for this problem? (i.e.,
   number of belief states).

2. Show the initial belief state corresponding to this problem.

3. Show the set of actions that can be applied to this belief state
   and the resulting belief states. 

4. Show one path (actions, and belief states) that lead to the
   goal.