UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Sanp : a communication level protocol for supporting machine-to-machine negotiation in organization Chang, Man Kit 1991

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata


831-UBC_1991_A6_7 C33.pdf [ 3.27MB ]
JSON: 831-1.0098502.json
JSON-LD: 831-1.0098502-ld.json
RDF/XML (Pretty): 831-1.0098502-rdf.xml
RDF/JSON: 831-1.0098502-rdf.json
Turtle: 831-1.0098502-turtle.txt
N-Triples: 831-1.0098502-rdf-ntriples.txt
Original Record: 831-1.0098502-source.json
Full Text

Full Text

SANP: A C O M M U N I C A T I O N L E V E L P R O T O C O L F O R S U P P O R T I N G M A C H I N E - T O - M A C H I N E N E G O T I A T I O N IN O R G A N I Z A T I O N By Man Kit Chang B. B . A . , The Chinese University of Hong Kong, 1987 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S M A N A G E M E N T I N F O R M A T I O N S Y S T E M S We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A September 1991 © Man Kit Chang, 1991 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may' be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of MANAGEMENT INFORMATION SYSTEMS The University of British Columbia Vancouver, Canada D a t e nPTORRT? R r 1991 DE-6 (2/88) r Abstract Organizations are distributed systems where agents (workers, departments, etc.) cooper-ate with one another to achieve organizational goals. However, conflict is also an inherent component of the process. In designing computer systems which aim to automate orga-nizational activities, we need to consider the conflicts among agents and how they can be resolved. Distributed Artificial Intelligent (DAI) researchers have long been interested in the question of how to resolve conflicts among cooperative agents in distributed problem solving environments. Negotiation has been suggested by many researchers as an impor-tant technique to resolve conflicts. However, most of the existing negotiation protocols used in DAI systems are inflexible. Actual protocols rarely take into account the re-sults from negotiation research. In this paper, we propose a negotiation protocol, S A N P (Speech Act based Negotiation Protocol), that is based on Ballmer and Brennenstuhl's speech act classification, and on the negotiation analysis literature from other disciplines. S A N P is a flexible protocol that supports multi-level negotiations between two parties. In addition, S A N P also allows third party arbitration if the parties involved in the nego-tiation cannot resolve the conflict themselves. The protocol is implemented as a domain independent system using Strudel which is an electronic mail toolkit for managing elec-tronic mail based conversations. A small study was conducted to test the protocol. A number of limitations of the protocol have been found in this study. Suggestions on how to improve the protocol are also discussed in this thesis. ii Table of Contents Abstract ii List of Figures v Acknowledgement vi 1 Introduction 1 1.1 Organization, Conflict, and Negotiation 1 1.2 Goal of the Thesis 3 1.3 Outline of the Thesis 3 2 Related Work 4 2.1 Contract Net Protocol 5 2.2 Multistage Negotiation Protocol 5 2.3 Commitment-based Communication Model 6 2.4 Partial Global Planning ; 7 2.5 P E R S U A D E R 8 2.6 Summary 9 3 Speech Act Theory 11 3.1 Why Use Speech Act Theory . 11 3.2 Searle's Speech Act Classification 12 3.3 Ballmer and Brennenstuhl's Speech Act Classification 14 3.4 The Struggle Model 16 in 3.5 Some Remarks 18 4 S A N P : The Negotiation Protocol 20 4.1 Principles behind SANP 20 4.2 A Communication Level Protocol for Negotiation 23 5 A n Example Application 27 6 Implementation and Test Use 31 6.1 Implementation 31 6.2 Test Uses 34 6.2.1 Design of the Study 35 6.2.2 The Study 36 6.2.3 Discussion 37 7 Conclusion 40 7.1 Thesis Contributions 40 7.2 Limitations of the Protocol and Future Research Directions 41 Bibliography 43 Appendices 46 A Descriptions of the SANP Protocol 46 iv List of Figures 3.1 Relation between Models (Adapted from Figure 4.19 in [2]) 15 3.2 Differences among 4 linguistic functions. (Adapted from Figure 4.20 in [2]) 16 3.3 Examples of speech act verbs in selected categories. . 18 5.1 An example dialogue for the budgeting example (part 1 of 2) 28 5.2 An example dialogue for the budgeting example (part 2 of 2) 29 6.1 Screen Dump for "Make Claim" Conversational Move 33 6.2 Conversational Move Type Definition for "Make Claim" 34 v Acknowledgement This thesis is dedicated to the memory of my father and mother. I would like to extend my greatest gratitude to Dr. Carson Woo, my thesis supervisor. Without his brilliant ideas and guidance, this thesis would not have been made possible. He not only gave me support in my academic research, but also showed great care and concern for problem of a personal nature. He is the kind of professor that I have really enjoyed and appreciated working with. I would also like to thank Dr. Richard Rosenberg and Dr. Andy Trice who took the time to sit on my thesis committee and to provided me with excellent feedback. I would also like to thank the following people for their helpful support of my thesis work: Thomas Hofbauer, Dr. Marius Janson, Enn Kiudorf, Feng Lu, Tanom Suravong-trakul, Clarence Martens, and Dr. Yair Wand. Special thanks are given to Enn Kiudorf and Francis Leung, who helped proofread the final draft of this thesis. I am most grateful to all the members of my family who have given me love and supports. Without them, it would have been impossible for me to achieve this work. The author is a member of the Institute for Robotics and Intelligent System (IRIS) and wishes to acknowledge the support of the Networks of Centres of Excellence Program of the Government of Canada, the Natural Science and Engineering Research Council, and the participation of P R E C A R N Associates Inc. vi Chapter 1 Introduction 1.1 Organization, Conflict, and Negotiation Organizations are open systems1 that are composed of many interdependent and in-terconnected subsystems [14, 15]. To accomplish organizational goals, work has to be distributed among agents (i.e., employees, departments, etc.) and their effort has to be coordinated in the direction of reaching the goals. However, each agent may have his own goals which may be inconsistent with the goals of others. In addition, agents can receive incomplete and inconsistent information from outside the system, or from dif-ferent parts within the system, and they develop their own viewpoints and beliefs that may be incompatible with the beliefs of other agents. Agents may also have different interpretations of the same situation caused by different personal knowledge and beliefs [12]. Hence, conflict is inevitable. For example2, an organization may have a goal of increasing profitability. The marketing department may suggest increasing the adver-tising expenditures in order to gain market share, which will in turn increase revenue. Conversely, the finance department may suggest cutting advertising expenditures in or-der to cut costs. This example illustrates the point that even though agents may have the same goal, they may still be in conflict because of different beliefs that they hold. Different kinds of conflict may arise [22]: (1) conflict of interest when two agents compete for scarce resources; (2) conflict of value; (3) cognitive conflict when two agents differ in 1 Although we wil l not directly deal with open systems in this thesis, some of their characteristics affect the method of conflict resolution. 2 Adopted from [14] Chapter 1. Introduction 2 their thought processes or perceptions; and (4) goal conflict when the desired outcomes of two agents differ. How can conflicts among cooperative agents be resolved in open distributed problem solving environments? Many methods have been proposed to reconcile disparities among agents [3]. Among them, negotiation has been suggested by many researchers as an important method to resolve multiagent conflicts in open systems [3, 7, 12, 14, 15, 27] in which no central authority and no 'globally correct answer' exist [12]. Negotiation is a process of communication between agents in which conflicting goals are reframed, conflicting issues are identified and narrowed, alternative solutions are proposed, attacked, and defended, and agreements are reached and confirmed [21]. A l l these functions should be provided if we want to support negotiation between agents to resolve conflicts in an organizational information system. It is important that agents can present arguments that support their beliefs and goals, so that the other party in the negotiation process can understand the rationale of the beliefs or claims. The articulation of the arguments may help to identify issues on which the parties disagree, and may also subsequently help to solve the problem. In order to automate negotiation in organizations, a communication protocol should be used to guide the communication between two intelligent agents. A number of nego-tiation protocols have been proposed in the Distributed Artificial Intelligent (DAI) area [6, 7, 9, 28]. However, most of them do not support many of the functions of negotiation mentioned in the previous paragraph. They tend to be inflexible and their design is not based upon any existing negotiation model or research. Therefore, there is a need to develop a flexible negotiation protocol that supports organizational work. Chapter 1. Introduction 3 1.2 Goal of the Thesis The primary objective of this thesis is to develop a flexible communication level protocol for negotiation. A communication level protocol is used to guide the conversations or negotiations among agents without concerning the domain dependent knowledge or con-tents of the conversations. The results from negotiation research and Speech Act Theory are used to guide the construction of the protocol. The protocol is designed to support: • two party negotiation • machine to machine negotiation • simple, semi-structure, and single issue negotiation We have implemented our protocol using Strudel, a high level communication toolkit, in order to test out the protocol. Uncontrolled and limited test uses were conducted to study the limitations of our protocol. 1.3 Outline of the Thesis In Chapter 2, we review the related research projects that use negotiation to coordinate distributed problem solvers. Chapter 3 describes Ballmer and Brennenstuhl's speech act classification. Our proposed negotiation protocol is presented in Chapter 4. An example application will be given in Chapter 5. Chapter 6 describes the implementation and the test uses. Chapter 7 outlines the contributions of this work, the limitations of our protocol, and possible future research directions. Chapter 2 Related Work Distributed Artificial Intelligence (DAI) researchers have long been interested in how to resolve conflicts among cooperative agents in distributed problem solving environment. Different methods have been used to reconcile disparities among agents. Some of them avoid dealing with the problem of conflict among agents by assuming that cooperative agents are benevolent, agreeable with each other, and ready to adapt each other's goals. On the other hand, some of the systems use centralized authority to resolve conflicts among agents [11]. However, these methods are not applicable to open systems because there is no central authority in open systems and agents do not always agree with each other. In open systems, negotiation has been recognized as an important method to resolve agents' conflicts [14, 15]. Moreover, the need for communication protocols is recognized by researchers in the DAI area. Compbell and D'Inverno [4], for example, suggest that communication protocols can be used to control excessive communication between agents that use a great deal of computer resources. A communication protocol is a set of well defined rules and conventions that are used to control data transfers in computer systems [5]. Several researchers have proposed negotiation protocols and frameworks to support the cooperation of distributed problem solvers or agents. Some of these are Contract Net Protocol [7, 16, 27], Multistage Negotiation Protocol [6], Partial Global Planning [9, 10], and P E R S U A D E R [28]. In this chapter, we will take a critical look at these protocols. 4 Chapter 2. Related Work 5 2.1 Contract Net Protocol Contract Net Protocol [7, 27] is a negotiation protocol used when distributing tasks to distributed problem solving nodes. In other words, the task assignments are treated as negotiation of contracts between nodes. Negotiation is viewed as "a discussion in which the interested parties exchange information and come to an agreement" [7]. It is an interactive process involving two-way transfers of information, evaluation of information by nodes using their local knowledge, and finally the reaching of an agreement by mutual selection [7]. There are two roles that the nodes can take in this protocol: manager and contractor. The negotiation involves the following steps: a manager announces the task which has to be done to contractors, the contractors listen to the announcements and use their local knowledge to evaluate their interest of biding the task and to determine their capability of processing the task, the interested contractors submit bids to the manager, the manager evaluates the bids and awards the task to the most suitable contractor. Davis and Smith took a very simplistic and restricted view of negotiation. They regard negotiation as a one time two-way exchange of information and a mutual selection process. The protocol does not provide any room for compromise and the generation of alternative solutions. The nodes involved in the negotiation do not communicate the reasons and assumptions of their decision; therefore, there is no way to detect the cause of conflict if it arises. 2.2 Multistage Negotiation Protocol Conry et al [6] introduces a Multistage Negotiation Protocol which is used to resolve resource allocation conflict. It can be viewed as a generalization of the Contract Net Protocol. This protocol allows iterative exchanges of information which is an improve-ment over the Contract Net Protocol. This negotiation protocol provides means for the Chapter 2. Related Work 6 communicating agents to acquire knowledge about the impact of local activity on nonlo-cal states and to modify its behavior accordingly. The negotiation process is as follows: each agent generates its own plan locally, contracts are tendered to other agents if the agent needs helps from other agents in order to fulfill its plan, other agents will either send a confirmation back if the requests are compatible with their local plan or they will send back information reflecting nonlocal resource conflict, the agent will modify its plan in light of the new information in the later case, and the whole process will start again. The process continues until a consistent set of choices can be confirmed. The only kind of information exchanged in this protocol is whether there are goal conflicts between agents. Although this is useful for the domain that the protocol is de-signed for, it is not flexible enough for other problems which require not only considering goal conflicts, but other kinds of conflict, such as conflict of interest and cognitive conflict as mentioned in Chapter 1. 2.3 Commitment-based Communication Model Koo [16] recognizes that the bidding process used in the Contract Net protocol for task assignment may be useful in the distributed problem solving environment, but it is not appropriate in the office setting. Therefore, he extends the Contract Net Protocol to a Commitment-Based Communication Model to synchronize agents' plans and to keep track of agents' commitments in distributed office environments. In this model, agents form agreements with one another in order to perform certain tasks and to ensure the coherent execution of their plans. The agreements or contracts between agents are formed by negotiation. The negotiation process involves: One agent, the asker (. . .) , starts the process with a request to another agent, the doer (. . .). The doer can reject, accept the proposal by asker, Chapter 2. Related Work 7 or counter-propose to the asker with modified proposal. If the doer accepts it, then both agents have committed themselves to a contract. If the doer reject its, the process terminates. However, when the doer counter-proposes, the decision is left to asker. The asker has the same set of choices as the doer had. The process continues until one of the agents rejects or accepts the proposal. [16] This negotiation protocol is more flexible than the Contract Net Protocol since it allows agents to compromise by exchanging counter proposal. Agents can alter a proposal by adding new terms to it or by qualifying the terms in the proposal with other terms. However, this protocol allows agents to exchange information only at one level—the proposal level. No reasons can be supplied to support their counter proposals. 2.4 Partial Global Planning Partial Global Planning [9, 10] is another framework designed for cooperating distributed problem solving nodes or agents. Negotiation, in this framework, is viewed as a "process by which autonomous nodes coordinate their views of the world and act and interact to achieve their goals" [10]. Individual nodes use local knowledge to form their own node-plan. Then, they selectively exchange node-plans with each other. Based on the model of itself and others' node-plans, nodes form Partial Global Plans (PGP). "Partial Global Plans represent expectations about how nodes could coordinate their actions and inter-actions along with the context (individual objective, plans, and relationships) that led to those expectations" [10]. Negotiation is viewed as the process of exchanging P G P infor-mation so that different nodes generate increasingly similar expectation (PGPs). Nodes in conflict will form a compromised P G P with the most up-to-date information from Chapter 2. Related Work 8 each of their PGPs. The Partial Global Planning framework is very similar to the Mult i -stage Negotiation Protocol. Both involve the exchange of partial plans and incremental refinement of nodes' local plans. They try to gain more global knowledge through the information exchange to construct their own plans. In this model, conflicts can always be resolved by forming compromised P G P using the most up-to-date information. The P G P protocol suffers the same problem as Koo's protocol—it only allows agents to negotiate at a fixed level. In this case, agents can only exchange partial global plans which are the products of the reasoning process. They cannot communicate the criteria or assumptions they used to make the decisions. 2.5 P E R S U A D E R One of the systems that does allow negotiation at different levels is the P E R S U A D E R [28]. The system uses a mediated negotiation model based on an integration of case-based reasoning and multiattribute utility theory to generate proposals and counterproposals based on feedback from the other party. Persuasive argumentation can also be generated to change the other party's mind. In this system, a mediator is used to control the process of negotiation. The mediator generates the initial proposal for the two parties to evaluate locally. If both parties accept the proposal, then it is the final compromise. If one of the parties rejects it, the mediator decides whether to change the proposal or to use argumentation to change the mind of the disagreeing party. Although the system provides good support for negotiation, it is not exactly a negotiation protocol. It is more like a negotiation support system. Also, it does not support many strategies that can be used in negotiation, such as delaying the discussion. Chapter 2. Related Work 9 2.6 Summary We have looked at different protocols that have been used in the DAI area. We would like to point out some of the common characteristics of these protocols. First, most of these protocols (except P E R S U A D E R ) view negotiation as a process of exchanging contracts or plans that result from planning or reasoning processes. In this case, each agent will have a better idea of what other agents plan to do and adjust their plans accordingly. These protocols suffer the problem of inflexibility in that they only allow agents to negotiate at a fixed level. That is, agents cannot negotiate the selection of a particular action, assumptions, and criteria of decision making. As Bond and Gasser [3] point out, negotiation "in general may shift to multiple level of meta-negotiation, and to negotiating over assumptions", we need a more flexible protocol to reflect this requirement. In addition, the design of these protocols is not based on any theory or model of negotiation, nor does it result from an analysis of negotiation processes. The protocols are only designed to solve the problem at hand, and they are not general enough to be used in other problem domains. Most of the protocols are designed for solving the problem of task assignment, so it is difficult to apply these protocols to the organizational environment to support the negotiation of distributed workers as recognized by Koo [16]. For example, while establishing policies or constructing budgets, it may not be easy to gain consensus by only exchanging plans. Another problem of the existing protocols is that they take a very simplistic view of negotiation. They do not support many tactics that are used in negotiation. For instance, when an agent lacks information it may request a postponement of the negotiation until it gets the necessary information. Another tactic that can be used is to request an arbitration if the parties involved in the negotiation cannot resolve the conflict themselves. Chapter 2. Related Work 10 However, none of these tactics are being supported by the existing negotiation protocols. In the next two chapters, we shall try to describe a more flexible negotiation com-munication protocol which can provide a broader range of support for negotiation. The protocol is derived from the analysis of the actual negotiation process and is based on the speech act classification of Ballmer and Brennenstuhl [2]. Chapter 3 Speech Act Theory The existing protocols used in the DAI area and their shortcomings have been reviewed in the last chapter. Their designs were criticized for the lack of a theoretical basis. In this chapter, we will discuss the basis of our negotiation protocol—Speech Act Theory. 3.1 Why Use Speech Act Theory Negotiation can be viewed from various angles. One angle is from the social and psy-chological analysis of actual negotiation situations. The findings from social science that are relevant to the construction of our protocol will be discussed in the next chapter. Since negotiation is one kind of linguistic behavior, another angle is through the analysis of language used in the process of negotiation. We believe that this will help in under-standing the structure of negotiation. Speech act theory is a good instrument to analyze the language used in negotiation. The central idea of the speech act theory [1, 23, 24] is that someone uttering a sentence is not just saying things (i.e., describing a state of affairs), but he is actually doing something [17]. For example, when somebody says "I promise to come", he is not only uttering the statement "I promise to come", but he actually commits himself to an action to be performed in the future. In speech act theory, the number of the kinds of actions that can be performed in speaking is limited, unlike the unlimited possible use of natural language. Therefore, no matter what approaches they use, speech act theory tries to come up with some classification scheme for speech acts, such as those provided in [24] 11 Chapter 3. Speech Act Theory 12 and [2]. These classification schemes of speech acts provide us with the construct to analyze the negotiation process and the construction of our protocol. Winograd and Flores [32] argue that there is a recurrent pattern in conversations in organizations. They observed that even though the contents of conversations may differ, the structure of some conversations will be the same. They see an organization as a network of commitments which are the results of conversations. In order to support organizational work, it is important to discover the recurrent patterns of conversations and to support them through information systems. Conversation is treated as an ordered speech act sequence in which each speech act creates a finite and quite limited set of appropriate speech acts as replies [25]. This observation makes the construction of a protocol possible. If the possibility of replies for a speech act were unlimited, it would be impossible for us to construct a protocol to support negotiation. The limited set of replies are made possible with a limited set of speech acts as provided by the analysis of speech act theory and the logical uses of language. 3.2 Searle's Speech Act Classification Searle's speech act classification is the most fully developed and widely used classification. Some researchers have applied it to the computer domain [8, 32, 33, 34, 35]. Others use Searle's taxonomy to analyze natural discourses (e.g., van Eemeren and Grootendorst [30] use it to analyze argumentative discussion). Searle [24] suggests that there are five basic kinds of actions that can be performed in speaking. He bases his classification on the goal that a speaker wants to achieve by his utterance and comes up with five categories: Chapter 3. Speech Act Theory 13 Assertive: which commits the speaker to the truth of the expressed proposition. Directive: which are attempts by the speaker to get the hearer to do something. Commissive: which commits the speaker to some future course of action. Expressive: which expresses the psychological state about the state of affairs. Declarative: which brings about change by virtue of the content of the utterance. However, this classification has been criticized and said to "lack a principle basis, . . . , it is not even built in any systematic way on felicity conditions1" [17]. Another shortcoming of Searle's work is that he only analyzes the speech act from the speaker's point of view [30], there is no analysis of interaction between the speaker and the hearer (i.e., the analysis is basically unidirectional). It is difficult to use this taxonomy to analyze natural discourses because most of these are interactive in nature. Another difficulty in using Searle's classification is that no matter what the function of a speech act is, we have to put it in one of the five categories. It overloads the semantics of the categories and makes it difficult to comprehend what the speaker really wants. For example, when we want to express disagreement on an argument, it is put into "illocutionary negation of commissive" in term of Searle's classification [30]. Another example is that even though "promise" and "threaten" have very different function in conversation, they are both in the category commissive. The intented function of a speech act may quickly get obscured if we use the classification to analyze any complex conversations. Therefore, another classification which provides more interactive analysis of the use of speech acts is needed if this theory is to be useful in constructing a communication protocol. Despite the shortcomings, Searle's speech act theory provides a detailed analysis of the use of speech acts through illocutionary logic [25]. Therefore, it will be very useful for domains which do not require complex interaction, such as in the situation where a 1 Felicity conditions are conditions that speech acts must meet if they are to be successful. Chapter 3. Speech Act Theory 14 boss robot gives an order to his subordinate robot. 3.3 Ballmer and Brennenstuhl's Speech Act Classification Ballmer and Brennenstuhl [2] were interested in classifying all German speech act verbs into Searle's speech act categories. At first, every verb is analyzed using Searle's prototype analysis of "promise"2. They hoped that this analysis would automatically lead to a classification. They experienced enormous difficulties, however, because the classification required constant revision with the addition of more verbs. This caused a re-analysis of all previously classified speech act verbs and, hence, this process seemed endless. To overcome this problem, Ballmer and Brennenstuhl employed a bottom-up ap-proach, instead of the top-down approach suggested by Searle, to classify speech act verbs. This approach starts with all speech act verbs in a German verbs dictionary. A number of semantic centers are extracted using the meaning content of verbs as a guide-line and verbs are grouped around these semantic centers. The semantic centers are: Expressing Emotion, Influencing Other, Verbal Struggle, Normative behavior, Express-ing Values, and Complex Discourse Functions [2]. Then verbs in each semantic center that are similar in meaning are grouped into categories3. For example, the category "Dissent" has speech act verb like "have words with someone", "quarrel", etc. There are a total of 600 categories in the classification. Some of the categories in a seman-tic center exhibit natural order based on temporal relations and degree of effectiveness. For example, "Dissent" is temporally ordered after "Make Claim", and "Threatening" is more effective than "Warning". These categories are grouped together with the ordering information to form models. There are 24 models and typifications4. 2Searle provides in [23] a detail analysis of the illocutionary act of promising. He tries to establish the necessary and sufficient conditions for the successful performance of the speech act. 3 T h e detail procedure is described in Chapter 4 of [2]. 4Typifications are less tightly structured semantic areas. Chapter 3. Speech Act Theory 15 Expression > Appeal > Interaction > Discourse Emotion Model Enaction Model Struggle Model Discourse Models I n s t i t u t i o n a l Model Text Model Valuation Models Theme Models Figure 3.1: Relation between Models (Adapted from Figure 4.19 in [2]) The models are related to each other as well. They can be grouped into four linguistic functions: (1) Expression, (2) Appeal, (3) Interaction, and (4) Discourse. Figure 3.1 shows the relation between the models. The Expression linguistic function contains speech act verbs for expressing emotional states. Appeal is a linguistic function that is directed towards a hearer and tries to affect his course of action. Interaction is the linguistic function that two parties engage in some form of negotiations. Discourse is the linguistic function which involves a more organized verbal interaction between two parties. The four linguistic functions can be summarized in Figure 3.2. The functions can be cross classified by two dimensions. The first one is mode of communication. Expression and Appeal are unidirectional, whereas Interaction and Discourse are bidirectional. The second dimension is privacy. Expression and Interaction are more personal in nature, while Appeal and Discourse are more institutionalized and controlled. A conversation can progress from a less complex linguistic function to a more complex ones: Chapter 3. Speech Act Theory 16 Privacy Mode of Communication Personal Institutionalized Unidirectional Expression Appeal Bidirectional Interaction Discourse Figure 3.2: Differences among 4 linguistic functions. (Adapted from Figure 4.20 in [2]) Expression —> Appeal — • Interaction — • Discourse For example, a person expresses his grievance about his work to his co-worker (Expres-sion) and the co-worker may offer to help. Then the person may request his co-worker to do something (Appeal) and they may begin to engage in a negotiation of what to do (Interaction). Moreover, the more complex linguistic functions subsume the less complex ones. For instance, Discourse conversation may use speech acts in Interaction, Appeal, and Expression. For our purpose of constructing a negotiation protocol, we are most interested in the Interaction linguistic function. The construction of the negotiation protocol will be largely based on the Struggle Model and partly on the Institutional Model (mainly appeal to authority). The Struggle Model contains speech act verbs that are used in various stages of negotiation. If the parties involved in the negotiation cannot reach agreement by themselves, they can require arbitration from a higher authority which is handled in the Institutional Model. 3.4 The Struggle Model The struggle model covers the semantic area of verbal struggle. The struggle starts by the attacker making a claim and by attacking an addressee if he disagrees with the claim. Then both parties engage in a competitive verbal fight: they argue with each other which Chapter 3. Speech Act Theory 17 may result in the victory of one and the defeat of the other or in a compromise [2]. In the course of struggle, both parties can employ tactics such as postponing the discussion or requesting arbitration. Figure 3.3 exhibits the categories in the Struggle Model and Institutional Model that we use to construct our protocol. Notice that we do not include all the categories in the models. We leave out categories that describe: 1. physical action (e.g., crash into), 2. emotional reaction after losing a negotiation (e.g., retaliate, refusing to admit de-feat) , 3. nonserious behavior (e.g., play a trick on), 4. emotional tactics (e.g., insult), and 5. coalition attempts with third parties. Speech act verbs related to physical actions, emotional reaction after losing a fight, emotional tactics, and nonserious behavior are not applicable to machine-machine com-munication in an organizational setting. Coalition with a third party is left for future work. We also made minor changes to the remaining categories. First, we combine some categories because the low level distinction is not necessary for our protocol. For example, it is not necessary to distinguish different kinds of claims (make justifiable claims, make negative viewed claim). Second, we rename some categories to reflect the functionality of the categories. For example, the category name of KAiw,a is "evasive manoeuvre without loss for defender". However, the functionality of the speech act verbs in the category (e.g., adjourn, delay, hold up, postpone, put off) can be better described as "postponing". We want to mention here that the label attached to each category represents the meaning of the speech act verbs. KA is the model name derived from the German word Chapter 3. Speech Act Theory 18 C O D E C A T E G O R Y N A M E E X A M P L E SPEECH A C T V E R B S KA_3a unacquainted status be strange, be unknown K A - i a make claim ask, assert, claim opinion KA-.U agree agree, share the same opinion KA.lc dissent break with someone, have words with someone KA-u withdraw abandon, abstain from, give up KAoj argumentative attack affirm, claim, confront K A n b a postpone adjourn, delay, hold up, postpone K A u b b admit defeat admit, agree to, give in, give way K A i b c d argumentative defense bring counterarguments, contradict, disprove K A \ c a b pinning down fix, pin down, tie down KA\cca repeated attack claim, iterate, repeat K A i c c b insisting persist in, press, pursue KAzh retreat = KA.ld KA4ab force concession force, overrule KA4cbd offer compromise make a contract, make an agreement KA4cba one-sided compromise admit, consent to, agree KA4cbc counter offer accept in part, make stipulation K A 4 c d a accept compromise accept, agree with, approve of N06Q appeal appeal to someone, bring forward N06c examining hear, question NOeda testify give testimony, show proof N07a make decision arbitrate, decide, settle Figure 3.3: Examples of speech act verbs in selected categories. "Kampfmodell" which means struggle model. The subscript is used to express sequencing and subcategory information. For example, the category K A \ is sequenced before K A 2 , and K A \ a is a subcategory of K A \ . 3.5 Some Remarks One advantage of Ballmer and Brennenstuhl's classification over Searle's is that it pro-vides the partial ordering information of the categories. This information is very useful for the analysis of, and the construction of, interactive discourses. Chapter 3. Speech Act Theory 19 Another advantage of Ballmer and Brennenstuhl's study is its empirical basis. Since they included all the speech act designating verbs in their analysis, it provides a certain degree of confidence that the classification reflects the actual linguistic behaviors. However, the classification is not without its shortcomings. First, the classification is based on the German verbs, and the version that we use is a direct English translation of the German lexicon. Therefore, the classification may miss words that have no German equivalent! We felt that this may not be a great problem for the moment and for our purpose. If our approach is found to be useful, the classification can always be reworked starting with English speech act verbs. We believe that the classification already reflects the major functionalities of language uses. Another problem is that the ordering infor-mation of the categories and the meaning of each category are not clearly documented, and thus users have to infer them from the verbs inside the categories. This problem is created by unclear and inconsistent labeling of the categories. Chapter 4 SANP: The Negotiation Protocol 4.1 Principles behind SANP The basis of S A N P (Speech Act based Negotiation Protocol), is the Struggle Model in [2]. We use the temporal relations between the categories and the alternative choice provided by the subcategories to construct the protocol. They provide information on the sequence of speech acts used in negotiation and the possible responses at each state of negotiation. For example, "Dissent" must appear after "Make Claim", and there are two alternatives after the sentence "Make Claim": "Agree" and "Dissent". The sequencing information is provided by the subscript of the category labels. Note that the sequencing information ensures that if category Y has to be used after category X, then Y has a subscript number which is greater than or equal to that of X. In constructing the protocol, we use the following rules to guide a conversation: 1. After speaking a sentence, the party must wait for the other party to reply before it is allowed to speak its next sentence1. 2. The next sentence spoken is restricted by the choices given at that state in the protocol diagrams in the appendix. As mentioned in the previous chapter, one angle we can take to understand negotiation is through the analysis of actual negotiation. Therefore, results from the negotiation 1 One exception of this rule is when the arbitrator declares the end of the arbitration in which he speaks twice. 20 Chapter 4. SANP: The Negotiation Protocol 21 literature are used to decide what should be included in the protocol and to confirm the validity of the Struggle Model. The processual model of negotiation of Gulliver [13], strategic choice model of Pruitt [20], and the analysis of argument structure of Toulmin [29] are used to support our design decisions. Gulliver [13] proposes an 8 phase processual model of negotiation which depicts the developmental progress of the negotiation process from the initial recognition of the dispute to some kind of outcome. His model only covers two-party negotiation without the intervention of a third party. The 8 phases are described as follow: 1. Search for arena: parties agree on the location where negotiation may occur. 2. Agenda Setting: parties agree on the issues to be negotiated. 3. Exploring the field: parties try to establish maximal limits to the issues in dispute. 4. Narrowing the difference: parties begin to look for the possibilities of approaching actual outcomes and try to narrow their differences. 5. Preliminaries to final bargaining: parties search for a viable bargaining range, refine persisting difference, test trading possibilities, and construct a bargaining formula. 6. Final bargaining: parties exchange specific and substantive proposals and counter proposals. 7. Ritual affirmation 8. Execution of the agreement Negotiations do not necessarily go through all phases in the model and phases may overlap each another in actual negotiation. Nevertheless, this model provides a guideline on how negotiation normally proceeds. Our protocol is not intended to support the entire process of negotiation described by Gulliver. We make a number of assumptions: the negotiation platform is computer, there are specific issues to be negotiated, and when a compromise is made it is automatically affirmed. Therefore, our protocol will Chapter 4. SANP: The Negotiation Protocol 22 only support the negotiation phases 4 to 6. More specifically, we would like to provide facilities for exchanging information among agents to increase the understanding of each other, for narrowing down differences, and for settling the dispute. Finally, the parties are allowed to offer proposals and counter-proposals in order to reach a compromise. Pruitt [20] proposes a Strategic Choice model of negotiation. The model states that parties involved in a negotiation have to make strategic choice at every point in time. The choices include: 1. concede unilaterally 2. stand firm and employ pressure tactics (e.g., persuasive arguments, threat) 3. collaborate with other parties in search of a mutually acceptable solution. Maynard [19] in his research on the structure of discourse in misdemeanor plea bar-gaining finds that bargaining results in three outcomes: reaching compromise, postponing discussion, and appealing to higher authority. Requests for postponement are used to collect more information or to put pressure on the other party. In addition to reaching a compromise, SANP is designed to support both "Delay" and "Appeal" functions. We also support all the strategic choices stated in the Strategic Choice model. We allow agents to make concessions by offering one-sided and two-sided compromise, and to persuade other agents by providing arguments. Toulmin [29] proposed a simple model of argument structure which is depicted by the following diagram: Data > so: Claim I since Chapter 4. SANP: The Negotiation Protocol 23 In Toulmin's analysis, the first step in an argument is that one party expresses an opinion, which Toulmin calls a "Claim". If the claim is challenged, it has to be defended by adducing of "Data" which supports the claim. If the challenger is not satisfied with the accuracy of the data, the objection has to be removed by a "Preparatory Argument". However, even if the accuracy of the data has not been questioned, the challenger can require further support for the claim. In this case, a "Warrant" which states the relation between the "Data" and "the Claim" has to be given [31]. A n Example of the structure is: It i s raining > so: the playground must be wet (Data) I (Claim) since I If i t rains, the playground w i l l be wet (Warrant) The structure of argument is not always that simple; more complicated models of arguments are discussed in [31]. However, from this simple structure, it can be concluded that arguments are recursive. We need to justify the accuracy of the "Data" by another argument. We need to do the same thing for the "Warrant": we can question its validity and require a justification. S A N P is designed to handle the recursive properties of argumentation. It supports multi-level negotiations so that the participants can identify and narrow down their differences more easily. 4.2 A Communication Level Protocol for Negotiation In this section, we shall discuss a communication level negotiation protocol, SANP, that incorporates the requirements discussed in the previous section. Chapter 4. SANP: The Negotiation Protocol 24 The format of a sentence in SANP consists of two components: <function><content> where <function> is a speech act category name and <content> is the representation of domain knowledge (an example domain knowledge representation is given in chapter 5). Figures in the appendix are the protocol diagrams. The state of a conversation is repre-sented by a node. The "-" and "+" signs labeled with the arc in the diagram are used to indicate the sentences spoken by the attacker and the defender, respectively. The "?" indicates the sentences spoken by the arbitrator. For example, " — K A ^ 2 a n means the attacker speaks "Make Claims". The arcs originating from a node are the allowable responses in that stage of negotiation. For example, in "Dissent" state, the attacker has two choices: "Retreat ( — K A 3 b ) v or "Argumentative Attack ( — K A Q J ) " . The rectangular box indicates the name of the subdiagram to be used at that point. "End" is used to terminate the conversation. A detailed description of the protocol is provided in the appendix. The following discussion will highlight some important points in the protocol. Basically, there are 6 main stages in the protocol: 1. Starting situation: The agents establish a common understanding of the topic and decide whether they have the necessary knowledge to enter into a discussion. 2. Making a claim and receiving dissent: The attacker starts by presenting his claim. It can be a plan, a request for action, or just an assertion. The defender then reasons whether he agrees with it or not. 3. Attacking: If the defender disagrees with the claim, the attacker will start attacking the defender by providing argument. 4. Tactical phase: The defender begins by defending his position, the attacker attacks the defender's argument. This process continues until they identify their differences Chapter 4. SANP: The Negotiation Protocol 25 and try to narrow them down. They can employ different tactics: request to delay, offer compromise, and insist on their own arguments. This phase corresponds to phase 4 and 5 of Gulliver's model. 5. Entering into a settlement: Both parties begin to offer compromises and counter-proposals . This phase corresponds to phase 6 of Gulliver's model. 6. End result: The result of the negotiation can be a one-sided compromise, mutual compromise, delay, or appeal to higher authority. Not every negotiation goes through all the stages. For example, some negotiation may not have the tactical phase if the attacker withdraws the claim after the defender expresses his dissent. Some negotiations may end up postponing to another time. Therefore, these phases of negotiation should be viewed as a rough guideline. When the use of the protocol begins, both parties are in the "Idle" state, the attacker needs to specify or declare the topic of discussion. If the defender does not have the necessary knowledge, the conversation ends. Otherwise, both parties should have all the necessary background to understand each other (e.g., the same variable will mean the same thing to both of them). The term "ack" (used in the protocol diagram in the appendix) means the defender agrees to discuss the topic. In the tactical phase, the protocol supports multi-level arguments by providing a looping between the "Being attacked" and "Defending" states. Therefore, both parties can request and provide deeper and deeper levels of support to their arguments. This looping also aims at identifying and narrowing the differences between the views of the parties. For implementation considerations, we only allow a maximum of 100 times of looping to avoid infinite looping. We believe this number is sufficient in an ordinary argument. Moreover, if the number of iterations on the same point at the same level exceeds 5, the looping is also terminated. We handle the looping between "Offer a Chapter 4. SANP: The Negotiation Protocol 26 compromise" and "Modify the compromise" in a similar way. Our protocol also supports the delay tactic suggested by Maynard [19]. A n agent can request to delay a discussion if he does not have enough information to continue the discussion. It must be emphasized that the date of postponement is also settled by negotiation. The other party can even deny the request if he is in a higher position of authority. Appeal to a higher authority is also supported. If the parties find that they cannot settle the dispute by themselves, they can request an arbitration. The arbitration process is simple—each party presents his own arguments and the arbitrator will make a decision based on this information. We assume that the arbitrator is either a human being or a system that has the necessary knowledge to make the decision. In designing this protocol, we always put flexibility as a high priority so that it can be applied to a wide variety of situations. In the following chapter, we will give an example of using our protocol. Chapter 5 An Example Application In this chapter, we describe how the proposed communication protocol is used to support the preparation of budgets. Consider two organizational workers where the attacker is responsible for preparing the departmental budget and the defender is an employee who prepares part of the departmental budget. The attacker feels that the "labor cost" budgeted by the defender is too high. Before presenting the dialogue, we need a representation of the domain knowledge: 1. knowledge and rules are represented as equations. For example labor cost = total hours x salary x number of workers 2. facts are represented using variables and their corresponding values. 3. A "?" in an equation means the agent does not know the value of a variable. We intentionally make the representation simple so that we can demonstrate our ideas easily. In Figure 5.1 and Figure 5.2, we present three scenarios for negotiation. The first column indicates the line number. The second column shows the speech acts used by the attacker and the defender. The last column indicates the contents that go with the speech acts. The attacker begins the conversation by declaring the topic as "Next year's budget". The defender knows the topic, so he agrees to discuss it. The attacker claims that the "labor cost" should be $91,520 and the defender disagrees with the attacker. The defender 27 Chapter 5. An Example Application 28 1 2 3 4 A : Declare topic . "Next year's budget" D: Ack A : Make claim ( K A - 2 a ) labor cost = $91,520 D: Dissent ( K A - l c ) A : Argumentative attack (KA0j) labor cost = $124,800 (Reason:) labor cost = hourly wage x total yearly hours hourly wage — $12 total yearly hours = 10400 hrs hourly wage = $11 total yearly hours = 8320 hrs (Reason:) hourly wage = last year wage x (l-f-%increase) last year wage = $10 %increase = 10% total yearly hours =#employee x 2080 ^employee = 4 After here, there are three scenarios: Scenario 1: Compromise 6 7 8 D: Offer compromise (KA4cbd) A : Accept compromise {KA4cda) D: End labor cost = $114,400 %increase = 10% ^employees = 5 labor cost = $114,400 Scenario 2: Postpone 10 D: Postpone ( K A n b a ) 11 A : Counter offer ( K A 4 c b c ) 12 D: Accept compromise ( K A 4 c d a ) 13 A : End Date = "6/30/91" (Reason:) %increase = ? Date = "6/27/91" Date = "6/27/91" Legend: " A " is the attacker, "D" is the defender. Figure 5.1: A n example dialogue for the budgeting example (part 1 of 2) Chapter 5. An Example Application 29 Scenario 3: Arbitration 14 15 16 17 18 19 20 21 22 23 D: Argumentative defense (KAUcd) A : Repeated attack (KA\cca) D: Insisting (KA\ccb) A: Appeal (N06o) S: Examining attacker (N06C) A : Testify (N06da) S: Examining defender (NOec) D: Testify (N06da) S: make decision (N07a) S: End Disagree: ^employee = 5 (Reason:) ^employee = round(workload/2080) workload = 10,000 hrs Disagree: workload = 8,000 hrs workload = 10,000 hrs labor cost = $91,520 (Reason:) ) labor cost = hourly wage x total yearly hours hourly wage = 11 total yearly hours = ^employee x 2080 ^employee = round(workload/yearly hours per employee) workload = 8,000 hrs Labor cost = $114,400 workload = 10,000 hrs workload = 10,000 hrs labor cost = $114,400 Legend: " A " is the attacker, "D" is the defender, and "S" is the arbitrator/superior. Figure 5.2: A n example dialogue for the budgeting example (part 2 of 2) Chapter 5. An Example Application 30 provides arguments why he disagrees in line 4. In line 5, the attacker disagrees with the value of "hourly wage" and "total yearly hours" and provides his argument. There are three possible scenarios after this. In the first scenario, the defender offers a compromise in line 6. He agrees on "hourly wage" but requires that the number of employees be 5. The attacker considers this compromise to be acceptable, so he accepts $114,400 as the labor cost. In the second scenario, the defender does not know the value for "%increase", he requests a postponement in the discussion to 6/30/91. However, in line 11, the attacker wants the discussion to be resumed earlier, so he counter offers an earlier date and the defender accepts this new date. In the third scenario, the defender agrees with the percentage of wage increase ^ i n -crease). However, he disagrees with the value of "^employee", so he presents his own calculation. In line 15, the attacker in turn disagrees with the value of "workload". How-ever, the defender insists that the value of "workload" is 10,000 hours. Since they cannot resolve the conflict among themselves, the attacker requests an arbitration in line 17. In line 18 to 21, the attacker and the defender present their arguments to their superior. Based on his knowledge, the superior makes a decision in line 22 that is in favor of the defender. These example scenarios show that in SANP, agents can present their supporting evidence in the negotiation process and they can discover the reasons for their conflict. For instance, in scenario three, the agents finally identify the cause of disagreement on the "labor cost" to be their different assessment on the value of "workload". In addition, agents can utilize strategies such as postponement and arbitration in SANP. Chapter 6 Implementation and Test Use Having introduced the SANP protocol in the last two chapters, we will describe how we implement our protocol and what we have learnt from the test uses of our protocol in negotiation. 6.1 Implementation S A N P is implemented using an electronic mail toolkit called Strudel [26]. The imple-mentation aims to provide a domain independent system which can be used for specific domains in the future. Therefore, the system should allow the for addition of domain knowledge to be used with the protocol. Strudel 1 provides facilities to manage electronic mail based conversations. It can be used to structure discourse. Strudel runs under Unix, X-Window, and Internet mail. We have been running it on a Sun Sparc IPC workstation. In Strudel 2, e-mail messages contain typed conversational moves, such as a "Re-quest" conversational move. A move can contain semi-structured fields. For example, a "Request-for-meeting" conversational move may contain fields such as "Date", "Time", and "Place". This is very similar to a semi-structured message [18]. In a conversational move, it is possible to restrict the next possible conversational moves that recipients can make. Strudel also allows automatic processing of incoming messages and sending 1 Strudel is copyrighted software of Hewlett Packard 2 W e wil l describe the function of Strudel that are relevant to our implementation only. Detail dis-cussion is in [26]. 31 Chapter 6. Implementation and Test Use 32 responses by writing programs in Lisp. Therefore, we can set up a system which can process the conversational moves automatically. Conversational moves in Strudel can be used to represent speech acts in SANP. Fig-ure 6.1 shows the conversational move or speech act "Make Claim" as implemented in Strudel. The definition of this move is shown in Figure 6.2. Fields in a conversational move can be used to represent domain knowledge during negotiations. There is only one field in the "Make Claim" move, which is "Claim". The definition of this field is given in the second half of Figure 6.2 and it is used in the fifth line of the "Make Claim" definition in Figure 6.2. The agent needs to provide its claim here when this speech act is used. The buttons3 at the bottom of the screen are the possible next moves that an agent can choose from. We use this to represent the possible speech acts that an agent can use in his response at each state in the negotiation. In this example, the possible next moves/speech acts are "Agree" or "Dissent". Since we only attempt to implement the domain independent structure of the SANP protocol, the fields which would be included in each move that depend on a specific do-main are beyond the scope of this thesis. A formal representation of domain knowledge has to be specified in order to enable machine to machine interaction. Since we can au-tomatically process conversational moves, it is possible to automate negotiation provided that we can provide agents with knowledge of how to reason about the content of the conversational moves/speech acts. In Strudel, conversational moves can be threaded together to form a conversation. We can also define conversation type to guide the way in which conversations are started, de-veloped, and ended. Conversation type definitions define a initial conversational move of the conversation, and what other conversational moves are allowable in this conversation. 3Since Strudel is a normal mail user agent, the buttons are presented to human users to choose their next move. Chapter 6. Implementation and Test Use ComposeNextj ^omposejiexMFUeJ J^asHJefadOjextJ ^lose^onvj Jtelpj chang cc: chang Subject: Make Claim Bate: 8/22 J ^ Claim as follow: Claim lets 90 to HacDonalds for lunch to*™** • f t g r e e l y Dissent| fictions: Figure 6.1: Screen Dump for "Make Claim" Conversational Move Chapter 6. Implementation and Test Use 34 (register-move-type 'make-claim • t i t l e "Make Claim" :to ( l i s t 'sender) :intro "Claim as follow:" :utterance-sequence ( l i s t 'claim) :preferred-reply-action-type 'agree :reply-action-types ( l i s t ( l i s t 'agree "Agree") ( l i s t 'dissent "Dissent") ) ) (send make-claim :s e t - f i e l d 'claim :label "Claim" .•presentation ( l i s t 'string) Figure 6.2: Conversational Move Type Definition for "Make Claim" In our case, we have defined a conversation type called "SANP-protocol". The initial conversational move type is "Declare Topic". Other conversational moves included in this conversation type are all the speech acts in the SANP protocol. Therefore, an agent can start a S A N P protocol by sending the "Declare Topic" conversational move to another agent and then follow the possible next conversational moves in each conversational move until the end of conversation. 6.2 Test Uses As described in the previous chapters, we have tried to design SANP based on the existing negotiation literature and models so that our protocol will provide the functions that are needed in actual negotiation. However, we would like to know the limitations of S A N P when it is put into actual use.. Therefore, we have asked people to use S A N P to conduct Chapter 6. Implementation and Test Use 35 negotiation and to provide us with their opinions on the protocol. This study is not meant to be a systematic and controlled experiment. We just want to solicit feedback from the users on how realistic the protocol is in terms of providing the necessary functions for negotiation. 6.2.1 Design of the Study This is a very small study with four subjects. The subjects were divided into two pairs. Each pair of subjects negotiated on the topic "Where to go for lunch". This topic was chosen for two reasons. First, we wanted the negotiation to be realistic. The subjects should have their own knowledge on the topic and they should be motivated to perform the negotiation. If we had used a domain that the subjects were not familiar with, then we would have had to make up the background information and the scenario for negotiation and the subjects would be told how to negotiate. There are two problems with this approach. First, the subjects did not really need to negotiate with each other and this might affect the way they negotiate. Second, since we made up the scenarios, it was possible that they would fit nicely in the protocol. In this case, we cannot achieve the objective of the study. The second reason for choosing this topic was that since S A N P is designed for use with the organizational negotiation in mind, we wanted to find a topic that was similar to some negotiation inside an organization. We thought that the chosen topic is very similar to a class of negotiations in organizations, such as negotiation on where to conduct a meeting. Of course this study is not intended to be a full test of the S A N P protocol. The usefulness of the protocol should be studied carefully when it is applied to specific domains. Another design decision that we made in this study was that we have used human subjects even though the protocol is design for machine to machine communication. Since the purpose of this study is to test the SANP protocol, we don't want the abilities of Chapter 6. Implementation and Test Use 36 agents, such as reasoning capability and knowledge representation scheme, to confront with the protocol design. Therefore, we used human subjects as intelligent agents so that we do not have to worry about the implementation of intelligent agents. In this way, we can separate the limitations of the agents and the limitations of the protocol. Another reason for using human subjects is that even though we design the protocol for machine communications, the protocol should provide the functions that are needed in actual negotiations. Using human subjects enables us to get feedback from them on the limitations of the protocol; they can thus indicate what functions they want to use but are missing in the protocol. This information is very useful for the future improvement of the protocol. Since S A N P is designed for machine use, extra caution is needed when it is used with human subjects. The speech acts used, such as "Attack", may provoke the emotion of being offended in a human subject but do not have the same effect in machine communi-cation. Therefore, the subjects were instructed to disregard any emotional effect in the speech acts. 6.2.2 The Study The subjects were told two or three days before the actual negotiation the subject to be negotiated and were asked to think about where they wanted to go for lunch at the day of the negotiation and why they wanted to go there. Our protocol is implemented using Strudel on a single Sun Sparc IPC workstation. Since we have only one workstation, the subjects were required to use the same machine during the study. Strudel software was running in two accounts simultaneously in the same workstation during the study. Subjects sent each other conversational moves within the same workstation. The e-mails were received, read, and responded to immediately during the study. Chapter 6. Implementation and Test Use 37 The studies were carried out in a small room in which the workstation was located. Two subjects and the author were in the same room during each study. The author solicited feedback and answered questions on the system. Before the negotiation took place, the subjects were briefly introduced to the S A N P protocol 4. They were asked to pretend they were intelligent agents without emotion. Subjects were requested to use the system to carry out negotiations without talking to each other. However, if they wanted to perform certain functions that were not provided in the protocol, they would talk to each other and go back to the protocol after they solved the problem. At this time, the author would ask the subject the reasons why they needed to use that function and would note these for future reference. Comments on the protocol were solicited during and after the studies. 6.2.3 Discussion Although we have only two pairs of subjects, the negotiation processes provide a number of insights on the potential use and limitations of the SANP protocol. This results may be useful for improving the protocol in the future. First, both pairs of subjects wanted to use some kind of information probing speech acts to get more information from the opponents. For example, when the attacker made a claim to indicate where he wanted to go for lunch, the defender did not want to decide whether he agreed or disagreed with the claim immediately. Instead, he wanted to get more information on the restaurant, such as whether there was a sun deck in that restaurant. When we designed the SANP protocol, we assumed that the agents will have enough domain knowledge to conduct the negotiation. If the attacker does not have enough information, it will have to withdraw the claim. If the defender does not 4 Most of the subjects were introduced to the protocol before the study because the author had presented it in a seminar. Chapter 6. Implementation and Test Use 38 have enough information, it should ask for a postponement. However, it will be useful to incorporate speech acts that allow agents to get information from each other. The S A N P protocol assumes that one agent will provide all the reasons supporting its argument at once and the other agent will attack the arguments in the previous move. However, in the study, subjects give one reason at a time. When one reason fails to convince the opponent, they give another one. We think this is reasonable and will happen in open systems since information may come in at any time, so there may be new supporting evidence coming in during negotiation. In the study, we did not know how to handle this, so the subjects are forced to give all supporting argument at once. However, after some thought we think SANP can handle this situation. It can be done in the tactical phase; the attacker and the defender can provide reasons which are not a direct attack on the previous move in the "Being Attacked" and "Defending" states. This also illustrates one point: our protocol does not restrict the contents that go with the speech acts. Another insight gained from this study is the kind of negotiation for which S A N P can be used most effectively. Although we had only two negotiation sessions, the processes of negotiation in these two cases were very different from each other. In the first negotiation, the attacker had a very strong opinion to go to MacDonalds for lunch; therefore, he tried to convince the defender by providing reasons to support his argument at every state of the negotiation. The negotiation basically followed the protocol until the defender was convinced by the attacker to go to MacDonalds. In the second case, however, the attacker did not insist very strongly on where to go. Therefore, when his suggestion was being challenged by the defender, he wanted to ask the defender to provide him with another suggestion. Our protocol cannot handle this situation. These two cases thus show that SANP is good at negotiation in which a decision has to be made on a single issue or a variable and there is only one set of supporting Chapter 6. Implementation and Test Use 39 arguments. However, it is not good for negotiations in which there are a number of alternatives and each of the alternative has a different sets of supporting arguments. A n example will make this point clear. In the budgeting example that we gave in Chapter 5, the only variable that the agents have to decide is the "Labor Cost". No matter what their arguments are, the agents have to agree on some value for the "Labor Cost". They do not have any other alternative to consider. However, in the case of deciding which restaurant to go, there may be a lot of alternative restaurants with each having a different set of arguments. For example, price may be an issue in one restaurant, and quality of service may be an issue in another. In this situation, it is hard to follow one protocol and get a resolution. In fact, there should be one protocol for each restaurant. In order to handle this kind of negotiation, we need a higher level control mechanism. The control mechanism should allow multiple instantiation of the SANP protocol to handle different issues or claims. The negotiation should be ended when any one of the protocols arrive at some sort of outcome for the negotiation. Chapter 7 Conclusion 7.1 Thesis Contributions The major contribution of this thesis work is the construction of the S A N P commu-nication level protocol for simple, semi-structure, single issue, machine to machine ne-gotiation. The SANP protocol is more flexible than the existing protocols used in the DAI area. It allows agents to negotiate at multiple levels and it supports many tactics of negotiation which are well recognized in the negotiation literature, such as delaying the negotiation and appeal to higher authority, which are not supported in the existing protocols. The SANP protocol is designed based upon the Struggle Model and the In-stitutional Model in Ballmer and Brennenstuhl's speech act classification. We also draw on the results of negotiation research to help make design decisions. It is hoped that all this effort will: 1. reduce the arbitrariness of the protocol design, 2. provide a cross validation for the protocol design, and 3. make the protocol applicable to a wider range of domains. The S A N P protocol can be used to coordinate agents in a multi-agent system. Agents in conflict can use the protocol to carry out negotiation in order to resolve it. However, since the S A N P protocol is only a communication level protocol, knowledge representa-tion and the reasoning mechanism for the domain have to be specified by the user. 40 Chapter 7. Conclusion 41 We also provide a system, which is a domain independent implementation of the struc-ture of the SANP protocol, to be used for future experimentation with the protocol. The system is implemented on an intelligent e-mail system called Strudel which can structure discourses and automatically handle incoming messages. Knowledge representation of a, specific domain can be added to this system at a later time in the form of semi-structured messages. Another contribution of this thesis is a small study on the protocol. Although the study is not a well controlled experiment, it provides a number of insights on the limita-tions of the protocol and the kind of negotiation that the protocol is most suitable for. This information may be useful for the further improvement of the protocol. 7.2 Limitations of the Protocol and Future Research Directions In order to use the protocol effectively, we have to know its limitations and apply it to the right problems. SANP is designed for very simple negotiation. It is not meant to model the complex negotiation of human beings. As shown in the empirical study, the SANP protocol is most suitable for single issue negotiations which have only one set of arguments. For a more complex situation in which several alternatives exist and each alternative has its own set of arguments, a higher level control mechanism is needed to instantiate one protocol for each alternative and to control the transition from one protocol to another. Another shortcoming of our protocol is that it lacks speech acts that allow parties to get information from each other. The protocol should be extented to incorporate some speech acts, such as "Asking Question", "Advising", "Answering Question", etc., in the Appeal linguistic function to support mutual questioning as in [35]. The SANP protocol could also be extended in other ways. First, our treatment of the Chapter 7. Conclusion 42 appeal function is very simple. In fact, it can be viewed as another negotiation with a mediator. One possible improvement would be to use a negotiation support system, like the P E R S U A D E R [28], to act as the mediator which can help in generating proposals and detecting and resolving conflicts among parties. Second, the detailed process of arguing, such as requesting more information and explaining and validating the argument, has not been incorporated into the protocol. The "Arguing Devices" model which includes speech acts for arguing in Ballmer and Brennenstuhl's classification can be used for this purpose. Third, the protocol could be extended to involve a third party in the negotiation which we intentionally left out in our construction of the protocol in order to start in a simple way. This third party is not the arbitrator, but an agent who collaborates with one of the parties in the conflicts. The Struggle Model could again be used to guide the design. S A N P is not meant to be complete. Many improvements have yet to be made. A l -though the validity of the protocol is derived in part by the match between the negotiation literature and the speech act classification, the final assessment of the protocol should be based on its usefulness when it is applied to different problem domains. Bibliography [1] Austin, J . L . , How to Do Things with Words, Oxford University Press, 1962. [2] Ballmer, T. and Brennenstuhl, W., Speech Act Classification: A Study in the Lexical Analysis of English Speech Activity Verbs, Springer-Verlag, Berlin, Heidelberg, 1981. [3] Bond, A . H . and Gasser, L . , "An Analysis of Problems and Research in D A I " , in Reading in Distributed Artificial Intelligence, A . H. Bond and L. Gasser, eds., Morgan Kaufmann Publishers, Inc., San Mateo, California, 1988, 3-35. [4] Campbell, J . A . and D'Inverno, M . P., "Knowledge Interchange Protocol", in De-centralized A.I., Y . Demazeau and J . P. Muller, eds., Elsevier Science Publishers B . V . , Amsterdam, Netherlands, 1990, 63-80. [5] Chou, Wushow, ed., Computer Communication: Volumn 1 Principle, Prentice-Hall, Inc., Englewood Cliffs, N . J . , 1983. [6] Conry, S. E . , Meyer, R. A . , and Lesser, V . R., "Multistage Negotiation in Dis-tributed Planning", in Reading in Distributed Artificial Intelligence, A . H . Bond and L . Gasser, eds., Morgan Kaufmann Publishers, Inc., San Mateo, California, 1988, 367-384. [7] Davis, R. and Smith, R. G., "Negotiation as a Metaphor for Distributed Problem Solving", Artificial Intelligence, Vol. 20, No. 1, 1983, 63-109. [8] De Cindio, F. , Simone, C , Vassallo, A . , and Zanaboni, A . , "CHAOS: A Knowledge-Based System for Conversing within Offices", in Office Knowledge: Representation, Management, and Utilization, W. Lamersdorf ed., Elsevier Science Publisher B . V . , Holland, 1988, 257-276. [9] Durfee, E . H . and Lesser, V . R., "Using Partial Global Plans to Coordinate Dis-tributed Problem Solvers", in Reading in Distributed Artificial Intelligence, A . H . Bond and L . Gasser, eds., Morgan Kaufmann Publishers, Inc., San Mateo, Califor-nia, 1988, 285-293. [10] Durfee, E . H . and Lesser, V . R., "Negotiation Task Decomposition and Allocation Using Partial Global Planning", in Distributed Artificial Intelligence, Volume II, L . Gasser and M . N . Huhns, eds., Pitman, London, 1989, 229-243. 43 Bibliography 44 [11] Galliers, J . R., "The Positive Role of Conflict in Cooperative Multiagent Systems", in Decentralized A. I., Y . Demazeau and J . P. Muller, eds., Elsevier Science Publishers B. V . , Amsterdam, Netherlands, 1990, 33-46. [12] Gerson, E. M . and Star, S. L . , "Analyzing Due Process in the Workplace", ACM Transactions on Office Information Systems, Vol. 4, No. 3, July 1986, 257-270. [13] Gulliver, P. H . , Disputes and Negotiations: A Cross-Cultural Perspective, Academic Press, New York, 1979. [14] Hewitt, C , "Offices Are Open Systems", ACM Transactions on Office Information Systems, Vol. 4, No. 3, July 1986, 271-287. [15] Hewitt, C , "Open Information Systems Semantics for Distributed Artificial Intelli-gence", Artificial Intelligence, Vol. 47, No. 1, 1991, 79-106. [16] Koo, Charles C , " A Commitment-based Communication Model for Distributed Of-fice Environments," Proceeding of Conference on Office Information System, (Palo Alto, California, March 23-25, 1988), 291-298. [17] Levinson, S. C , Pragmatics, Cambridge University Press, New York, 1983. [18] Malone, T. W. , Grant, K . R., Lai , K . Y . , Rao, R., and Rosenblitt, D. , "Semistruc-tured Messages are Surprisingly Useful for Computer-Supported Coordination", ACM Transactions on Office Information Systems, Vol. 5, No. 2, 1987, 115-131. [19] Maynard, D. W., "The Structure of Discourse in Misdemeanor Plea Bargaining", Law & Society Review, Vol. 18, No. 1, 1984, 75-104. [20] Pruitt, D. G. , Negotiation Behavior, Academic Press, New York, 1981. [21] Putman, L . L. and Poole, M . S., "Conflict and Negotiation", in Handbook of Or-ganizational Communication: An Interdisciplinary Perspective, F . M . Jablin, et al., eds., Sage, Newbury Park, C A , 1987, 549-599. [22] Rahim, M . A . , Managing Conflict in Organization, Praeger, New York, 1986. [23] Searle, J . R., Speech Acts: An Essay in the Philosophy of Language, Cambridge University Press, New York, 1969. [24] Searle, J . R. "A Taxonomy of Elocutionary Acts", In Language, Mind and Knowl-. edge, Minnesota Studies in the Philosophy of Science, Vol. 7, K . Gunderson, ed., University of Minnesota Press, Minneapolis, 1975, 344-369. [25] Searle, J . R. and Vanderveken, D., Foundation of Illocutionary Logic, Cambridge University Press, London, 1985. Bibliography 45 [26] Shepherd, A . , Mayer, N . , and Kuchinsky, A . , "Strudel - An Extensible Electronic Conversation Toolkit", CSCW 90 Proceedings, (Los Angeles, California, October 7-10, 1990), 93-104. [27] Smith, R. G. , "The Contract Net Protocol: High Level Communication and Control in a Distributed Problem Solver", IEEE Transactions on Computing, Vol. C-29, No. 12, December 1980, 1104-1113. [28] Sycara, K . , "Multiagent Compromise via Negotiation," in Distributed Artificial In-telligence, Volume II, L. Gasser and M . Nuhns, eds., Pitman Publishing, London, 1989, 119-137. [29] Toulmin, S. E . , The Uses of Argument, Cambridge University Press, Cambridge, 1969. [30] van Eemeren, F. H . and Grootendorst, R., Speech Acts in Argumentative Discus-sions, Foris Publication, Dordrecht, 1983. [31] van Eemeren, F . H , Grootendorst, R., and Kruiger, T., The Study of Argumentation, Irvington Publishers Inc., New York, 1984. [32] Winograd, T. and Flores, F. , Understanding Computers and Cognition, Addison-Wesley, N J , 1986. [33] Woo, C. C , "SACT: A Tool for Automating Semi-Structured Organizational Com-munication", Processing of Office Information System, (Cambridge, Massachusetts, Apri l 25-27, 1990), 89-98. [34] Woo, Carson. C. and Zeng, Tao, "An Application Layer Communication Protocol for Supporting Organizational Work", Working Paper 90-MIS-019, University of British Columbia, Vancouver, Canada, August 1990. [35] Zeng, T., An Organizational Communication Protocol Based on Speech Acts: De-sign, Verification and Formal Specification, M.Sc. thesis, Department of Computer Science, University of British Columbia, Vancouver, Canada, 1990. Appendix A Descriptions of the SANP Protocol The detail of the protocol is described in this appendix. The state of a conversation is represented by a node. The "-" and "+" signs labeled with the arc in the diagram are used to indicate the sentences spoken by the attacker and the defender, respectively. The "?" indicates the sentences spoken by the arbitrator. The arcs originating from a node are the allowable responses in that stage of negotiation. The rectangular box indicates the name of the subdiagram to be used at that point. The title of the sections (in bold) and subsections (in italic) corresponds to the subdiagram names and nodes, respectively. Opening Stage Idle At the beginning of the conversation, parties involved should establish a common under-standing. They need to agree on the topic of discussion and make sure they both have the knowledge for that topic. The attacker begins the conversation by saying "Declare topic" with the topic as content. Opening If the defender has the knowledge of the topic, he says "ack", which means he agrees to discuss the topic. If the defender does not have any knowledge of the topic, he says "end" to end the 46 Appendix A. Descriptions of the SANP Protocol 4 7 conversation. Make Claim Ready to make claim The attacker says "make claim" with the claim as content. The claim can be a statement or a request for action, as well as a plan. In an organization most conversations will be requests for action [32] and solicitation of commitments. For every request for action, the final result should be either having a commitment, may be in the form of a contract, or rejecting the request. Claim made If the defender agrees with the claim of attacker, he says "agreement". Otherwise, he says "dissent" with the reasons of disagreement as the content. Dissent If the attacker agent 1) agrees with defender, or 2) does not have necessary information to continue the discussion, or 3) does not have any supporting argument, he says "withdraw" to withdraw the claim. If the attacker disagrees with the argument of the defender, he says "argumentative attack" with information of what he disagrees together with argument to support them as content. <>' Agreement The attacker says "offer compromise" with the claim as its content. The content may be in the form of a contract so that both parties can keep track of the commitment made Appendix A. Descriptions of the SANP Protocol 48 (as in [16]). Attacker offers compromise The defender says "accept compromise" and enter the contract into his knowledge base. Tactical Phase Being attacked If the defender agrees with the attacker's argument, he should say "admitted defeat", and enter into an agreement with the attacker. The process will be described in the "Defender Admitted Defeat" section. If the defender does not have necessary information or knowledge, he says "postpone" with the date as content to require a postponement of the discussion. If the defender does not agree with the attacker's argument, he says "argumentative defense" with what he disagrees and supporting argument as the content. If 1) the defender runs out of argument or 2) the number of iterations between Being attacked and Defending on the same point exceeds five, or 3) the total iterations between Being attacked and Defending on the whole argument exceeds 100, the defender can either say 1) "insisting" with his argument as content or 2) "offer compromise" with the compromise as content. Defending If the attacker agrees with the argument of the defender, he should say "withdraw" with empty content. If 1) the attacker runs out of argument or 2) the number of iterations between De-fending and Being attack on the same point exceeds five, the attacker can either say 1) Appendix A. Descriptions of the SANP Protocol 49 "insisting" with his argument as content or 2) "offer compromise" with the compromise as content. Defender Requests Postponement Defender requests postponement If the attacker agrees with the date of postponement, he says "accept compromise". If the attacker agrees to postpone but with different date, he says "counter offer" with the new date as content. If the attacker is in higher authority, he can say "forcing concession" with the postpone date as the content. If both parties cannot reach an agreement on the postpone date, attacker can say "appeal" to require an arbitration from higher authority. If the attacker is in higher authority, he can say "pinning down" to force a compromise from the defender. However, if the number of iterations between Defender requests postponement and Attacker modify date exceeds five, attacker is forced to choose other responses. Attacker modify date If the defender agrees with the date, he should say "accept compromise" with the date as content. If the defender want a different date, he should say "counter offer" with the new date as content. If the defender is in higher authority, he can say "forcing concession" with the post-pone date as the content. Appendix A. Descriptions of the SANP Protocol 50 If both parties cannot reach an agreement on the postpone date, defender can say "appeal" to require an arbitration from higher authority. Pinning down The defender has to search for a compromise in his knowledge base. He should say "offer compromise" with the compromise in the knowledge base, or if there isn't any, with the attacker's argument as content. Defender Admitted Defeat Defender admitted defeat The attacker says "offer compromise" with the claim as its content. The content may be in the form of a contract so that both parties can keep track of the commitment made (as in [16]). Attacker offers compromise The defender says "accept compromise" and enters the contract into his knowledge base. Defender Offers Compromise Defender offers a compromise If the attacker agrees with the compromise, he says "accept compromise" with the com-promise as content. If the attacker agrees only partly with the compromise, he can say "counter offer" with the modified compromise as content. Appendix A. Descriptions of the SANP Protocol 51 If the attacker is in higher authority, he can say "forcing concession" with his proposed compromise as content. The attacker can also say "appeal" to require an arbitration from higher authority. However, if the number of iterations between Defender offers compromise and attacker modify compromise exceeds five, the attacker is forced to choose other response. Attacker modify the compromise If the defender agrees with the compromise, he says "accept compromise" with the com-promise as content. If the defender agrees only partly with the compromise, he can say "provisos in compromise" with the modified compromise as content. If the defender is in higher authority, he can say "forcing concession" with its proposed compromise as content. The defender can also say "appeal" to require an arbitration from higher authority. Attacker Offers Compromise Similar to Defender Offers Compromise. Defender Insists On Argument Defender insists on argument If there is alternative in the knowledge base, the attacker should say "offer compromise" with the alternative as content or if there isn't any, uses the defender's argument as the content. The attacker can say "appeal" to require an arbitration from a higher authority. Appendix A. Descriptions of the SANP Protocol 52 If the attacker is in higher authority, he can say "forcing concession" with its own argument as content. Attacker Insists On Argument Similar to Defender Insists On Argument. Request Arbitration Arbitration requested The arbitrator says "examining attacker" to ask the attacker to testify. Attacker being questioned The attacker says "testifying" with his argument as content. Attacker testified The arbitrator says "examining defender" to ask the defender to testify. Defender being question The defender says "testifying" with his argument as content. Defender testified The arbitrator says "make decision" with his decision as the content. Arbitration made The arbitrator says "End" to end the negotiation. Appendix A. Descriptions of the SANP Protocol 53 Defender Forcing a Concession Defender forcing a concession If the defender has not changed its initial position, the attacker says "withdraw" to withdraw the claim. If the defender has changed his initial position, the attacker says "one-sided compro-mise" with the defender's argument or proposal as content. Attacker Forcing a Concession Attacker forcing a concession The defender says "one-sided compromise" with the proposal of the attacker as content. Retreat Withdraw claim The defender says "end" to end the conversation. Appendix A. Descriptions of SANP Protocol 54 Protocol Diagrams for SANP OPENING STAGE +end k +ack ) • Make Claim KA(-3a) = Unacquainted status MAKE CLAIM + KA(-1a) -KA(-2a) ->{ Claim made + KA(-1c) KA(-2a) = make claim KA( - l a ) = agree KA(- Ic) = = dissent KA(Oj) = argumentative attack KA(3b) = withdraw KA(4cbd) = offer compromise KA(4cd) = accept compromise -KA(4cbd) Agreement ] ^ -end Retreat Tactical Phase Appendix A. Descriptions of SANP Protocol 55 T A C T I C A L PHASE +KA(1bbb) ^ L/C 1 CI lUtl admitted defeat +KA(1bba) ^ Defender f requests postponement +KAOccb) ^ Defender Insists on argument Defender L ^ K A C ^ b d ) ^ offer compromise KA(Oj) = argumentative attack KA(lbbb) = admitted defeat KA(lbba) = postpone KA( 1 ccb) = Insisting KA(4cbd) = offer compromise KA(lbcd) = argumentative defense KA( lcca) = repeated attack KA(3b) = withdraw -KA(3b) Retreat -KA( lcca) \ -KA( lccb) ^ Attacker * Insists on argument Attacker ^ -KA(4cbd) ^ offer compromise Appendix A. Descriptions of SANP Protocol D E F E N D E R R E Q U E S T P O S T P O N E M E N T 5 6 + end -KA(lcab) Pinning down Defender offer + KA(4cbd) compromise KA(4cda) = accept compromise KA(4cbc) = counter offer KA(K4ab) = force concession KA(lcab) = pinning down KA(4cbd) = offer compromise NCX60) = request arbitration Appendix A. Descriptions of SANP Protocol 57 DEFENDER ADMITTED DEFEAT KA(4cbd) = offer compromise KA(4cd) = accept compromise DEFENDER OFFER COMPROMISE endix A. Descriptions of SANP Protocol A T T A C K E R OFFER COMPROMISE Appendix A. Descriptions of SANP Protocol OFFENDER INSISTS ON ARGUMENT 59 -N0C60) Request Arbitration -KA(4ab) Attacker offer compromise Attacker forcing concession N0(60) = appeal KA(4cbd) = offer compromise KA(4ab) = force concession A T T A C K E R INSISTS ON ARGUMENT -KA(lccb) /Attacked Insists on \argument +N0(60) Request Arbitration Defender k +KA(4cbd) offer compromise *KA(4ab) Defender forcing concession NO(60)= appeal KA(4cbd) * offer compromise KA(4ab) = force concession Appendix A. Descriptions of SANP Protocol RFQUFST ARBITRATION N0(6C) = Examining N0(6da)= Test i fy N0(7a) = Make decision Appendix A. Descriptions of SANP Protocol DEFENDER FORCING CONCESSION 61 A T T A C K E R FORCING CONCESSION +KA(4ab KA(4cba) = one-sided compromise R E T R E A T 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items