LIMITED OFFER
Save 50% on book bundles
Immediately download your ebook while waiting for your print delivery. No promo code needed.
Heuristic Search
Theory and Applications
- 1st Edition - May 31, 2011
- Authors: Stefan Edelkamp, Stefan Schroedl
- Language: English
- Hardback ISBN:9 7 8 - 0 - 1 2 - 3 7 2 5 1 2 - 7
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 9 1 9 7 3 - 7
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… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteSearch 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
Researchers, professors, and graduate students
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
- No. of pages: 712
- Language: English
- Edition: 1
- Published: May 31, 2011
- Imprint: Morgan Kaufmann
- Hardback ISBN: 9780123725127
- eBook ISBN: 9780080919737
SE
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 BremenSS
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.Read Heuristic Search on ScienceDirect