Using abstraction to interleave planning and execution

Abstraction is a technology that enables interleaved planning and execution, the much sought-after quality of a robot architecture that can both plan and act (and plan and act and plan...) in short order. This paper presents a definition for Abstraction and for an architecture composed of a collection of abstractions, or an Abstraction System. We span both the theoretical extreme of formally defining abstraction and the empirical extreme of implementing an Abstraction System on a real-world robot and collecting compelling experimental results. I What is Abstraction? Abstraction is a term that has been used by many to denote some strategic form of problem simplification. Particular instances of abstraction can be found in early planning literature (Sacerdoti 1974), while more recent, formal discourse in the planning community has led to crisp definitions of abstraction (Holte et al. 1996). The most elemental ingredient of abstraction is a representational transformation. An abstraction can perform a transformation on the original search space, yielding a new, less complex search space in which discrimination between (irrelevant) details has been removed. More formally: An Abstraction is a mapping from the original search space to an abstract search space, such that every state in the original search space is mapped to exactly one state in the abstract search space. l°O Pigure 1: A security robot reasoning at two levels of abstraction This surjective mapping of states, known as State Abstraction, is fully general. Even in the case of continuous worlds, volume-based reasoning can reduce representation requirements to finite degrees, thereby allowing this definition to function without difficult