DAI-List Digest Friday, 16 August 1991 Issue Number 48 Topics: Response to comments on MA, DPS When does DPS turn into MA, or MA turn into DPS? Classifying Werkman's DFI System 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. ------------------------------------------------------------------------ Date: Thu, 15 Aug 91 11:57:49 -0400 From: durfee@caen.engin.umich.edu (Ed Durfee) Subject: Response to comments on MA, DPS I'm very much enjoying the use of DAI-LIST for discussion to try to develop something approaching a "common" understanding of terms such as DPS and MA. To keep the discussion going, I thought I'd comment on some of the interesting thoughts shared by Les and Jeff. Les says: >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. An interesting distinction, but I have trouble comprehending it, possibly because it seems there are a few different ideas being thrown together. The initial idea - that "DPS-like problems presume and rely upon (some form of) global perspective, even for understanding and stating the problem" certainly captures the distinction between problems that inherently exceed the bounds of separate individuals (requiring DPS) and problems that don't. This reflects what I see (my previous message) as a reason to distinguish between problems like distributed vehicle monitoring, and other, more "MAS" problems like those studied by Jeff Rosenschien where there is no "global" statement of the problem. However, even in work like Jeff's, agents assume common interagent semantics in their rational offer groups to converge on deals, or in their representations of mixed joint plans within the Unified Negotiation Protocol. If "MAS" problems are really those for which the agents have absolutely no common semantics, common conceptual vocabularies, etc., then I see no opportunity at all for coordination in MAS problems. If agents cannot assume some commonality - in their environment, perceptual capabilities, primitive concepts (like hunger or fatigue), or some such - I don't see that they have a basis for treating each other as anything but an uncontrollable source of change in the world. For example, some people in planning are not worried about DAI, because they believe an agent can simply react to the environmental changes produced by another agent exactly as it reacts to random domain dynamics. But if an agent can model another agent to the extent that it can cause the other agent to behave differently (in its favor), the agent has a distinct advantage. How this is possible without assuming some sort of common semantics or concepts, if only to the extent of "an agent believing that a change it makes to the environment will have a meaning to the other agent such that the other agent will do x," is beyond me. Agents that inherently have some mutual abilities can use these as a basis for more sophisticated notions. For example if agents can assume that agents in the same vicinity will see roughly the same thing (such as "he will see that when I do x, the world is changed in way y"), they can exploit these assumed capabilities (in this case, assumed mutual observation) to generate more advanced concepts (such as "Now I know he has the concept of `x causes y'"). But I see the formation of more sophisticated shared concepts and semantics as another DPS task, so I guess I don't see why having this as part of the problem makes MAS different from CDPS. >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. This brings in problems of knowing what to point to as a system "goal." As mentioned, each agent may be doing its separate part, and so have no concept of any more global goal. But what does it mean to say that a separate part only "makes sense" in terms of the global picture? Makes sense to whom? Who is doing the evaluation, and what does it mean to the agents? Why should the agents care whether what they do makes sense to some external observer? One answer: They should care because the evaluation of the external observer determines which agents (or agents' code) propagates to future generations of the system. Taking a page out of "The Selfish Gene," it is feedback from the environment (whether the jungle or the programmer) that determines the fitness of an agent; if coordinating effectively with other agents makes an agent more fit (makes the DVMT programmer happier; increases the agent's overall payoffs), then the agent should coordinate because of the "global criterion." The point is, that it could be argued that all agents, whether in DPS or MA systems, have the same reasons for coordinating their activities: to improve their fitness. >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 >classified as DPS problems. And of course, like many classifications, >there is more a continuum than a discrete separation. I've enjoyed the AIJ paper's discussion about problems in shared viewpoints, and I'm convinced that these are hard problems. But the question I have is whether what the research to date is assuming is that agents have shared viewpoints, or whether the agents have "assumed shared viewpoints." I guess I have real trouble figuring out what it means to coordinate (at least in anything but a reactive sense) if agents cannot make any assumptions about what other agents believe, intend, etc. Of course, guaranteeing that such assumptions are in fact true, in any complex multiagent world, is extremely difficult. But as long as they are true within bounds, coordination can still take place. As an example from personal experience: when I initially developed the PGP code in which an agent combined the separate major plan step summaries from several agents into the expected concurrent actions in a PGP, I failed to account for message delays in the formation process. What this essentially meant was that the time intervals associated with plan steps of different agents were incorrectly offset relative to each other. It was as if the agents were assuming that their clocks were synchronized (that time 10 means the same thing to you as it does to me), when in fact they were only synchronized within message-delay bounds (what you said you would be doing at your time 10 could be happenning anywhere from time 8 to 12 on my clock). But the algorithms would treat the information as if the clocks were synchronized. The agents thus failed to have exactly common knowledge of time, but because they assumed that they did, AND this assumption was accurate within reasonable bounds, they could still coordinate fairly well (although not as well as when I improved the code). _____________________________________ Jeff says: >My perspective on the difference between DPS and MA systems is that in >DPS, the system designer can *depend* on agents helping one another with >information, actions, etc. if that would be an effective way to build >the desired system, while in Multiagent research, the system designer >simply cannot *depend* on agents helping one another. >It's more a matter of fundamental overall control of the interaction >environment, rather than the details of who has what goals, or how >helpful the agents are. In a DPS system, the agents might not help each >other, but that was at some level the designer's choice. In a MA system, >the agents might help each other (and might even have identical goals), >but at some level that was not the designer's choice, it was not really >under his control. >In other words, I believe the distinction is in the options available to >the agent builder at the design stage, not (necessarily) in the agent's >behavior at run-time. You could happen upon a group of agents >interacting, and from their goals, beliefs, and behavior, not know >whether or not they were centrally designed. There were sort of three passes here. From the first two paragraphs, you indicate that the system designer in a DPS system can *depend* on agents helping each other, presumably because, as the designer, he or she can design the agents any way wanted. But in an MA system, the designer is in some way handcuffed in the freedom to design the agents. The third paragraph makes this more clear: That it is the system builder and what he/she is allowed to do that makes the difference. This is a neat way of looking at it; I'd never considered it before. The next question arises, then, of what "options" for an agent builder cause the designed agents to be DPS versus MA. Perhaps the ideas of Les enter here, in terms of whether or not to allow a designer to build agents with common (or similar) knowledge representations, concepts, assumptions about each other and each other's rationality, etc. But, as I discussed above, I don't think that drawing the line would be very easy. Moreover, for a variety of reasons (historical, political, etc.), designers of DPS systems might have their options restricted: they have to implement agents using a particular architecture, or using a particular knowledge representation, etc. When the architecture can lead to a variety of often unanticipated behaviors, it is hard for a designer of a DPS system to *depend* on the agents helping each other. Are such designers actually building MA systems instead? >It's my hope that the MA perspective helps builders of DPS systems >consider more autonomous, "competitive" attitudes for their centrally >designed agents---when that ends up being an effective way to build the >kinds of systems they want to build. I agree wholeheartedly that cooperation in DPS should be tempered with a little bit of self-interest (competitiveness). Years ago, Dan Corkill made these observations with the DVMT, by experimenting with making agents more or less locally directed. His experiments showed that introducing "skepticism" (self-interested tendencies) into a DPS system could increase robustness and improve overall performance. And even before that work, the work on blackboard systems involved cooperating knowledge sources that were nonetheless competing for computation resources. It was precisely the competition among KSs at this level that allows the blackboard architecture (on serial machines) to be opportunistic. Thus, I once again argue that many DAI systems, whether DPS or MA, blend cooperation and competition, and that neither DPS nor MA can exclusively claim either of these forms of interaction. ___________________________________________ Ed says: I'm learning a lot in these discussions, and I hope they continue, especially before summer ends and term-time commitments sap away my time for participating... - Ed ------------------------------------------------------------------------ Date: Thu, 15 Aug 91 12:55:21 EDT From: keithw@owgvm0.vnet.ibm.com Subject: When does DPS turn into MA, or MA turn into DPS? Just curious.... After about two weeks of this MA/DPS discussion, I started wondering just how my system would be classified...What do you think... My system (DFI)...contains multiple agents....working on a common goal...hence overall behavior is unigoal directed...but during the negotiation phase (moderated by an arbitrator agent) the agents become competitive in their counterproposal generation. Thus, is this a DPS system because there is a final common goal (best design critique from multiple perspectives of manufacturability and assembly) and the outcome is arrived at basically through cooperative behavior? Or, is it the case that the system is a Multiple Agent (MA) system because the agents generate their counterproposals initially from a competitive viewpoint (improve agent's position, but consider other agent's positions during counterproposal)? Jeff Rosenschein in his reply entitled "DPS vs. MA, again" says that (emphasis added to key points by me): > It's more a matter of FUNDAMENTAL OVERALL CONTROL of the interaction > environment, rather than the details of who has what goals, or how > helpful the agents are. In a DPS system, the agents might not help > each other, but that was at some level the DESIGNER'S CHOICE. In a MA > system, the agents might help each other (and might even have > identical goals), but at some level that was not the designer's > choice, it was not really under his control. So, I guess my system is a DPS system because there is agent cooperation toward a high level common goal which I designed into the system. But what if the agents tend to become more independent, more competitive in behavior given the context of the problem-solving? Eg: the context data of a particular connection design causes the behavior of the agents to change. They now feel strongly about their position and won't budge. This feature of competitiveness was also designed into the system. Does that mean that the system is now an MA architecture? That is where the arbitrator comes in...to help "enlighten" (during mediation) and "command" (during binding arbitration) the agent's counterproposal behavior. On system design, Jeff states: > In other words, I believe the distinction is in the options available > to the agent builder at the design stage, not (necessarily) in the > agent's behavior at run-time.... Given this, does this mean that systems with arbitrators which handle both cooperative and competitive behavior are both DPS and MA systems? The arbitrator was "designed" in so that it could handle agents when they get to "wild" (off the common goal mark). Or, is it simply the case that because the agents can choose to become cooperative or competitive the system is of an MA classification? On MA systems, Jeff states: > It's my hope that the MA perspective helps builders of DPS systems > consider more autonomous, "competitive" attitudes for their centrally > designed agents---when that ends up being an effective way to build > the kinds of systems they want to build. Good point...but what if there are systems that possibly fall in between these classifications? What would we call these? Hybrid MA/DPS systems? (By the way, I sort of think my system is a DPS system, but maybe it actually is a hybrid?) ......Just curious.....What do you think...? Keith Werkman - IBM Owego Labs - email: keithw@owgvm0.vnet.ibm.com ------------------------------------------------------------------------ Date: Fri, 16 Aug 91 14:00 CDT From: Michael N. Huhns Subject: Classifying Werkman's DFI System To decide how to classify the system Keith constructed, I ask myself the following question: "Do the entities in your system seem more like agents or more like specialized problem solvers?" Clearly, their capabilities are limited to a small subset of civil engineering (except for the arbitrator, whose expertise is in negotiation), so they seem to be just specialized problem solvers. Hoever, the entities have explicit representations for their goals, which they pursue somewhat independently and over which they cooperate, negotiate, and compete. Presumably, they could choose to be uncooperative. This makes them seem to be agents. So overall, I would characterize your system as a multiagent system, although the classification is obviously fuzzy. Of course, as has already been pointed out in this discussion, this is an external characterization and does not change the way your system operates, which is what really matters.