It has been recognized since the inception of artificial intelligence that abstractions,
problem reformulations and approximations (AR&A) are central to human
common-sense reasoning and problem solving and to the ability of systems
to reason effectively in complex domains. AR&A techniques have been used in
a variety of problem-solving settings, including automated reasoning, cognitive
modelling, constraint programming, design, diagnosis, machine learning, modelbased
reasoning, planning, reasoning, scheduling, search, theorem proving, and
intelligent tutoring. The primary use of AR&A techniques in such settings has
been to overcome computational intractability by decreasing the combinatorial
costs associated with searching large spaces. In addition, AR&A techniques are
useful for knowledge acquisition and explanation generation in complex domains.