This book is intended to serve as a comprehensive introduction to artificial intelligence (AI) heuristic state space search. It includes many developments that are not yet covered by any textbook, including pattern databases, symbolic search, search with efficient use of external memory, and parallel processing units. Thus, the book is suitable for readers who do not yet have a background in search and are looking for a good introduction to the field, as well as for readers who do have some background in search and are interested in reading up on the latest developments in the field. It serves as a unique reference to the large body of research and provides many pointers to the literature.

The book is intended to strike a balance between search algorithms and their theoretical analysis on one hand, and their efficient implementation and application to important real-world problems on the other hand. It is intended to cover the field comprehensively, from well-known basic results to recent proposals that push the state of the art.

The book supplements broad textbooks on AI and, more importantly, serves as a primary textbook for more advanced AI classes on search. It discusses search applications in a variety of subfields of AI, including puzzle solving, game playing, constraint satisfaction, action planning, and robotics. However, the book is also suitable for self-study and provides a valuable source of information for graduate students, researchers, and practitioners in a variety of decision sciences (including AI and operations research), as well as application programmers who need to use search algorithms to solve their problems.

The book is relatively self-contained. In particular, we do not require the readers to have any prior knowledge of AI. Instead, we assume the reader to have basic knowledge of algorithms, data structures, and calculus. It uses examples to introduce the search algorithms and motivate their properties. The text often contains proofs of the correctness and other properties of search algorithms to give it formal rigor and introduces the readers to important proof techniques. (This aspect of the book is especially important for graduate students and researchers.)

The presented material also teaches how to implement search algorithms. It includes pseudo code to avoid the typical problems that practitioners (or students) have with converting ideas into running programs if textbooks describe algorithms only verbally or do not explicitly discuss implementation details. The book discusses how to implement the data structures needed to run the search algorithms, from very simple but somewhat slow implementations to highly sophisticated and extremely fast implementations. Moreover, the book includes exercises that can be used either as homework exercises in classes or as self-tests.

This text gives the readers a feeling for when to use which search algorithm. For example, it discusses the time and space complexities of search algorithms and which properties make some of them well suited for a given search problem and others less suited for the same search problem. Finally, it provides case studies that show how search algorithms can be applied to a large variety of problems from different application areas. Thus, it contains cookbook solutions for a variety of important real-world problems, demonstrates the impact that search techniques already have in practice, and gives the reader a feeling for the amount of work that is needed to adapt search algorithms to specific applications. (This aspect of the book is especially important for practitioners.)

The book is divided into five main parts: Heuristic Search Primer (I), Heuristic Search Under Memory Constraints (II), Heuristic Search Under Time Constraints (III), Heuristic Search Variants (IV), and Heuristic Search Applications (V). Part I introduces basic problems, algorithms, and heuristics. Parts II and III address refined solutions in the context of existing resource limitations in time and space. Part II considers memory-limited, symbolic, and disk-based search, and Part III addresses parallel search, various pruning techniques, and move-committing search strategies. Part IV attacks related search methods that apply more general notions of search heuristics, including game evaluations, constraint satisfaction, as well as local search approaches. Part V is dedicated to different real-world application areas and shows how the concepts of the first four parts have been turned into rather complex search engines. We address application areas traditionally closer to AI, such as action planning and robotics, and other areas not originating in AI, such as vehicle navigation, computational biology, and automated system verification. You will notice some sections preceded by an asterisk; the asterisks in front of chapter and section headings indicate advanced material that can be skipped in a first reading of the book.