Informatics Report Series


Report   

EDI-INF-RR-1101


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Planning as Heuristic Search
Authors: B. Bonet ; Hector Geffner
Date:Jun 2001
Publication Title:Artificial Intelligence
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:129 (1-2) Page Nos:5-33
DOI:10.1016/S0004-3702(01)00108-4 ISBN/ISSN:0004-3702
Abstract:
In the AIPS98 Planning Contest, the HSP planners showed that heuristic search planners can be competitive with state of the art Graphplan and SAT planners. Heuristic search planners like HSP transform planning problems into problems of heuristic search by automatically extracting heuristics from Strips encodings. They differ from specialised problem solvers such as those developed for the 24-Puzzle and Rubik's cube in that they use a general declarative langugae for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are based on a simple and general heuristics that assumes that action preconditions are independent. The heuristic is then used in the context of best-first and hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting information about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do best. We also compare the performance of these planners with two state-of-the-art planners, and show that the simplest planner based on a pure best-first search yields the most solid performance over a large set of problems. We also discuss the strengths and limitations of this approach, establish a correspondance between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic-search planners and specialized solvers.
Links To Paper
1st link
Bibtex format
@Article{EDI-INF-RR-1101,
author = { B. Bonet and Hector Geffner },
title = {Planning as Heuristic Search},
journal = {Artificial Intelligence},
publisher = {Elsevier},
year = 2001,
month = {Jun},
volume = {129 (1-2)},
pages = {5-33},
doi = {10.1016/S0004-3702(01)00108-4},
url = {http://dx.doi.org/10.1016/S0004-3702(01)00108-4},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh