DAI-List Digest Monday, 12 August 1991 Issue Number 46 Topics: Competition vs. Cooperation Discussion on CDPS, MA, etc. Please send submissions to DAI-List@mcc.com. Send other requests, such as changes in your e-mail address, to DAI-List-Request@mcc.com. ------------------------------------------------------------------------ From: Jeff Rosenschein Date: Mon, 12 Aug 91 11:27:11 +0300 Subject: related paper Steve Marsh wrote on DAI-List Digest #45: "I'm interested in the idea that competition amongst individuals may sometimes be more productive than cooperation, and in which circumstances." This happens to be a question that very much interests me. At the MAAMAW-91 Workshop in Germany last week (that's "Modeling Autonomous Agents in a Multi-Agent World") I presented a paper co-authored with Ran Levy that touched on that topic. We conducted experiments on the Pursuit Problem (4 blue agents surrounding a randomly moving red one), where the blue agents are individually motivated, and where they work together to capture their prey based on a selfish game-theoretic view of the world (sort of like wolves working together to capture their prey because of selfish motivations). The mechanism that we presented is quite general, though how effective it is obviously depends on the specific utility function or functions that the agents have (similar, I think, to the way a one-agent heuristic search strategy is a general framework, whose effectiveness depends on the specific heuristic). We ran some experiments using a particular utility function (including some experiments on the Stephens-Merx set of Pursuit Problem scenarios), and proved some results about our particular function that allow it to be used very efficiently in analyzing the game matrix. Our results for self-motivated agents were considerably better than Stephens and Merx's for "autonomous" agents, though our agents (using the specific utility function we gave them) couldn't always capture the red agent, even when other Stephens-Merx approaches to coordination could. My conjecture is that this is purely an artifact of our utility function, and that when we come up with a better one, our capture rate will improve. On the plus side, our self-motivated agents needed almost no communication to corner their prey (communicating only to resolve symmetrical equilibrium points; other communication was obviously supplanted by local computation), and tended to converge more rapidly than other Stephens-Merx approaches. Actually, their speed of convergence may have occasionally hindered a solution (a red agent trapped on three sides will scamper away in its only free direction). An improved utility function for this problem might slow the agents down, at least when they're very near the prey, so that further-away agents can catch up. The actual technique is to consider a utility function for any arbitrary coalition's action, consider how the coalition's payoff is divided among members (we use the Shapley value to divide payoffs among coalition members), then allow each agent to selfish join whatever coalition he wants (including, of course, the coalition where he is the only member). Perhaps this mixing of selfish and cooperative coalition formation is a pertinent example of Ed Durfee's message about the DPS-MA spectrum: "Most interesting problems have agents that are partially adversarial and partially cooperative all at the same time." I hope to expand the experiments into more complicated scenarios (e.g., 6 blue agents deciding which of several red agents to capture), and consider other utility functions and how they drive solutions. The approach of considering how global behavior emerges from local strategies has a parallel in other current DAI work, including the ecosystem problem solving model of Ferber (also reported on at MAAMAW-91); there, agents are designed using explicit local strategies of behavior, while our agents are designed to be locally evaluative. --Jeff Rosenschein ------------------------------------------------------------------------ From: Les Gasser Subject: MA and DPS Date: Mon, 29 Jul 91 13:14:54 +0200 > From: Farhad Heidari > Subject: MultiAgent Systems & Coop. Distr. Problem Solving > > PLEASE HELP ME CLARIFY THE CONCEPTUAL DIFFERNCE BETWEEN (MA) AND > (CDPS). > > Referring to papers on Distributed Artificial Intelligence > by Edmund H. Durfee, Victor R. Lesser, and Daniel D. Corkill, > CDPS is defined.... > > On the other hand, A.H. Bond and L. Gasser divide the world of DAI > into two primary arenas: Distibuted Problem Solving (DPS) and > MultiAgent systems (MA)..... > > Now is there any difference between these two concepts? If yes, > please clarify. Briefly, in my view, there is a very significant difference. First, a methodological observation: the reason for making the distinction we made was to 1) categorize existing research, and 2) categorize sets of research problems---problems OF DAI and problems FOR DAI---some of which have not been adequately addressed to date. Note that I said we were trying to categorize research PROBLEMS, not DAI SYSTEMS. The most basic difference, then, between problems that fall in the DPS category and those that fall in the MAS category is that DPS-like problems presume and rely upon (some form of) global perspective, even for understanding and stating the problem. For example, the coordination problems addressed by the DVMT research (in novel and interesting ways) are stated and addressed using a conceptual vocabulary that is common to all agents. Solutions are posed in terms of, e.g., communications languages and structures that assume common interagent semantics (e.g. PGPs). If one agent describes a goal or a point in the sensed region, the others know what it is talking about. There is an important class of problem for which these assumptions do not hold---this is one of the the primary reasons we established the class of MAS problems-- to recognize that there are some situations in which common semantics, common conceptual vocabularies, etc. are part of the problem, not givens. In most cases what we were classifying as DPS problems (e.g. the interpretation problems addressed by the DVMT, or the well-known pursuit problem) also involve some overall global "goal" - i.e. the whole system is working toward a global picture of the sensed region or a global "captured" state. Each agent may be doing its separate part, but that separate part only "makes sense" in terms of the global picture. To see it another way, in these problems there is a global criterion for progress or for success. This is not necessarily the case in MAS problems, in which agents may be coordinating their activities for entirely different reasons. Personally, from the standpoint of building scientific, descriptive, and explanatory theories of multiagent activity, I don't think we need the concepts "global" or "shared" or "common" to explain multiagent activity in either case - I think it's perfectly possible to coordinate without any shared anything. In fact I think some pretty grand problems emerge when we try seriously to explain how viewpoints CAN be shared (see, e.g. my paper in AIJ Jan '91 or forthcoming MAAMAW paper). But the fact is, these days many problems are stated and understood in these terms, and many solutions are constructed under these assumptions; these we classifieded as DPS problems. And of course, like many classifications, there is more a continuum than a discrete separation. -- Les ------------------------------------------------------------------------ From: Les Gasser Subject: MA and DPS Date: Mon, 29 Jul 91 17:36:54 +0200 Brief clarification to my previous message: Farhad had actually asked about the difference between the terms CDPS and MA. It's not so important to me whether the term used is "CDPS" or "MA" - I believe the more important difference is the one I tried to articulate. Aesthetically, for me, the term "Cooperative Distributed Problem Solving" gives the sense that there is some problem solving which has been "distributed" - that is, "distributed" is an adjective used to describe problem-solving, and the problem (and its solving) came first. The term "Multi-Agent Systems" puts the emphasis on the multiplicity, not on the problem-solving (and that's why I like it). Finally, the use of the term "DAI" for the whole research area is, I think, an unfortunately limiting one that has stuck for historical reasons. ("Decentralized AI" has pretty much the same problems.) Anyhow, in the end the important thing is not so much what you call these things as what you do with them. -- Les LAFORIA Universite de Paris VI 4 Place Jussieu 75252 Paris CEDEX 05 France Phone: 33 1 44 27 70 01 Fax: 33 1 44 27 70 00 gasser@laforia.ibp.fr gasser@usc.edu ------------------------------------------------------------------------ From: "I.Shah" Date: Tue, 6 Aug 91 16:32:59 BST Subject: DPS, CDPS, and MA I am not sure whether this is an issue but it is not clear to me: where do the goals come from in these systems? Can one say that in DPS systems the goals are set up by task decomposition (e.g based on the capabilities of nodes or agents) while as in MA systems agents set up their own goals depending on their "self interest"? I.Shah. ------------------------------------------------------------------------ Date: Thu, 8 Aug 91 16:05 CDT From: Ed Durfee Subject: Re: DPS, CDPS, and MA I think that trying to discriminate between DPS and MA by considering the source of goals will be problematic, because goals occur at so many different levels and in so many different forms. In the most abstract sense, agents' goals can be designed in (DVMT nodes WANT to track vehicles) or can be an artifact of architecture/evolution (people WANT to seek pleasure and avoid pain). Operationalizing these goals in specific circumstances lead to more concrete goals (node1 wants to track vehicle1 in region1, John wants to pull off the highway to find a restaurant before he gets too hungry). Now, the question arises, what does it mean for an agent to set up its own goals given that, at an abstract level, its goals were "forced" upon it (by nature or design)? For example, if I design an organizational structure in the DVMT such that different nodes have different interest areas (thus, they have different self interests because they will prefer some results/activities to others), and then I start giving the nodes data, and they share partial results and converge on solutions (because that is what the organizational structure dictated as being what they value), then is this a DPS or MA system? From the view of the designer, it looks like DPS by your definition (task was decomposed based on agent abilities); from the view of the agents, each is only doing what it is interested in, and the overall success of the network is immaterial to an individual agent -- it is MA. I guess I think that, at some level, all agents are self interested. Sticking to my previous statements, what separates DPS from MA is that DPS agents need each other for each to satisfy his/her/its self interests. - Ed