TY - GEN
T1 - Planning with SAT, admissible heuristics and A
AU - Rintanen, Jussi
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84878789520&partnerID=8YFLogxK
U2 - 10.5591/978-1-57735-516-8/IJCAI11-336
DO - 10.5591/978-1-57735-516-8/IJCAI11-336
M3 - Conference contribution
SN - 9781577355120
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 2015
EP - 2020
BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
T2 - 22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
Y2 - 16 July 2011 through 22 July 2011
ER -