Heuristic Search

Heuristic Search

Theory and Applications

1st Edition - May 31, 2011

Write a review

  • Authors: Stefan Edelkamp, Stefan Schrodl
  • Hardcover ISBN: 9780123725127
  • eBook ISBN: 9780080919737

Purchase options

Purchase options
Available
DRM-free (Mobi, PDF, EPub)
Sales tax will be calculated at check-out

Institutional Subscription

Free Global Shipping
No minimum order

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.

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

Readership

Researchers, professors, and graduate students

Table of Contents

  • 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

Product details

  • No. of pages: 712
  • Language: English
  • Copyright: © Morgan Kaufmann 2011
  • Published: May 31, 2011
  • Imprint: Morgan Kaufmann
  • Hardcover ISBN: 9780123725127
  • eBook ISBN: 9780080919737

About the Authors

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 Schrodl

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.

Ratings and Reviews

Write a review

There are currently no reviews for "Heuristic Search"