Search Progress and Potentially Expanded States in Greedy Best-First Search

Manuel Heusner, Thomas Keller, Malte HelmertIJCAI 2018 · DOI

TL;DR

This paper introduces the concept of "high-water mark benches" to precisely characterize the states explored by Greedy Best-First Search (GBFS), a common satisficing search algorithm. By understanding these benches and their connectivity, the authors provide a complete picture of which states could be expanded by GBFS under any tie-breaking strategy, offering a significant step towards a formal understanding of satisficing search.

What Problem Does This Paper Address?

Optimal search algorithms like A have a well-understood theoretical basis for predicting which states they will expand. For instance, A with an admissible heuristic will expand a state s if its estimated total cost f(s) is less than the optimal solution cost c*. However, for satisficing search algorithms, which aim to find any solution quickly rather than necessarily the optimal one, this level of theoretical understanding is lacking. Greedy Best-First Search (GBFS) is a prominent example of such an algorithm, but its behavior, especially concerning which states it might explore, is not fully characterized. This paper aims to bridge this gap by providing a formal framework to understand GBFS's search progress and the set of potentially expanded states.

Methods

The core contribution of this paper is the introduction of "high-water mark benches." These benches are defined based on a concept called the "high-water mark" (hwm), which intuitively measures how high heuristic values must climb before a solution can be found from a given state.

  1. Progress States: The authors first identify "progress states." A state s is a progress state if its high-water mark is greater than the high-water mark of its successors (hwm(s) > hwm(succ(s))). These states are crucial because expanding a progress state effectively resets the search, making all other currently open states ineligible for future expansion. This observation reveals that GBFS operates episodically, with progress states marking the boundaries of these episodes.
  2. High-Water Mark Benches: Each progress state s induces a "bench," denoted B(s). A bench represents a single search episode, starting with the expansion of s and continuing until another progress state (an "exit state" of the bench) is expanded. Benches are defined by the set of states reachable from s while staying below a certain heuristic value threshold (the "level" of the bench), and importantly, without encountering other progress states until an exit state is reached.
  3. Bench Transition System: The connectivity between these benches is formalized by a "bench transition system." This is a directed graph where nodes are benches, and an edge exists from bench B(s) to bench B(s') if s' is an exit state of B(s) and s' is not a goal state. This system captures the sequence in which GBFS can transition between search episodes.

By combining the states within all benches defined by the bench transition system, the authors can precisely characterize the set of all states that could potentially be expanded by any GBFS tie-breaking strategy.

Datasets

Not discussed in the paper. The paper uses a running example state space topology to illustrate its concepts.

Key Insights and Ideas

  • GBFS is Episodic: The most significant insight is that GBFS, despite its greedy nature, operates in distinct episodes. Progress states act as natural separators for these episodes, and once a progress state is expanded, the search effectively restarts from that state, discarding previously explored branches that are now deemed suboptimal for the current episode.
  • Progress States as Reset Points: Progress states are not just markers but functional reset points. Their property (hwm(s) > hwm(succ(s))) guarantees that any path from a successor of s to a goal state will involve states with strictly lower heuristic values than s's current heuristic value. This makes states with higher heuristic values than s (that were previously open) permanently irrelevant.
  • Benches Capture Local Behavior: High-water mark benches provide a formal way to analyze the behavior of GBFS within a single search episode. They delineate the states that can be explored before the search must transition to a new episode (marked by expanding another progress state).
  • Complete Characterization of Potentially Expanded States: The union of all states belonging to benches in the bench transition system precisely defines the set of states that any GBFS tie-breaking strategy could potentially expand. This is a powerful result for understanding the limits of GBFS exploration.

Key Results

The paper's main result is Theorem 1: "the set of states potentially expanded by GBFS is the union of states of all benches in the bench transition system." This theorem provides a formal characterization of the state space explored by GBFS, irrespective of the specific tie-breaking strategy used. The authors state that this set can be computed in polynomial time in the number of states.

Limitations and Future Work

  • Tie-breaking Strategy: While the paper characterizes the set of potentially expanded states across all tie-breaking strategies, it doesn't delve into how specific tie-breaking strategies influence the order of expansion within a bench or the specific path taken.
  • Heuristic Properties: The analysis relies on certain assumptions about heuristic values (e.g., initial state having a higher heuristic than others, goal states having lower heuristic values than non-goal states). While these are stated not to affect GBFS behavior, they simplify definitions.
  • Future Work: The authors suggest that their framework can be used to analyze the performance of GBFS and potentially guide the design of better satisficing search algorithms. The efficient computation of the potentially expanded states is also highlighted.

Summary updated

BibTeX
@inproceedings{heusner2018search,
  author = {Manuel Heusner and Thomas Keller and Malte Helmert},
  title = {{Search Progress and Potentially Expanded States in Greedy Best-First Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/735},
}
Figure