CSE 574 Planning & Learning Methods in AI
Spring 2003
Midterm

Given: Thursday, [Apr  3, 2003]
Due: [Apr 10, 2003]
(Shouldn't really take more than April 8th.]


Please answer all questions.  Please make sure that your answers are
written in a legible hand writing. 

You are allowed to read as many papers, notes, web-pages as you
want. But, you are NOT ALLOWED to discuss the exam with anyone else. 

Direct all requests for clarifications to rao@asu.edu


Qn I Short answer questions. Please answer as concisely as
possible. Content is way more important than the length of your
answer.  Each question carries 5 points unless otherwise stated. 



1. [5] We discussed in the class that planning is P-space complete (in
   that it is the hardest problem that is solvable with polynomial
   amount of space). We also know that P-space complete is considered
   to be a higher level of computational hardness than
   NP-completeness. And yet, we have been able to pose planning as a 
   SAT problem, where SAT is just NP-complete. Why is this not
   inconsistent?

2. [5]The SAT encodings have axioms for stating some rather zany
   things. For example, in the linear encoding, we have an axiom
   saying that  at least one action will occur at each
   level. Why do we need to add such "darned obvious" axioms to the
   encoding? 


3. [5] RePOP, in contrast to normal partial order planners, maintains 
   disjunctive ordering constraints. Think of two extreme cases one in 
   which RePOP strategy is much better and the other in which it is
   much worse. 

4. [5] Compare and contrast "Page replacement strategies" in operating 
   systems to the "Nogood maintenance" strategies in explanation-based 
   learning. 

5. [5] Suppose a CSP problem with n variables is strongly n-consistent
    (i.e., it is 1-consistent, 2-consistent, etc upto 
    n-consistent). Show (argue) that this problem can always be solved
    with a backtrack-free search.


6. [5] Why is it feasible to handle actions with disjunctive preconditions and
    conditional effects within classical planning framework but not
    actions with disjunctive effects? In particular, aren't
    conditional effects really "disjunctive effects" (given that A=>B 
    is the same as ~A V B ?)


7. [5] Why is it said that  "classical frame axioms" make it impossible to support
    parallel actions in the solution? Can you think of a way you can
    extend the classical frame axioms so you can support parallel actions?


8.[5] Why is growing a (serial) planning graph of length k cheaper than growing the 
   progression search tree to depth k? Explain both in terms of time and space. 



9.[5] Explain how the notions of "completeness" and "soundness" of a
planner change in the case of knowledge-based planning. 


10.[10] For each of the pairs of planners A vs. B  below, give one
reason why A could be better and one reason why B could be better. 
One reason each will be enough. No need to write long paragraphs. 

--Progression planners vs. Regression planners

--State space vs. Plan-space planners

--Graphplan with direct graph search vs. Graphplan with CSP/SAT compilation

--Domain independent vs. Knowledge-based planners

--Planners using "lifted" actions vs. planners using "ground" actions


Qn II [45] THE BIG PROBLEM

 Consider the following simple planning problem:

  Operator A1 prec: L Eff: P

           A21 Eff: Q, ~L
           A22 Eff: Q, ~J

           A3 Prec: J  Eff: R
 
           A41  Prec: P,Q Eff: G1
           A42  Prec: Q,R Eff: G2


  Init: L, J
  Eff: G1, G2


Part A.[10]  Show 
  (1)[2] first level of a progression planner's search
  (2)[2] first level of a regression planner's search
  (3)[6] a trace of  how a partial order planner finds the solution for this
     problem. You need to show one solution path, and at each node on the
     solution path, the other branches that were left pending.

part B.[10]
  1. [5] Show the planning graph (as built by standard graphplan) for
         2 levels.
  2. [4]  Show how Graphplan searches this graph trying to find a
        solution. (Please make your trace elaborate enough that I can
        understand that you understand the details of Graphplan operation.)

  3. [1] How does your answer above demonstrate that Graphplan finds only a
   *subset* of 2-sized mutexes?


Part C[10]. With respect to the planning graph in Part B, for each of the
following heuristics, give the heuristic cost given to the set {G1,G2}
by that heuristic, and indicate whether it under-estimates,
over-estimates, or exact-estimates the true cost.

 1. h_ind,
 2.  h_max,
 3. h_level, 
 4. h_relaxed_plan_length 
 5. h_adjsum. 


Part D.[5]  Take the  planning graph constructed in part B, and Convert
it into a (standard) CSP encoding.


Part E.[10]   For the problem above, write a 2-step SAT causal encoding. 




			  -----end---------