From: Tyler Robison (trobison_at_cs.washington.edu)
Date: Wed Nov 05 2003 - 09:31:28 PST
Automatic SAT-Compilation of Planning Problems
Michael D. Ernest, Todd D. Millstein, and Daniel S. Weld
Summary:
This paper looks at various methods for automatically compiling
STRIPS-like planning problems into propositional satisfiability problems,
examines some optimizations, and discusses results.
Important Ideas:
The paper provides a good comparison of the various methods, and
combinations of methods, considered; we can get a better feel for which
techniques work, and which don't. When implementing a planning system,
this knowledge could help choose the right technique and so improve
performance.
The optimizations used are also a key part of the paper for the
reason mentioned above: performance. The paper also considers the
effects of certain optimizations with certain encodings, giving us some
insight into when and why some methods can be made to work better than
others.
Flaws:
Although we are given a comparison of the methods, the comparisons
tend to be in a 'good or bad' scale, without seeing particular strengths
or weaknesses of various methods, and situations in which they may
prevail. One example of this is the statement that explanatory frame
clauses are superior to classical frame clauses because we expect each
action to affect few fluents. But we could of course construct a
particular problem in which this is not the case. The results given in
the paper appear to be geared toward the general case, and so the results
may vary in more exotic situations.
Research questions:
As mentioned above, an analysis of these methods in different
situations may show that some of the 'lesser' methods may be preferable in
certain obscure situations; such an investigation may give more insight
into the methods themselves, as well as allowing us to pick the best
technique for a given problem.
Several other interesting research issues are some of those posed
by the paper itself, such as looking more into the solve-time
characteristics of each of the methods in order to provide a more complete
comparison.
This archive was generated by hypermail 2.1.6 : Wed Nov 05 2003 - 09:31:29 PST