Extending the realm of the social world to include autonomous computer systems has always been an awesome, if not frightening, prospect. However it is now becoming both possible and necessary through advances in the field of Artificial Intelligence (AI). In the past several years, AI techniques have become more and more robust and complex. To mention just one of the many exciting successes, a car recently steered itself more than 95% of the way across the United States using the ALVINN system [60]. By meeting this and other such daunting challenges, AI researchers have earned the right to start examining the implications of multiple autonomous ``agents'' interacting in the real world. In fact, they have rendered this examination indispensable. If there is one self-steering car, there will surely be more. And although each may be able to drive individually, if several autonomous vehicles meet on the highway, we must know how their behaviors interact.
Multiagent Systems (MAS) is the emerging subfield of AI that aims to provide both principles for construction of complex systems involving multiple agents and mechanisms for coordination of independent agents' behaviors. While there is no generally accepted definition of ``agent'' in AI [68], for the purposes of this article, we consider an agent to be an entity with goals, actions, and domain knowledge, situated in an environment. The way it acts is called its ``behavior.'' (This is not intended as a general theory of agency.) Although the ability to consider coordinating behaviors of autonomous agents is a new one, the field is advancing quickly by building upon pre-existing work in the field of Distributed Artificial Intelligence (DAI).
DAI has existed as a subfield of AI for less than two decades. Traditionally, DAI is broken into two sub-disciplines: Distributed Problem Solving (DPS) and MAS [10]. The main topics considered in DPS are information management issues such as task decomposition and solution synthesis. For example, a constraint satisfaction problem can often be decomposed into several not entirely independent subproblems that can be solved on different processors. Then these solutions can be synthesized into a solution of the original problem.
MAS allows the subproblems of a constraint satisfaction problem to be subcontracted to different problem solving agents with their own interests and goals. Furthermore, domains with multiple agents of any type, including autonomous vehicles and even some human agents, are beginning to be studied.
This survey of MAS is intended as an introduction to the field. The reader should come away with an appreciation for the types of systems that are possible to build using MAS as well as a conceptual framework with which to organize the different types of possible systems.
The article is organized as a series of increasingly complex general multiagent scenarios. For each scenario, the issues that arise are described along with a sampling of the techniques that exist to deal with them. The techniques presented are not exhaustive, but they highlight how multiagent systems can be and have been used to build complex systems.
Because of the inherent complexity of MAS, there is much interest in using machine learning techniques to help deal with this complexity [95, 2]. When several different systems exist that could illustrate the same or similar MAS techniques, the systems presented here are biased towards those that use machine learning (ML) approaches. Furthermore, every effort is made to highlight additional opportunities for applying ML to MAS.
Although there are many possible ways to divide MAS, the survey is organized along two main dimensions: agent heterogeneity and amount of communication among agents. Beginning with the simplest multiagent scenario, homogeneous non-communicating agents, the full range of possible multiagent systems, through highly heterogeneous communicating agents, is considered. Centralized, single-agent systems are shown to belong at the complex end of this spectrum. As illustrated in Figure 1, the heterogeneity dimension is varied first, followed by the communication dimension. The result is a steady increase in system complexity. When appropriate, systems with low agent heterogeneity and high inter-agent communication are also mentioned. However by first increasing heterogeneity and then communication, all of the important issues and techniques in MAS are encountered.
For each multiagent scenario presented, a single example domain is presented in an appropriate instantiation for the purpose of illustration. In this extensively-studied domain, the Predator/Prey or ``Pursuit'' domain [9], many MAS issues arise. Nevertheless, it is a ``toy'' domain. At the end of the article, a much more complex domain--robotic soccer--is presented in order to illustrate the full power of MAS.
The article is organized as follows. Section 2 introduces the field of MAS, listing several of its strong points and presenting a taxonomy. The body of the article, Sections 3 - 6, presents the various multiagent scenarios, illustrates them using the pursuit domain, and describes existing work in the field. A domain that facilitates the study of most multiagent issues is advocated as a testbed in Section 7. Section 8 concludes.