From: Parag (parag_at_cs.washington.edu)
Date: Tue Apr 08 2003 - 12:49:56 PDT
Paper Title: Automatic SAT-Compilation of Planning Problems
Authors: Michael D. Ernst, Todd D. Millstein, Daniel S. Weld
The paper explores the idea of automatizing the compilation
of planning problems to SAT encodings using various
encoding techniques and compares the performace between
different encodings.
Key Ideas:
Several possible encodings for automatic SAT-compilation
of planning problems have been proposed. The representation
of encoding in 2 dimensional space - one for action representation
and other for frame axioms seem to be interesting one. It also
gives a useful insight into the tradeoff between the number of
variables/number of clauses/applicability of various optimization
techniques in particular encodings.
Several optimizations like factoring, type optimizations,
introducing conflict exclusions have been proposed which seem to
help the reduce the size of the encodings significantly in many of
the cases.
Flaws:
As already has been pointed out, it seems that there is too much of
information floating around in the paper and it is easy to get lost.
Though quite a few interesting observations have been made e.g. regular
explanatory encodings seem to be competitive with others even in case
of large problems, the authors did delve into analysis of why these might
be happening. Such an analysis might have been further insightful into the
problem.
Future Work:
One direction for the future work would be to analyze how one
could incorporate domain specific axioms into the automated compilation
techniques. Though, I have a very basic doubt on this - Can't one just
encode these as preconditions in STRIPS at the start state, and since
no action would touch these, using the frame axioms, they would hold
true throughout.
Another interesting direction would be to see if there is any inherent
relation between the constraints in a problem and the specific encodings that
would work best for the given problem thereby helping to classify the problems
accroding to which encoding might work best for them.
This archive was generated by hypermail 2.1.6 : Tue Apr 08 2003 - 12:49:56 PDT