Abstract: 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 (GBFSLE), 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 unbounded UHRs.
Introduction
In automated planning, Greedy Best-First Search (GBFS) is a fundamental algorithm that uses a heuristic function ($h$) to estimate the distance to a goal. However, GBFS suffers from a significant vulnerability: Uninformative Heuristic Regions (UHRs). These regions include local minima and large plateaus where heuristic values remain constant, providing no guidance. When GBFS enters a UHR, it often expands thousands of nodes across disparate parts of the state space, leading to a "stall" in progress. This paper introduces GBFS-LE, a framework designed to break out of these regions more efficiently through targeted local exploration.
Methodology
GBFS-LE implements a two-level search strategy. A Global Level maintains a standard GBFS, while a Local Level is triggered if the global search fails to improve its best-seen heuristic value ($h_{min}$) after a fixed number of expansions (STALL_SIZE). The system then pauses to launch a LocalExplore(n) procedure from the current best node.
Two primary local exploration strategies were developed:
- Local GBFS (LS): A small-scale, systematic search that restricts itself to a single plateau or branch, preventing the "pollution" of the global open list.
- Local Random Walk (LRW): A stochastic approach that performs walks of increasing length to jump out of local minima.
If the local search discovers a state with a better $h$-value than the current global $h_{min}$, the global search resumes from this improved state.
Heuristic Topology and Datasets
The effectiveness of local exploration is intrinsically linked to the search space topology. The researchers evaluated their methods using 2,112 problems from 54 domains across seven International Planning Competitions (IPC). These domains were categorized based on their heuristic topology, distinguishing between Large-UHR, Small-UHR, and Unrecognized-Deadend domains.
Experimental Results
The integration of local exploration strategies yielded substantial performance gains. When added to a baseline GBFS using the $h^{FF}$ heuristic, the LS strategy increased coverage from 1,561 to 1,657 solved problems. Furthermore, the authors integrated these methods into the LAMA-2011 framework. The resulting LAMA-LS solved 18 more problems than the original LAMA-2011 and demonstrated a significant speed advantage, particularly in Large-UHR domains.
A critical insight is that local exploration allows the planner to focus its effort on escaping the current region rather than oscillating between many. For example, in a specific notankage instance, standard GBFS took 763 seconds to escape a plateau, while GBFS-LS achieved the same in under one second.
Conclusion
GBFS-LE provides a robust solution to the limitations of standard greedy search in complex planning domains. While highly effective in navigating plateaus, the framework still faces challenges in "unrecognized dead ends" where heuristics are fundamentally misleading. Future work will focus on dynamic parameter adaptation and hybridizing systematic and stochastic local search methods to further improve robustness across diverse domain topologies.
Summary updated