ML Anthology

Planning with SAT, Admissible Heuristics and A*

Jussi Rintanen
IJCAI 2011 pp. 2015-2020
doi:10.5591/978-1-57735-516-8/IJCAI11-336 /ijcai/2011/rintanen2011ijcai-planning/

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.

PDF IJCAI Semantic Scholar

Cite

Text

Rintanen. "Planning with SAT, Admissible Heuristics and A*." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-336

Markdown

[Rintanen. "Planning with SAT, Admissible Heuristics and A*." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/rintanen2011ijcai-planning/) doi:10.5591/978-1-57735-516-8/IJCAI11-336

BibTeX

@inproceedings{rintanen2011ijcai-planning,
  title     = {{Planning with SAT, Admissible Heuristics and A*}},
  author    = {Rintanen, Jussi},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {2015-2020},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-336},
  url       = {https://mlanthology.org/ijcai/2011/rintanen2011ijcai-planning/}
}