DAI-List Digest Friday, 2 August 1991 Issue Number 45 Topics: Reply on DPS, CDPS, and MA Definitions of CDPS, MA, etc. Discussion of Trust 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: Tue, 30 Jul 91 10:06:05 -0400 From: durfee@caen.engin.umich.edu (Ed Durfee) Subject: DPS, CDPS, and MA The principal touchstone I use in discriminating between CDPS (DPS) and MA systems is part of the definitions you cite: in CDPS (and DPS), the agents are faced with problems to solve (goals to achieve) that are beyond their individual capabilities, and so must work together to satisfy their goals; in MA, the agents are not assumed to be facing problems beyond their individual capabilities, but because they share an environment, they still must deal with issues of coordinating to resolve conflicts between actions or to take advantage of the actions of others in achieving their goals. In my opinion, the essential characteristic dividing the areas is not whether the agents have common or distinct goals, but whether or not the goals in whatever form require collective activity. More generally, the problem of terminology between DPS, CDPS, and MA arises because we are trying to break apart a continuum of behaviors into neat little pigeon holes. At the far DPS extreme are groups of agents that together must solve one big problem and who are just aching to do everything they can toward this goal. But what if one of the agents wants the goal achieved but does not want to contribute? Is this as clearly a DPS situation? Or what if different factions of agents have different, and incompatible, "global" goals? Then inside a team we have DPS, but between teams it's like MA? Pushed toward the MA extreme, we have the view of agents who could achieve their goals without any help, but need to coordinate to avoid interfering with each other. Or even more strongly in this direction, agents purposely lying to each other to maximize selfish utility at the expense of others by getting others to do more than their share. While I find the DPS versus MA differentiation helpful in an abstract sense, I don't think it can act as a clearcut classification because agents often have multiple goals, some of which might be satisfiable working alone and others which might require cooperation. An agent that is trying to sufficiently satisfy both types of goals might appear as being involved in both DPS and MA systems. For example, in a "DPS" system like the DVMT where agents must work together to map vehicle movements in an area, there is still some MA character because agents generally prefer to pursue solutions based on locally generated results rather than competing solutions based on others' results. This tension between needing help while favoring selfish ends leads to issues in "distraction." Similarly, in an "MA" application such as the slotted-blocks-world looked at by Rosenschein et al, the agents are maximizing their individual utilities, but in so doing might propose a global goal state that avoids either one clobbering the other. They then negotiate to decide how they will achieve the global goal - which could be viewed coming up with a DPS strategy. Most interesting problems have agents that are partially adversarial and partially cooperative all at the same time (just look at my kids!). That's what makes life interesting. - Ed PS: I will cc this message to Mike Huhns at dai-list; perhaps if you (or someone else) disagree with this answer or have a better one, it will serve to spark more discussion on dai-list, which is something I strongly favor. ------------------------------------------------------------------------ Date: Fri, 2 Aug 91 12:02 CDT From: Michael N. Huhns Subject: Definitions of CDPS, MA, etc. (At last, a real discussion on DAI-List!) I use the following taxonomy of terms to distinguish some of these concepts: Distributed Artificial Intelligence / | \ / | \ Parallel AI Distributed Problem Solving Multiagent Systems / \ | / \ | Blackboard-based CDPS | Knowledge Sources \ | \ | \ | Cooperating Agents Parallel AI includes systems for which execution time is of primary importance, and is usually characterized by the use of distributed hardware and distributed operating systems to speed up the execution of conventional AI software. An example is the work at CMU to speed up OPS5 by parallelizing the Rete algorithm. Both Distributed Problem Solving (DPS) systems and Multiagent Systems have either a common goal for their constituents or competition for a common resource that is essential for the constituents to achieve their individual goals. That is, there must be some motivation for the constituents to interact--otherwise they would simply be a random collection of problem solvers or agents. They need to coordinate their actions, but they do not necessarily cooperate. I distinguish a DPS system from a Multiagent System as follows: a DPS system can consist of multiple expert systems or multiple knowledge sources (KSs), as in a blackboard-based system. I think of agents as having an additional characteristic--an explicit representation of their goals. The conventional description of an agent requires the abilities to perceive, reason, and act. Adding the requirement that goals be represented enables these goals to then become a subject for their reasoning. To me, the lack of this in most expert systems is what precludes those systems from being thought of as agents. For example, a thermostat (which is like an expert system with one rule, and which perceives its environment, reasons about it, and acts) just doesn't seem to be an intelligent agent, because it can't reason about what it is doing--maintaining some temperature. A second distinction is that the reason a DPS system exists is to solve problems--this is not necessarily true for multiagent systems. Michael Huhns MCC ------------------------------------------------------------------------ From: PLai@cup.portal.com (Patrick L Faith) Subject: Re: Trust Date: 30 Jul 91 02:54:23 GMT Organization: The Portal System (TM) >Do we have different levels of trust Trust can be modeled as the conflict between 4 weights: propogation - goodness frequency - how often something is used amplitude - when you do something, how hard should you do it phase - should you do something at an exact time or doesn't it matter I view these 4 weights as constituting an event, with all of the ai's events associated in a n-dimensional space. Trust then would be propogation (experience of success) diminished by a poor phase value (not knowing when to expect something), boosted by the event happening often (frequency), and also boosted by amplitude - though extremes in any of the frequency,amplitude,phase weights should trigger a poor propogation factor - and thus a poor "concept" of trust. PLai ------------------------------------------------------------------------ From: garland@maccs.dcss.mcmaster.ca (Bill Garland) Subject: Re: Trust Date: 30 Jul 91 13:37:45 GMT Organization: McMaster University, Hamilton, Ontario, Canada In an article steve@canon.co.uk (Steve Marsh) writes: >Hi, I have a request. Does anyone know of any work being done on >trust, and the effects it can have on inter-'agent' relationships? >Specifically, I'd like to know of any work in the distributed AI area, >but anyone's thoughts on the subject would be interesting and useful. >I've written a few questions down that may help along the way... >How >does trust enter into relationships? Is trust an important factor in >interagent discussions and communications? How are cliques formed? >(What role does trust play in this?) Is a clique more succesful than >an individual? Why? Do we have different levels of trust? Do we have >different levels of information-secrecy? (And relate this to trust >levels?) >Thanks for your help. > Steve Marsh. Temporarily in residence at steve@canon.co.uk. One of the best books (non-AI) that I have found on the subject is a little paperback written by Peter Singer called The Expanding Circle of Trust (I think)or Expanding the Circle of Trust, something like that. If you have trouble finding it, post again and I will look up the ISBN etc at home. This is a book to savour. Another related book is by Robert Axelrod: The evolution of Cooperation. His book is about the computer simulations reported in Scientific American. Remember those? Tit for Tat keep winning - hence, in a way, trust was not a factor! I've tried to write about this myself.... someday I may even finish it! Bill Garland garlandw@mcmaster.ca McMaster University EngPhys Chairman ------------------------------------------------------------------------ From: steve@canon.co.uk (Steve Marsh) Subject: Re: Trust Date: 31 Jul 91 09:36:20 GMT Organization: Canon Research Europe, Guildford, UK garland@maccs.dcss.mcmaster.ca (Bill Garland) writes: [Stuff on trust...] >One of the best books (non-AI) that I have found on the subject is a >little paperback written by Peter Singer called The Expanding Circle of >Trust... Yes, Axelrod's book is a good read. Problem is, I don't know whether the concept of trust was lost there, since tit-for-tat is trusting to a certain extent - until it's trust was abused - at which time it was very forgiving also. It's worth noting (and this bothers me a little) that tit-for-tat could never *win*. The best it could do was do as well as its opponent Still, that's by-the-way. The original questions I asked were related (in my mind) to the concept of how trust allows us to build relationships, why these relationships work, and so on, and how robust they are. At present, I'm trying to implement a model of the idea in a simple multi-agent world, to see what comes out. I'm interested in the idea that competition amongst individuals may sometimes be more productive than cooperation, and in which circumstances. BTW, do you have a publisher's name for Singer's book? Sounds like it could be useful. Steve Marsh. Temporarily in residence at steve@canon.co.uk. (But really I'm spm@cs.stir.ac.uk, honest!) ------------------------------------------------------------------------ From: erwin@trwacs.UUCP (Harry Erwin) Subject: Re: Trust Date: 31 Jul 91 11:45:11 GMT Organization: TRW Systems Division, Fairfax VA garland@maccs.dcss.mcmaster.ca (Bill Garland) writes: >In an article steve@canon.co.uk (Steve Marsh) writes: >>Hi, I have a request. Does anyone know of any work being done on >>trust...stuff omitted... The Dynamics of Computation group at Xerox PARC, under the leadership of Bernardo Huberman and Tad Hogg, has been looking into aspects of this area. Harry Erwin ------------------------------------------------------------------------ From: PLai@cup.portal.com (Patrick L Faith) Subject: Re: Trust Date: 31 Jul 91 04:49:10 GMT Organization: The Portal System (TM) [plai] >>events associated in a n-dimensional space. Trust then would be >>propogation ( experience of success) diminished by a poor phase >>value (not knowing when to expect something), boosted by the event >>happening often (frequency), and also boosted by amplitude - though >>extremes in any of the frequency,amplitude,phase weights should trigger >>a poor propogation factor - and thus a poor "concept" of trust. [btaplin] > Huh? Seemed obvious when i wrote it, not so obvious when i read it the next day :D The basic concept is, how do you "trust" information, or how do you know how correct/bad the information is that you are given. For a sophisticated ai, certain events need to be more important and higher weighted - those things that are higher weighted (things you are going to do) are the things that you want to trust. If the IAI is self learning , then it has to determine what you tell it is true. I bassically see truth/trust as associating to an event which is consistent with other similiar events. Using frequency, amplitude, phase, and propogation are ways of specifying an event, and thus are the metrics which similiarity are weighted to determine trust ( self consistency of computation). PLai ------------------------------------------------------------------------ From: M16143@mwvm.mitre.org Subject: Re: Trust Date: 31 Jul 91 14:00:02 GMT Organization: The MITRE Corporation, McLean VA 22102 *********** Steve Marsh writes: The original questions I asked were related (in my mind) to the concept of how trust allows us to build relationships, why these relationships work, and so on, and how robust they are. At present, I'm trying to implement a model of the idea in a simple multi-agent world, to see what comes out. I'm interested in the idea that competition amongst individuals may sometimes be more productive than cooperation, and in which circumstances. ************************************** It would seem that you are trying to address not the credibility of the information sources as other responses have mentioned, but rather the concept of when an agent should not kill another agent or fear being killed by another agent. This is the ultimate competition/cooperation question. In that case, an agent must have some kind of measure (not necessarily a formal metric) of the benefit that will accrue to itself and to its neighbors as a result of its choice of cooperation vs competition. If there is a "world view" of success (like we all join together to stop global warming), then the success of trust as a strategy depends on agents sharing that world view. In an individual case, without a world view, in order for one agent to trust another, they will have to understand each others personal motives - what is the objective function that an agent is min/maxing? In the self learning situation, the agents will have to learn by trial and error, and that will probably mean giving the agent the capability to hypothesize a motive for his neighbors, and then inductively testing the correctness of that motive. Sounds like a lot of hard work to me. You might want to look at some of D.A. Schum's works on credibility related issues since, if your agents exchange information, you will have to come up with some schemes for helping the agents to decide if another agent is lying. The above random thoughts are strictly my own and do not necessarily reflect the opinions of my wife, employer, or school, nor are they the product of a really in-depth, all out, stay-up-till-midnight think on the topic. Tony Zawilski ------------------------------------------------------------------------ From: steve@canon.co.uk (Steve Marsh) Subject: Re: Trust (Longish...) Date: 1 Aug 91 12:55:39 GMT Organization: Canon Research Europe, Guildford, UK M16143@mwvm.mitre.org writes: >It would seem that you are trying to address... Yes. Or, more specifically, I'll split it up... >It would seem that you are trying to address not the credibility of the >information sources as other responses have mentioned, but rather the >concept of when an agent should not kill another agent or fear being >killed by another agent. This is the ultimate competition/cooperation >question. In that case, an agent must have some kind of measure (not >necessarily a formal metric) of the benefit that will accrue to itself >and to its neighbors as a result of its choice of cooperation vs >competition. This is okay so far. The basic idea behind this is like Axelrod's "Shadow of the Future". I don't think it's just restricted to death, or things as extreme as that - the idea of credible info sources is just as important, depending on what the information is, I suppose. >If there is a "world view" of success (like we all join together to >stop global warming), then the success of trust as a strategy depends on >agents sharing that world view. In an individual case, without a world >view, in order for one agent to trust another, they will have to >understand each others personal motives - what is the objective function >that an agent is min/maxing? I don't think it's that explicit, to be honest. The agent should certainly have a metric about how it trusts another, but this is based on a lot of things. To quote a bit from a paper I'm writing at present: "What makes us cooperate with some people or agents, and not with others? In other words, why do we trust some more than others? In the real world, we have some level of trust for everyone to an extent. Some of the trust we have in others is derived from a belief in the skills of certain people, and the amount of trust they have in those we trust. For example, we trust other road users when we are driving in our cars, simply because they have been examined by someone we have placed our trust in. Society as a whole then operates on a notion of trust, and since we cannot judge everyone ourselves, it is necessary to place our trust in certain people to judge for us. The shock we suffer as a result of this trust being misplaced is not inconsiderable, even in terms of something as trivial as the driving test. We trust those in authority to judge for us where we cannot, not because we don't want to, but simply because it is impossible - there are too many people that we interact with to judge them all on an individual level. When a person joins our social set, however, in a close sense, then we judge them for ourselves, with regard to our own notions of trustworthiness." There's more, but basically the idea is that our notion of trust comes from a lot of sources: >In the self learning situation, the agents will have to learn by trial >and error, and that will probably mean giving the agent the capability >to hypothesize a motive for his neighbors, and then inductively testing >the correctness of that motive. Sounds like a lot of hard work to me. Trial and error is exactly how real life works, IMO. The agents I propose (or am thinking of) are actually quite simple bods, and the concept of success is survival of agent-specific behaviour - a kind of Larmarckian evolution, where notions of trust and cooperation in/with others are passed down generations, as well as genetic (in a very limited sense) structure. Letting evolution do the hard work in some way, that's the name of the game! Seriously, however, some metric for trust/cooperation/ behaviour and so on will have to be introduced, and that won't be easy, which is why I asked the original questions. After all, a platform for testing individual hypotheses would be useful, I think I seem to have strayed off the path a little, but I hope it makes sense... All comments greatly appreciated :-) Steve Marsh. steve@canon.co.uk to 31 August, spm@cs.stir.ac.uk afterwards.