From: Sumit Sanghai (sanghai_at_cs.washington.edu)
Date: Tue Apr 08 2003 - 11:20:11 PDT
Automatic SAT-Compilation of Planning Problems
--M. Ernst and T. Millstein and D. Weld
Summary : The paper presents several ideas for automatic compliation of
planning problems into SAT problems.
Ideas : The important ideas presented in the paper are the different
techniques to represent the planning problems as SAT problems. The paper
does not focus on anyone technique and instead comapres the advs/disadvs
of different representations. Some of the interesting ones were the
classical and explanatory frame axioms, and the simple and overloaded
split. The experiments also pointed some interesting observations such as
regular representation is as good as the split ones, and factoring,
parallelization and type optimizations are important.
Flaws : The paper doesn't talk about the complexity of the problems on
which the testing was done and why exactly would regular do better than
the split representation. As people have suggested before Fig 6 looks
extremely confusing and there should have been separate graphs analysing
the various observations. Finally, the paper lacks any substantial idea
about the disparity in running times of the various representations.
Future Work : Since the representations discussed work for a given path
length, the paper uses binary search (along with no-ops) to get a
solution. A future work could be to come up with representations which are
independent of path length(easier said than done though :) or which work
by intelligently guessing a feasible path length (which is not too large).
The authors also mention that domain dependent optimization is one of the
key reasons why the original SATPlan ran fast. Thus, a possible direction
could be to look at automated techniques for reconginizing various domain
dependent optimizations (which again seems a tough task).
This archive was generated by hypermail 2.1.6 : Tue Apr 08 2003 - 11:20:11 PDT