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 of the art satisficing planners. One major weakness of GBFS is its behavior in so-called uninfor-mative 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 de-tail, 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 an