Note taker:     Terry Zimmerman (zim@asu.edu)
Date:           7 Feb 2000
Subject:        DISJUNCTIVE REFINEMENT PLANNING
In exchange with  No-one!

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

Started from the slide: "Disjunctive Refinement Planning"
Ended with the slide: "Refining Disjunctive plans (4)"
----------------------------------------------------------------------------------

Disjunctive planning (DP) poses special problems:
A key question is "If you have a disjunctive plan, how do you refine it?"
One approach is to generalize the notion of FSS refinement to apply to disjunctive plans.
Then the FSS based proof could be applied to determine if a valid plan exists. (Recall 
that there are 3 types of proofs for plan correctness.)  
Since plan refinement must be quick, in general you want to use "cheap" inferences such 
as modus ponens.  Unfortunately modus ponens is often not real effective with 
disjunction.  Resolution works, but it is expensive.

Graphplan provides one system for refining disjunctive plans.

(Note that currently we don't have an effective plan-space refinement approach for 
disjunctive planning.)

Alternately we could setup a proof-of-correctness procedure for disjunctive structures.

The effect of DP is to push the search effort into the solution extraction phase.  This 
makes this phase more expensive than that for conjunctive planning.  Two possible 
approaches to soln extraction are 1) direct combinatorial search  2) compile the search 
problem into CSP or SAT or ILP. (These are the "workhorses" for combinatorial problems)

At this point Rao conducted a brief review of CSP and SAT based closely on the first 4 
slides under CSP AND SAT REVIEW.  A key concept that was discussed is the idea of 
"k-consistency": An n-variable CSP problem is said to be k-consistent iff every 
consistent assignment for (k-1) of the n variables can be extended to include any k-th 
variable.  So, for example, a 2-consistent problem means any single variable and its 
assignment can be extended to the 2nd variable.  Note that it is NOT the case that 
k-consistency => k-1 consistency.

We can enforce consistency in a problem by ADDING constraints.  This typically involves 
preprocessing:  worst case O(2**n) for any CSP for n variables.  Ideally we expect the 
search cost vs. preprocessing costs to look something like:

	| .               *
	|  .             * <---preprocessing cost
	|   .           *
	|     .        *
	|       .     *
	|          .*
	|         *|   .
	|      *   |       . <---search cost
	|__*_______|_____________ 
		 ~k=2		K
	
For general CSP's 2-consistency if typically the optimum.  For temporal CSP's you 
generally need 3-consistency.  (2-consistency can be enforced by enforcing 
"arc-consistency" / 3-consistency can be enforced by enforcing "path-consistency")

Binary CSPs are those for which every constraint is between 2 variables. (Not the same as 
boolean CSP where every var is either T or F).  The real world tends to be full of binary 
CSPs.  We can use a "constraint graph" to enforce arc-consistency on a binary CSP with 
effort of O(n**2).  The process is basically an iterative procedure to remove domain 
values from variables based on the dictates of the given constraints.

Path consistency is assessed in a similar manner except you reason based on 3 vars.

The lecture wrapped up with a discussion of the 4 slides relating to Refining Disjunctive 
Plans -each illustrating a possible approach:
  1) Indirect unioned approach  -gives maximum "progressiveness" (pruning power) but it's
                                 INFEASIBLE due to exponential refinement cost
  2) Direct naive approach  
       Most naive: put in all possible actions at all levels (used in SATPLAN)
       Less naive: union the states associated with all actions at each level
       Solution extraction cost goes higher than for 1.     
  3) Enforce partial 1-consistency   (at O(n) cost)
       Here unsupported conditions are precluded from the proposition levels
       Solution extraction cost goes higher than for 1.                                  
  4) Enforce (partial) 2-consistency 
       Consider pairs of props to see if all are consistent. (Graphplan does this
       with mutexing)  Basically constraints such as At(R E) => ~At(R M) get added.
       
Refinements can now be seen as "canned" inference procedures that try to increase the 
local consistency of a CSP problem.

Given a disjunctive structure of partial plans (such as a planning graph) you must now 
decide how to check for (i.e. extract) a solution.   This is the topic for the next 
class.