Multiple Approaches to Multiple Agent Problem Solving

Multiple Approaches to Multiple Agent Problem Solving

James Hendler (Chair) Computer Science Department University of Maryland College Park, Md. 207 42, USA

Danny Bobrow Xerox Palo Alto Research Center, USA bobrow.pa~xerox.com

Carl Hewitt MIT, USA hewitt~ai.mit.edu

Pick up any modern operating systems textbook, and you will find sections on distributed processing - the sharing of computation among multiple physical proces­ sors. Familiarity with this literature brings the reader into contact with a jargon filled with the sorts of terms that computer science thrives on: load balancing, net­ work topology, routing strategies, circuit switching, col­ lision detection, job migration, and the like. The dis­ cussion centers on how the bits of data that make up a computation can be physically moved among machines.

If, however, one picks up a book on distributed AI processing 1 , the papers are very different. Instead of solely seeing the technical jargon of computer science, the pages are full of terms borrowed from sociology: negotiation, interaction, contracts, agreement, organiza­ tion, cohesion, social order, and collaboration, to name but a few. This is not to say that serious AI scientists aren't concerned with the issues in the underlying com­ putation, but rather that concentrating on the issues in­ volved in determining how a set of separate agents can give rise to global "intelligent" behavior forces the re­ searcher to go beyond consideration of the computation itself.

It is clear that an understanding of how multiple agents can jointly achieve the solution of complex prob­ lems demands insights into the bases of communication and social organization. For example, consider a group of humans working together to build a house. Such an endeavour requires a number of instances of cooperation and organization, in particular, the communication of in­ formation between participants and the organization of the activity so that specialists in one area (electricians, carpenters, architects) can cooperate with those work­ ing in another, all organized so as to achieve a shared goal. These same features emerge, however, as a swarm of bees work together to establish a hive. The similar- Les Gasser Ecole des Mines, France gasser<Ousc.edu Marvin Minsky MIT, USA minsky~ai.mit.edu ities and differences between these situations brings us to the topic of this panel : what .are some of the differ­ ences in perspective arising from differing views of mul­ tiple agent problem solving? The goal of this panel is to bring together researchers attacking multiagency in dif­ ferent ways and to explore the similarities and differences between their approaches.

1 for example, Readings in Distributed Artificial Intelli­ gence, A. Bond and L. Gasser (eds.), Morgan-Kaufman, 1988.

The panelists represent a set of very different ap­ proaches to understanding multiagent problem solving. These include:

• Collaborative Work: Danny Bobrow has been study­ ing issues involved in enabling a set of humans to work together in the solving of complex problems. His work involves both the observation of humans attacking complex problems across a wide spectrum of activities and an examination of computer sys­ tems aimed at supporting such collaborative work. A large part of this work focuses on the establish­ ment of a "common ground" for the agents involved in the problem solving- no agent can fully describe its languages or its assumptions to another, and yet they must work together with shared assumptions if they are to solve problems without conflict. The­ ories must be developed to explain how actors can come to establish mutually compatible languages, sets of assumptions (e.g., common defaults), and other common bases for interaction given the ab­ sence of global semantics.
• Social Conceptions of Knowledge and Action: Les Gasser's work focuses on "identifying the princi­ ples that underly a fundamentally multi-agent (so­ cial) conception of action and knowledge for Dis­ tributed AI research" (Gasser, 1991). This work in­ vestigates foundational issues in understanding and representing the existence and interaction of multi­ ple agents. Important issues include how to inte­ grate the multiple perspectives arising among dif­ ferent participants, how to integrate the situated

information arising from an individual's particular problem-solving context into the group's more gen­ eral knowledge, and how to understand the relation­ ships between the autonomy of an individual agent and an externally imposed social order.

• Open Information Systems Semantics: Carl Hewitt's work focuses on the building of large scale open information systems (OIS), those "which are always subject to unanticipated outcomes in their operation and which can receive new information from outside themselves at any time." One major aspect of this work is the development of a seman­ tics for such systems. The work involves the devel­ opment of a framework in which concepts such as commitment, cooperation, negotiation, conflict, and distributed problem solving can be made rigorous. In addition, his work raises the question of how the important AI concept of deduction is changed when it is viewed in a multiagent framework.
• Abstraction and Reaction: James Hendler has been investigating planning systems which can react to dynamic change in the world. His system is based on the use of a number of asynchronously processing "monitors" which observe conditions in the world and report their observations to effectors and to other monitors. The monitors, arranged in an ab­ straction hierarchy, thus form a distributed network of cooperating entities, in essence a social order is imposed on a network of agents with very limited autonomy. One of the key questions under consid­ eration is how this sort of multiagency can achieve complex problem solving tasks.
• The Society of Mind: Marvin Minsky's work looks at multiagent problem solving from a very differ­ ent perspective. In his model "mind" (or thought) arises from the interaction of a myriad of simple agents, none of which by themselves can be charac­ terized as having thoughts. He raises questions as to how these agents function, how they are embodied, how they communicate, what happens when they "disagree," how they are differentiated, and, most importantly of all, how such a group of agents can have a competence far beyond that of any of the single agents.

The panelists will address basic questions as to how their different perspectives on the nature of the agents, the means of communication, and the social organiza­ tion of agents affect their views of multiagent problem solving. Issues to be addressed include:

1. What implications result from the differing views of the "granularity" of agents (from individual humans through mindless agents)?
2. What are the tradeoffs between autonomy and order in the different models?
3. What does each approach have to say about the basic nature of multi-agent communication?
4. In each model, what information does an agent need to know about itself? About others?
5. How does each account for the arising of globally desirable behavior from interactions of between in­ dependent individual agents?