Unifying SAT-based and Graph-based Planning

Kautz, Henry A.; Selman, Bart

Unifying SAT-based and Graph-based Planning

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Challenge Papers. Pages 318-324.

Abstract

The Blackbox planning system unifies the planning as satisfiability framework (Kautz and Selman 1992, 1996) with the plan graph approach to STRIPS planning (Blum and Furst 1995). We show that STRIPS problems can be directly translated into SAT and efficiently solved using new randomized systematic solvers. For certain computationally challenging benchmark problems this unified approach outperforms both SATPLAN and Graphplan alone. We also demonstrate that polynomialtime SAT simplification algorithms applied to the encoded problem instances are a powerful complement to the "mutex" propagation algorithm that works directly on the plan graph.

Henry A. Kautz, and Bart Selman. 1999. Unifying SAT-based and Graph-based Planning. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99. IJCAI, 318–324. https://ijcai.org/proceedings/1999/47

@inproceedings{ijcai1999p47,
  title     = {Unifying SAT-based and Graph-based Planning},
  author    = {Kautz, Henry A. and Selman, Bart},
  booktitle = {Proceedings of the Sixteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-99}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Thomas Dean},
  pages     = {318--324},
  year      = {1999},
  note      = {Challenge Papers},
  url       = {https://ijcai.org/proceedings/1999/47},
}

TY  - CPAPER
TI  - Unifying SAT-based and Graph-based Planning
AU  - Kautz, Henry A.
AU  - Selman, Bart
T2  - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1999
SP  - 318
EP  - 324
UR  - https://ijcai.org/proceedings/1999/47
ER  -