From: Russell Power (rjpower_at_u.washington.edu)
Date: Tue Nov 04 2003 - 18:01:48 PST
Automatic SAT-Compilation of Planning Problems
Michael D. Ernst, Todd D. Millstein, Daniel S. Weld
The paper describes a methodology for automatically translating problems
from a STRIPS-style language into an equivalent SAT problem, and evaluates
the performance of the resulting planner.
The paper follows up on the work of Kautz et. al. and their success with the
translation of certain planning problems via a process specific to the
problem at hand. The authors describe the general rules necessary to
convert between a STRIPS representation and a SAT problem, briefly
explaining the options examined and the tradeoffs between them in terms of
resulting SAT equation. The paper also examines ceratin optimizations
possible in the general compilation case, and describe the results of the
process as compared to the SATPLAN planner.
In the experimental section, the various planning problems tested are not
explained in any depth (unless these are part of a standard test suite?).
It's difficult to tell whether the results are due to a lucky choice of
problems, or to the effectiveness of the technique at hand. Also, no
mention is made of possible extensions of the technique to handle richer
languages than STRIPS.
Further research in the direction of this paper abounds. The possibility of
more and better optimization and compilation strategies is a nice target.
It would also be interesting to see if the technique could be applied to a
more general representation language, or to attempt to utilize it in a
realistic planning environment.
This archive was generated by hypermail 2.1.6 : Tue Nov 04 2003 - 22:12:34 PST