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.