Multi-Agent Systems

(a subtopic of Agents)

Contents Good Places to Start Readings Online Related Web Sites Related Pages More Readings News Feed

The characteristics of MASs are that (1) each agent has incomplete information or capabilities for solving the problem and, thus, has a limited viewpoint; (2) there is no system global control; (3) data are decentralized; and (4) computation is asynchronous. - from MultiAgent Systems, by Katia Sycara

The study of multiagent systems (MAS) focuses on systems in which many intelligent agents interact with each other. The agents are considered to be autonomous entities, such as software programs or robots. Their interactions can be either cooperative or selfish. That is, the agents can share a common goal (e.g. an ant colony), or they can pursue their own interests (as in the free market economy).

MAS researchers develop communications languages, interaction protocols, and agent architectures that facilitate the development of multiagent systems. For example, a MAS researcher can tell you how to program each ant in a colony in order to get them all to bring food to the nest in the most efficient manner, or how to set up rules so that a group of selfish agents will work together to accomplish a given task. MAS researchers draw on ideas from many disciplines outside of AI, including biology, sociology, economics, organization and management science, complex systems, and philosophy.

---

Good Places to Start

Best-kept secret agent revealed - No longer just the province of specialist sectors, agent-based computing is changing the way systems interact and how they are managed. By Boris Sedacca. ComputerWeekly.com (October 12, 2006). "Agent-based computing has already transformed processes such as automated financial markets trading, logistics, and industrial robotics. Now it is moving into the mainstream commercial sector as more complex systems with many different components are used by a wider range of businesses. Organisations that have successfully implemented agent technologies include DaimlerChrysler, IBM and the Ministry of Defence. So what are agent technologies? In essence, they are autonomous software systems that can decide for themselves what they need to do. Agents are capable of operating in dynamic and open environments and often interact with other agents - including both people and software. 'Agents are a way to manage interactions between different kinds of computational entities, and to get the right kind of behaviour out of large-scale distributed systems,' says Michael Luck of the School of Electronics and Computer Science at the University of Southampton and executive director of the EU-funded AgentLink action co-ordination programme. 'The idea of grid computing is based on large-scale distributed computation in support of what are called virtual organisations. All they need to do is to be able to interact.' ... Luck argues that the growing complexity of the interactions in emerging distributed systems means new dynamic techniques need to be introduced to provide more flexible mediation and management.One of the basic ideas of agent-based computing is that there are multiple agents in the environment which talk to each other, essentially autonomous software systems that can decide for themselves what they need to do.For example, laws, norms, guides for behaviour, even policing and trust between electronic components, can all help in the mediation and management of such computational systems.'We can build these systems, but we have no experience of how to manage such large-scale, open and dynamic systems,' Luck says. 'Management of these systems is concerned with mediating the interactions of components, whether they are supercomputers or groups of low-level factory floor devices like sensors and actuators. In human societies we have developed laws, norms, regulations and systems of policing, but we do not have that in computational systems. We need computational entities that will do what we do in the real world. We need norms and rules of behaviour within systems, so that if agents joining and leaving a system do not comply, there must be some sort of sanction.'"

MultiAgent Systems. By Katia Sycara. AI Magazine 19(2): Summer 1998, 79-92. "Agent-based systems technology has generated lots of excitement in recent years because of its promise as a new paradigm for conceptualizing, designing, and implementing software systems. This promise is particularly attractive for creating software that operates in environments that are distributed and open, such as the internet. Currently, the great majority of agent-based systems consist of a single agent. However, as the technology matures and addresses increasingly complex applications, the need for systems that consist of multiple agents that communicate in a peer-to-peer fashion is becoming apparent. Central to the design and effective operation of such multiagent systems (MASs) are a core set of issues and research questions that have been studied over the years by the distributed AI community. In this article, I present some of the critical notions in MASs and the research work that has addressed them. I organize these notions around the concept of problem-solving coherence, which I believe is one of the most critical overall characteristics that an MAS should exhibit." (Also see the quote from this article at the top of this page.)

Multiagent Systems: An Emerging Subdiscipline of AI. Victor R. Lesser. ACM Computing Surveys 27(3): 340 -342 (1995). [Made available by the author for personal or classroom use.] "As more AI applications are being formulated in terms of spatially, functionally, or temporally distributed processing, multiagent systems (or what was previously called distributed AI) are emerging as an important subdiscipline of AI. ... In general multiagent systems are computational systems in which several semi-autonomous agents interact or work together to perform some set of tasks or satisfy some set of goals."

Standardization of Multi-Agent System Frameworks. By Roberto A. Flores-Mendez. ACM Crossroads 5(4): Summer 1999. "Various definitions from different disciplines have been proposed for the term multi-agent system (MAS). As seen from DAI, a multi-agent system is a loosely coupled network of problem-solver entities that work together to find answers to problems that are beyond the individual capabilities or knowledge of each entity [fn]. More recently, the term multi-agent system has been given a more general meaning, and it is now used for all types of systems composed of multiple autonomous components showing the following characteristics [fn]: * each agent has incomplete capabilities to solve a problem * there is no global system control * data is decentralized * computation is asynchronous."

Multi-agent technology: removing the 'artificial' from AI. By Fran Howarth. IT-Director.com (March 18, 2004). "Agents are small software programs that communicate with each other, acting behaviorally to interact and respond, matching available resources to demand. ... In a multi-agent system, each agent communicates with the network of agents, considering options for matching its capabilities with demand, negotiating on such constraints as quality, price and time, and then making decisions for committing resources to match demand."

Intelligent Agents and Multi-Agents. From ASAP, the Automated Scheduling, Optimisation and Planning Group, School of Computer Science and Information Technology, University of Nottingham. "Agent theory concerns the definition of agents and Multi-agent systems, properties, architectures, communication, cooperation and coordination capabilities. The practical side concerns the agent languages and platforms for programming and experimenting with agents. ... Several researchers have proposed formal definitions for agents and multi-agent systems, we retain the following...."

IEEE Distributed Systems Online: "IEEE DS Online hopes to serve as a springboard for building a stronger distributed systems community and offer researchers, students, educators, application developers, and program managers a forum for sharing ideas and discussing projects. To achieve this goal, the site provides content through two primary avenues: our monthly issue packed with features and our expert-moderated Community pages."

• Distributed Agents home is one of the community topic areas and offers resources such as:
  • About Distributed Agents: "The research areas of multi-agent systems and distributed systems coincide,and form the research area of distributed agent computing. In short, multi-agent systems are often distributed systems, and distributed systems are platforms to support multi-agent systems. ..."
  • Projects
  • Reference Material
  • Resources
  • Tutorials & Courses

To find out what Pandemonium & Demons have to do with MAS, see our Namesakes page.

Readings Online

Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence. Reviewed by Julie A. Adams. AI Magazine 22(2): 105-108 (Summer 2001). " As the title indicates, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence covers the design and development of multiagent and distributed AI systems. The purpose of this book is to provide a comprehensive overview of the field. It is an excellent collection of closely related papers that provides a wonderful introduction to multiagent systems and distributed AI."

AI think, therefore I am. Virtual agents feature - Computerised characters that look, sound, move and seemingly think like real people are emerging from the realms of science fiction into everyday life. Superguide by David Braue. apcmag.com (December 16, 2003). "'We have agents embedded in trucks, excavators and individuals [robots] in order to mine the right material at the right time,' says Hugh Durrant-Whyte, research director at CEAS [Centre of Excellence in Autonomous Systems]. 'We do not approach it at all from a human point of view -- robots are really physical embodiments of agents. They won’t discuss Plato with you, but they can work 24 hours a day and have cooperation and negotiation strategies [to interact with each other].'"

Agents of creation - Artificial "agents" can model complex systems. The Economist (October 9, 2003). "In this context, an agent is a program that acts in a self-interested manner in its dealings with numerous other agents inside a computer. This arrangement can mimic almost any interactive system: a stockmarket; a habitat; even a business supply-chain."

Collaborative Systems: Barbara Grosz's 1994 AAAI Presidential Address. AI Magazine 17(2): Summer 1996, 67-85. "The construction of computer systems that are intelligent, collaborative problem-solving partners is an important goal for both the science of AI and its application. From the scientific perspective, the development of theories and mechanisms to enable building collaborative systems presents exciting research challenges across AI subfields. From the applications perspective, the capability to collaborate with users and other systems is essential if large-scale information systems of the future are to assist users in finding the information they need and solving the problems they have. In this address, it is argued that collaboration must be designed into systems from the start; it cannot be patched on. Key features of collaborative activity are described, the scientific base provided by recent AI research is discussed, and several of the research challenges posed by collaboration are presented. It is further argued that research on, and the development of, collaborative systems should itself be a collaborative endeavor--within AI, across subfields of computer science, and with researchers in other fields."

Planning and Acting Together. By Barbara J. Grosz, Luke Hunsberger, and Sarit Kraus. AI Magazine 20(4): Winter 1999, 23-34. "People often act together with a shared purpose; they collaborate. Collaboration enables them to work more efficiently and to complete activities they could not accomplish individually. An increasing number of computer applications also require collaboration among various systems and people. Thus, a major challenge for AI researchers is to determine how to construct computer systems that are able to act effectively as partners in collaborative activity. Collaborative activity entails participants forming commitments to achieve the goals of the group activity and requires group decision making and group planning procedures. In addition, agents must be committed to supporting the activities of their fellow participants in support of the group activity. Furthermore, when conflicts arise (for example, from resource bounds), participants must weigh their commitments to various group activities against those for individual activities. This article briefly reviews the major features of one model of collaborative planning called SHARED-PLANS (Grosz and Kraus 1999, 1996). It describes several current efforts to develop collaborative planning agents and systems for human-computer communication based on this model. Finally, it discusses empirical research aimed at determining effective commitment strategies in the SHAREDPLANS context."

Tutorial on Intelligent Agents and Multiagent Systems. By Vasant Honavar, Department of Computer Science, Iowa State University.

Dependable Agent Systems. IEEE Intelligent Systems Special Issue (Volume 19, Number 5; September/October 2004). "It is well known that building dependable software systems for dynamic environments is difficult. It is also well known that building large-scale distributed software systems is difficult. The relatively few attempts to combine these two tasks confirm that successfully building large-scale distributed systems with predictable dependability properties is exceptionally difficult. The articles in this special issue of IEEE Intelligent Systems deal with this issue and discuss an emerging and exciting new approach to building these most challenging kinds of systems. " - Abstract: Guest Editors' Introduction

Journal of Artificial Societies and Social Simulation, "an inter-disciplinary journal for the exploration and understanding of social processes by means of computer simulation."

Swarm Behavior - A single ant or bee isn't smart, but their colonies are. The study of swarm intelligence is providing insights that can help humans manage complex systems, from truck routing to military robots. By Peter Miller. National Geographic Magazine (July 2007). "'Ants aren't smart,' [Deborah M.] Gordon says. 'Ant colonies are.' A colony can solve problems unthinkable for individual ants, such as finding the shortest path to the best food source, allocating workers to different tasks, or defending a territory from neighbors. As individuals, ants might be tiny dummies, but as colonies they respond quickly and effectively to their environment. They do it with something called swarm intelligence. ... . It relies instead upon countless interactions between individual ants, each of which is following simple rules of thumb. Scientists describe such a system as self-organizing."

Software agents ask for help. By Kimberly Patch, Technology Research News (September 18/25, 2002). "If you're good at something, people naturally ask your advice about it. Researchers from the University of Porto in Portugal are tapping this learning strategy by programming tiny bits of software, called agents, to ask other agents for help as the group figures out how to control the timing of traffic lights."

On the Backs of Ants - New networks mimic the behavior of insects and bacteria. By Kimberly Patch. Technology Review (March 19, 2003). "Drawing heavily on the chemistry of biology, researchers from Humboldt University in Germany have devised a way for electronic agents to efficiently assemble a network without relying on a central plan."

Multiagent Systems: A Survey from a Machine Learning Perspective. By Peter Stone and Manuela Veloso, Computer Science Department, Carnegie Mellon University. "Distributed Artificial Intelligence (DAI) has existed as a subfield of AI for less than two decades. DAI is concerned with systems that consist of multiple independent entities that interact in a domain. Traditionally, DAI has been divided into two sub-disciplines: Distributed Problem Solving (DPS) focusses on the information management aspects of systems with several branches working together towards a common goal; Multiagent Systems (MAS) deals with behavior management in collections of several independent entities, or agents. This survey of MAS is intended to serve as an introduction to the field and as an organizational framework."

• Multiagent Systems: "The most important reason to use MAS when designing a system is that some domains require it. In particular, if there are different people or organizations with different (possibly conflicting) goals and proprietary information, then a multiagent system is needed to handle their interactions. Even if each organization wants to model its internal affairs with a single system, the organizations will not give authority to any single person to build a system that represents them all: the different organizations will need their own systems that reflect their capabilities and priorities."
• Robotic Soccer: Several multiagent domains have been mentioned throughout the course of this survey, including design, planning, entertainment, games, air-traffic control, air combat, personal assistants, load-balancing, and robotic leg control. In this section a single domain which embodies most multiagent issues is presented.

I Think, Therefore I Am -- Sorta. The belief system of a virtual mind. Quark Soup column by Margaret Wertheim. LA Weekly (July 22 -28, 2005). "Far more than mere cartoons, these virtual people have each been endowed with a virtual mind complete with its own internal 'desires' and 'goals.' Technically known as 'agents,' they are driven by a revolutionary software system known as PsychSim that enables programmers to simulate the cognitive faculties of human minds. Dr. Stacy Marsella, a leading agent researcher and one of the primary architects of PyschSim, declares that agents actually 'think for themselves.' Indeed, the ultimate goal of agent research is to create autonomous self-determining minds capable of a full spectrum of human behavior."

• Check out the PsychSim Multiagent Social Simulation Project.

Related Web Sites

ACE. "Agent-based computational economics (ACE) is the computational study of economies modelled as evolving systems of autonomous interacting agents. ACE is thus a specialization to economics of the basic complex adaptive systems paradigm." Maintained by Leigh Tesfatsion, Department of Economics, Iowa State University. The site offers links to a variety of helpful resources.

The ASSERT group [Agent Systems Research and Technology] at the Blekinge Institute of Technology, School of Engineering "focuses on the theory and application of multi-agent systems. This work includes topics such as coordination mechanisms, agent-based simulation, and models of agent societies and their dynamics."

CASOS. Computational Analysis of Social and Organizational Systems. "Gourps, organizations, and societies are inherently computational and computational multi-agent systems are inherently organizational. Thus, within CASOS we attempt to understand and formally model two distinct but complimentary types of phenomena. The first is the natural or human group, organizational or society, which is universally informatted and continually acquires, manipulates, and produces information (and possibly other material goods) through the joint, and interlocked activities of people and automated information technologies. The second is the artificial computational systems which is generally comprised of multiple distributed agents who can mutually influence, constrain and suppurt each other as they try to manage and manipulate the knowledge, communication and interaction networks in which they are embedded. Computational analysis is used to develop a better understanding of the fundamental priciples of organizing, coordinating, and managing multiple information processing agents (whether they are human, WebBot, or robots) and the fundamental dynamic nature of groups, organizations and societies." - from their Mission Statement

CORO. Collective Robotics Research Group at the Center for Neuromorphic Systems Engineering at the California Institute of Technology. "The use of multiple mobile robots offers significant advantages over the use of single mobile robots: key features are the possibility of distributed sensing, distributed action, task dependent reconfigurability, and the enabling of robustness and system reliability through redundancy. There are several approaches for controlling systems of multiple mobile robots: most of them, rooted in the conventional artificial intelligence paradigm, base on complex robots that build and maintain internal models relevant to the task, and communicate only explicitly with other robots and external agents including humans. In the CORO group, we focus instead on the application of Swarm Intelligence principles, where local interactions among robots and between robots and environment play a crucial role for achieving the required task."

Control of Agent Based Systems. Defense Advanced Research Projects Agency (DARPA), U.S. Department of Defense. Overviews and detailed descriptions of military research projects involving agents.

Distributed Artificial Intelligence links from the Department of Sociology, University of Surrey.

Distributed Systems Group at the ETH Zurich: "The overall research interests of the Distributed Systems Group span the broad fields of models and concepts for distributed computations, ubiquitous computing, Internet applications, programming of parallel and distributed systems, middleware, sensor networks, and privacy and security concepts." Their research topics include:

• Smart Cooperative Objects: "One of the main overarching themes of our research into ubiquitous computing is the vision of smart cooperative objects. Smart objects are equipped with sensing, computation, and communication capabilities and are able to perceive and interact with their environment and with other smart objects."

The Flocking Robots Project at the Artificial Intelligence Laboratory, Department of Information Technology, University of Zurich. "Flocking adresses a variety of important topics in the field of multiagent simulation and collective robotics which include agent interaction, kin recognition, and finally the emergence of collective behavior." And their flocking applet is simply beautiful!

• For related information, also see: Boids

Learning in Multi-Agent Systems: Webliography. By M. V. Nagendra Prasad (University of Massachusetts, Amherst) and Thomas Haynes (University of Tulsa), Links to research sites, projects, conferences, journals and more.

MultiAgent Systems. "This site contains pointers to information about multiagent systems, including both research and industrial references. The front page also has breaking news of some relevance." Maintained by José M. Vidal.

Multi-Agent Systems at The Intelligent Software Agents Group, Robotics Institute, Carnegie Mellon University. Be sure to scroll down their page to their collection of "Applications of Multi-Agent Research."

The Multi-Agent Systems Laboratory at the Department of Computer Science at the University of Massachusetts at Amherst. "[This lab] is concerned with the development and analysis of sophisticated AI problem-solving and control architectures for both single-agent and multiple-agent systems. The laboratory has pioneered work in the development of the blackboard architecture, approximate processing for use in control and real-time AI, and a wide variety of techniques for coordination of multiple agents."

Open Agent Architecture - A framework for integrating a community of heterogeneous software agents in a distributed environment. From SRI's Artificial Intelligence Center. Resources include:

• What is an Agent?
• Agent Architectures as a programming methodology.
• Videos of OAA in action

"The Planning and Activity Management Group in the School of Informatics at the University of Edinburgh is exploring representations and reasoning mechanisms for inter-agent activity support. The agents may be people or computer systems working in a coordinated fashion. The group explores and develops generic approaches by engaging in specific applied studies. Applications include crisis action planning, command and control, space systems, manufacturing, logistics, construction, procedural assistance, help desks, etc."

"The Research Center for Team-Based Agents [School of Information Sciences and Technology, The Pennsylvania State University] aims to develop agents with 'team intelligence', which enables them to support and enhance collaborative activities of teams, which may include both human users and software agents. The center's research will build on the findings and theories about effective human team behaviors and incorporate them into intelligent agent technologies."

The Swarmanoid Project: "a Future and Emerging Technologies (FET-OPEN) project funded by the European Commission. The main scientific objective of this research project is the design, implementation and control of a novel distributed robotic system. The system will be made up of heterogeneous, dynamically connected, small autonomous robots. Collectively, these robots will form what we call a swarmanoid. The swarmanoid that we intend to build will be comprised of numerous (about 60) autonomous robots of three types: eye-bots, handbots, and foot-bots. The Swarmanoid project is the successor project to the Swarm-bots project, and will build on the results obtained during the Swarm-bots project."

The Teamcore Research Group, part of the Department of Computer Science at the University of Southern California, "is focused on research on multi-agent systems, where multiple agents (including software agents, robots and people) may interact. Our work has typically focused on situations where such interactions are collaborative, often in form of agent teams." Be sure to check out their many exciting projects as well as their demos and software collection.

Related Pages

• Artificial Life
• Nature of Intelligence
• Robots
• Social Science
• Web-Searching Agents

More Readings

Durfee, Edmund H. 1992. What Your Computer Really Needs to Know You Learned in Kindergarten. In Proceedings of the 10th National Conference on Artificial Intelligence, 858-864. San Jose, CA: AAAI Press.

Ferber, Jacques. 1998. Multi-Agent Systems: Towards a Collective Intelligence. Reading, MA: Addison-Wesley.

Lesser, Victor., editor. 1995. Proceedings of the First International Conference on Multiagent Systems. Menlo Park, CA: AAAI Press.

Tokoro, Mario, editor. 1996. Proceedings of the Second International Conference on Multiagent Systems. Menlo Park, CA: AAAI Press. Topics cover coordination, distributed planning, implementing multi-agent systems, market-oriented approaches, multiagent applications, multiagent learning, multiagent search, mutual knowledge, negotiation, organizational aspects, real-world agents, situated agents, sociability, and teams of agents.