A Framework For Collaboration

We propose a collaborative solution to the problems above. While a particular agent may not have any prior knowledge, there may exist a number of agents belonging to other users who do. Instead of each agent re-learning what other agents have already learned through experience, agents can simply ask for help in such cases. This gives each agent access to a potentially vast body of experience that already exists. Over time each agent builds up a trust relationship with each of its peers analogous to the way we consult different experts for help in particular domains and learn to trust or disregard the opinions of particular individuals.

Collaboration and communication between various agents can take many different forms. This paper is only concerned with those forms that aid an agent in making better predictions in the context of new situations. There are two general classes of such collaboration.

Desperation based communication is invoked when a particular agent has insufficient experience to make a confident prediction. For example, let us suppose that a particular agent has just been activated with no prior knowledge, and its user receives a set of new mail messages. As doesn't have any past experience to make predictions, it turns in desperation to other agents and asks them how their user would handle similar situations.

Exploratory communication, on the other hand, is initiated by agents in bids to find the best set of peer agents to ask for help in certain classes of situations. We envisage future computing environments to have multitudes of agents. As an agent has limited resources and can only have dealings with a small number of its peers at a given time, the issue of which ones to trust, and in what circumstances, becomes quite important. Exploratory communication is undertaken by agents to discover new (as yet untried) agents who are better predictors of their users' behaviors than the current set of peers they have previously tested.

Both forms of communication may occur at two orthogonal levels. At the situation level, desperation communication refers to an agent asking its peers for help in dealing with a new situation, while exploratory communication refers to an agent asking previously untested peers for how they would deal with old situations for which it knows the correct action, to determine whether these new agents are good predictors of its user's behavior. At the agent level, desperation communication refers to an agent asking trusted peers to recommend an agent that its peers trust, while exploratory communication refers to agents asking peers for their evaluation of a particular agent perhaps to see how well these peers' modelling of a particular agent corresponds with their own. Hence agents are not locked into having to turn for help to only a fixed set of agents, but can pick and choose the set of peers they find to be most reliable.

For agents to communicate and collaborate they must speak a common language as well as follow a common protocol. We assume the existence of a default ontology for situations in a given domain (such as electronic news, e-mail, meeting scheduling, etc). Our protocol does not preclude the existence of multiple ontologies for the same domain. This allows agent creators the freedom to decide which types of ontologies their agents will understand. As the primary task of an agent is to assist its particular user, the protocol for collaboration is designed to be flexible, efficient and non-binding. We briefly present the protocol below.

• Registration: Agents wishing to help others register themselves with a ``Bulletin Board Agent'' whose existence and location is known to all agents. While registering, agents provide information regarding how they can be contacted, what standard domains they can provide assistance in, what ontologies they understand and some optional information regarding their user. Every agent registering with a bulletin board agent is given a unique identifier by the bulletin board.

• Locating peers: Agents wishing to locate suitable peers may query bulletin board agents. An agent querying a bulletin board agent need not itself register with that bulletin board. Queries to a bulletin board agent can take many different forms depending on the type of information required. This allows agents to locate suitable peers in the most convenient way. For example, an agent's user may explicitly instruct it to ask a specific user's agent for help in dealing with certain types of situations.

• Collaboration: Collaborative communication between agents occurs in the form of request and reply messages. An agent is not required to reply to any message it receives. This leaves each agent the freedom to decide when and whom to help. Any request always contains the agent's identifier, the agent's contact information (for replies), the ontology used in the request, and a request identifier (reqid) generated by the agent issuing the request. The reqid is necessary since an agent may send out multiple requests simultaneously whose replies may arrive out of order.

  Analogously every reply always contains the replying agent's identifier and the reqid used in the request.

  The types of requests and their associated replies are presented below.

  • Situation level collaboration: When a situation occurs for which an agent does not have a good prediction, it sends off a Request-for-Prediction message to its peers. A prediction request contains all the features of the situation which the agent issuing the request wishes to divulge. This allows the requesting agent the freedom to withhold sensitive or private information.

    An agent receiving a prediction request may choose to ignore it for any of a variety of reasons. It may not have a good prediction for the specific situation, it may be too busy to respond, the agent issuing the request may not have been very helpful in the past, or the agent may not be important enough. If however, an agent decides to respond to a prediction request, it sends back a response containing its prediction and its confidence in this prediction (a normalized value).

    Note that the prediction request is used by agents for both desperation and exploratory communication. An agent receiving a prediction request does not know whether the request originated via exploratory or desperation based behavior on the part of the agent issuing that request. The distinction is made by the agent issuing the request. Replies to requests sent in desperation are used to predict an action for a particular situation, while replies to requests sent in exploratory mode are compared with the actions that the user actually took in those situations, and are used to model how closely a peer's suggestions correspond with its user's actions.

  • Agent level collaboration: An agent may send its peers a Request-for-Evaluation request. An evaluation request is sent when an agent wants to know what some of its peers think about a certain agent in terms of being able to model their users in particular classes of situations. An evaluation request contains the identifier of the agent to be evaluated (designated as the target agent) and the particular class of situations for which the evaluation is needed.

    In any domain and ontology there exist different classes of situations. Certain agents may model a particular user's behavior in a particular class of situations very well and fail miserably in other classes. Note that we expect the domain ontologies to define these classes. For example an email agent may discover that peer agent is a very good predictor of its user's actions for messages sent to a mailing list, while being quite useless in predicting what its user does with any other type of message. On the other hand peers and are excellent predictors of its user's behavior with regards to email forwarded by her groupmates. This enables agents to locate and consult different `expert' peers for different classes of situations.

    An agent that chooses to respond to an evaluation request sends back a normalized value which reflects its trust in the target agent's ability to model its user's behavior for that particular class of situations.

    An agent may also ask trusted peer agents to recommend a peer who has been found to be useful by the trusted peer in predicting its user's behavior for a particular class of situation. A Request-for-Recommendation contains the situation class for which the agent would like its trusted peer to recommend a good agent. Replies to recommendation requests contain the identifier and contact information of the agent being recommended.

Agents model peers' abilities to predict their user's actions in different classes of situations by a trust value. For each class of situations an agent has a list of peers with associated trust values. Trust values vary between 0 and 1.

The trust values reflect the degree to which an agent is willing to trust a peer's prediction for a particular situation class. A trust value represents a probability that a peer's prediction will correspond with its user's action based on a prior history of predictions from the peer. Agents may start out by picking a set of peers at random or by following their user's suggestion as to which peer agents to try first. Each previously untested peer agent gets has its trust level set to an initial value. As a peer responds to a prediction request with a prediction , and an agent's user takes a particular action , the agent updates the trust value of its peer in the appropriate situation class as follows: where

and represents the trust level of a peer, represents the confidence the peer has in this particular prediction, is the trust learning rate, and ensures that the value of always lies in . The rationale behind the modelling above is as follows. An agent's trust in a peer rises when the peer makes a correct prediction and falls for incorrect predictions. The amount it rises and falls by depends on how confident the peer was in its prediction. That is, a peer who makes an incorrect prediction with a high confidence value should be penalized more heavily than one that makes an incorrect prediction but with a lower confidence value.

When an agent sends out a prediction request to more than one peer it is likely to receive many replies, each with a potentially different prediction and confidence value. In addition, the agent has a trust value associated with each peer. This gives rise to many possible strategies which an agent can use to choose a prediction and a confidence value for this prediction. We believe that both trust and peer confidence should play a role in determining which prediction gets selected and with what confidence. Each predicted action is assigned a trust-confidence sum value which is the trust weighted sum of the confidence values of all the peers predicting this action. The action with the highest trust-confidence sum is chosen. The confidence associated with the action chosen is currently that of the most confident peer suggesting this action. We are exploring more sophisticated trust-confidence combination strategies using decision theoretic and Bayesian strategies.