The role of preprocessing in problem solving systems: An ounce of reflection is worth a pound of backtracking

Abstract

We describe REFLECT, a problem solver in simulated robot worlds. REFLECT has successfully solved a variety of non-linear problems described as a conjunction of subtasks, including most of those found in the literature. First, during a preprocessing phase, the system explores its capabilities in the environment it is presented with. Various intrinsic properties of the given operators are inferred, such as the unattainability of certain conjunctive tasks. Macro operators are built, again considering only the given operators. REFLECT is then ready to accept problems, and proceeds by conducting backward heuristic search on a variation of a regular state-space graph termed a Goal-Kernel graph. Attention is not focused on any one sub task in particular, so that a global view of the problem is always maintained.