Abstraction, Reformulation, and Approximation

It has been recognized since the inception of Artificial Intelligence (AI) 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 to solve a variety of tasks, including automatic programming, constraint satisfaction, design, diagnosis, machine learning, search, planning, reasoning, game playing, scheduling, and theorem proving. The primary purpose of AR&A techniques in such settings is to overcome computational intractability. In addition, AR&A techniques are useful for accelerating learning and for summarizing sets of solutions. This volume contains the proceedings of SARA 2002, the fifth Symposium on Abstraction, Reformulation, and Approximation, held at Kananaskis Mountain Lodge, Kananaskis Village, Alberta (Canada), August 2 4, 2002. The SARA series is the continuation of two separate threads of workshops: AAAI workshops in 1990 and 1992, and an ad hoc series beginning with the "Knowledge Compilation" workshop in 1986 and the "Change of Representation and Inductive Bias" workshop in 1988 with followup workshops in 1990 and 1992. The two workshop series merged in 1994 to form the first SARA. Subsequent SARAs were held in 1995, 1998, and 2000.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Presentations.- Model Checking and Abstraction.- Reformulation in Planning.- Spatiotemporal Abstraction of Stochastic Sequential Processes.- State Space Relaxation and Search Strategies in Dynamic Programming.- Invited Presentations.- Admissible Moves in Two-Player Games.- Dynamic Bundling: Less Effort for More Solutions.- Symbolic Heuristic Search Using Decision Diagrams.- On the Construction of Human-Automation Interfaces by Formal Abstraction.- Pareto Optimization of Temporal Decisions.- An Information-Theoretic Characterization of Abstraction in Diagnosis and Hypothesis Selection.- A Tractable Query Cache by Approximation.- An Algebraic Framework for Abstract Model Checking.- Action Timing Discretization with Iterative-Refinement.- Formalizing Approximate Objects and Theories: Some Initial Results.- Model Minimization in Hierarchical Reinforcement Learning.- Learning Options in Reinforcement Learning.- Approximation Techniques for Non-linear Problems with Continuum of Solutions.- Approximation of Relations by Propositional Formulas: Complexity and Semantics.- Abstracting Visual Percepts to Learn Concepts.- Short Presentations.- PAC Meditation on Boolean Formulas.- On the Reformulation of Vehicle Routing Problems and Scheduling Problems.- The Oracular Constraints Method.- Performance of Lookahead Control Policies in the Face of Abstractions and Approximations.- TTree: Tree-Based State Generalization with Temporally Abstract Actions.- Ontology-Driven Induction of Decision Trees at Multiple Levels of Abstraction.- Research Summaries.- Abstracting Imperfect Information Game Trees.- Using Abstraction for Heuristic Search and Planning.- Approximation Techniques in Multiagent Learning.- Abstraction and Reformulation in GraphPlan.- Abstract Reasoning for Planning and Coordination.- Research Summary: Abstraction Techniques, and Their Value.- Reformulation of Non-binary Constraints.- Reformulating Combinatorial Optimization as Constraint Satisfaction.- Autonomous Discovery of Abstractions through Interaction with an Environment.- Interface Verification: Discrete Abstractions of Hybrid Systems.- Learning Semi-lattice Codebooks for Image Compression.- Research Summary.- Principled Exploitation of Heuristic Information.- Reformulation of Temporal Constraint Networks.