From: Jessica Kristan Miller (jessica_at_cs.washington.edu)
Date: Wed Nov 05 2003 - 10:53:07 PST
Paper Reviewed: Automatic SAT Compilation of Planning Problems
Paper Author: Ernst, Millstein, & Weld
Reviewed By: Jessica Miller
Summary:
This paper examines how traditional planning problems can be automatically
compiled to propositional satisfiability problems and searched by a SAT
solver whose results are turned back into a plan for the original problem.
Two Important Most Ideas:
(1) One of the most important apects of the paper is the exploration of
the tradeoffs of different encodings of the planning problem.
Furthermore, the paper takes a very scientific approach in examining the
different encoding options by building a system that is not married to any
particular encoding but rather allows the user to choose an encoding.
This system seems to provide a great opportunity to actually be
experimental about the encodings.
(2) Another major contribution of the paper is simply the fact that the
authors were able to produce a system that did automatically compile
planning problems into SAT problems. Before this paper, this process was
done by hand. In the results section, the authors examine the benefits
and drawbacks to automatic versus hand encoding of planning problems to
satisfiability problems.
Largest Flaw in the Paper:
After reading up to the results section, I was very excited to see what
kind of data an experimental system would yield. However, I found the
results section less than satisfactory for two reasons. First, authors
didn't say much about the nature of the problems that were used to perform
experiments on their system nor did they relate the results to how they
would expect the system would work on "real world" planning problems.
Secondly, I found the graphs were hard to read because of symbol
overlapping...there must be a better way to visually display the results.
Two Open Research Questions:
(1) The authors seemed to have preliminary evidence that domain-dependent
axioms help in producing a plan more quickly. Can these domain-dependent
axioms somehow be deduced by the system?
(2) Another open question concerns how/what hybrid encodings could be used
by this system to make the system produce plans more efficiently.
This archive was generated by hypermail 2.1.6 : Wed Nov 05 2003 - 10:53:08 PST