2008 · 27 citations · 16 references
ComputingIndustrial EngineeringAlgorithmsOptimizationPath PlanningHeuristic OptimizationHeuristic SearchAdmissible HeuristicsDomain-specific HeuristicsHeuristic AlgorithmsHeuristic ComputationHeuristic Search PlanningHeuristicsPattern DatabasesSearch Heuristics
The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In assessing the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h + heuristic, the h k family of heuristics, and certain (additive) pattern database heuristics, compared to the optimal heuristic h ∗. Whereas h + and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive h k and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.
16
Blai Bonet, Héctor Geffner · Artificial Intelligence · 2001 · 961 citations · Full text
The computational complexity of propositional STRIPS planning
Tom Bylander · Artificial Intelligence · 1994 · 863 citations
Unifying SAT-based and graph-based planning
Henry Kautz, Bart Selman · 1999 · 423 citations
Admissible heuristics for optimal planning
Patrik Haslum, Héctor Geffner · 2000 · 311 citations