Planning with SAT, Admissible Heuristics and A*

Rintanen, Jussi

doi:10.5591/978-1-57735-516-8/IJCAI11-336

Planning with SAT, Admissible Heuristics and A*

Jussi Rintanen

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2015-2019.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-336

Abstract

We study the relationship between optimal planning algorithms, in the form of (iterative deepening) A* with (forward) state-space search, and the reduction of the problem to SAT. Our results establish a strict dominance relation between the two approaches: any iterative deepening A* search can be efficiently simulated in the SAT framework, assuming that the heuristic has been encoded in the SAT problem, but the opposite is not possible as A* and IDA* searches sometimes take exponentially longer.

Jussi Rintanen. 2011. Planning with SAT, Admissible Heuristics and A*. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2015–2019. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-336

@inproceedings{ijcai2011p336,
  title     = {Planning with SAT, Admissible Heuristics and A*},
  author    = {Rintanen, Jussi},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2015--2019},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-336},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-336},
}

TY  - CPAPER
TI  - Planning with SAT, Admissible Heuristics and A*
AU  - Rintanen, Jussi
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2015
EP  - 2019
DO  - 10.5591/978-1-57735-516-8/IJCAI11-336
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-336
ER  -