Efficient Goal-Directed Exploration

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Search Control

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 exploitation: the former approaches explore the state space using only knowledge of the physically visited portion of the domain, 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 utilize 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 switching from exploitation to exploration on parts of the state space where exploitation does not perform well. VECA provides better performance guarantees than previously studied heuristic-driven exploitation algorithms, and experimental evidence suggests that this guarantee does not deteriorate its average-case performance.