Augmenting Exploration with Locally Greedy Probes

Abstract

Enhancing Greedy Best First Search (GBFS) with stochastic exploration will often greatly improve search performance. In this work, we show that one way exploration does so is by helping the search find states that are "easy" for standard GBFS without exploration. In particular, we show that in problems in which standard GBFS struggles and exploration helps, there are often many states that are reachable from the initial state that standard GBFS can quickly find solutions from. Many such states are actually outside the Bench Transition System (BTS) --- which is a structure that contains all states that standard GBFS may encounter --- meaning GBFS cannot reach them without using exploration. To allow exploration mechanisms to better exploit the existence of such states, we introduce a method called locally greedy probes. Upon a successor having an improved heuristic from its parent, locally greedy probes pause exploration and greedily hill-climb along a single path as long as heuristic improvements keep occurring. Our empirical evaluation shows that this approach is effective at enhancing several exploration mechanisms in a variety of classical planning domains.