Heuristic Search

Heuristic Search

by Stefan Edelkamp, Stefan Schroedl
Released May 2011
Publisher(s): Morgan Kaufmann
ISBN: 9780080919737

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book 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.

  • 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

Table of contents

  1. Cover Image
  2. Table of Contents
  3. Front Matter
  4. Copyright
  5. List of Algorithms
  6. Preface
  7. Chapter 1. Introduction
    1. 1.1. Notational and Mathematical Background
    2. 1.2. Search
    3. 1.3. Success Stories
    4. 1.4. State Space Problems
    5. 1.5. Problem Graph Representations
    6. 1.6. Heuristics
    7. 1.7. Examples of Search Problems
    8. 1.8. General State Space Descriptions
    9. 1.9. Summary
    10. 1.10. Exercises
    11. 1.11. Bibliographic Notes
  8. Chapter 2. Basic Search Algorithms
    1. 2.1. Uninformed Graph Search Algorithms
    2. 2.2. Informed Optimal Search
    3. 2.3. *General Weights
    4. 2.4. Summary
    5. 2.5. Exercises
    6. 2.6. Bibliographic Notes
  9. Chapter 3. *Dictionary Data Structures
    1. 3.1. Priority Queues
    2. 3.2. Hash Tables
    3. 3.3. Subset Dictionaries
    4. 3.4. String Dictionaries
    5. 3.5. Summary
    6. 3.6. Exercises
    7. 3.7. Bibliographic Notes
  10. Chapter 4. Automatically Created Heuristics
    1. 4.1. Abstraction Transformations
    2. 4.2. Valtorta's Theorem
    3. 4.3. *Hierarchical A*
    4. 4.4. Pattern Databases
    5. 4.5. * Customized Pattern Databases
    6. 4.6. Summary
    7. 4.7. Exercises
    8. 4.8. Bibliographic Notes
  11. Chapter 5. Linear-Space Search
    1. 5.1. *Logarithmic Space Algorithms
    2. 5.2. Exploring the Search Tree
    3. 5.3. Branch-and-Bound
    4. 5.4. Iterative-Deepening Search
    5. 5.5. Iterative-Deepening A*
    6. 5.6. Prediction of IDA* Search
    7. 5.7. *Refined Threshold Determination
    8. 5.8. *Recursive Best-First Search
    9. 5.9. Summary
    10. 5.10. Exercises
    11. 5.11. Bibliographic Notes
  12. Chapter 6. Memory-Restricted Search
    1. 6.1. Linear Variants Using Additional Memory
    2. 6.2. Nonadmissible Search
    3. 6.3. Reduction of the Closed List
    4. 6.4. Reduction of the Open List
    5. 6.5. Summary
    6. 6.6. Exercises
    7. 6.7. Bibliographic Notes
  13. Chapter 7. Symbolic Search
    1. 7.1. Boolean Encodings for Set of States
    2. 7.2. Binary Decision Diagrams
    3. 7.3. Computing the Image for a State Set
    4. 7.4. Symbolic Blind Search
    5. 7.5. Limits and Possibilities of BDDs
    6. 7.6. Symbolic Heuristic Search
    7. 7.7. * Refinements
    8. 7.8. Symbolic Algorithms for Explicit Graphs
    9. 7.9. Summary
    10. 7.10. Exercises
    11. 7.11. Bibliographic Notes
  14. Chapter 8. External Search
    1. 8.1. Virtual Memory Management
    2. 8.2. Fault Tolerance
    3. 8.3. Model of Computation
    4. 8.4. Basic Primitives
    5. 8.5. External Explicit Graph Search
    6. 8.6. External Implicit Graph Search
    7. 8.7. * Refinements
    8. 8.8. * External Value Iteration
    9. 8.9. * Flash Memory
    10. 8.10. Summary
    11. 8.11. Exercises
    12. 8.12. Bibliographic Notes
  15. Chapter 9. Distributed Search
    1. 9.1. Parallel Processing
    2. 9.2. Parallel Depth-First Search
    3. 9.3. Parallel Best-First Search Algorithms
    4. 9.4. Parallel External Search
    5. 9.5. Parallel Search on the GPU
    6. 9.6. Bidirectional Search
    7. 9.7. Summary
    8. 9.8. Exercises
    9. 9.9. Bibliographic Notes
  16. Chapter 10. State Space Pruning
    1. 10.1. Admissible State Space Pruning
    2. 10.2. Nonadmissible State Space Pruning
    3. 10.3. Summary
    4. 10.4. Exercises
    5. 10.5. Bibliographic Notes
  17. Chapter 11. Real-Time Search
    1. 11.1. LRTA*
    2. 11.2. LRTA* with Lookahead One
    3. 11.3. Analysis of the Execution Cost of LRTA*
    4. 11.4. Features of LRTA*
    5. 11.5. Variants of LRTA*
    6. 11.6. How to Use Real-Time Search
    7. 11.7. Summary
    8. 11.8. Exercises
    9. 11.9. Bibliographic Notes
  18. Chapter 12. Adversary Search
    1. 12.1. Two-Player Games
    2. 12.2. *Multiplayer Games
    3. 12.3. General Game Playing
    4. 12.4. AND/OR Graph Search
    5. 12.5. Summary
    6. 12.6. Exercises
    7. 12.7. Bibliographic Notes
  19. Chapter 13. Constraint Search
    1. 13.1. Constraint Satisfaction
    2. 13.2. Consistency
    3. 13.3. Search Strategies
    4. 13.4. NP-Hard Problem Solving
    5. 13.5. Temporal Constraint Networks
    6. 13.6. *Path Constraints
    7. 13.7. *Soft and Preference Constraints
    8. 13.8. *Constraint Optimization
    9. 13.9. Summary
    10. 13.10. Exercises
    11. 13.11. Bibliographic Notes
  20. Chapter 14. Selective Search
    1. 14.1. From State Space Search to Minimization
    2. 14.2. Hill-Climbing Search
    3. 14.3. Simulated Annealing
    4. 14.4. Tabu Search
    5. 14.5. Evolutionary Algorithms
    6. 14.6. Approximate Search
    7. 14.7. Randomized Search
    8. 14.8. Ant Algorithms
    9. 14.9. * Lagrange Multipliers
    10. 14.10. * No-Free-Lunch
    11. 14.11. Summary
    12. 14.12. Exercises
    13. 14.13. Bibliographic Notes
  21. Chapter 15. Action Planning
    1. 15.1. Optimal Planning
    2. 15.2. Suboptimal Planning
    3. 15.3. Bibliographic Notes
  22. Chapter 16. Automated System Verification
    1. 16.1. Model Checking
    2. 16.2. Communication Protocols
    3. 16.3. Program Model Checking
    4. 16.4. Analyzing Petri Nets
    5. 16.5. Exploring Real-Time Systems
    6. 16.6. Analyzing Graph Transition Systems
    7. 16.7. Anomalies in Knowledge Bases
    8. 16.8. Diagnosis
    9. 16.9. Automated Theorem Proving
    10. 16.10. Bibliographic Notes
  23. Chapter 17. Vehicle Navigation
    1. 17.1. Components of Route Guidance Systems
    2. 17.2. Routing Algorithms
    3. 17.3. Cutting Corners
    4. 17.4. Bibliographic Notes
  24. Chapter 18. Computational Biology
    1. 18.1. Biological Pathway
    2. 18.2. Multiple Sequence Alignment
    3. 18.3. Bibliographic Notes
  25. Chapter 19. Robotics
    1. 19.1. Search Spaces
    2. 19.2. Search under Incomplete Knowledge
    3. 19.3. Fundamental Robot-Navigation Problems
    4. 19.4. Search Objective
    5. 19.5. Search Approaches
    6. 19.6. Greedy Localization
    7. 19.7. Greedy Mapping
    8. 19.8. Search with the Freespace Assumption
    9. 19.9. Bibliographic Notes
  26. Bibliography
  27. Index

Product information

  • Title: Heuristic Search
  • Author(s): Stefan Edelkamp, Stefan Schroedl
  • Release date: May 2011
  • Publisher(s): Morgan Kaufmann
  • ISBN: 9780080919737