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

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

Started from the slide: "Graphplan Plangraph"
Ended with the slide: "Compilation to Integer Linear Programming"
----------------------------------------------------------------------------------

Observation: suppose we have a disjunct -  P V Q V W V S V M
             These are some of the "models":  PQ,  P,  SVM
             But if we have S mutex with M we reduce the # of models
             
This is a means of enforcing consistency.  An inference procedure can be seen as 
enforcing consistency incrementally.  General k-consistency enforcement tends to be too 
costly and too undirected.  But if you know how to "can" the inference procedure this can 
give you direction and (hopefully) the "right amount" of consistency enforcement.
             
Rao conducted a brief review of Graphplan and it's backward search process on the 
planning graph.  Timeline:
	1995 Graphplan (Blum & Furst)
	1996 SATPLAN (Kautz & Selman)
	     Converts the planning graph to CSP and does basically undirectional search
	     Beats Graphplan
	1998 Rintanen:  For a fair comparison to Graphplan, do undirectional search in
	     GP also.  Does as well/better than SATPLAN
	     
There is no reason that the search process (soln extraction) has to procede in a backward 
directed fashion on the planning graph, and a number of variations have produced 
impressive results.

Compilation to a CSP:
An entirely different approach involves compiling the planning graph structure into a CSP 
and using the powerful algorithms that have been developed for such problems to extract a 
solution (if one exists for the given planning graph).  Unlike Graphplan's goal-directed 
search CSP search is largely undirected, so it may well assign values to irrelevant 
variables (propositions that aren't subgoals).  In spite of this it generally outperforms 
GP.  Level-by-level ranking (ordering) of variables to be assigned can be implemented in 
CSP to introduce a similar directedness, but it's NOT always the best approach.  
Sometimes prefering the most-constrained variable is MUCH better.

Compilation to SAT:
This has a certain appeal because it looks like you're using logic to do planning. (a 
PROLOG way of life).  There are 2 ways to do this compilation:
	1) Directly from CSP  (Var = Value  T/F)
	2) The system illustrated in the "Compilation to SAT" slide, which looks like
	   situation calculus.
	   
There are 2 factors that can make a HUGE difference on the effectiveness of this 
approach:
 1) What is the best way to translate your problem into CSP/SAT (encodings)
 2) Modify the CSP/SAT solver itself to specialize it to your particular problem
 
Compilation to Integer Linear Programming:
Rao conducted a very brief review of linear programming/integer linear programming.  
Basically, LP deals with continuous constraints.  Consider:
	Goal:         x+3y+4z+15m  (x,y,z are Reals)
	Constraints:  x+2y+3z <= 15
		      y+m >= 0
		      ...
	The goal is to optimize the goal eqn while satisfying the constraints
You can do CSP-style optimizing (depth-first/branch & bound)

Linear Programming is of polynomial complexity in the number of variables.
Integer Linear Programming adds the constraint that all vars are integers.  It allows 
more realistic problems to be addressed (strangely enough) and it is NP-complete. 

SAT converts to an MILP "Mixed Integer Linear Programming" problem.

A useful graph for comparing the various types of LP:

			MILP
  NP-COMPLETE =>	/   \
  		       /     \
  		      /    ILP  (CSP)
  		     /        \
  		    /          \
  		   /           0-1 ILP
             ....................................
		 /
		LP
  POLYNOMIAL		              
  

And again the issue becomes what is the "right" type of ILP encoding for a particular 
planning problem.

There are trade-offs with all of these approaches to solution extraction and no single 
system has been demonstrated superior in all cases.

This is another way of stating a well-known maxim in AI:  
 Choosing a representation/language to express a concept (such as a problem) NECESSARILY  
 limits or makes it more difficult to express certain concepts at the same time that it
 facilitates expression of other concepts.