Proceedings of the AAAI Conference on Artificial Intelligence · 2014 · 26 citations · 25 references
ComputingDecision SciencesOptimizationPath PlanningSpace PlanningGreedy AlgorithmsHeuristic OptimizationHeuristic SearchMetaheuristic OptimizationBest-first SearchExplorationGreedy Best-first SearchHeuristic CoverageHeuristic Search Planning
Greedy Best-First Search (GBFS) is a powerful algorithm at the heart of many state of the art satisficing planners. One major weakness of GBFS is its behavior in so-called uninformative heuristic regions (UHRs) - parts of the search space in which no heuristic provides guidance towards states with improved heuristic values. This work analyzes the problem of UHRs in planning in detail, and proposes a two level search framework as a solution. In Greedy Best-First Search with Local Exploration (GBFS-LE), a local exploration is started from within a global GBFS whenever the search seems stuck in UHRs. Two different local exploration strategies are developed and evaluated experimentally: Local GBFS (LS) and Local Random Walk Search (LRW). The two new planners LAMA-LS and LAMA-LRW integrate these strategies into the GBFS component of LAMA-2011. Both are shown to yield clear improvements in terms of both coverage and search time on standard International Planning Competition benchmarks, especially for domains that are proven to have large or un- bounded UHRs.
25
The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks
2010 · 519 citations
A planning heuristic based on causal graph analysis
Malte Helmert · 2004 · 191 citations
Computing, Industrial Engineering, Knowledge Representation +10
A lookahead strategy for heuristic search planning
Vincent Vidal · 2004 · 122 citations