2009 · 144 citations · 10 references
ComputingAutonomous SystemsMotion PlanningPath PlanningSpace PlanningHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationAdmissible HeuristicsBest-first SearchEmpirical EvaluationHeuristic Search PlanningHeuristicsLandmark Heuristics
Planning landmarks are facts that must be true at some point in every solution plan. Previous work has very successfully exploited planning landmarks in satisficing (non-optimal) planning. We propose a methodology for deriving admissible heuristic estimates for cost-optimal planning from a set of planning landmarks. The resulting heuristics fall into a novel class of multi-path dependent heuristics, and we present a simple best-first search procedure exploiting such heuristics. Our empirical evaluation shows that this framework favorably competes with the state-of-the-art of cost-optimal heuristic search. 1
10
Generalized best-first search strategies and the optimality of A*
Rina Dechter, Judea Pearl · Journal of the ACM · 1985 · 1.1K citations · Full text
Blai Bonet, Héctor Geffner · Artificial Intelligence · 2001 · 961 citations · Full text