From: Daniel J. Klein (djklein_at_aa.washington.edu)
Date: Wed Nov 05 2003 - 10:10:05 PST
Research question:
When translating planning problems into propositional satisfiability problems, which encoding/decoding scheme will have the best properties?
Plan of Research:
Explore the space of encodings, which is parameterized as a two dimensional space of action and frame.
Main Ideas:
The main idea presented by the authors is that the space of translations from STRIPS to SAT can be represented with two parameters, action and frame. The choice of transformation has a significant impact on the solution time and encoding size. The authors explore the space of possible transformations in order to find the encoding scheme with the best properties.
After explaining the four action representations and two frame axioms, the authors discuss factoring for optimization. The authors then present the MEDIC planner - a planner than compiles STRIPS problems into SAT using any combination of the two encoding parameters. I believe the MEDIC planner to be the most important part of this research. The MEDIC planner directly lead to the results because it allows easy comparison of the different parameterization schemes. The broad result from searching the space with the MEDIC planner is that regular and simply split explanatory encodings result in the smallest encodings.
Largest Flaw:
This paper had two main flaws. The initial assumption made by the authors is that there is one encoding scheme that has "better properties" than the others. As the results show, no single encoding scheme is "best". Instead of seeking the encoding scheme with the best properties, it may have been better to simply seek the properties of each encoding scheme and allow the reader to decide which scheme is appropriate for their particular application.
The other flaw is that the results are difficult to interpret, possibly due to the limited length of the paper. Specifically, I found it difficult to decode the results presented in Figure 6. Is there another way to present this data?
Future Research:
This paper lends itself to future research in this area. After reading the Conclusion section, I got the impression that there are more questions than answers at this time. It seems research in the coming years will lead to greatly improved solutions to the path planning problem.
This archive was generated by hypermail 2.1.6 : Wed Nov 05 2003 - 10:12:50 PST