From: Stanley Kok (koks_at_cs.washington.edu)
Date: Tue Apr 08 2003 - 01:12:55 PDT
Paper Title: Automatic SAT-Compilation of Planning Problems
Authors: Michael D. Ernst, Todd D. Millstein, Daniel S. Weld
One-line summary:
This paper presents novel encodings of STRIPS schema, and
experimentally compares how the encodings affects a
SAT-Compiler's performance on planning problems.
Most Important Ideas in the Paper:
1. The framework of action and frame encodings and the
classification of factoring techniques are important ideas.
This is because they provide a clear taxonomy for the comparison
of encodings and optimizations for SAT-compilations of planning
problems.
2. Another important idea is the discovery (against conventional
wisdom then) that regular action representation is effective .
This suggest that the simple approach of using regular action
encoding is sufficient to solve some real-world problems.
Flaw in the Paper:
1. The paper speculates on the possible causes of the performance
differences of the encodings but does not proceed to verify them. For
example, it speculates that the simplifier's type optimizations
reduce formula sizes but does not perform any test to support it.
Important, open research questions:
1. From Fig 6, we can see that the encoding with the best solution
times varies from problem to problem. This suggests that the
structure of the problem lends itself to different optimal
representation. Can a problem be formally classified based on some
"structure criteria"? With such a criteria, we can select the
encoding to best solve a problem.
2. The MEDIC planner iteratively tries plans of longer length.
Instead of starting from length one, is there a way to
intelligently guess the approximate "right" length to start
searching for a solution? Could the structure of the problem
give insight to this length? With such a length, we can restrict
our search to the space close to the solution.
This archive was generated by hypermail 2.1.6 : Tue Apr 08 2003 - 01:12:55 PDT