Abstraction, Reformulation, and Approximation: 5th International Symposium, SARA 2002, Kananaskis, Alberta, Canada, August 2-4, 2002, Proceedings (Lecture ... / Lecture Notes in Artificial Intelligence)

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. Model Checking And Abstraction / Robert P. Kurshan -- Reformulation In Planning / Derek Long, Maria Fox And Muna Hamdi -- Spatiotemporal Abstraction Of Stochastic Sequential Processes / Sridhar Mahadevan -- State Spate Relaxation And Search Strategies In Dynamic Programming / Aristide Mingozzi -- Admissible Moves In Two-player Games / Tristan Cazenave -- Dynamic Bundling: Less Effort For More Solutions / Berthe Y. Choueiry And Amy M. Davis -- Symbolic Heuristic Search Using Decision Diagrams / Eric Hansen, Rong Zhou And Zhengzhu Feng -- On The Construction Of Human-automation Interfaces By Formal Abstraction / Michael Heymann And Asaf Degani -- Pareto Optimization Of Temporal Decisions / Lina Khatib, Paul Morris And Robert Morris. Sven Koenig, Robert C. Holte (eds.). Includes Bibliographical References And Index. Also Available Via The World Wide Web. Model Checking and Abstraction....Pages 1-17 Reformulation in Planning....Pages 18-32 Spatiotemporal Abstraction of Stochastic Sequential Processes....Pages 33-50 State Space Relaxation and Search Strategies in Dynamic Programming....Pages 51-51 Admissible Moves in Two-Player Games....Pages 52-63 Dynamic Bundling: Less Effort for More Solutions....Pages 64-82 Symbolic Heuristic Search Using Decision Diagrams....Pages 83-98 On the Construction of Human-Automation Interfaces by Formal Abstraction....Pages 99-115 Pareto Optimization of Temporal Decisions....Pages 116-125 An Information-Theoretic Characterization of Abstraction in Diagnosis and Hypothesis Selection....Pages 126-139 A Tractable Query Cache by Approximation....Pages 140-151 An Algebraic Framework for Abstract Model Checking....Pages 152-169 Action Timing Discretization with Iterative-Refinement....Pages 170-177 Formalizing Approximate Objects and Theories: Some Initial Results....Pages 178-195 Model Minimization in Hierarchical Reinforcement Learning....Pages 196-211 Learning Options in Reinforcement Learning....Pages 212-223 Approximation Techniques for Non-linear Problems with Continuum of Solutions....Pages 224-241 Approximation of Relations by Propositional Formulas: Complexity and Semantics....Pages 242-255 Abstracting Visual Percepts to Learn Concepts....Pages 256-273 PAC Meditation on Boolean Formulas....Pages 274-281 On the Reformulation of Vehicle Routing Problems and Scheduling Problems....Pages 282-289 The Oracular Constraints Method....Pages 290-298 Performance of Lookahead Control Policies in the Face of Abstractions and Approximations....Pages 299-307 TTree: Tree-Based State Generalization with Temporally Abstract Actions....Pages 308-315 Ontology-Driven Induction of Decision Trees at Multiple Levels of Abstraction....Pages 316-323 Abstracting Imperfect Information Game Trees....Pages 324-325 Using Abstraction for Heuristic Search and Planning....Pages 326-327 Approximation Techniques in Multiagent Learning....Pages 328-329 Abstraction and Reformulation in GraphPlan....Pages 330-330 Abstract Reasoning for Planning and Coordination....Pages 331-332 Research Summary: Abstraction Techniques, and Their Value....Pages 333-334 Reformulation of Non-binary Constraints....Pages 335-335 Reformulating Combinatorial Optimization as Constraint Satisfaction....Pages 336-337 Autonomous Discovery of Abstractions through Interaction with an Environment....Pages 338-339 Interface Verification: Discrete Abstractions of Hybrid Systems....Pages 340-341 Learning Semi-lattice Codebooks for Image Compression....Pages 342-343 Research Summary....Pages 344-344 Principled Exploitation of Heuristic Information....Pages 345-346 Reformulation of Temporal Constraint Networks....Pages 347-347 This book constitutes the refereed proceedings of the 5th International Symposium on Abstraction, Reformulation, and Approximation, SARA 2002, held in Kananaskis, Alberta, Canada, in August 2002. The 15 revised full papers and 6 short papers were carefully reviewed and selected for inclusion in the book. Also included are 4 invited papers and 14 abstracts. All current aspects of abstraction, reformulation, and approximation in the context of human common-sense reasoning, problem solving, and efficiently reasoning in complex domains are addressed. Among the application fields of these techniques are automatic programming, constraint satisfaction, design, diagnosis, machine learning, search, planning, reasoning, game playing, scheduling, and theorem proving