From: Patrick Haluptzok (patrickh_at_windows.microsoft.com)
Date: Tue Nov 04 2003 - 23:23:42 PST
CSE 573 Paper Review #3 - Reviewed by Patrick Haluptzok Nov 4, 2003
Automatic SAT-Compilation of Planning Problems
Michael D. Ernst, Todd D. Millstein, and Daniel S. Weld
One-line summary:
A method is presented for converting planning problems in STRIPS into propositional constraint problems which can be solved quickly and from which a solution to the original planning problem is produced.
The (two) most important ideas in the paper, and why:
Planning problems can be converted into propositional constraint problems where fast algorithms like WalkSAT or Tableau exist to find solutions. From the solutions for the propositional constraint problems a solution for the original planning problem is produced. This is important because planning problems that couldn't be solved in reasonable time using planning methods can be converted to proposition constraint problems and solved.
The conversion of planning problems to propositional constraint problems can be automated with a compiler. Extremely clever and non-obvious techniques for encoding a STRIPS problem into propositional logic give numerous trade-offs in the number of variables and clauses produced - which greatly effect the final run time. Finding the right combination of options makes a big difference in the run-time of solving the propositional constraint problem. The encoding of the actions, and the factoring of the frame axioms are impressive methods.
The one or two largest flaws in the paper:
The addition of domain axioms can greatly speed up the solution of the constraint satisfaction problem - which previous hand-coding techniques could take advantage of but the lack of an easy way to represent domain axioms in STRIPS limits the current automated approach. Also I didn't see measurements comparing the time to solve the STRIPS planning problem with the classic planner techniques versus the time to solve the constraint satisfaction problem with WalkSAT, and the estimated conversion time for any problems.
Identify two important, open research questions on the topic, and why they matter:
Can domain axioms be generated automatically or encoded in another representation so the automatic method can approach the other method in run-time? Larger and more complex planning problems will be able to be solved if this can be done.
Are there other tricks in representing actions, such that after splitting, factoring and simplifying the result is a simpler propositional constraint problem that can be solved much more quickly. Again this will enable larger and more complex planning problems to be solved.
This archive was generated by hypermail 2.1.6 : Tue Nov 04 2003 - 23:25:08 PST