Planning with SAT, admissible heuristics and A*
作者： Jussi Rintanen
DOI: 10.5591/978-1-57735-516-8/IJCAI11-336
关键词: Heuristic 、 Iterative method 、 Heuristics 、 Mathematics 、 Optimal planning 、 Dominance relation 、 Reduction (complexity) 、 Mathematical optimization 、 Iterative deepening depth-first search 、 Sat problem
摘要: We study the relationship between optimal planning algorithms, in form of (iterative deepening) A* with (forward) state-space search, and reduction problem to SAT. Our results establish a strict dominance relation two approaches: any iterative deepening search can be efficiently simulated SAT framework, assuming that heuristic has been encoded problem, but opposite is not possible as IDA* searches sometimes take exponentially longer.
ijcai.org
sci-hub.st 参考文章(14)
Jussi Rintanen, Planning graphs and propositional clause-learning principles of knowledge representation and reasoning. pp. 535- 543 ,(2008)
David G. Mitchell, A SAT Solver Primer. Bulletin of The European Association for Theoretical Computer Science. ,vol. 85, pp. 112- 132 ,(2005)
Jussi Rintanen, Heuristics for planning with SAT principles and practice of constraint programming. pp. 414- 428 ,(2010) , 10.1007/978-3-642-15396-9_34
Knot Pipatsrisawat, Adnan Darwiche, On the power of clause-learning SAT solvers with restarts principles and practice of constraint programming. pp. 654- 668 ,(2009) , 10.1007/978-3-642-04244-7_51
Bart Selman, Henry Kautz, Planning as satisfiability european conference on artificial intelligence. pp. 359- 363 ,(1992)
Peter Hart, Nils Nilsson, Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths IEEE Transactions on Systems Science and Cybernetics. ,vol. 4, pp. 100- 107 ,(1968) , 10.1109/TSSC.1968.300136
Jose L. Balcazar, Joaquim Gabarro, Josep Diaz, Structural Complexity I ,(1988)
Donald Loveland, George Logemann, Martin Davis, A machine program for theorem-proving ,(2011)
R. I. Brafman, On reachability, relevance, and resolution in the planning as satisfiability approach Journal of Artificial Intelligence Research. ,vol. 14, pp. 1- 28 ,(2001) , 10.1613/JAIR.737
Blai Bonet, Héctor Geffner, Planning as heuristic search Artificial Intelligence. ,vol. 129, pp. 5- 33 ,(2001) , 10.1016/S0004-3702(01)00108-4