Browse Books

Reviewer: Susan Bridges

The title of this book does not adequately describe the scope and depth of the material included. The book and the accompanying computer program listings provide a detailed presentation and analysis of artificial intelligence problem-solving techniques, with emphasis on pattern-directed inference systems, truth maintenance systems (TMSs), and constraint languages. It will be an invaluable resource for artificial intelligence programmers and others who want to learn more about truth maintenance systems and the wide variety of problems to which they may be applied. The authors are pioneers in truth maintenance system research and have designed this book to provide a much-needed synthesis of ideas that is difficult to glean from the literature. The goal of the book, as stated by the authors, is “to teach the reader how to design and build computer problem solvers.” In contrast to other books that describe LISP and AI programming, the authors assume a thorough knowledge of Common Lisp, focus on techniques for building reasoning systems (with particular emphasis on truth maintenance systems), and show how to build programs that exhibit the critical features of the techniques. They present a detailed analysis of the types of problems for which each technique is suited, discuss the limitations of each technique, and analyze the tradeoffs in terms of “efficiency, coherence, flexibility, additivity, and explicitness” that one must consider as the techniques become more complex. The authors state that “the book is intended for two audiences. First, it is designed to be used as a textbook for a graduate (or advanced undergraduate) course in AI programming.… Second, it is designed to be useful for self-study and industrial training for those with other backgrounds who wish to master AI technology.” Readers whose goal is to gain a high-level overview of the problem-solving approaches described in the book can read approximately the first half of each chapter (after the first three). For a more in-depth understanding of the material, it is necessary to read and use the programs that are developed to illustrate all the techniques. The program listings are available as a separate volume, Building problem solvers: listings , or may be obtained via anonymous ftp or World Wide Web. Chapters 1 and 2 introduce the purpose of the book, its organization, and the authors' approach in presenting the material. In each of the remaining chapters, the authors describe a problem-solving technique and then present a careful description of the design decisions that must be made when implementing the technique. Each chapter builds on the previous material by pointing out the limitations of the techniques that have already been described, showing how another technique can be used to address these limitations, and then illustrating the types of problems that can be addressed by building a problem solver that uses the new technique. Chapter 3 briefly reviews state space search and shows how to design modular code to implement a variety of searches. Chapters 4 and 5 describe a specific form of pattern-directed inference system that serves as a starting platform for the problem-solving techniques described in the book. The potential of this type of system is illustrated by developing a powerful natural deduction system for propositional logic. Chapter 6 introduces the basic concepts of truth maintenance systems and classifies them as “justification-based, logic-based, and assumption-based systems.” The next eight chapters explore the implications of these types of systems, “including how to interface truth maintenance systems to various inference engines, and how to use them effectively as part of a larger problem-solving system.” Chapters 7 and 8 describe the basics of justification-based TMSs and illustrate how they can be used to support dependency-directed search and explanation production. Chapters 9, 10, 11, and 13 discuss logic-based TMSs and their application to Boolean constraint propagation and contradiction handling. Chapters 12 and 14 explore assumption-based TMSs. The last portion of the book shifts from the pattern-directed inference model to the use of constraint languages. The characteristics of constraint languages and the justification of their use are presented in chapter 15. Chapters 16 through 18 explore the basic ideas of constraint suspension, illustrate how constraint languages can be combined with an assumption-based TMS, apply constraint languages to diagnosis problems, and describe a constraint language that supports symbolic relaxation. In chapter 19, the authors present their appraisal of the most important research frontiers in the design of reasoning systems. The book appears lengthy due to the inclusion of so much code, but it is well written and easy to read. The illustrations are particularly well designed. The careful development of ideas makes this a book that should be read from beginning to end. It is not an encyclopedia of techniques, but instead provides the fundamental ideas needed in order to apply truth-maintenance techniques to a variety of problems. This book will give the artificial intelligence community access to a toolkit of techniques whose use has been largely restricted to a few elaborate commercial products and to the laboratories where the original research was done. The careful synthesis of ideas from several different research threads and discussion of the wide applicability of the techniques should encourage the incorporation of these techniques into other problem-solving systems. A section titled “Backpointers” included at the end of most chapters briefly discusses the evolution of the techniques, presents alternative techniques, and supplies pointers to the relevant literature. This material, along with the extensive reference list, should help improve access to the literature. This volume will also be a valuable AI programming textbook. The clear discussion of design decisions in the development of the programs makes this book an excellent way to introduce students trained in top-down design to the bottom-up approach for exploratory development of programs that is critical to successful artificial intelligence research. Thought-provoking exercises of graduated difficulty are included at the end of each chapter.