![[*]](../../CDROM/refereed/211/footnote.png)
.
David Trastour |
Claudio Bartolini |
Chris Preist |
| david_trastour@hp.com | claudio_bartolini@hp.com | chris_preist@hp.com |
Hewlett-Packard Laboratories
Filton Road, Stoke Gifford
Bristol, BS34 8QZ, UK
If an e-services approach to electronic commerce is to become widespread, standardisation of ontologies, message content and message protocols will be necessary. In this paper, we present a lifecycle of a business-to-business e-commerce interaction, and show how the Semantic Web can support a service description language that can be used throughout this lifecycle. By using DAML+OIL, we develop a service description language sufficiently expressive and flexible to be used not only in advertisements, but also in matchmaking queries, negotiation proposals and agreements. We also identify which operations must be carried out on this description language if the B2B lifecycle is to be fully supported. We do not propose specific standard protocols, but instead argue that our operators are able to support a wide variety of interaction protocols, and so will be fundamental irrespective of which protocols are finally adopted.
K.4.4 Computing Milieux: Computers and Society - Electronic Commerce; I.2.4 Computing Methodologies: Artifitial Intelligence - Knowledge Representation Formalisms and Methods
Languages, Standardization
Semantic Web, E-Commerce, Matchmaking, Automated Negotiation, DAML+OIL, Service Description
Electronic commerce is having a revolutionary effect on business. It is changing the way businesses interact with consumers, as well as the way they interact with each other. Electronic interactions are increasing the efficiency of purchasing, and are allowing increased reach across a global market.
E-commerce is not a static field, but is constantly evolving. Initially, e-commerce involved the use of EDI and intranets to set up long-term relationships between suppliers and purchasers. This increased the efficiency and speed of purchasing, but resulted in lock-in in the relationships. Both suppliers and purchasers had to invest significantly up-front in the relationship, so were not easily able to move their business elsewhere. The technological relationship between the parties was a friction factor, preventing free competition in the longer term.
The second phase of e-commerce aimed to address this problem. With the increasing availability of the web, a more open e-commerce environment is developing, allowing businesses to trade more flexibly with each other. Some of this openness is achieved by competition between web portals, while some competition occurs within a single web portal, acting as a marketplace for buyers and sellers to meet. Some of the efficiencies of EDI can now be achieved in a more open environment, where relationships no longer need to be long-term.
However, there is a benefit of the EDI approach that is often lost in this new phase. Price negotiation was carried out in advance in the EDI world, so purchasing can be entirely automated. When a manufacturing planning and forecast system identifies the need for a purchase, it can initiate it automatically without any human involvement, increasing speed and efficiency. In phase two, each purchase may involve interaction with a new supplier, and so may involve new negotiation of terms. As a result of this, many of these purchases cannot be made automatically, and instead require human interaction, mediated by the web.
The third phase of e-commerce is just beginning. It aims to address this issue, allowing automated business interactions to take place in a fluid environment. Technology will no longer be a friction factor to changing supplier or customer. Long-term relationships will still play an important role, but they will persist because of the choice of both parties rather than technological lock-in. The key building blocks of this new world, e-services, will be able to interact dynamically with each other to create short-term or long-term trusted trading relationships.
The remainder of this paper is structured as follows. In section 2 we describe a framework for modelling the lifecycle of B2B e-commerce interactions. In section 3 we explore the phases of matchmaking and negotiation in detail, with particular attention to the operations that are carried out on the messages that participants exchange. In section 4, we identify the need for a declarative language for service descriptions, derive requirements for it and show that DAML+OIL satisfies them. We also present a set of example service descriptions used at various stages in the B2B e-commerce interaction lifecycle. In section 5, we specify the operations that are required during the B2B lifecycle, and demonstrate that they can be straightforwardly be implemented on a description logics reasoner. We then discuss related work (section 7) and we conclude presenting our future work intentions (section 8).
We have developed a lifecycle model to help us understand the interactions which take place between businesses engaged in e-commerce. This model (based on that in [19]) follows the lifecycle of an interaction between two (or more) parties and has the following stages:
If the third phase of e-commerce is to become pervasive, interactions throughout this lifecycle must be standardised by the industries using it. Standardisation must take place at three levels:
The ARPA knowledge-sharing project [25] was the first to tackle these standardisation issues, albeit in the domain of information exchange rather than e-commerce. Ontolingua [15] provides a tool for defining standard ontologies, KIF [12] a language for representing information and KQML [10] a set of messages for exchanging this information. The FIPA [11] agent standardisation effort has defined a messaging language, and protocols for conducting B2B interchanges such as auctions. While some of the ideas developed in these efforts are clearly important (such as the notion of advertising and facilitators), they do not provide appropriate primitives for defining the constructs used in e-commerce.
The focus of this paper is primarily on standardisation of B2B constructs (point 2). As a result of this, we assume the existence of appropriate domain-specific ontologies. We believe that the semantic web provides an opportunity to develop a service description language that can be used throughout the lifecycle of interaction, rather than just at the advertising phase.
In the industry standard arena, initiatives such as UDDI [33], ebXML [26] and WSDL [7] are gaining momentum. However, they offer limited support for ontologies, semi-structured data and constraints which are essential when modelling B2B constructs as we shall discuss in section 4, and have argued more fully in [32].
In this paper, we demonstrate that DAML+OIL [20] can be used to specify a highly expressive service description language. Such a service description language is sufficiently expressive and flexible that it can be used not only in advertisements, but also in matchmaking queries, negotiation proposals and agreements. We also identify which operations must be carried out on this description language if the B2B lifecycle is to be fully supported. We do not propose specific standard protocols, but instead argue that our operators are able to support a wide variety of interaction protocols, and so will be fundamental irrespective of which protocols are finally adopted.
In this paper, we focus on the first two stages of the e-commerce lifecycle presented above: Matchmaking and Negotiation. We now describe these phases in detail, showing the different interaction protocols that can be used. We identify commonalities between the different protocols, to allow us to develop a service description language and set of operators able to support them all. We also identify commonalities between the different stages, to allow the same service description language and operator set to support both stages in the lifecycle.
Matchmaking is the process whereby potential trading partners become aware of each other's existence [8]. A buyer wishing to purchase access to a service must locate potential service providers able to meet its needs. The buyer's requirements may initially be not fully specified, and the service providers may be able to offer a range of services. The process of matchmaking should not result in the service becoming fully specified: this is the purpose of the negotiation phase which follows. Instead, the matchmaking phase should result in a buyer (or service provider) having a list of potential trade partners, each with an associated partially specified service description. This description defines the set of possible services the provider can offer which are of interest to the buyer.
There are many different protocols which can be used to accomplish this. Work on information brokerage using KQML identified the majority of these [10]. Here, we list some canonical examples. For more, see [10] or the FIPA proposed standards [11].
Despite these different agent architectures and communication protocols that can be used to achieve the matchmaking process, we can identify clear roles which are common to all of them. We have a repository of information about services or service requirements, which is maintained by the repository host. Agents adopting advertiser role are willing to advertise descriptions of services in the repository. These are usually, though not always, service providers. (They may be buyers, advertising a service request, or may be marketplaces offering environments where such services can be traded.) Similarly, agents adopting the seeker role wish to locate appropriate advertisers. Seekers can query a repository, via the repository host, and may be able to browse the repository.
In the first matchmaking protocol described above, the buyer adopts the seeker role, and all service providers adopt the role of advertiser and repository host. However, the repository is local to the service provider, and only contains information about their own service offerings. The buyer must broadcast their query. In the second protocol, the buyer is both seeker and repository host. Instead of broadcasting their query, they make it locally. However, advertisements must be broadcast. In the third protocol, the facilitator agent plays the role of repository host. In the final protocol described above, the meta-facilitator is also a repository host, but uses the repository to direct a query rather than to respond immediately.
As [29] demonstrates, different protocols may be appropriate in different situations, depending on the expected message flow. Hence, it is not appropriate to standardise on a unique protocol for all agent systems. Instead, we should allow choice from a variety of such protocols, but standardise aspects of the roles which are common to all of them. Protocol specifications determine where information is stored, and how appropriate messages are passed to access it. Role specifications determine how the information is represented, accessed and used.
For the advertiser to place an advert, it must be able to specify the set of services it is interested in trading. In many cases, these services will not be fully specified immediately. Because of this, it needs a language which is rich enough to allow an abstraction of a service to be advertised, together with constraints over that abstraction. Similarly, for a seeker to make a query, it must be able to specify, as an abstraction together with constraints, the set of services it is interested in. When a query is made, this is treated as a constraint on the acceptable set of services to the seeker. The repository host must identify which advertisements are compatible with the query. An advertisement is compatible with a query if there is at least one instantiation of the advertisement which is also an instantiation of the query. The repository host responds with a list of all such advertisers and their advertisements. Ideally, it would also return an abstraction of a service, together with constraints, specifying the most general solution acceptable to both the seeker and the advertiser.
The negotiation stage of the e-commerce interaction lifecycle refines the abstract service specification from the matchmaking phase to a concrete agreement between two parties. Negotiation can be one-to-one, one-to-many or many-to-many, and as a result, many different protocols have been designed to carry this out. Negotiation protocols determine the interchange of messages which take place during negotiation, and the rules by which the negotiators must abide. One-to-one protocols include the shop-front, where a seller simply offers a good at a fixed price, and iterated bargaining, with buyer and seller taking turns to exchange proposed agreements. One-to-many protocols include the English auction, the Dutch auction and the Contract Net. Many-to-many protocols include the Continuous Double Auction and the Call Auction [34]. We now describe some example protocols in more detail.
The Contract Net protocol [30] defines two roles: manager and contractor. The manager has the responsibility of monitoring the execution of a task that can be split in many sub-tasks whose results are to be aggregated. Each of the contractors can assume the responsibility of executing one or more sub-tasks.
The manager advertises the task via a task announcement. Prospective contractors evaluate the announcement and can decide to submit a bid to the manager. The manager then sends an award message to one or more bidders, indicating that they have been selected to perform the task.
The announcement contains information such as criteria for eligibility of contractors (eligibility specification) a description of the task (task abstraction) and a specification of the bid format (bid specification).
The award specification contains a complete specification of the task to be executed. The Contract Net protocol also defines what happens in the execution phase, but in the context of our discussion only the negotiation phase is relevant. The Contract Net protocol doesn't specify the format of the information objects (eligibility specification, task abstraction and bid specification). The assumption is that manager and contractors will draw from a common ontology.
A one-to-one iterated bargaining process [28] consists of two participants playing the role of buyer and seller exchanging proposals between them. The proposals consist of a tentative agreement, with all parameters of the agreement specified. On receipt of a proposal, the recipient may respond by accepting, or may send an alternative proposal with different parameter values.
An English auction [21] defines the role of auctioneer (seller) and bidder (buyer). The auctioneer makes a description of the good for sale (good description) available to all bidders. It communicates to the bidders the minimum bid price that is requested to get the auction going (starting price) and the minimum increment over the current highest bid for a new bid to be accepted (bid increment). It also records private information about the minimum price that it is prepared to sell the good at (reservation price). The auctioneer then solicits progressively higher bids from the bidders until only one bidder is left. The winner claims the item, at the price they last bid.
In the same way we analysed the different protocols for matchmaking in section 3.1, we can analyse the different negotiation protocols and identify roles and behaviours common to all. Because of the rich variety of negotiation protocols available, this is more complex than the matchmaking case. We present our full analysis of the commonalities in [4], and use this analysis to define a general software framework for negotiation. This framework abstracts away from the particular message interchange required for a given protocol, and can be parameterised with rules to implement different protocols. Here we summarise this work, restricting our attention to commonalities of role and role behaviour.
From the analysis of the negotiation protocols presented above, and others, we can identify certain abstract roles, data structures and behaviours common to all. In each case there are at least two negotiation participants trying to make a deal with each other. In addition, there is at least one (possibly more) negotiation host, responsible for enforcing the rules of the negotiation and ensuring it goes smoothly. Before negotiation can begin, the parties have already agreed roughly what the negotiation is about (usually as a result of the matchmaking process). Hence, this places a restriction on the parameters and values to be negotiated. We call this restriction the negotiation template. The negotiation template refers to a common ontology accepted by all participants in the negotiation. It defines a schema for valid negotiation proposals that participants submit to each other. The schema declares which fields are admissible and how their values are constrained. A proposal is a further refinement of the negotiation space that represents a configuration of parameters that would be acceptable to the submitter. The result of the negotiation process is an agreement. That is a configuration of parameters that is non-ambiguous and can be used during the execution phase to instantiate the service. Therefore we can define the negotiation process as the process through which participants move from a pre-agreed negotiation template to an agreement, via an exchange of negotiation proposals. A single negotiation may involve many parties, resulting in several agreements between different parties and some parties who do not reach agreement. For example, a stock exchange can be viewed as a negotiation where many buyers and many sellers meet to negotiate the price of a given stock. Many agreements are formed between buyers and sellers, and some buyers and sellers fail to trade.
Revisiting the three example protocols described above, we can represent them in terms of our abstract roles and behaviours.
The contract net manager is both negotiation participant (as buyer) and negotiation host. The contractor is a negotiation participant (as seller). The bid specification within the task announcement defines the negotiation template, and the bids made by contractors are negotiation proposals. The award specification is the final agreement, determined by the contract net manager.
During iterated bargaining, there are two negotiation participants. One, possibly both, will also play the role of negotiation host (to ensure that the other party submits proposals at the appropriate time, in an appropriate format.) The negotiation template will be agreed prior to the negotiation, usually as the output of the matchmaking process. Each proposal is a fully instantiated version of the template, and when one party agrees to the proposal of the other, that proposal becomes the agreement.
In an auction, there is one seller participant (who remains silent after specifying the good for sale), many buyer participants, and the auctioneer who acts as the negotiation host. The negotiation template is fully instantiated to define exactly what good/service is for sale in the auction, except for the price which remains undetermined. The seller participant lodges a proposal with the auctioneer which states that they are willing to sell the good, and the minimum price they will accept. Buyers announce proposals, in the form of versions of the negotiation template with the price instantiated to their current bid. When no more proposals arrive, the last proposal is used as an agreement, provided the price is higher than the minimum price in the buyer's original proposal.
We now describe the three key actions which the negotiation host carries out during the abstract negotiation process presented earlier:
Much work has gone into standardising the different protocols used in negotiation (for instance [11]) though this (rightly) accepts that many different protocols must be available. However, these standards do not standardise the agreement formation process, or the validation process. We propose that these actions, which are common to all negotiations, should also be standardised. Hence we introduce a language for describing templates, proposals and agreements and operations on this language to carry out proposal validation and agreement formation. Furthermore, we design this language to be sufficiently general and flexible to cover the matchmaking phase.
In the previous section we have highlighted the information constructs that are exchanged in messages during matchmaking and negotiation, irrespective of what protocol is used. We have categorized them as advertisements, queries, negotiation proposals, negotiation templates and agreements. We have also identified the operations that are carried out on these constructs: matching, proposal validation, protocol checking and agreement formation. If these constructs and operations are to be standardised, we wish to build the constructs from a declarative language for describing services. Furthermore, we need to show that this declarative language can support the required operations over it. We now identify the requirements on this language, and then show that DAML+OIL satisfy most of these requirements.
A description language for the B2B e-commerce lifecycle should satisfy the following requirements:
DAML is a DARPA programme aiming to provide a language and tools for the semantic web. One the most promising technologies it has produced so far is the DAML+OIL [20] ontology language. DAML+OIL will serve as starting point for the design of the future Web Ontology Language from W3C.
DAML+OIL is a good candidate for the language we are looking for, and meets the requirements introduced in section 4.1:
reasoners Racer [16] and FaCT [17]) that can perform this operation on DAML+OIL descriptions.Furthermore, because DAML+OIL is expressed in RDF [23] and XML schema, it provides the added advantage that the many resources and toolsets developed for these technologies can be applied to the B2B interaction lifecycle.
In this section, we explain how we use DAML+OIL to describe the various descriptions that are used in the e-commerce lifecycle. While other more general efforts like [24] already use DAML+OIL in their service descriptions, we show here how DAML+OIL is suitable for e-commerce, and especially automated negotiation.
We recognise that service description ontologies and domain specific ontologies will have an important role to play in order to achieve the semantic level of agreement between the various parties. For the sole purpose of the following examples, we define a simple service description ontology along with an ontology for the sale and delivery of computers. To keep the descriptions concise, we have chosen to use the description logics notation which is equivalent to the RDF DAML+OIL syntax.
We now give an example for each description type. These examples will use the ontologies we have just defined.
An advertisement is expressed as a DAML+OIL class defined as the boolean combination of a set of restrictions over abstract properties and datatype properties. In Description Logics terms, advertisements are expressed as T-Boxes.
The following example shows an advertisement where R1 would like to buy some PCs. More precisely, R1 is advertising for the Sale and Delivery service. The restrictions over the Sale concept are that:
Since the advertiser is not interested in getting results of delivery services only, they chose not to describe their advertisement as being a Sale service and a Delivery service (i.e. by subclassing the intersection of Sale and Delivery), but rather as being a Sale service that has a Delivery service.
The restrictions on the Delivery service are the following:
In description logics notation, this advertisement can be written as:
As we can see from the ontology of the Sale service, we require both the buyer and the seller roles to be part of the information that is specified in the agreement. When submitting an advertisement, an advertiser who wants to play the role of a seller (resp. a buyer) should restrict the seller (resp. buyer) property to be its identifier. As the ontology shows, it is not forced to do so, but it is in its best interest. If it does not, it would be matched with advertisements of other sellers (resp. buyers). The seller (resp. buyer) can leave the buyer (resp. seller) property unconstrained, or can constrain it to be a certain subset or subcategory if they want to focus business on a certain set, for example, a pre-qualified set of trusted buyers. Advert2 above is made by seller 
who wishes to avoid doing business with buyer 
.
A Query is similar to an Advertisement. It is also a T-Box. We give an example of a Query where the seeker is looking for all buyers and sellers of PCs with an Athlon processor and who are also requesting or providing delivery.
After matchmaking, some parties can choose to enter into negotiation to determine the exact terms of service delivery. The negotiation template represents what is in common between all parties and is the starting point for negotiation. It also serves as a guide to scope the negotiation: negotiation proposals must comply with this template. In DAML+OIL terms, they would have to be subclass of this template.
As stated above, a negotiation proposal must be a subclass of the negotiation template associated with the ongoing negotiation. We now give an example of negotiation proposal which satisfies the template Template1:
When a negotiation terminates with an agreement acceptable to both parties, this agreement must specify the service that is going to be exchanged in an exact and non-ambiguous manner. Hence, whereas a negotiation proposal is a T-box, an agreement must be a fully-instantiated instance of the negotiation template. For this reason, we model an agreement as an A-Box.
In figure 1 we give an example in RDF syntax of an Agreement reached in a negotiation with Template1 as its negotiation template.
We now return to the operations over descriptions which we identified in section 3 as essential to support a variety of matchmaking and negotiation protocols. In this section, we present specifications of these operations, together with examples of their operation, and identify the core functionality required by a reasoner to execute them.
be the set of all advertisements in a given advertisement repository. For a given query or advertisement, 
, the matchmaking algorithm of the repository host returns the set of all advertisements which are compatible, 
:
, must initially check that it is valid. It is valid if it is a more constrained version of the negotiation template 
for this negotiation. In description logic, this means that the negotiation host must check that subsumes . Formally, this can be specified as:
be the set of all valid proposals currently registered with the negotiation host.
Protocol validation and protocol-specific aspects of agreement formation are beyond the scope of this discussion. For a full discussion of these operations, together with a rule-based approach to standardising them, see [4]. When an agreement is formed, it can be verified a posteriori that the agreement subsumes the proposals that were used to form it and therefore the original negotiation template.
Note that only two atomic operations are required to define the operations specified above:
)
).A standard description logics reasoner is able to carry out both of these. Satisfiability lies at the core of such a reasoner, as all other reasoning or inference techniques are transformed into satisfiability checks. The subsumption operator is already defined by the DAML+OIL subClassOf, because our service descriptions are expressed as DAML+OIL classes (i.e. description logics concepts). A description logics reasoner can check whether two concepts subsume each other [18]. Hence, a description logics reasoner provides a good platform to implement the operations required in the B2B e-commerce interaction lifecycle.
We have implemented a prototype matchmaking system, based on the FaCT [17] reasoner, operating on service descriptions in DAML+OIL. A full description of the prototype can be found in [13]. A prototype of our negotiation framework is described in [4]. In the current version, the negotiation framework prototype does not use DAML+OIL as a language for proposals. Work is underway to merge the two efforts in order to have a prototype based on DAML+OIL that supports both matchmaking and negotiation.
In terms of performance requirements, the matchmaking and negotiation phases are very different. To find a match for a particular advertisement, the reasoner needs to check the satisfiability of the intersection of the advertisement with each advertisement that has been previously submitted. With the dataset we have (around 100 advertisements and queries), the time spent by the reasoner is barely noticeable. We need to design a way to automatically generate large amounts of meaningfull data to put the system under a bigger load and study its beahaviour. For negotiation, the number of descriptions to manipulate is function of the number of participants in the negotiation. Compared to matchmaking, the negotiation phase uses few but more complex descriptions (which current reasoners can handle).
Before putting this system to the test of a real e-commerce problem, we would need a reasoner that supports datatype natively.
Work on service description for use in matchmaking is an important part of developing open agent-based systems. However, work on developing such description languages [31,2,22,27] has focussed on their application in matchmaking and brokering, ignoring the potential role of negotiation. Matchmaking is not used to locate potential trade partners, but rather to determine the functionality of another agent prior to execution. As a result of this, agents advertise exact specifications of their service (with some small amount of flexibility left to the discretion of the service user). This works for a cooperative community of agents, but will not work for a competitive environment such as in e-commerce. Instead, we treat the advertisement as an invitation to trade, and so it will be less constrained. Additionally, we define appropriate operations to support the negotiation phase, to refine an advertisement to a final agreement, and use the same service description language throughout this process.
DAML-S [1] is a core set of markup language constructs for describing the properties and capabilities of Web services, built on top of DAML+OIL. DAML-S markup of Web services is intended to facilitate the automation of Web service tasks including automated Web service discovery, execution, interoperation, composition and execution monitoring. DAML-S is complementary to our work and there is no reason why our work could not be based on DAML-S. One of the features of DAML-S we would benefit most is the support for process description. The service descriptions we are considering in this paper should be thought as the input and output parameters of a DAML-S Service Profile. The points we made in this paper that DAML+OIL allows to model quite complex descriptions of goods and services and that current reasoners allow to perform the necessary computational operations for the e-commerce lifecycle is hence also valid for DAML-S Service Profiles.
In this paper, we have presented an analysis of the B2B e-commerce interaction lifecycle in terms of roles, information constructs and operations necessary to carry out the interactions. We have argued that a variety of protocols can be used for matchmaking and negotiation, but that the same information constructs and operations can be used to support them all. For this reason, we advocate standardization of these constructs and operations, as opposed to standardization on a single protocol. We have assessed the requirements on an appropriate service description language for this, and have argued that DAML+OIL meets these requirements. We have shown how DAML+OIL can be used to represent advertisements, queries, negotiation templates, proposals and agreements. Furthermore, and more importantly, we have shown that the key operations necessary to support B2B interactions can be expressed in terms of satisfiability and subsumption - two operations which existing Description Logics reasoners are capable of executing. Hence, the Semantic Web provides an ideal framework for the standardization of the B2B e-commerce interaction lifecycle.
We have argued that constraint evaluation is also an important requirement to support this lifecycle. While some constraints can be expressed in DAML+OIL, existing Description Logics reasoners do not support all of these constructs. The Racer [16] reasoner has been enhanced with limited support for concrete domains (i.e. datatypes) and we plan to integrate it with our prototype.
Research on automation of negotiation requires the ability to assess the likely utility of a given advertisement or negotiation proposal. In our service description language, such proposals and advertisements can be complex structures. Up to now, most work on negotiation has assumed that only one parameter (usually price) is being negotiated. Some work has been carried out on multi-attribute negotiation (e.g. [9]) but this assumes a relatively simple utility model. If we are to be able to assign utilities to complex proposals, then research on tools to help people assess the value of different proposals (preference extraction) will be necessary. It will also be necessary to represent the relative utilities of a space of possible proposals. The application of Multi-Attribute Utility Theory to negotiation [3] is a promising approach to do this. We are currently working on ways of extending this work to assign utilities to complex service descriptions.
In this paper, we have not addressed the operations involved in moving from the matchmaking phase to the negotiation phase. If only one matchmaking query is made, and only one advertisement selected, then this process is straightforward: the negotiation template is taken to be the intersection between the query and the advertisement. However, if many queries are made and many advertisements are matched, then the problem becomes more complex. Clusters of potentially compatible participants must be formed, together with appropriate negotiation templates. We hope to explore this issue in the future.
