The stated purpose of this book is to offer a comprehensive introduction to the field of multiagent systems. It is meant to be a textbook for use in graduate or advanced undergraduate classes. I was lucky enough to be able to use a preprint version when teaching a graduate class on multiagent systems and distributed AI last semester. It was the only textbook we used, along with a few selected papers. Many of the homeworks included problems from the book. From this experience I was able to get an understanding of the students' opinions of the book and its viability as a textbook for a graduate class.
Each chapter in this volume is written by a different author. Much care was taken in ensuring that the chapters followed a logical flow and built on the previous chapters' material. This effort is often successful, but not always. For example, a notation for talking about agents is introduced in the first chapter. This notation is sometimes referred to in later chapters but is not as integrated into the text as it could have been. On the other hand, the overall flow of the book is very agreeable. The first chapters define the basic concepts and lay out the central ideas, which the rest of the book expands upon.
The book comprises thirteen chapters. The first eight describe the different aspects of multiagent systems. Chapter nine is titled ``Industrial and Practical Applications of DAI'', written by H. Van Dyke Parunak, and is a very good summary of the state of the art in applying multiagent systems to industry. The rest of the chapters deal with related themes such as ``Groupware and Computer Supported Cooperative Work'', ``Distributed Models for Decision Support'', ``Concurrent Programming for DAI'', and ``Distributed Control Algorithms for AI''. I found that the first eight chapters contained more than enough material for a one semester course. I will examine each one of those chapters in detail.
The first chapter is titled ``Intelligent Agents'' and was written by Michael Wooldridge. It defines the concept of ``agent'' as used in the book. It also introduces a notation for describing agents, including their behavior and their environment. This notation is used to illustrate the differences between purely reactive agents, agents that separate perception and action, and agents with state. Finally, the last section describes some common agent architectures: logic based, reactive, belief-desire-intention, and layered. The chapter concludes with a brief introduction to agent-oriented programming (as introduced by Yoav Shoham) and the concurrent MetateM language developed by Fisher.
This chapter provides a solid introduction to the concepts of agent, and agent architecture. The high level notation for describing agents and their environment is very useful for formally describing the differences between the many agent architectures. The section on implemented agent architectures makes it clear that these are not just just theories, but that these ideas have been implemented into working systems. The chapter also includes a discussion of the differences between agents and objects, a question that is certainly on the mind of many readers new to the field.
The second chapter, titled ``Multiagent Systems and Societies of Agents'' and written by Michael N. Huhns and Larry M. Stephens, is also an introductory chapter. Its focus moves away from individual agents and into multiagent systems. The chapter covers agent communications and agent interaction protocols. An introduction to the study of agent communications is given, followed by brief overviews of speech acts, KQML, KIF, and ontologies. Interaction protocols are defined as a series of communication acts meant to achieve some form of coordination between agents. Coordination is then divided into cooperation and competition. Cooperation protocols are those where the agents share a common goal. The chapter discusses the typical divide-and-conquer approach, as well as devoting a section to the contract net protocol and another one to blackboard systems. The next section explains how competition is resolved through the use of negotiation protocols such as multiagent belief maintenance and market mechanisms, each one of which is described in detail. The chapter concludes with a mention of societies of agents and social commitments.
This chapter lays the foundation for the rest of the book. Many, if not all, of the ideas and techniques introduced in it will be expanded and instantiated by techniques described in later chapters. The chapter provides a solid framework for a the rest of the book. However, after finishing the book and rereading this chapter I felt that it should have been divided into two: one chapter serving as the framework for the rest of the book, and another chapter detailing the specifics of agent communication languages. For example, this chapter is the only place where KQML is introduced. My students found that there was not enough information there to get a working knowledge of KQML. We addressed this problem by reading some papers on the topic but it would have been useful to have a more detailed chapter on agent communications.
The third chapter is titled ``Distributed Problem Solving and Planning'', written by Edmund H. Durfee. The chapter starts by introducing a couple of example problems. This use of concrete examples, also evident in other chapters, really helped the students get a better understanding of why the concepts might be important. The first section covers task sharing in heterogeneous systems, in distributed sensor networks, and the task sharing of interdependent tasks. The next section deals with result sharing. It covers functionally accurate cooperation, negotiated search, distributed constrained heuristic search, organizational structuring, communication strategies, and task structures. The final sections deal with distributed planning and execution, which are covered in detail.
The chapter does a very good job at summarizing the important research in this area of distributed problem solving. It is very useful to have a concise introduction to such a wide and mature area of research.
The chapter often focuses on distributed AI planning. This requires the reader to have a firm understanding of traditional AI planning. While in the past AI planning was central to any introductory AI class, these days it is only one of the many topics the students must learn, if they learn it at all. I felt that a quick review of AI planning, perhaps with some example problems, would have helped the students' understanding of the later parts of this chapter.
The fourth chapter is titled ``Search Algorithms for Agents'', written by Makoto Yokoo and Toru Ishida. It deals with specific algorithms that have been used to solve search problems in multiagent systems. The first section introduces the constraint satisfaction problem, as exemplified by the N-queens problem. The algorithms provided for solving this problem are the filtering algorithm, the hyper-resolution-based consistency algorithm, asynchronous backtracking, and asynchronous weak-commitment search. The chapter provides pseudo-code for each one of them and explains how they can be implemented using multiple agents. Next, the chapter presents the path-finding problem. The solution algorithms for this problem are: asynchronous dynamic programming, learning real-time A*, real-time A*, moving target search, and real-time bidirectional search. Finally, the last section covers two-player games and minimax with alpha-beta pruning.
This chapter was one of the most popular with the students because it presented concrete algorithms and toy problems that they could easily understand and implement. The N-queens and moving-target problems were especially entertaining and illustrative of some of the challenges that arise when building multiagent systems. The pseudo-code provided was fairly easy for the students to translate into working code. I did, however, feel that the last section on two-player games was out of place. It is not clear how relevant two player games are to multiagent systems. Also, most of the students were already familiar with minimax from the prerequisite AI class.
The fifth chapter is titled ``Distributed Rational Decision Making'', written by Tuomas W. Sandholm, and deals with negotiations among self-interested agents who might have different goals. The chapter starts with a section on different evaluation criteria, such as social welfare, pareto efficiency, individual rationality, stability, computational efficiency, and communication efficiency. The next sections introduce various methods for handling negotiations. The methods discussed are voting, auctions, bargaining, market mechanisms, contract nets, and coalition formation. Each one of these sections discusses the advantages and problems associated with the particular method, and introduces a few sample protocols. For example, the section on auctions first defines the various types of auctions (i.e., first-price vs. second-price, open-cry vs. sealed-bid, etc.) and discusses the possible drawbacks of each one, such as bidder collusion and lying auctioneers.
This chapter introduces the reader to a lot of relevant material from Economics, utility theory, and game theory. While the material is certainly relevant, I often felt that the book made undue assumptions about the reader's familiarity with economic and utility theory. I also felt that some of the material was too advanced for an introductory text. For example, in the section on voting the book gives a proof of the Gibbard-Satterwthwaite impossibility theorem, as well as an algorithm using the Clarke Tax for circumventing the theorem, as long as the agents have quasilinear preferences. These are complex concepts whose relevance to the design of multiagent systems is arguably only tangential. A discussion of how and when the algorithm might be used in a system would seem more appropriate for an introductory text.
The material in this chapter is, by its nature, mathematically dense. The chapter makes a valiant effort at trying to make some of the more complex ideas appeal to the reader's intuition. Still, I would have appreciated the addition of simple examples illustrating an application of the ideas within each section. One such toy problem is given as part of the exercises at the end of the chapter. I found that the students had a lot of trouble mapping the theory in the chapter to the problem but, once I had made this mapping for them, they were able to better understand both the problem and the theory.
Chapter six is titled ``Learning in Multiagent Systems'' and was written by Sandip Sen and Gerhard Weiss. It starts with a characterization of the different types of learning, detailing the features that distinguish them. The section also reviews the credit-assignment problem from the context of multiagent systems. The next section introduces reinforcement learning, both for individual agents and within societies of learning agents. From these model-free learners we move to agents learning about and from other agents. This section presents methods for agents to build models of other agents and discusses the utility of that approach for achieving coordination. The last section tackles the relationship between learning and communication-how learning can reduce the need for communication and improve the quality of the communication.
This chapter is a good introduction to the topic of learning. I was pleased to see that the authors included a basic description of reinforcement learning in the single-agent domain before expanding it to multiple agents. This helped many of the students. The chapter illustrates some of the sections with sample problems such as the game of Connect-Four (for opponent modeling) and the pursuit problem (for learning and communications). However, I still felt that a few of the equations and algorithms presented lacked enough detail for a student who is not familiar with the corresponding literature to use them for the implementation of toy systems. Like the previous chapter, this chapter also requires the reader interested in a deep understanding of the material to be familiar with a wide body of literature, this time in machine learning. Readers with no machine learning background will still get a general idea of the problems that arise in multiagent learning and an intuition into the types of solutions available.
Chapter seven is titled ``Computational Organization Theory'' (COT) and was written by Kathleen M. Carley and Les Gasser. It starts by defining how COT ``uses mathematical and computational methods to study both humans and automated organizations as computational entities'' and contrasts several modeling approaches. It then describes some useful concepts for modeling organizations, such as agents, organizational design, tasks, and technology. There is then a short section on the dynamics of organizations followed by a section describing the methodological issues that arise in COT, which include the use of virtual experiments, the problem of validation and verification, and the use of computational frameworks.
We found this chapter very confusing. Part of the blame lies with me since I was not familiar with some of the literature referenced, but I believe the chapter presumes too much familiarity with COT literature. In fact, parts of it read like a critical review-comparing the pros and cons of a dozen COT models without ever explaining the details of these models. The models mentioned, but not explained, include the Garbage Can model, Plural-Soar, ACTION, ORGAHEAD, TAEMS, Sugarscape, and others. The chapter also lacked concrete example applications that the reader could use for grounding the ideas presented in the chapter. Finally, while there were several mentions of the computational aspects of COT, there were no equations or algorithms for us to test. In a class full of computer science and engineering students, a chapter without algorithms or equations leads to confusion and doubts about the usefulness of the material. To help this situation, I scheduled a class on the computational aspects of the Garbage Can model, TAEMS, and Sugarscape. I believe the use of these concrete examples leads the students to a better appreciation of COT.
The eighth chapter was the last one we covered. It is titled ``Formal Methods in DAI: Logic-Based Representation and Reasoning'' and was written by Munindar P. Singh, Anand S. Rao, and Michael P. Georgeff. This is a long chapter and we were only able to cover the first few sections. The chapter starts with a comprehensive introduction to logic. It then introduces cognitive primitives such as beliefs, desires and goals. The next section uses this logical framework to give a detailed introduction to BDI architectures. It is followed by sections on coordination, communication and social primitives, all using the same logic framework. Finally, the last section gives brief overviews of many of the available agent architectures and tools that are based on logic principles, such as PRS, dMARS, COSY, AGENT0, and ARTIMIS.
This is another chapter that makes a lot of demands on the reader's background. In this case the reader is best served if he is acquainted with propositional, predicate, modal, deontic, dynamic, and temporal logics. I do not mean to imply that one needs a deep understanding of all these logics, but a casual acquaintance is very helpful. The chapter's comprehensive introduction does serve as a quick refresher course, presenting all the concepts that will be used later in the chapter. However, it would be foolish to believe that a student with no previous background in logic will be able to read this section and learn all he needs to fully understand the logic-based architectures presented. The challenge lies in the time needed to fully digest the logic theorems, which are so quickly presented in the introductory section.
To summarize, the challenge in teaching a course in multiagent systems lies in the fact that the field brings together research from many different fields such as AI, Economics, game theory, computational organizational theory, machine learning, and logic. Each one of these fields has its own set of literature, algorithms, and theorems that the reader needs to understand. While we can expect that some students will be familiar with one or two of these areas, it is extremely unlikely that all the students will be versed in all the areas. Therefore, an instructor must choose between a shallow approach where each topic is simply introduced, and a deep approach where only a few topics are studied but to greater depth. I chose to use the former approach in the hopes of giving the students a wide view of the field, accompanied by a final project where the students could pursue their favorite topic to a greater depth. Others might choose a different approach.
In general, I found that this book provided an excellent framework on which to base a multiagent systems course, perhaps supplemented with a few introductory readings on those areas the students have had little or no exposure. The book is very thorough, covering all the different aspects of multiagent systems. The problems at the end of each chapter serve as good homework assignments and project ideas. The book is a successful attempt at bringing all the various branches of multiagent systems together under one tome. This effort is especially noteworthy given the relative immaturity of multiagent systems research.