CURTIN
University of Technology
Department School of Computing
Masters by Research in Computer Science
Project Supervisor: Andrew Marriott (raytrace@cs.curtin.edu.au)
Project Supervisor: Tim McGrath (tmcgrath@portcomm.com.au)
Project Student: Sacha Schlegel 1
Student ID: 12253634
E-Mail: sacha@schlegel.li
Document
The purpose of this research is to find an algorithm to form an ebXML Collaboration Protocol Agreement (CPA) from two ebXML Collaboration Protocol Profiles (CPP) at three levels. First level is an algorithmic process which parses two CPPs and creates a draft CPA. Different information elements in both CPP are related so the algorithm has to find matching elements. The second level is an automated negotiation system which negotiates over negotiatable elements of a CPA. The third level is a basic human based web-enabled negotiation system to finalise the CPA. Algorithms and negotiations are used in this research.
The objective is to provide free tools which allow the creation of a valid CPA from two CPP's. These are algorithms and a negotiation system for an automated negotiation.
The research methodology is more quantitative than qualitative and also of type ``design and demonstration''. An evaluation of the tools will be done by an expert.
The results will go into the summary in the masters thesis and the source code will be contributed to an open source ebXML project. The intelectual property (IP) will be held by the researcher. There does not exist a free ebXML CPA formation tool and this research can provide a CPA formation prototype. The results of this research can be used in further research in real world CPA formation.
This candidacy report summary states the objectives of this research followed by background information of electronic business and artificial intelligence (software agents and negotiation). After the significance of this research, the research methodology is shown. The ethical issues are presented and information about facilities and resources, data storage and a time line are provided. The summary finishes with a definition of terms and the references.
The purpose of this research is to find an algorithm to form an ebXML Collaboration Protocol Agreement at three levels (see 5.1 for three level details).
``CPA formation'' is a way to get a CPA from two CPPs or from a CPA template. Electronic business-to-business is about exchanging electronic information whereas the choreography and structure of the messages are clearly defined in the collaborative business processes. In the electronic age of doing business not only the business processes have to be defined but also technical attributes for the underlying executing software systems such as network, data channels, messaging, transportation and encryption. The question of how to reach this agreement leads to the statement of the research problem as:
the problem of this research is how to negotiate, calculate or form a CPA from two CPPs or a CPA template.
The aim of the research is to develop a CPA formation tool as proposed in various ebXML specifications (10,5,7,15).
The concrete outcome of this research will be:
The idea of electronic data interchange was stated as ``conducting inter-organisational transaction electronically'' (20). EDI is computer-to-computer communication based on standard business transactions in a standard form.
EDI has several normative benefits such as cost reduction and strategic benefits such as improved document handling and document processing. Typical economic transaction costs are, ``searching for a supplier; drafting, negotiating and safeguarding a contract; or adapting to contract misalignments, settling arbitration disputes, and establishing secure commitments'' (Williams (1975, 1985) in Krcmar et al. (20)). EDI also has strategic benefits such as the know-how from a thorough internal analysis of how the current business processes work. From such an analysis, time consuming, complicated, redundant business processes can be reengineered and optimised or even removed. Once ``optimal'' internal business processes are achieved and in place, then inter organisational projects can be approached.
High costs such as setup costs, EDI message translation costs, private network subscription and transaction costs, are a serious problem with EDI implementations so only big companies are able to use EDI. Value-added private EDI networks provide the following services: Mailboxing (incoming and outgoing EDI message queues), protocol conversion, standard conversion, implementation assistance, auditing, message tracking, archiving, query status, reporting, billing, security and more (12).
EDI embraced new web technologies such as Hypertext Transfer Protocol (HTTP) and Hypertext Markup Language (HTML) and private networks could be replaced with Internet network connections (12).With Web-based EDI the party without an EDI system reads and writes data through a webbrowser and a webserver, which is connected to an EDI system.
With XML EDI the message sent between sending EDI system and receiving EDI system is structured in Extensible Markup Language (XML). XML is used to define expressive data structures and is a world wide web consortium4 standard. The advantage of using XML EDI is to have a broad range of XML parsers available (also as free software). Conversion from EDI message structure to any other message structure can be done with the use of Extensible Stylesheet Language Transformation (XSLT) processors.
EDI, Web-based EDI and XML EDI are all steps forwards but still the SMEs (Small to Medium Enterprises) could not be part of the community as they should. Different approaches around the world to tackle the significant shortcomings of EDI (high costs, complexity, know-how) occured everywhere.
Electronic Business XML (ebXML) stands for electronic business XML and is one such new initiative. ebXML is a joint initiative by the United Nations Centre for Trade Facilitation and Electronic Business (UN/CEFACT)5 and the Organisation for the Advancement of Structured Information Standards (OASIS)6. It is not only an XML vocabulary but a general guideline and framework of how to achieve global electronic business. ebXML concentrates on collaborative business processes, which are inter-organisational business processes (9).
A Collaboration Protocol Profile (CPP) is a companies capabilities whereas the Collaboration Protocol Agreement (CPA) is a final agreement of how to do business between two trading partners (10). An ebXML registry/repository is used to store CPPs and allows companies to query for CPPs (8). Once company A has found a suitable CPP (a capable business partner) a CPA can be formed (please see the technical architecture specification (9) for an ebXML scenario).
The CPP references the intended Collaborative Business Processes and the roles the company will play in this business process, plus technical aspects such as transportation (e.g. HTTP, HTTP over Secure Socket Layer (SSL), File Transfer Protocol (FTP)), messaging such as Simple Object Access Protocol (SOAP) with attachments and security constraints such as digital signatures, certificates, and non-repudiation. A Collaborative Business Process is defined is modelled using UN/CEFACT Modelling Methodology (UMM) (14), which is based on the Unified Modelling Language (UML) (26). In the first place one or many CPP's have to be created for each company with the help of specified worksheets (25).
In the early days of electronic business, EDI used the concept of a trading partner agreement (TPA). Dan et al. (6) describe a TPA as ``...contracts that define both the legal terms and conditions and the technical specifications that both partners must implement to put the electronic trading relationship into effect.''. Further the paper notes that ``In business-to-business electronic commerce, there is a need to agree not only on the traditional terms and conditions but also on Information Technology (IT) procedures ranging from communication protocols to business protocols.''.
In ebXML the CPA is not only the technical agreement between the two companies but also the configuration (script) for the Business Service Interface (BSI). A BSI does the ebXML message handling, based on the ebXML Message Service Specification (11) and interacts with the internal business infrastructure/architecture.
This idea of having an executable CPA is very useful considering that a company might have 100 or more different CPA's (24). In this way the company can ``just'' load the new CPA within the BSI system and the BSI system from then on has another CPA installed. Of course the interaction between the BSI and the internal business infrastructure has to be implemented as well (kickstart or update an internal business process).
ebXML does not specify how to get the CPA but provides some useful information. The ebXML technical architecture document (9) says: ``A CPA is negotiated after the Discovery and Retrieval Phase ...An eventual goal of ebXML is to facilitate fully automated CPA generation.''. The Collaboration Protocol Profile and Agreement Specification document (10) says: ``This specification defines and explains the contents of the CPP and CPA XML documents. Its scope is limited to these definitions. It does not define how to compose a CPA from two CPPs nor does it define anything related to run-time support for the CPP and CPA.''. Further Appendix F says: ``The detailed procedures for CPA formation are currently left for implementers. Therefore, no normative specification is provided for algorithms for CPA formation.''. A typical normative specification would be a concrete algorithm. Some non-normative information is provided in the ebXML specifications (10,5,15).
There are two ways to get a CPA: either from two CPP's or from a CPA template. The later situation will be the case when one trading partner is ``dictating how to do business'' or when it is just easier for the smaller company to ``fill out'' the missing parts of a CPA template. The small company still needs the possibility to run an ebXML BSI and configure it with the CPA. Currently very little research is done in this problem area and this thesis will add some new knowledge.
At this point some background information on negotiation, which is part of the CPA formation is provided. Negotiation is a topic in computer science in the disciplines of Artificial Intelligence (AI) in particular with the sub-disciplines Intelligent Software Agents and Distributed Artificial Intelligence (DAI) with Multi Agent Systems (MAS).
After many years of philosophical and psychological research into the area of intelligence, with the invention of the computer, a new research area was born in 1956, called Artificial Intelligence (AI) (27). The driving philosophical research question was how man sees, learns, remembers and reasons. Computer scientists started to explore these questions with the aid of computing power.
Weiss (27) lists four main categories of AI: systems that think like humans, systems that act like humans, systems that think rationally, and systems that act rationally. The category ``systems that think like humans'' has several disciplines including natural language processing, knowledge representation, automated reasoning, machine learning, computer vision and robotics. The key processes of AI are problem solving, planning, decision making and learning (27).
Distributed Artificial Intelligence (DAI) is a sub branch of AI and is split among multi-agent systems and distributed problem solving systems. Distributed problem solving systems decompose a task and then synthesis a solution.
Some AI research was applied in the business world; business expert system and decision support systems. According to Holsapple and Whinston (16), a business expert systems has two cornerstones: the ability to understand natural language and the ability to reason.
Bradshaw (3) gives a very good introduction to intelligent software agents, one of the disciplines of artificial intelligence researchers. There are many views on software agents. Some attributes of the agents are: interaction and communication, decomposition and distribution of tasks, co-ordination and co-operation as well as conflict resolution via negotiation. Reactivity, autonomy, collaborative behaviour, communication ability, inferential capability, temporal continuity, personality, adaption and mobility are attributes an agent can have. Furthermore agents can be defined by intelligence, mobility and agency. Software agents are useful for simplifying the complexities of distributed computing (17). Another common definition of software agent is that ``an agent is a pro-active software component that interacts with its environment and other agents'' (13).
An attribute of an agent system is whether the agents are cooperative or non-cooperative (also called competitive). Cooperative agents are software agents working together in order to achieve a common higher goal (1). A cooperative agent is non-selfish whereas a competitive agent is self-interested. Non-cooperative or competitive agents have different goals. If two competing agents have negotiation capabilities, it is possible that they achieve an agreement. One of the main questions within Intelligent software agents research is ``When and how should agents interact - cooperate and compete - to successfully meet their design objectives'' (27).
A multi-agent system (MAS) is a software system where multiple agents interact with each other and is researched for over two decades (22).
Even in ebXML literature software agent are mentioned to be eventually the actors in a CPA negotiation.
Beam and Segev (2) define negotiation in electronic commerce as ``the process by which two or more parties multilaterally bargain resources for mutual intended gain, using the tools and techniques of electronic commerce''. Oliver in Beam and Segev (1) uses the following definition: ``negotiators jointly searching a multi-dimensional space and then agreeing to a single point in space''. Lomuscio et al. (22) use the following definition: ``Negotiation is the process by which group of agents communicate with one another and to try to come to a mutually acceptable agreement on some matter''. Kersten and Lo (19) say: ``The complexity of negotiation processes and the difficulty that they pose to participants are behind many efforts in constructing analytical models and negotiation support systems''.
It is important to mention, that in a negotiation it shall always be possible to not get an agreement. Real negotiation about anything and everything is called bargaining. Offers and counter-offers are typically bargaining negotiations. When looking at negotiations we see that there is the negotiation process and the negotiation strategy. Lomuscio et al. (22) say about negotiation strategies: ``Negotiation strategies and their corresponding properties depend heavily on the specific characteristics of the scenarios under consideration'' and call variables of the negotiation itself the negotiation space. This quote leads to the assumption, that a generic negotiation implementation is complex.
Auctions are seen as a subset of negotiations where process efficiency, ease of use, reach and the ability to have auctions in parallel with a very large number of bidders are important features Kersten and Lo (19). The problem with auctions is the fixation on the price, which is the main target of this kind of negotiation. Most often the goods auctioned are well-defined objects like a car, a house, or a chair.
Kersten and Lo (19) define a Negotiation Support Systems (NSS) as: ``NSS are designed to help and advise negotiators; they are used to structure and analyse the problem, elicit preferences and use them to construct a utility function, determine feasible and efficient alternatives, visualise different aspects of the problem and the process, and facilitate communication.''
There are process driven NSS and solution driven NSS. Process driven NSS provide the infrastructure to guide the participants through the negotiation process. A solution driven NSS is concerned with the outcome of the negotiation itself, and provides the tools for the parties to make offers and evaluate offers (counter-offers).
The more the NSS is tailored to a specific negotiation (CPA negotiation in this case) the more support the system can provide for the negotiators. Of course negotiators' personal charm and negotiation skills have less influence during an electronic negotiation. If software agents are actors of a NSS, they need intelligence to pursuit a negotiation strategy.
Negotiation can be seen as a game and game theory is the study of how rational people make their decisions. Game Theory results from studies in schools of economics. Osborne and Rubinstein (1994) in Bui (4) describe game theory as: ``Game theory is a bag of analytical tools designed to help us understand the phenomena that we observe when decision-makers interact. The basic assumptions that underlie the theory are that decision-makers pursue well-defined exogenous objectives (they are rational) and take into account their knowledge or expectations of other decision-makers' behaviour (they reason strategically)''. A typical competitive game is called prisoners' dilemma (see Bui (4) for a short overview of game theory). In non-cooperative (competitive) games there are no pre-game agreements allowed, as opposed to cooperative game theory where players can build coalitions in the pre-game phase, in order to increase their chances to reach their goals (1).
Negotitation, negotiation support systems and mathematical calculations based on game theory can be applied to the CPA formation problem.
The research methodology is more quantitative than qualitative (21). The official ebXML specifications are the strict guidelines for this research and the findings will be a collection of software tools including algorithms and a negotiation system. The official ebXML example data (CPPs) will be the core input data. A comparison between the official ebXML output example (example CPA) and the output of this research will go into the summary in the thesis.
The research is also of type ``design and demonstration'' research methodology (23). The research will construct and describe a new operational software system. A formative evaluation of the usefulness of the outcome will be conducted by a qualified person or company. The concrete evaluation procedure and test cases are not defined yet.
The CPA formation process in three levels:
(CPP from partner 1), 
(NDD from partner 1), 
(CPP from partner 2) and 
and two output files: a draft CPA and a log file. The algorithm has to consider all four files. In the first run the algorithm will just consider and and check the following CPP specific elements and element relations: 1) business collaboration process reference and corresponding role elements, 2) bindings, 3) transportation, 4) packing, 5) security, 6) signals and 7) protocol patterns. In the second run the algorithm will further take the NDDs into account, besides the CPPs, and will try to match values from the NDDs and CPPS for which no negotiation is necessary. Visualisation of problem areas in the draft CPA will be made available in the form of a log file. The algorithm will detect problem areas and mark them as such, but will pass over the problem area and continue to finish the job.
, , , and level-1-CPA. According to the bootstrap negotiation process (boot-NCPA) the later negotiation process will be negotiated (real-NCPA) first. Both services then need access to the real-NCPA. A general algorithm has to be implemented, which parses the boot NCPA and a simple NCPA, and acts accordingly. Offers and counter-offers (updated draft CPA or differences) will be exchanged. The service which does the negotiation will have to implement a negotiation strategy. After some time the negotiation will be either successful, not successful or partly successful. The artefact (latest CPA, including problem areas log file), are input for level three of the CPA formation process.
The researcher provides a working computer. The school has to provide Internet access and a study desk. At this stage no additional software is necessary. The researcher shall only use free and open source software including the programming language, development environment, documentation tools, operating system, system tools, web server, dynamic web pages and more.
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.48)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -dir documents/www_onefile -t 'Candidacy Report' -split 0 -custom_titles -local_icons -no_footnode -address 'author: Sacha Schlegel' -auto_navigation -index_in_navigation -show_section_numbers candidacy_report
The translation was initiated by Sacha Schlegel on 2002-10-21