Heuristic Search book cover

Heuristic Search

Theory and Applications

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.

Audience
Researchers, professors, and graduate students

Hardbound, 712 Pages

Published: June 2011

Imprint: Morgan Kaufmann

ISBN: 978-0-12-372512-7

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-1238-68150
    "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


Contents

  • I Heuristic Search Primer

    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

    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

    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

    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

    II Heuristic Search under Memory Constraints
    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

    6 Memory Restricted Search
    6.1 Linear Variants using Additional Memory
    6.2 Non-Admissible 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

    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

    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

    III Heuristic Search under Time Constraints
    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

    10 State Space Pruning
    10.1 Admissible State Space Pruning
    10.2
    10.3 Summary
    10.4 Exercises
    10.5 Bibliographic Notes

    11 Real-Time Search by Sven Koenig
    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 Additional Variants of LRTA
    11.6 Examples for How to Use Real-Time Search
    11.7 Summary
    11.8 Exercises
    11.9 Bibliography

    IV Heuristic Search Variants
    12 Adversary Search
    12.1 Two-Player Games
    12.2 Multi-Player Games
    12.3 General Game Playing
    12.4 AND/OR Graph Search
    12.5 Summary
    12.6 Bibliographic Notes

    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

    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.11Summary
    14.12 Exercises
    14.13 Bibliographic Notes .

    V Heurstic Search Applications

    15 Action Planning
    15.1 Optimal Planning
    15.2 Suboptimal Planning
    15.3 Bibliographic Notes

    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

    17 Vehicle Navigation
    17.2 Routing Algorithms
    17.3 Cutting Corners
    17.4 Bibliographic Notes

    18 Computational Biology
    18.1 Biological Pathway
    18.2 Mulitple Sequence Allignment
    18.3 Bibliographic Notes
    19 Robotics by Sven Koenig
    19.1 Search Spaces
    19.2 Search with Incomplete Information
    19.3 Fundamental Robot-Navigation Tasks
    19.4 Planning
    19.5 Bibliographic Notes

Advertisement

advert image