Heuristic Search, 1st Edition

Theory and Applications

 
Heuristic Search, 1st Edition,Stefan Edelkamp,Stefan Schroedl,ISBN9780123725127
 
 
Up to
25%
off
 

  &      

Morgan Kaufmann

9780123725127

9780080919737

712

235 X 191

Your guide to the analysis, implementation and application of heuristic search for artificial intelligence problem-solving techniques

Print Book + eBook

USD 107.94
USD 179.90

Buy both together and save 40%

Print Book

Hardcover

In Stock

Estimated Delivery Time
USD 67.46
USD 89.95

eBook
eBook Overview

VST (VitalSource Bookshelf) format

DRM-free included formats : EPUB, Mobi (for Kindle), PDF

USD 67.46
USD 89.95
Add to Cart
 
 

Key Features

  • Provides real-world success stories and case studies for heuristic search algorithms
  • Includes many AI developments not yet covered in textbooks such as pattern databases, symbolic search, and parallel processing units

Description

Search has been vital to artificial intelligence from the very beginning as a core technique in problem solving. The authors present a thorough overview of heuristic search with a balance of discussion between theoretical analysis and efficient implementation and application to real-world problems. Current developments in search such as pattern databases and search with efficient use of external memory and parallel processing units on main boards and graphics cards are detailed.

Heuristic search as a problem solving tool is demonstrated in applications for puzzle solving, game playing, constraint satisfaction and machine learning. While no previous familiarity with heuristic search is necessary the reader should have a basic knowledge of algorithms, data structures, and calculus. Real-world case studies and chapter ending exercises help to create a full and realized picture of how search fits into the world of artificial intelligence and the one around us.

Readership

Researchers, professors, and graduate students

Stefan Edelkamp

Stefan Edelkamp is senior researcher and lecturer at University Bremen, where he heads projects on intrusion detection, on model checking and on planning for general game playing. He received an M.S. degree from the University Dortmund for his Master’s thesis on "Weak Heapsort", and a Ph.d. degree from the University of Freiburg for his dissertation on "Data Structures and Learning Algorithms in State Space Search". Later on, he obtained a postdoctoral lecture qualification (Venia Legendi) for his habilitation on "Heuristic Search". His planning systems won various first and second performance awards at International Planning Competitions. Stefan Edelkamp has published extensively on search, serves as member on program committees (including recent editions of SARA, SOCS, ICAPS, ECAI, IJCAI, and AAAI) and on steering committees (including SPIN and MOCHART). He is member of the editorial board of JAIR and organizes international workshops, tutorials, and seminars in his area of expertise. In 2011 he will co-chair the ICAPS Conference as well as the German Conference on AI.

Affiliations and Expertise

Senior Researcher and Lecturer at University of Bremen

Stefan Schroedl

Stefan Schroedl is a researcher and software developer in the areas of artifical intelligence and machine learning. He worked as a freelance software developer for different companies in Germany and Switzerland, among others, designing and realizing a route finding systems for a leading commercial product in Switzerland. At DaimlerChrylser Research, he continued to work on automated generation and search of route maps based on global positioning traces. Stefan Schroedl later joined Yahoo! Labs to develop auction algorithms, relevance prediction and user personalization systems for web search advertising. In his current position at A9.com, he strives to improve Amazon.com's product search using machine-learned ranking models. He has published on route finding algorithms, memory-limited and external-memory search, as well as on search for solving DNA sequence alignment problems. Stefan Schroedl hold a Ph.D. for his dissertation "Negation as Failure in Explanation- Based Generalization", and a M.S degree for his thesis "Coupling Numerical and Symbolic Methods in the Analysis of Neurophysiological Experiments".

Affiliations and Expertise

Senior Scientist at Yahoo!, Inc.

Heuristic Search, 1st Edition

List of Algorithms

Preface

Chapter 1. Introduction

1.1. Notational and Mathematical Background

1.2. Search

1.3. Success Stories

1.4. State Space Problems

1.5. Problem Graph Representations

1.6. Heuristics

1.7. Examples of Search Problems

1.8. General State Space Descriptions

1.9. Summary

1.10. Exercises

1.11. Bibliographic Notes

Chapter 2. Basic Search Algorithms

2.1. Uninformed Graph Search Algorithms

2.2. Informed Optimal Search

2.3. *General Weights

2.4. Summary

2.5. Exercises

2.6. Bibliographic Notes

Chapter 3. *Dictionary Data Structures

3.1. Priority Queues

3.2. Hash Tables

3.3. Subset Dictionaries

3.4. String Dictionaries

3.5. Summary

3.6. Exercises

3.7. Bibliographic Notes

Chapter 4. Automatically Created Heuristics

4.1. Abstraction Transformations

4.2. Valtorta's Theorem

4.3. *Hierarchical A*

4.4. Pattern Databases

4.5. * Customized Pattern Databases

4.6. Summary

4.7. Exercises

4.8. Bibliographic Notes

Chapter 5. Linear-Space Search

5.1. *Logarithmic Space Algorithms

5.2. Exploring the Search Tree

5.3. Branch-and-Bound

5.4. Iterative-Deepening Search

5.5. Iterative-Deepening A*

5.6. Prediction of IDA* Search

5.7. *Refined Threshold Determination

5.8. *Recursive Best-First Search

5.9. Summary

5.10. Exercises

5.11. Bibliographic Notes

Chapter 6. Memory-Restricted Search

6.1. Linear Variants Using Additional Memory

6.2. Nonadmissible Search

6.3. Reduction of the Closed List

6.4. Reduction of the Open List

6.5. Summary

6.6. Exercises

6.7. Bibliographic Notes

Chapter 7. Symbolic Search

7.1. Boolean Encodings for Set of States

7.2. Binary Decision Diagrams

7.3. Computing the Image for a State Set

7.4. Symbolic Blind Search

7.5. Limits and Possibilities of BDDs

7.6. Symbolic Heuristic Search

7.7. * Refinements

7.8. Symbolic Algorithms for Explicit Graphs

7.9. Summary

7.10. Exercises

7.11. Bibliographic Notes

Chapter 8. External Search

8.1. Virtual Memory Management

8.2. Fault Tolerance

8.3. Model of Computation

8.4. Basic Primitives

8.5. External Explicit Graph Search

8.6. External Implicit Graph Search

8.7. * Refinements

8.8. * External Value Iteration

8.9. * Flash Memory

8.10. Summary

8.11. Exercises

8.12. Bibliographic Notes

Chapter 9. Distributed Search

9.1. Parallel Processing

9.2. Parallel Depth-First Search

9.3. Parallel Best-First Search Algorithms

9.4. Parallel External Search

9.5. Parallel Search on the GPU

9.6. Bidirectional Search

9.7. Summary

9.8. Exercises

9.9. Bibliographic Notes

Chapter 10. State Space Pruning

10.1. Admissible State Space Pruning

10.2. Nonadmissible State Space Pruning

10.3. Summary

10.4. Exercises

10.5. Bibliographic Notes

Chapter 11. Real-Time Search

11.1. LRTA*

11.2. LRTA* with Lookahead One

11.3. Analysis of the Execution Cost of LRTA*

11.4. Features of LRTA*

11.5. Variants of LRTA*

11.6. How to Use Real-Time Search

11.7. Summary

11.8. Exercises

11.9. Bibliographic Notes

Chapter 12. Adversary Search

12.1. Two-Player Games

12.2. *Multiplayer Games

12.3. General Game Playing

12.4. AND/OR Graph Search

12.5. Summary

12.6. Exercises

12.7. Bibliographic Notes

Chapter 13. Constraint Search

13.1. Constraint Satisfaction

13.2. Consistency

13.3. Search Strategies

13.4. NP-Hard Problem Solving

13.5. Temporal Constraint Networks

13.6. *Path Constraints

13.7. *Soft and Preference Constraints

13.8. *Constraint Optimization

13.9. Summary

13.10. Exercises

13.11. Bibliographic Notes

Chapter 14. Selective Search

14.1. From State Space Search to Minimization

14.2. Hill-Climbing Search

14.3. Simulated Annealing

14.4. Tabu Search

14.5. Evolutionary Algorithms

14.6. Approximate Search

14.7. Randomized Search

14.8. Ant Algorithms

14.9. * Lagrange Multipliers

14.10. * No-Free-Lunch

14.11. Summary

14.12. Exercises

14.13. Bibliographic Notes

Chapter 15. Action Planning

15.1. Optimal Planning

15.2. Suboptimal Planning

15.3. Bibliographic Notes

Chapter 16. Automated System Verification

16.1. Model Checking

16.2. Communication Protocols

16.3. Program Model Checking

16.4. Analyzing Petri Nets

16.5. Exploring Real-Time Systems

16.6. Analyzing Graph Transition Systems

16.7. Anomalies in Knowledge Bases

16.8. Diagnosis

16.9. Automated Theorem Proving

16.10. Bibliographic Notes

Chapter 17. Vehicle Navigation

17.1. Components of Route Guidance Systems

17.2. Routing Algorithms

17.3. Cutting Corners

17.4. Bibliographic Notes

Chapter 18. Computational Biology

18.1. Biological Pathway

18.2. Multiple Sequence Alignment

18.3. Bibliographic Notes

Chapter 19. Robotics

19.1. Search Spaces

19.2. Search under Incomplete Knowledge

19.3. Fundamental Robot-Navigation Problems

19.4. Search Objective

19.5. Search Approaches

19.6. Greedy Localization

19.7. Greedy Mapping

19.8. Search with the Freespace Assumption

19.9. Bibliographic Notes

Bibliography

Index

Quotes and reviews

"Heuristic Search is a very solid monograph and textbook on (not only heuristic) search. In its presentation it is always more formal than colloquial, it is precise and well structured. Due to its spiral approach it motivates reading it in its entirety." --Zentralblatt MATH 2012

"The authors have done an outstanding job putting together this book on artificial intelligence (AI) heuristic state space search. It comprehensively covers the subject from its basics to the most recent work and is a great introduction for beginners in this field." --BCS.org

"Heuristic search lies at the core of Artificial Intelligence and it provides the foundations for many different approaches in problem solving. This book provides a comprehensive yet deep description of the main algorithms in the field along with a very complete discussion of their main applications. Very well-written, it embellishes every algorithm with pseudo-code and technical studies of their theoretical performance." --Carlos Linares López, Universidad Carlos III de Madrid

"This is an introduction to artificial intelligence heuristic state space search. Authors Edelkamp (U. of Bremen, Germany) and Schrödl (a research scientist at Yahoo! Labs) seek to strike a balance between search algorithms and their theoretical analysis, on the one hand, and their efficient implementation and application to important real-world problems on the other, while covering the field comprehensively from well-known basic results to recent work in the state of the art. Prior knowledge of artificial intelligence is not assumed, but basic knowledge of algorithms, data structures, and calculus is expected. Proofs are included for formal rigor and to introduce proof techniques to the reader. They have organized the material into five sections: heuristic search primer, heuristic search under memory constraints, heuristic search under time constraints, heuristic search variants, and applications." --SciTech Book News

"This almost encyclopedic text is suitable for advanced courses in artificial intelligence and as a text and reference for developers, practitioners, students, and researchers in artificial intelligence, robotics, computational biology, and the decision sciences. The exposition is comparable to texts for a graduate-level or advanced undergraduate course in computer science, and prior exposure or coursework in advanced algorithms, computability, or artificial intelligence would help a great deal in understanding the material. Algorithms are described in pseudocode, accompanied by diagrams and narrative explanations in the text. The vast size of the ‘search algorithms’ subject domain and the variety of applications of search mean that much information--especially pertaining to applications of search algorithms--had to be left out; however, an extensive (though still limited) bibliography is included for follow-up by the reader. Exercises are provided for each chapter, except the five chapters on applications, and bibliographic notes accompany all chapters." --Computing Reviews

 
 
Free Shipping
Shop with Confidence

Free Shipping around the world
▪ Broad range of products
▪ 30 days return policy
FAQ

Contact Us