Training Compositional Agents on Negotiation Protocols
M. Amor, L. Fuentes and J.M. Troya
Departamento de Lenguajes y Ciencias de la Computación
Universidad de Málaga
{pinilla, lff, troya}@lcc.uma.es
Abstract
Internet facilitates the rising of new markets, which has motivated the development of new technologies for e-commerce. The increasing number of e-markets poses a big challenge to e-consumers. Agent-based applications are the most appropriate for merchandising because software agents are suitable for automating tedious tasks that may be performed by the user, such as, the searching of goods. Furthermore, software agents are able to negotiate on user behalf according to negotiation protocols. However, new challenges arise from the evolution of negotiation mechanisms. The protocol interoperability is a challenging issue, because the set of interaction protocols supported by a software agent is usually fixed once the agent is created, and any protocol adjust needs agent replacement. Thus new software technologies for the development of more flexible, adaptable and reusable software agents are needed. We propose the use of component technology for the development of adaptive software agents to new negotiations protocols. In this paper we describe the compositional architecture of a software agent, and how we take advantage of the component orientation for training agents on new negotiation mechanisms at runtime.
1 Introduction
Nowadays the development of agent-based applications has increased due to the use of Internet in the diary life, especially that related with the e-commerce. Not only branded companies offer a web site for online shopping but also particular users can put on sale their goods on specialized sites, such as ebuy [1]. In e-markets, software agents help users to negotiate, besides automating some commercial tasks. For instance, software agents are able to search among available offers, find the best suited according user preferences, and also they may negotiate in different e-markets, such as auctions.
Negotiation has long been recognized as an essential topic in multi-agent systems. Negotiation between two or more parties or software agents is carried out using a negotiation mechanism, also known as a market mechanism [2]. The negotiation mechanism consists on a negotiation protocol, and a set of rules and constraints that determine the possible actions that participants can take. This mechanism must be public and shared by all software agents involved in the negotiation. The individual strategy adopted in the negotiation stays private, but it should be adapted to the negotiation protocol.
Emerging activity in this area [3][4][5][6] is currently focused on the automated negotiation, which involves the design of high-level protocols for agent interaction. This research endeavours to make more adaptive and flexible software agents. However, most of state-of-the-art about multi-agent systems present important shortcomings related to negotiation protocol interoperability.Software agents participating in a negotiation mechanism must agree in the interaction protocol and have to share the same assumptions about it. However in most of the agent-based solutions, interactions protocols or more specifically negotiation mechanisms, are fixed in the agent implementation, that means hard coded inside the agents [7][8][9]. It would be desirable that e-commerce software agents could understand an open-ended list of interaction protocols, but this characteristic is not really supported by current software agents. This is an important limitation issue for agent interoperability in open markets.
The use of standards guarantees the agreement about the negotiation protocol. FIPA [10] defines some standard interaction protocols for negotiation [11][12], and different well-known auctions [13]. However, although FIPA interaction protocols can be parameterised for different protocol instantiation, they do not cover all the possible auctions or negotiation policies. Additionally these protocols only formalize interactions between software agents, and omit information related to other aspects and rules included in the negotiation mechanism [3]. Misplaced information could complicate the agent participation in a negotiation (e.g. auction
termination criteria could be different for two participants in an auction). Hence, a standard should either establish something more than the flow of messages between participants, including which negotiation rules have to be applied, or provide a standardized way of agreeing them [3].
Another challenge in dynamic negotiation is facing the evolution of a negotiation mechanism. If the specification of a negotiation protocol changes, all the software agents that comply with it should be updated. The cost of producing new agent versions depends on the adaptability and extensibility of the software agent model. Unfortunately, these features related to software evolution are not widely taken into account in the development of software agents. It is commonly agreed that component-based software engineering (CBSE) provides advanced techniques that can be applied to the design and development of software agents [14][15] by plugging the reusable software components.
We propose a component-based architecture for developing software agents that deals with some of these challenges [16]. The benefits of component-oriented systems lies on their increased flexibility: a system built from components should be easier to recompose to address new requirements [17]. A compositional design may allow software agents to be dynamically adapted to support new negotiation protocols and new functionality. Our goal is to endow software agents with a high-level mechanism for the runtime adaptation of software agents to be able to participate in any negotiation regardless interaction protocols supported.
Agent behaviour is provided by different plug-ins components. In order to improve agent modularisation we apply the separation of concerns technologies. Concretely functionality and coordination issues are separated internally in different entities. The composition between agent internal components is performed at runtime, allowing the reconfiguration and adaptation of agent behaviour to support new interactions.
To evaluate our contribution the model is applied to the domain e-commerce. One of the most extended negotiation mechanisms in e-commerce is the auction. Internet hosts many auction sites that work as traditional auction houses, where software agents are used to automate the negotiation. A key aspect of these systems is the richness and flexibility of the inter-agent interactions.
The benefits of our proposal can be successfully applied in “real” scenarios of open markets, where software agents are demanded of more flexibility and interoperability. For example, suppose a user called “Peter”, who is interested in buying the first edition of Shakespeare’s famous novel “Othelo”. After searching for it in several bookstores, he decides to try on the Internet, and he launches a software agent to bid on behalf of him. But, the only place that offers a special edition of the desired book is an auction site where the type of auction is the Vickrey auction, and Peter’s agent only supports the English auction. Well, if Peter decided to use one of our software agents, he can have a last possibility. Peter’s agent can be trained to participate in this auction, following Vickrey auction rules. Peter’s agent will adapt quickly to the new protocol, without any need to change its internal functionality, or lose Peter’s preferences (product, maximum price, etc).
2 Software Agent Compositional Model
In this section we describe a compositional model for software agents. Software agents are systems that perform actions or tasks autonomously to reach a set of goals. Our model encapsulates agent functionality in software components. Modelling agent functionality as components we find that a software agent contains components for data storing (e.g. to store its internal goals, facts, etc.), or providing application domain functionality (e.g. buy, bid, search), and components that coordinate the agent internal and external execution. To improve agent functional decomposition we apply the principle of separation of concerns [18], that is, we model the coordination issue separately in an entity called connector. We mean by coordination the flow control between agent inner components and/or external agents. Thus connectors model negotiation protocols. In a previous work we successfully applied this paradigm [19][20]. In this case, it eases the agent dynamic adaptation to new interaction protocols through the runtime composition of components and connectors inside the software agent.
Figure 1 shows the UML class diagram of the proposed compositional architecture of a software agent based on components and connectors. We use UML stereotypes for modelling the principal entities of our model, which are Component, Connector, Mediator and Interface.
Figure 1. Compositional Architecture for Software Agents.
Connectors coordinate the different interactions or conversations the agent is involved. An agent can participate in more than one interaction or conversation simultaneously, and a protocol connector controls each conversation. Connectors coordinate dialogues according to a specific protocol (e.g. English Auction Negotiation Protocol). These connectors differ only in the coordinated protocol, given by a template filled by the protocol specific rules, transitions and constraints.
Components encapsulate data and behaviour. Some behavioural components are always presented in the architecture providing the generic agent functionality (BasicAgentActions and TpfNActions components), such as to send a message, or to store the general data (KnowledgeBase component). Domain specific behaviour is provided also by components. The components will be plugged into agent functionality on demand being domain dependent, and are changeable over the lifetime of the agent. In Figure 1, the e-market component offers functionality to perform e-commerce tasks, such as generate a bid or make an on-line payment. Interface components manage agent’s external interactions. They process the input messages and send replays to agent platform for delivery. The component AgentExternalCommunication (AEC) encapsulates the external communication interface of the agent. This interface component deals with incoming and outgoing messages. Incoming messages are first processed by this component, and it may discard messages, which are not syntactically well formed. The component AgentInterface (AI) contains the public agent interface, which is an extension of the ordinary interfaces regarding CBSE concepts. For instance, AI includes the provided services, public negotiation protocols, etc., (the agent interface description is beyond the scope of this paper). Concerning this paper, this component mainly stores the templates of the supported protocols.
The mediator component AgentCompositionalCore (ACC) performs the coordination of messages received by the agent. This entity is a mediator between components and connectors, performing the dynamic composition of them. The ACC receives incoming messages from the AEC component, dispatching them to the appropriate conversation according to the conversation identifier contained in the message. In addition, this component launches the connector that encapsulates a specific protocol as a new conversation or interaction is initiated. Dynamic composition is used for the late binding of coordination connectors and the agent behaviour provided by components. A relevant characteristic of out model is that components and connectors have no
direct references among them, which increase their dependency. For instance, auction connectors will be linked to e-market actions component, since this component encapsulates the functionality of any auction. Dynamic composition also allows plugging a new component implementation into the agent dynamically, or upgrading this compositional agent without replacing the agent.
The next section shows the execution of a protocol through an example. Concretely, we use the protocol that instructs a new negotiation protocol.
3 Agent Protocol Training
In this section we will show the training protocol of a new negotiation protocol. We mean by the term training to tell somebody how to do something. In our case somebody is the agent, and the action is how to follow a protocol. Actually, the software agent has enough functionality to use a negotiation mechanism, because it can send messages, receive messages, and do a particular activity (sell, buy). Imagine that Peter’s agent is interested in participate in an auction of books, but it does not understand the negotiation protocol. The auctioneer agent will train Peter’s agent through Training Protocol for Negotiation (TPfN). During the protocol execution, the trainee agents receives a protocol description that contains the protocol state machine (STD) and the actions that the agent has to perform during a negotiation, for example an auction. The training protocol does not add functionality to the agent, but increases its interaction capability.
Figure 2. TPfN Protocol Diagram.
A message sequence diagram of TPfN is given in Figure 2. Participants involved in the training process are the trainer and the trainee agents. The trainer agent sends the trainee agent the description of a new negotiation mechanism. This protocol is composed by two FIPA interaction protocols. The first action is taken by the trainer inquiring trainee agent about its disposition to be trained in a new negotiation protocol
(Query Interaction Protocol [21] in Figure 2). This decision is taken by the agent based on the minimum functionality required, suggested by the trainer in the query message, and its own internal constraints. The trainee agent notifies whether it accepts to be trained by inform message or not with refuse or not-understood messages. If the trainee agent wants to be trained then the training is initiated (Request Interaction Protocol
[22] in Figure 2). The process of training consists on communicate a negotiation protocol description in the content part of a request message. In the example, the trainer agent, for example the auctioneer agent, inquires the bidder agent whether it understands the Vickrey auction protocol with the semantic defined by the e-market ontology.
TPfN protocol is defined using FIPA communicative acts and protocols, in such a manner that can be implemented by any FIPA compliant agent platform. The message content language used is XML, that is a standard language for representing structured information. It is used primarily in the context of Internet applications and communications. The essence of XML is the separation of abstract content from presentation. A major advantage of using XML is the range of XML tools that can be applied. Besides the matters referred to, XML is programming language-neutral.
Accordingly, to train a software agent means to give the correct instructions. These instructions explain the agent what to do to follow the protocol. Both agents (trainer and trainee) have to agree about the terms used in the given instructions. These terms refer to agent internal actions, variables or predicates. The semantic definition of these terms is comprised in an ontology. The ontology involves a meaning and both agents share this meaning. This concept is similar to a role : if a software agent commits the e-market ontology means that this component understands the semantic of the defined terms that correspond to actions (bid , buy ), and exists a correspondence between these actions and the component internal functionality. This means that there is a component that implements the ontology functionality required. Using object oriented terminology this component is a container of all the methods defined as terms in an ontology.
Query-if / T2 (b) Figure 3. (a) STD and (b) TPfNActions component interface.
In this example, at least two ontologies are considered necessary. The ontology that defines the terms for training, and another one that defines the terms used in the trained protocol (in the example, the e-market ontology). The actions defined in the TPfN ontology are given in Figure 3 (b). These actions are invoked in the training protocol execution to validate and extract the protocol description contained in the request message of the TPfN protocol.
Internally training is performed through a protocol, thus it is integrated in the agent architecture by a protocol connector, and a component that commits the TPfN ontology (TpfNActions component of Figure 1). The training process, in the trainee agent side, consists on translating the negotiation protocol description to template. A negotiation template is represented internally by the protocol state transitions rules (Figure 4) and the description of the transitions as a set of agent actions (Figure 5). The state machine of the TPfN connector is shown in Figure 3 (a) where the circles are states and the arrows are transitions from one state to another, which is equivalent to the internal representation given in Figure 4.
Figure 4. TPfN protocol :Table representation of the STD transition rules.
A transition is described as a set of one or more agent actions. Transitions of TPfN protocol are described in Figure 5. The actions are included in the TPfNActions component interface, and in components that provide basic agent behaviours. While verifyProtocol and trainProtocol actions make reference to TPfN specific actions, sendMessage and addVar are part of the agent basic functionality provided by the components BaiscAgentActions and KnowledgeDatabase of Figure 1. These actions do respectively the sending a message and the adding data to a knowledge database.
Figure 5. Table representation of transitions description in actions.
Any protocol operation mode is the same, and we illustrate it through the TPfN protocol. When the first TPfN protocol message is received (query-if message), the TC component creates a TPfN connector. The implementation of the protocol connector is the same for all protocols. Only differs the protocol template provided on instantiation. Once it is created and initialised (initial state), the mediator component ACC forwards the first message to the TPfN connector. This connector checks which state transition rules are applicable or active. For example, having a look at Figure 4 when quey-if message arrives, first and second rules become active. Afterwards the TPfN connector evaluates active rules. Rules are conditioned by the actual state and an input message. But also can be conditioned by a predicate ( e.g. isTrue(understandProtocol(…))) that has to be evaluated when the state and message conditions are fulfilled.
It is possible that several rules are successfully evaluated, but the connector only chooses one, executes the corresponding transition, and modifies the actual state according to the rule.
In the example only one rule has success, because the connector has to evaluate a excluding conditions (isTrue(understandProtocol(…)) and isFalse(understandProtocol(…) predicates). The action understandProtocol(“protocol-name”,ontologies) performed by TpfNActions component decides if the agent
is going to be trained based on the new protocol and the ontology specified in the query-if message content. Protocol execution continues if the agent accepts to be trained. After informing about its disposition (transition T2), the connector waits for the new protocol description to come. When the message containing the XML protocol specification arrives the TPfN connector executes transition T3, which performs the new protocol validation and training from the received specification. The TPfN connector invokes verifyProtocol
action over the TPfNActions component. The component uses component introspection1 property to check if the agent commits the ontology referred in the specification (if the agent has the corresponding components that implements the former ontology); and to check if the agent supports the protocol message content language ( if the agent has an appropriate language parser); moreover, the component could perform a formal verification.
If the protocol specification is successfully validated an agree message is sent. Next step is to translate the XML description to a new protocol template, and add the new protocol to agent capabilities. This is done by the trainProtocol action of the TPfNActions component. This action generates the protocol template, and updates the AgentInterface component adding the new template.
4 XML Protocol Description
The interaction mechanism description is not a trivial issue, as there are many aspects to consider. A simple description of the flow of interchanged messages is not enough, because it is also necessary to express the actions the agent performs during interaction. When agent is instructed about a new interaction mechanism it needs to know how entry and output messages relate or link with its internal behaviour.
In last section we showed how the agent is trained. Now, we present how to describe a negotiation mechanism in XML through an example. The example is based on the Vickrey auction protocol, which is not a FIPA standard, but is FIPA compliant so it can be implemented in any agent platform. STD is given in Figure 6.
Figure 6. State transition diagram for Vickrey Auction Interaction Protocol.
Every transition is labelled with the received message that triggers the transition. Since the STD raises from the interaction protocol diagram, for every transition is also specified the message sent in response. As can be seen, it is a very simple protocol. In a Vickrey Auction, also known as second-price sealed bid, the bids are submitted to auctioneer with no knowledge of the bids of others. The auction winner, that is the best bid, pays the second highest amount bid [23].
Some pieces of the XML representation are given in next figures. The main structure of the description is given in Figure 7. The protocol is described in terms of messages (either input and output messages), states, transitions, and state transition rules.
1 Introspection is the ability of a component to say something about its behavior. Component interfaces give information about the offered services, required services, quality of service, how to customize the appearance and behavior of a component and so on.
Figure 7. XML protocol description.
Firstly, the specification describes all the messages that are interchanged between the protocol parties. The description of a message has to include the performative and should contain at least a description of the content. An identifier can be assigned to the description to make reference lately in the specification, inside the rules and transitions. Figure 8 shows how is described the cfp (Call for proposal) message in the protocol description and gives an example of a message sent by the auctioneer to the bidder advising Peter’s agent that it is going to be auctioned a book, and its initial price its 10 (€). This message is received at the beginning of the interaction.
Figure 8. Example of Call for Proposal Message: XML Description and Runtime Instance.
The FIPA performative cfp is used to open an auction, and informs that the auctioneer is prepared to receive bids. The XML description shows that this message is identified as cfp and the content of this message includes the initial price or the best bid (bid element) offered for the auctioned product (product element). The second section of the protocol description identifies the states and specifies the initial state. The description for the Vickrey auction protocol is given in Figure 9:
…
Figure 9. XML state enumeration.
The third section describes the transition as a set of sequenced actions. The execution of a transition actions implies dynamic method invocations on internal agent components. When the TPfNActions component is validating the protocol checks (using component introspection) that the actions listed in the transitions are available in the internal component (the one that commits the ontology).
SetValue(last-best-bid,
getContent(cfp,bid))
Figure 10. XML description of a transition.
Figure 10 gives an example of part of a transition, and gives an example of nested actions. An action can provide a value for another action parameter. This transition is composed of setValue action, implemented in BasicAgentActions component. This action assigns to the variable last-best-bid the content of the message cfp tagged as bid (showed in Figure 8). The action getContent retrieves the content field of an entry message. The TPfNActions component validates that the getContent return type and the parameter (the value that is assigned to the variable) are compatible.
After the transition execution there is a variable named last-best-bid with value 10 in the KnowledgeDatabase component. This variable can be retrieved from the knowledge database using the action getValue(“last-best-bid”).
…
Figure 11. XML rule description.
Lastly the state transition rules that condition the interaction mechanism are described. These rules specify for a state and an entry message, which transition is executed and which is the next state. In addition a rule application can be conditioned by the evaluation of an action. Figure 11 shows the description of one rule of the Vickrey auction protocol. The rule is applied when the agent is waiting for the auction to start and the cfp message arrives . This rule is only conditioned by the actual state (waiting-for-cfp state) and the input message (cfp message), both described by their identifier. Also the triggered transition and the next state are described by their identifier (transition2 and waiting-for-inform ). The protocol specification described in this section was validated and verified during training.
5 Related Work
In most of multi-agent systems the interaction mechanism is fixed once the agent is created. To extend, update or simply change a parameter of the understandable protocol set it is necessary to replace the agent. Also, the
protocol coordination and the related agent internal behaviour are tightly coupled. One of the agent design challenges is to endow software agents with flexible mechanisms to support almost any interaction protocol. Some recent research works about this issue have recently arisen. In [3] is proposed an explicit representation of the negotiation mechanism. It is a modular approach to negotiation mechanisms that defines a general protocol for negotiation, which can be specialized with declarative rules. But this approach is working for JADE and JESS. We can find proposals [6][4] that provides a framework that enables agents to execute interaction protocols explicitly represented (respectively contained in XML documents or in policy packages) but not in a declarative form. In both cases, protocols representations are based in production rules and states. However the former proposal does not give any hint about how the messages interchanged are related with the agent internal functionality. It simply present the XML protocol representation based on the AUML protocol specification. The latter approach allows exchanging and installing protocols in agents dynamically. These agents execute a protocol by rules, states and transitions. For every transition an external code is upload and executed. The agent does not have control over this code at all, and it is not related with the agent internal state. This idea also is applied in [5] where agents carry application-specific actions, which can be loaded and modified on the fly. Uploading external code at runtime is not very efficient, and it also presents security drawbacks. In our approach software components providing new functionality are plugged once at the beginning of the interaction, but not for every transition of the protocol state machine.
6 Conclusions
In this paper, we propose a component-based architecture for software agents that combine component orientation and separation of concerns. Agent domain specific functionality and coordination are modelled in separated entities. Functional components (e.g. e-commerce) are bound at runtime and linked with the corresponding negotiation protocol connector.
The flexibility provided by the component orientation enables software agent to support new negotiation protocols. We outline the TPfN protocol for training at runtime a software agent in a new negotiation protocol specified in a XML schema. This mechanism increases agent interoperability regarding protocol interactions support inside an application domain. We have presented the benefits for the e-market domain, where the agent is not restricted to negotiate through a fixed set of negotiation protocols.
Now we are developing a FIPA compliant working prototype of a generic software agent using the compositional architecture showed in previous sections.
7 References
[1] eBuy. The world′s Online Marketplace. https://www.doczj.com/doc/725568725.html,
[2] A.R. Lomuscio, M. Wooldridge, N.R. Jennings, “A Classification Scheme for Negotiation in Electronic Comerse”In Agent-MediatedElectronic Commerce: A European Agentlink erspectiv. eds. F. Dignum and C. Sierra, pp. 19–33. Springer Verlag, 2001.
[3] C. Bartolini, C. Preist and N.R. Jennings. “Architecting for Reuse: A Software Framework for Automated Negotiation”. AOSE 2002.
[4] T. Iwao et al. “A framework for the exchange and Installation of Protocol in Multi-Agent Systems”, CIA 2001, LNAI 2182, pp. 211-222, 2001.
[5] Q. Chen, P. Chundi, U. Dayal, and M. Hsu. “Dynamic Agents”. CoopIS 98. 1998.
[6] J. Freire, L. Botelho, “Executing Explicitly Represented Protocols” 1st Workshop Challenges in Open Agent Systems, 2002.
[7] FIPA-OS. Emorphia. https://www.doczj.com/doc/725568725.html,/
[8] ZEUS. http://193.113.209.147/projects/agents/zeus/
[9] JADE. http://jade.cselt.it/
[10] FIPA. The foundation for Intelligent Physical Agents. https://www.doczj.com/doc/725568725.html,
[11] FIPA English Auction Interaction Protocol Specification. Foundation for Intelligent Physical Agents, 2000. https://www.doczj.com/doc/725568725.html,/specs/fipa00031/
[12] FIPA Dutch Auction Interaction Protocol Specification. Foundation for Intelligent Physical Agents, 2000. https://www.doczj.com/doc/725568725.html,/specs/fipa00032/
[13] FIPA Contract Net Interaction Protocol Specification. Foundation for Intelligent Physical Agents, 2000. https://www.doczj.com/doc/725568725.html,/specs/fipa00029/
[14] F.M.T. Brazier et al. “Compositional Specification and Reuse of a Generic Co-operative Agent Model”, International Journal of Cooperative Information Systems, 9(3), pp. 171-207, 2000.
[15] N. Skarmeas, K.L. Clark, “Component-Based Agent Construction”, International Journal of Artificial Intelligence Tools, 11(1), pp. 139-163, 2002.
[16] M. Amor, M. Pinto, L. Fuentes, J.M. Troya, “Combining Software Components and Mobile Agents”, ESAW 2000, LNAI 1972, Springer-Verlag, 2000.
[17] O. Nierstrasz, L.Dami, “Component-Oriented Software Technology”, Object-Oriented Software Composition, eds. O.Nierstrasz and D. Tsichritzis, Pp. 3-28, Prentice Hall, 1995.
[18] G. Kiczales et al. “Aspect-Oriented Programming”, Proceedings of ECOOP′97, LNCS 1241, Springer-Verlag, 1998.
[19] L. Fuentes, J.M. Troya, "A Java Framework for Web-based Multimedia and Collaborative Applications", IEEE Internet Computing, 3(2): pp. 55-64, April 1999.
[20] L. Fuentes, J.M. Troya, “Coordinating Distributed Components on the Web: An Integrated Development Environment”, Software Practice & Experience, 31(3), pp. 209-233, March, 2001.
[21] FIPA Query Interaction Protocol Specification. Foundation for Intelligent Physical Agents, 2000. https://www.doczj.com/doc/725568725.html,/specs/fipa00027/
[22] FIPA Request Interaction Protocol Specification. Foundation for Intelligent Physical Agents, 2000. https://www.doczj.com/doc/725568725.html,/specs/fipa00026/
[23] K. Reynolds, “Going ... Going … Gone! A Survey of Auction Types”, Agorics Inc. August 2002. https://www.doczj.com/doc/725568725.html,