PROJECT: Agent-Based Semantic Web Services: Trustworthy Partner Selection, Interoperation, and Composition

 

Selecting the right parties to interact with is a fundamental problem in open and dynamic environments. The problem is amplified when the number of interacting parties is high, and the parties’ reasons for selecting others vary. In this project, we examine the problem of service selection in an e-commerce setting where consumer agents cooperate to identify service providers that would satisfy their service needs the most. Open multiagent systems do not provide guarantees about the quality of the service of its providers. This makes it difficult for service consumers to find correct service providers. Many existing approaches share the intuition that service consumers can share their knowledge about service providers to help locate useful service providers. However, representing existing past knowledge and reasoning about this knowledge are two important challenges. A traditional approach for dealing with these challenges is to represent past dealings with ratings and to aggregate the ratings. However, rating-based approaches lack the expressiveness to articulate objective information about service dealings. To enable richer representations, we have developed an objective experience-based approach for service provider selection, in which consumers record their experiences with service providers rather than the overall, subjective ratings for a provider. A consumer’s experience with a service provider is represented using an ontology that can capture subtle details including the context in which the service was requested. When a service consumer decides to share her experiences with a second service consumer, the receiving consumer evaluates the experience using its own context and evaluation criteria.

 

 

Introduction

Finding service providers for specific needs is difficult when service providers offer services at varying levels. A consumer agent can try various service providers on its own and choose a provider solely based on its previous experiences. But, that means many trial-and-errors on the consumer side. A more acceptable solution is to enable consumers to exchange knowledge about service providers, so that each agent can reason about the knowledge it gathers from other agents. The simplest form of such exchange is that of ratings, commonly employed in today’s e-commerce sites. The basic idea is that the consumers rate the providers that they interact with and reveal their ratings publicly [1] or privately to certain agents. The agents then examine these ratings and decide if any of the service providers are satisfactory for their own purposes [2]. Rating-based approaches reflect the subjective opinion of the raters. Most of the time, the context of the ratings are not made explicit. Hence, it is hard to judge what the rating would correspond to in a different setting. Furthermore, even if the context of the ratings is made explicit, these ratings may still mislead the consumers, because the satisfaction criteria of the consumer using these ratings may be different from the satisfaction criteria of those who give the ratings in the first place.

The reasoning process is inherently dependent on how the knowledge is represented. For example, since the ratings represent previous knowledge compactly, it is difficult to interpret what the numbers mean in different settings and to reason on these ratings. Thus, reasoning elaborately on others’ knowledge will require the knowledge to be expressed in greater detail.

In this project, We have developed an approach for distributed service selection that allows consumers to capture their experiences with the service providers using ontologies [3]. The ontology represents the details of the requested service description and the received service. The consumers can then exchange their detailed experiences of service providers rather than plain ratings. A consumer that receives another agent’s particular experience evaluates the received experiences individually considering her own context to decide on which service provider to select. Whereas rating-based approaches reflect the subjective opinion of the raters, the experience-based approach allows the objective facts of the experience to be communicated to the other party.

The proposed approach enables experiences to be expressed in detail. The immediate question is how the agents will use these experiences to select a service provider. We  employed a parametric classification technique using Gaussian model. In the scope of this project, we also developed a strategy in which agents use case-based reasoning to select a service provider. 

Representation of Experiences

Rating-based approaches reflect the subjective opinion of the raters. Even though the context of the ratings is explicitly expressed, these ratings may still mislead the consumers, because the satisfaction criteria of the consumer using these ratings may be different from the satisfaction criteria of those who give the ratings. Even if their service interests are the same, consumers rate the same service differently depending on their satisfaction criteria. The main question at this point is how to get rid of subjectiveness of ratings in the service selection.

Instead of ratings, consumers can record their interactions with service providers in a great detail within an experience structure. An experience contains the consumer’s service demand and the provided service in response to the service demand. Actually, an experience expresses the story between the consumer and the provider regarding a specific service demand. So, any consumer receiving an experience can evaluate the service provider according to its own criteria using the objective data in the experience. This approach removes the subjectiveness of the rating-based approaches.

Experiences require representational power of ontologies. For each domain, a different ontology for the representation of experiences is necessary. We represent a base level ontology for domain independent concepts and a domain ontology for domain dependent ones (see Base-level Ontology). The base level ontology covers domain-independent infrastructure of the experience ontology. It is centered around the Experience class, whose instances represent experiences of service consumers. This is motivated by the concept of experiences in real life. An experience is a combination of what we have requested from a service provider and what we have received at the end. So, in the ontology, an experience consists of a service demand and supplied service for the demand. For this purpose, Demand and Service classes are included in the base ontology. Both demand and supplied service concepts are descriptions of a service for a specific domain and hence share a number of properties. Domain level ontology captures domain specific properties and concepts (see Domain-level Ontology). For example, a domain level ontology for online shopping may include concepts such as hasShoppingItem, toLocation, hasDeliveryType, hasDelivery-Duration, hasShipmentCost, and hasPrice. Since our focus in this paper is on reasoning, we do not give the details of our representation. Details of base level and domain level ontologies used for simulations can be found elsewhere [3].

Service consumer will need to interact with other service consumers with similar demands. Since the definition of a similar demand varies from one agent to another, we allow each consumer to define its understanding of a similar demand using the ontology and the Semantic Web Rule Language (SWRL) [4].

When a consumer agent has a particular service demand and a list of others’ experiences, then it can apply the SWRL rule to select those experiences in which the service demands were similar to that of her own. If the consumer makes its SWRL rule for similar demands public, other consumers can also use this expression of similarity to reason about whether their past service demands were similar to the demand of the consumer or not (see SWRL Examples).

Retrieving Experiences

The service consumers are organized in a peer-to-peer multiagent system. Each service consumer knows only a subset of all consumers in the society and lists these consumers in its acquaintance list. An acquaintance list is a dynamic list of service consumers having service demands classified as similar demand by the owner of the list. When a new service consumer joins the society, its acquaintance list is populated with a small number of randomly chosen service consumers. Each consumer collects others’ experiences in an experience repository. Each time a service consumer makes a service selection, it uses the experiences in this repository for decision making. Service consumers refresh and update their repositories periodically by removing old experiences and adding newly found ones. Initially, service consumers do not have any experiences.

When a service consumer decides to receive a service, it checks its experience repository. If number of experiences in the repository is small, the service consumer collects new experiences. However, in order to collect new experiences, the consumer should have sufficient number of acquaintances. If it does not have enough acquaintances, then it increases the number of its acquaintances by first discovering other service consumers having similar demands and by populating its acquaintance list with those service consumers. This procedure is summarized in Figure 1.

In order to discover new acquaintances, a service consumer X uses two messages: Peer Discovery Message (PDM) and Request for Acquaintances Message (RAM). Both PDM and RAM messages contain a SWRL rule that expresses the similar demand criteria of the message originator. When a consumer Y receives a PDM message, it checks if its service demands are similar to that of the originator X. If so, it notifies X and X adds Y as a new acquaintance entry in its acquaintance list. This entry contains identity of Y and its demands classified as similar demand by similarity criteria of X. The consumer Y also forwards the request to a set of service consumers in its acquaintance list if these consumers have similar demands with respect to similarity criteria in the PDM message. If there is no such consumer, Y randomly selects consumers from its acquaintance list. How long the request is going to be forwarded is controlled using a time-to-live field. All other consumers that receive the request act the same way Y does. When, Y receives a RAM message from the originator X, it checks its acquaintance list for the consumers having similar demands with respect to similarity criteria in the RAM message. Then, Y sends identities of these consumers to X. So, X can add these consumers to its acquaintance list. After having sufficient number of acquaintances, the consumer uses Request for Experience Message (REM) to collect new experiences. A REM message also contains a rule for expressing similar demand criteria of the sender. When service consumer Y gets a REM message from service consumer X, it evaluates its service demands in its own experiences using the similarity criteria in the REM and sends its experiences to X if these experiences have similar demands with respect to similarity criteria in the REM. So, X can populate its repository with these experiences. The details of the peer-to-peer discovery protocol is described elsewhere [5].

Figure 1. State diagram of an agent (click on the figure to enlarge).

 

Service Selection Using Parametric Classification

Different AI techniques can be applied on objective experience data. Information in the experiences can be used for the modeling of provider behaviors for different service demands. For this purpose, a parametric classification method, multivariate Gaussian model (GM), can be used [3]. In this method, a service consumer models each service provider by building a multidimensional Gaussian model using the collected experience data. There are two classes for each model: satisfied and dissatisfied. These classes represent the experiences in which the supplied services are classified as satisfactory and unsatisfactory with respect to the satisfaction criteria of the consumer. Then, for each of the models, a discriminant function is defined to compute the probability of satisfaction [6]. The service consumer performs this computation for every service provider and chooses the provider with the highest satisfaction probability. Modeling of providers may require a high volume of experiences concerning different providers. Collecting that many experiences may be costly in terms of time and messaging complexity.

Case-Based Service Selection

Non-parametric methods such as case-based reasoning (CBR) can also be used for service selection. CBR is an approach for problem solving and learning in which old problems and their solutions are encapsulated into a case structure and stored in a case-base. When a new problem is encountered, the most similar past cases are retrieved from the case-base and solutions in these cases are modified to conform to the new situation [7]. The idea is that if two problems are similar, the solutions to these problems will probably be similar, too. The concept of similarity plays a crucial role in CBR.

The most important challenge in the CBR is the selection of metrics for the similarity, because performance of CBR systems critically depends on these metrics. Another challenge is that most CBR approaches are centralized. This implies that ill-constructed metrics for the similarity could drastically affect the performance of the whole system. The proposed approaches in this project can be combined to construct a context-aware, flexible and distributed CBR approach for the service selection. In this approach, each consumer uses consumer society as a distributed case-base. Additionally, unlike the classic CBR systems, each consumer can represent its own similarity metrics using an OWL ontology and SWRL rules. Using this well defined similarity metric, the consumer queries the consumer society for similar experiences using the procedure explained above. After retrieving the similar experiences, the consumer computes a score for each retrieved experience. The computation depends on the following factors:

  • Recency: The new experiences are preferred over old experiences since they are likely to hold again in the near future. For this reason, each experience is assigned a recency value. The newer the experience, the larger the recency value.

 

  • Similarity: This is a factor that measures the similarity of the current demand with the examined experience. The similarity value ranges between 0 and 1, where 0 denotes total difference and 1 denotes identical demands.

 

  • Satisfaction: This is an important factor that measures how satisfied the current consumer agent would be, had it lived the examined experience itself. The consumer evaluates the supplied service depending on its current service demand and its own satisfaction criteria and obtains its expected degree of satisfaction.

We combine these factors using the formula below:

Si = recencyi × simi × sati

where, Si is the computed score for the experience i, recencyi is the recency factor, simi is the similarity factor and sati is the satisfaction factor. After computing the scores for each experience, the consumer picks the experience with the highest score and selects the provider supplying the service within this experience. This approach is unique from different perspectives. To the best of our knowledge there is no CBR system using OWL ontologies for the representation of cases and there is no distributed CBR approach in which similarity metrics are defined individually by each user using SWRL rules.

 

References

  1. eBay: http://www.ebay.com (1995)
  2. Sabater, J., Sierra, C.: Reputation and social network analysis in multi-agent systems. In: Proceedings of the 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). (2002) 475–482
  3. Sensoy, M., Yolum, P.: A context-aware approach for service selection using ontologies. In: Proceedings of Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). (2006)
  4. SWRL: A Semantic Web Rule Language Combining OWL and RuleML (2004)
  5. Sensoy, M., Yolum, P.: Experience-based service provider selection in agent-mediated e-commerce. Engineering Applications of Artificial Intelligence. Volume 20, Issue 3, pp. 325-335. (2007)
  6. Duda, R.O., Hart, P.E., Stork, D.G.: Pattern Classification. John Wiley and Sons, West Sussex (2001)
  7. Aamodt, A., Plaza, E.: Case-based reasoning: Foundational issues, methodological variations, and system approaches. Artificial Intelligence Communications 7 (1994) 39–59
  8. KAON2: Kaon2 Web site:  http://kaon2.semanticweb.org (2005)
  9. Jena – A Semantic Web Framework for Java, Jena Web site: http://jena.sourceforge.net 

 

 

SUPPLEMENTARY DOCUMENTS RELATED TO THE PROJECT

(Ontologies and SWRL rules are created using Kaon2 [8] and Jena [9])

Base-level Ontology

 Click here to download XML version of the base-level ontology

Figure 2. Base-level Ontology.

 

Domain-level Ontology

 Click here to download XML version of the domain-level ontology

Figure 3. Domain-level Ontology.

SWRL Similar Demand Description Examples 

Example 1. In this example, the consumer states that a demand is a similar demand only if it contains a book as a shopping item and it requires a delivery duration less than or equal to two weeks (click here to see XML document).

 

Example 2. In this example, the consumer states that a demand is a similar demand only if it requires a price less than $100 and  a delivery duration less than or equal to two weeks (click here to see XML document).