---
title: "Planning with SAT, Admissible Heuristics and A*"
authors:
  - "Jussi Rintanen"
doi: "10.5591/978-1-57735-516-8/IJCAI11-336"
url: "https://ijcai.org/proceedings/2011/336"
pdf: "https://ijcai.org/proceedings/2011/0336.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "2015-2019"
track: ""
keywords:
---

# Planning with SAT, Admissible Heuristics and A*

Jussi Rintanen

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 2015-2019. DOI: [10.5591/978-1-57735-516-8/IJCAI11-336](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.