Efficient Goal-Directed Exploration

Abstract

If a state space is not completely known in advance, then search algorithms have to explore it sufficiently to locate a goal state and a path leading to it, performing therefore what we call goal-directed exploration. Two paradigms of this process are pure exploration and heuristic-driven exploita-tion: the former approaches explore the state space using only knowledge of the physically visited portion of the do-main, whereas the latter approaches totally rely on heuristic knowledge to guide the search towards goal states. Both approaches have disadvantages: the first one does not uti-lize available knowledge to cut down the search effort, and the second one relies too much on the knowledge, even if it is misleading. We have therefore developed a framework for goal-directed exploration, called VECA, that combines the advantages of both approaches by automatically switch-ing from exploitation to exploration on parts of the state space where exploitation does not perform well. VECA pro-vides better performance guarantees than previously studied heuristic-driven exploitation algorithms, and experimental evidence suggests that this guarantee does not deteriorate its average-case performance.