Adding local exploration to greedy best-first search in satisficing planning

摘要: Greedy Best-First Search (GBFS) is a powerful algorithm at the heart of many state art satisficing planners. One major weakness GBFS its behavior in so-called uninformative heuristic regions (UHRs) - parts search space which no provides guidance towards states with improved values. This work analyzes problem UHRs planning detail, and proposes two level framework as solution. In Local Exploration (GBFSLE), local exploration started from within global whenever seems stuck UHRs. Two different strategies are developed evaluated experimentally: (LS) Random Walk (LRW). The new planners LAMA-LS LAMA-LRW integrate these into component LAMA-2011. Both shown to yield clear improvements terms both coverage time on standard International Planning Competition benchmarks, especially for domains that proven have large or unbounded UHRs.