From: Lincoln Ritter (lritter_at_cs.washington.edu)
Date: Wed Nov 05 2003 - 09:09:44 PST
Automatic SAT-Compilation of Planning Problems
Ernst, et al.
Reviewed by Lincoln Ritter
Summary:
The authors develop a system for evaluating the relative performance
of various planning encoding schemes and use this tool to discover
that Regular and Split-fluent explanatory encodings dominate all
others tested.
Probably the most important idea present in this paper from a computer
*science* perspective is the emphasis on experimental testing. It is
ironic that computer scientists seem prone to argue with religious
fervor about that which has undergone no experimental evaluation.
This paper presents a system by which various encoding strategies can
be compared by translation to a common form and subsequent
evaluation. In this way, substantive arguments can be made about the
effectiveness of each method.
Another striking point of this paper was the discovery that, against
expectation, bit-wise encodings and regular encodings have the
smallest and largest number of variables respectively, and that in
fact regular and simply split explanatory encodings are the smallest
and fastest. While these results are useful and enlightening in
their own right, it also emphasizes the point made above about the
importance of experimental verification. Even though our intuition
leads us to believe something (say, that bit-wise encodings should be
smallest), it is not necessarily so.
While the paper is laudable for bringing experimental verification to
the forefront, it mentions that WalkSAT based methods with the
presented compiler might result in the "world's fastest STRIPS-style
planner" but does not compare the results of this work with other
STRIPS-style planners. This may be admissible due to the fact that
the paper focuses on encodings, yet a claim this large needs to be
backed up.
To take the experimental methods of this paper forward, methods for
comparing planners using divers styles need to be developed. For
example, can some non-STRIPS-style planner compete with the fastest,
best encoded planner from this paper? Is this an apple vs oranges
debate? If so, can we develop tools that determine the be style of
planner to use for a particular problem?
This archive was generated by hypermail 2.1.6 : Wed Nov 05 2003 - 09:09:45 PST