It has been recognized since the inception of artificial intelligence that abstractions,problem reformulations and approximations (AR&A) are central to humancommon-sense reasoning and problem solving and to the ability of systemsto reason effectively in complex domains. AR&A techniques have been used ina variety of problem-solving settings, including automated reasoning, cognitivemodelling, constraint programming, design, diagnosis, machine learning, modelbasedreasoning, planning, reasoning, scheduling, search, theorem proving, andintelligent tutoring. The primary use of AR&A techniques in such settings hasbeen to overcome computational intractability by decreasing the combinatorialcosts associated with searching large spaces. In addition, AR&A techniques areuseful for knowledge acquisition and explanation generation in complex domains.