Learning, Commitment, and Completeness in Real-Time Heuristic Search

Abstract

In real-time heuristic search, an agent must select its next action within a prespecified time bound. Amazingly, it has been possible to prove that, despite this myopia, certain real-time search algorithms are complete (guaranteed to eventually reach a goal) under a small set of assumptions. This hinges on the algorithms learning updated heuristic values. In order to elucidate the space of complete real-time algorithms, previous work has provided general algorithm frameworks, into which components that meet certain criteria can be plugged, and proved them complete. Recently, a cost-algebraic real-time framework was proposed that makes strong assumptions on its heuristic learning component but only weak assumptions on its action commitment component. In this paper, we show that the opposite is also possible: we present and prove complete an alternative framework that makes weaker assumptions about heuristic learning but stronger assumptions on action commitment. We demonstrate in the domain of Real-time SIPP how the new framework implies the completeness of previously-published algorithms This work expands our knowledge of the design space of complete real-time search algorithms.