alexa A Critical Investigation of Agent Interaction Protocols in Multiagent Systems | Open Access Journals
ISSN: 0976-4860
International Journal of Advancements in Technology
Like us on:
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

A Critical Investigation of Agent Interaction Protocols in Multiagent Systems

Rashmi Singh1*, Aarti Singh2, Saurabh Mukherjee1

1Banasthali University, Banasthali, Rajasthan, India

2Maharishi Markandeshwar University, Mullana-Ambala

*Corresponding Author:
Rashmi Singh
Banasthali University
Banasthali, Rajasthan, India
E-mail: [email protected]

Visit for more related articles at International Journal of Advancements in Technology

Abstract

Although, multiagent systems are operative from more than three decades now, very few agent interaction protocols meeting the communication specific requirements have been designed till date. Researchers have strongly been demanding for a protocol which is able to formalize the semantics for flexible and understandable communication i.e. to understand the meaning of rules of communication and interaction. Since, agents active in a multi-agent system are socio-technical entities that interact with its peers for every day computing; therefore, a protocol that meets the above concerns is highly desired. The current investigation of existing protocols for agent interaction in multiagent systems is critical as it investigate both positive and negative aspects of available protocols; thus laying the foundation for a novel protocol.

Keywords

Multiagent Systems, Agent Interaction Protocols, Semantic Communication

Introduction

An interaction protocol enables agents to exchange messages and establish conversation with other competing agents. Agent interaction has primarily evolved as a result of cross-organizational business processes and socio-technical systems. In order to converse in an open environment such as multiagent systems, agent is provided necessary infrastructure specifying communication or interaction protocol [1]. Fundamentally, an agent is assumed to have ability to communicate i.e. ability to receive (perception) and send (action) messages. With this ability, agents communicate with their peers to achieve better goals and enhance the efficiency of the system. During this communication, agents coordinate, cooperate, compete, plan and negotiate on various aspects turning into a social entity. A multi-agent system [2] in this state behaves as a unit and is known as a coherent system. Agents interacting in a coherent system may interact directly or indirectly with each other; however all of them must follow certain rules of synchronization known as interaction protocols especially, if there is a possibility that they can interfere with one another in a destructive way. The key concern here is that the semantics behind these rules should be clear and should be interpreted in the way they are designed for. Unfortunately, the semantics of communication had not been so important earlier and hence were not considered at the design time. But with the growing popularity and applications of multiagent systems, this shortcoming has emerged as a bottleneck in the practical implementation of many real-time multiagent systems.

This paper has been structured into five sections. Section 2 scrutinizes the taxonomy of existing agent protocols and highlights a comparison amongst them. Section 3 focuses on related work by reputed researchers. Section 4 presents the gaps in literature and possible solutions that could bridge these gaps. Also, it aims to focus on the design issues associated with the novel protocol. Section 5 concludes by highlighting the future research directions in the field under consideration.

Agent Interaction Protocols

Agent interaction in a multiagent system is primarily based on two important aspects i.e. degree of heterogeneity and degree of communication [3]. A multiagent system is usually a mix of both homogeneous and heterogeneous agents. Further, theses agents can be classified as homogeneous non-communicating agents, heterogeneous noncommunicating agents and heterogeneous communicating agents. The aim of this section is to identify the interaction protocols suitable for the third category of agents’ i.e. heterogeneous communicating agents only. A conceptual taxonomy of agent based interaction models is given in [4] (see figure 1).

advancements-technology-conceptual-taxonomy

Figure 1: A Conceptual Taxonomy of Agent-based Interaction Models [4]

Agents in a distributed system can communicate directly as well as indirectly. In the former case, an abstraction of the actual communication channel is not required while in the later case, creation and exploitation of artifacts that represent a media for the agents' interaction is required. Direct Interaction models usually employ Agent Communication Language (ACL) [5, 6, 7]. For instance, in order to effectively communicate, agents must "know" each other by a unique name. This issue is dealt by either providing direct apriori information about peer agents in the system or the mediator agents can be used for agent discovery and development of more complex acquaintance models which adds robustness and scalability to MAS.

Technically, agent communication is generally indirect and uses an end-to-end message passing mechanism. Indirect agent interaction models are classified into artifact mediated and spatially grounded models [4]. The former provide the design and implementation of an artifact while the later focuses on the agent’s environment.

On the basis of above taxonomy, various interaction protocols which have been in existence are being depicted in figure 2 and following subsection provides an overview of each one of them.

advancements-technology-existing-interaction

Figure 2: Existing Agent Interaction Protocol

Coordination Protocol

Coordination Protocols are executed among multiple agents to satisfy both individual and group goals. Example of coordination protocol includes providing information to peer agents on time. Coordination protocols are basically required to maintain dependencies between actions of various agents, to meet global constraints and more importantly when no one agent has sufficient competence, resources, or information to achieve system goals, coordination adds intelligence of the system. In order to construct a distributed coordinated system, prime requirement is to distribute control and data which in turn implies that agents have autonomy to generate new actions and to decide which goals to pursue next. The actions of agents, dependencies between the goals and the resources required to execute the actions are represented using AND/OR goal graphs [8].

In a multi-agent coordinated system, a team of agents undergo a joint commitment towards a common goal. Each team member expects that the status of commitment along with the status of objectives shall be minimally informed to all members. If any of the team member opts to change its belief, it should be informed else this change may jeopardize the entire system. Moreover, on such a betrayal, the committed agents reassess themselves w.r.t. to a common goal which is yet to be achieved.

Cooperation Protocol

Cooperation protocols are based on divide and conquer strategy. Initially, a complex task is decomposed into subtasks which later are distributed among different agents according to the role they play in the system. This strategy aims to reduce the complexity of tasks and optimize resource allocation. Common mechanisms used in task decomposition are market mechanisms, contract net, multiagent planning and organization structures. The decomposition can be based on the agreements, expertise of any agent, functional requirements or each agent in a system may have fixed role to play. Whatsoever may the way of task decomposition, the distribution is made ensuring the following [9]:

• Avoid overloading critical resources

• Assign tasks to agents with matching capabilities

• Make an agent with wide view assign tasks to other agents

• Assign overlapping responsibilities to agents to achieve coherence

• Assign highly independent tasks to agents in spatial or semantic proximity minimizes communication and synchronization costs

• Reassign tasks if necessary for completing urgent tasks

Contract Net Protocol

Contract Net Protocol is a high level protocol which is concerned with the interpretation of the communication rather than the transmission of bit streams. CNP facilitates distributed control of cooperative task execution with efficient inter node communication and also allows participation in fully automated competitive negotiations. It categorizes agents as either Initiator/Manager or Participant/Contractor [10]. The agents can exchange their roles for different contracts as CNP allows further delegation of subcontracts to other agents. FIPA has standardized contract net interaction protocol and the flow diagram for the same is as depicted in figure 3.

advancements-technology-fipa-standardized

Figure 3: FIPA Standardized Contract Net Protocol

CNP exists mainly between an Initiator agent (IA) and a contractor agent (CA). Now the IA and CA undergo steps as illustrated in figure 3 repeatedly until a contract gets negotiated and finalized. CNTEP, a variation in this form of CNP has also been proposed in 2010 [11] by Singh and Juneja and further, an improvement in the same is being suggested in [12]. The CNTEP version considers trust establishment among negotiating agents as one of the prime factors before actual communication starts. Figure 4(a) and figure 4(b) given below depicts the working of CNTEP and its extended version.

advancements-technology-contract-establishment

Figure 4(a): Contract Net Trust Establishment Protocol [11]

advancements-technology-extended-contract

Figure 4(b): The Extended Contract Net Trust Establishment Protocol [RCNTEP]

Negotiation Protocol

Negotiation is a process by which joint decision is reached by two or more agents, each trying to reach an individual goal [13]. The major features of negotiation are language used by participating agents, protocols followed by agents as they negotiate and the decision process used for concession, criteria for agreement and to determine its position. Negotiation techniques are either environment centric or agent-centric. In contrast to environment-centric techniques which focus on designing the rules such that participating agents are able to negotiate irrespective of their origin and capabilities, the agent-centric approach considers designing the agents such that they are able to fit into an existing environment. An agent while negotiating may conflict, compromise and choose to cooperate with other agents. In case of conflict, the agents will not benefit by negotiating and hence should choose to act alone. In compromising state, agents are forced to get into negotiations as single agent can not achieve the desired objective while in cooperative state, all offers are acceptable by both negotiating agents [13].

The next section presents a study of literature work being carried out by the founders and pillars in the allied domain.

Literature Review

The development of multi-agent system involves research issues such as cooperation protocols, distributed control and effective communication. In fact, once agents are ready for collaboration, they will need to find other agents they need to collaborate with. Such a task is easy if they know exactly which agents to contact at which location. However, our everyday human experience has shown us that such a static setting is very unlikely to exist: people are usually on the move and they are not always readily available to interact with others. The same holds true for dynamic multi-agent systems: agents need support to find other agents. Such are the motivations pursued by research groups working on the standardization of dynamic collaborative multi-agent systems [14].

Chopra et al. [1] presented a detailed study about research directions in agent communication. Authors highlight that techniques used in traditional distributed systems which are primarily meant for enumerating possible message sequences without considering the message meanings. Hence, these are not well suited for agent communication. Authors further emphasizes that contrary to existing protocols, multiagent protocols should be flexible so that agents can exercise their autonomy but at the same time, agents should also be held accountable for their actions. Singh [15] call attention to the fact that along with syntax and semantics, pragmatics i.e. how messages can be used or what they mean; is also important. The metrics to evaluate qualitative aspects of multiagent protocols still need to be decided [16].

Sycara in an article [17] has raised several issues pertaining to multi-agent systems. For instance, how do we enable agents to communicate and interact? What communication languages and protocols do we use? How can heterogeneous agents interoperate? What and when can they communicate?, just to list a few. One of the major impediments while designing MAS is the lack of flexible tools and protocols to specify agent’s problem solving behavior.

There have been several proposed methodologies for analyzing, designing, and building multi-agent systems [18], most of which are based on existing object-oriented or knowledge-based methodologies. In contrast, MaSE [19] is a general purpose methodology for developing heterogeneous multi-agent systems but wider application of the same could not be found in literature. Gerard and Singh [20] proposed a business protocol that decouples agent and protocol designs in contrast to conventional designs which offers coupling both agent and protocol. This work suggests modifying JADE middleware so as to accommodate run-time modifications in agents but the same has not been carried out so far.

Work by Genesereth and Ketchpel [21] raises number of important questions not only related to agent communication languages but also to the design of agents so that they can communicate in an environment. Authors talk about the hindrances posed due to interoperability and also inconsistencies due to syntax and vocabulary. Further, in order to address the incompatibility and inconsistency issue, Agent Communication Language (FIPA-ACL) seemed to be satisfying the need initially but later on with the developing complex systems, FIPA-ACL also started posing problems such as lack of sufficient performatives.

Cao and his team constructed groups of mobile robots with an aim to study issues such as group architecture, resource conflict, origin of cooperation, learning, and geometric problems and reported that as yet, few applications of cooperative robotics have been reported, and supporting theory is still in its formative stages [22].

Few works [23,24] mentions that achieving coordination in multi-agent systems is a major problem. Although various protocols for task allocation, resource allocation and negotiations have been proposed but with the proliferation of agents, the demand for coordination protocol suitable to a heterogeneous domains have increased. Another article by Durfee and Rosenschein mentions that in an open system where standard task level protocols among agents are brittle or undefined, allowing interaction patterns and protocols to emerge from first principles i.e. agent preferences, abilities, and rationality in a MAS manner is a promising approach [25, 26].

Few researchers [27, 28] have questioned the cost incurred either in terms of required bandwidth for the exchange of information or in terms of risk of revealing the information to peer agents. Further, author doubts on the reliability of communication which in turn adds another dimension of complexity to the problem [29]. A community of researchers [30] is concerned about the inheritance anomaly i.e. limitation of reusing the existing synchronization methods and remedial solutions for the same exist in context of conventional object oriented concepts but none of them is directly suitable for agent oriented computing and hence extension of the current solution is still an open challenge.

Beer et al. have raised various questions [31] related to negotiation in multi-agent systems with the aim to categorize certain protocols as negotiation–based. On a similar note, author points that “Can all aspects of negotiation be incorporated into predefined communication protocols?”[31] which, is clearly a debatable issue and is critical research issue. Efforts have been put [11,12,13] suggesting the improvements in the backbone protocols such as contract net protocol and hence current research work find motivation to propose a new protocol which would be generic and hence suitable to most of the applications.

A critical look at the aforementioned literature reflects some aspects of these issues have been addressed; still practical developments, run-time mergers and analysis of different protocols in different domains need to be investigated. The current research work draws motivation from the above open challenges. Few gaps that still prevail in the domain of current work are being listed in the upcoming section.

Gaps in Literature

Although a general idea of various interaction protocols was presented above but the said protocols are implemented in application-specific mode. Hence, a generalized model is very much required. Few of the prominent gaps that need to be bridged include the demand of interaction protocol which is flexible and supports semantic based communication. A compatibility check between two communicating entities needs to be ensured. Above mentioned studies emphasized on facilitating dynamic interaction amongst agents which is a complex and untouched challenge as agents operate in a complex and distributed environment usually. Demand-based and urgent communication sometimes gets mishandled due to ambiguity in understanding the message. Therefore, semantics of messages communicated should be unambiguous and should be clearly understood by both the communicating parties. Further, lack of performatives in agent communication languages also contributes to limitation of agent interaction. Available literature does not support much on this issue. Further, gaps such as enabling agents to interact, selection of communication language and protocol, issues pertaining to heterogeneous entities are big hindrances in smooth implementation of multi-agent systems. One of the most difficult to handle problem is allowing run-time modification of existing agents which is not possible at the time of listing. The trustworthy and reliability of agents in operation is also one of the major factors acting as obstacles for the wide usage of multiagent communities. Above listed gaps are just few of the prominent issues that must be addressed for agent technology to develop and contribute towards the intelligent systems.

More precisely, some aspects of theses issues have been addressed still practical developments and integration of different protocols leading to the design of a new and generic agent interaction protocol still need to be investigated and hence forms the basis of motivation carrying out this research work.

Conclusions and Future Work

The critical investigation of existing literature presented above reflects that in contrast to traditional distributed systems where the meaning of communication remains abstracted, in MASs the meaning shall not only be explicitly defined but also shall be made public to ensure compliance checking as implementation of agents may change from one instance to another. In fact, various requirements have given birth to various theoretical solutions such as speech act theory, agent communication languages, ontologies for agent communication and coordination languages. In order to address the issues prevailing in existing protocols, various solutions have been proposed, few of them have proved to good practically but most of others fail to compete practically. For instance, Vanderveken in 2005 proposed an abstract idea of dialogue and conversation which is a challenging and still an open research problem [32]. The challenges in the multiagent community are untouched primarily due to the fact that most of the agents based systems designed so far are domain specific and very few researchers have thought of designing a generic protocol.

References

[1] Chopra et al. ,” Research Directions In Agent Communication”, TIST, Vol. V, No. N, December 2010, Pp:1-26.
[2] Michael Wooldridge, “An Introduction To Multiagent Systems”, Published By Wiley Publications.
[3] Stone P and Veloso. M.M “ Multiagent Systems: A survey from machine learning prespective” Tech. Rep. CMU-CS-97-193, Carnegie Mellon University, Pittusburg, PA
[4] Stefania B., Sara M. And Giuseppe V., Agent Based Modeling And Simulation: An Informatics Perspective Journal Of Artificial Societies And Social Simulation 12 (4) 4, 2009.
[5] Foundation for Intelligent Physical Agents. FIPA 2001, "Specification : Agent Communication Language", Available At Http://Www.Fipa.Org
[6] N. R. Jennings, “Coordination Techniques For Distributed Artificial Intelligence”, In G.M.P O’Hare And N R Jennings Editors, Foundation Of Distributed Artificial Intelligence, Pp:187-210, John Wiley And Sons, 1996.
[7] Michael N. Huns & Larry M. Stephens, “Multiagent Systems & Societies Of Agents”,
[8] N. R. Jennings, “Coordination Techniques For Distributed Artificial Intelligence”, In G.M.P O’Hare And N R Jennings Editors, Foundation Of Distributed Artificial Intelligence, Pp:187-210, John Wiley And Sons, 1996.
[9] Michael N. Huns & Larry M. Stephens, “Multiagent Systems & Societies Of Agents”,
[10] Smith G.R, “The Contract Net Protocol: High Level Communication And Control In A Distributed Problem Solver”, In IEEE Transactions On Computers, Vol C-29, No. 12, December 1980.
[11] Singh A., Juneja D. and Sharma A.K.(2010), ‘Introducing Trust Establishment Protocol in Contract Net Protocol’. Proceedings of 2010 IEEE International Conference on Advances in Computer Engineering, Bangalore, India, June 21-22, 2010.
[12] Aarti Singh, Dimple Juneja, “An Improved Design Of Contract Net Trust Establishment Protocol”, ACEEE Int. J. On Communications, Vol. 4, No. 1, July 2013, Pp: 19-25.
[13] Borhen Marzougui , Kamel Barkaoui, “Interaction Protocols In Multi-Agent Systems Based On Agent Petri Nets Model”, International Journal Of Advanced Computer Science And Applications, Vol. 4, No.7, 2013,166-173.
[14] Roberto A. Flores-Mendez, “Towards the Standardization Of Multi-Agent Systems Architectures: An Overview”, ACM Crossroads' Special Issue On Intelligent Agents, Summer 1999.
[15] Singh, M. P.,”A Social Semantics For Agent Communication Languages”, In Proceedings of The 1999 IJCAI Workshop On Agent Communication Languages. Lecture Notes in Artificial Intelligence, Vol. 1916. Springer, Berlin, 31–45,2000.
[16] Yolum, P., ”Design Time Analysis Of Multi-agent Protocols. Data and Knowledge Engineering Journal 63, 1, 2000, 137–154.
[17] Katia P. Sycara, “Multi Agent Systems”, AI Magazine Volume 19 Number 2 (1998), American Association For Artificial Intelligence, 79-92.
[18] C. Iglesias, M. Garijo, And J. González, "A Survey Of Agent-Oriented Methodologies," In Intelligent Agents V. Agents Theories, Architectures, And Languages, Lecture Notes In Computer Science, Vol. 1555, J. P. Müller, M. P. Singh, And A. S. Rao (Eds.), Springer-Verlag, 1998.
[19] Scott A. Deloach, Mark F. Wood And Clint H. Sparkman,” Multiagent Systems Engineering”, International Journal Of Software Engineering And Knowledge Engineering, Vol. 11, No. 3 (2001) 231-258.
[20] Scott N. Gerard, Munindar P. Singh,” Evolving Protocols And Agents In Multiagent Systems”, 12th International Conference On Autonomous Agents And Multiagent Systems (AAMAS 2013), Ito, Jonker, Gini, And Shehory (Eds.), May, 6{10, 2013, Saint Paul, Minnesota, USA, Pp:997-1004
[21] Michael R. Genesereth, Steven P. Ketchpel, “Software Agents”, Center For Integrated Facility Engineering Working Paper, Standford University, 1994
[22] Y. Uny Cao, Alex S. Fukunaga, Andrew B. Kahng,” Cooperative Mobile Robotics: Antecedents And Directions”, Autonomous Robots 4, 7–27 (1997).
[23] K. Kuwabara, T. Ishida And N. Osato. Agentalk: Describing Multiagent Coordination Protocols With Inheritance. IEEE Conference On Tools With Artificial Intelligence (TAI-95), Pp.460-465, 1995.
[24] Conry, S.E. ; Kuwabara, K. ; Lesser, V.R. ; Meyer, Robert A.,” Multistage negotiation for distributed constraint satisfaction “ , IEEE Transactions on Systems, Man and Cybernetics, Volume: 21 , Issue: 6 , 1991 , Page(s): 1462 – 1477
[25] Edmund Durfee , Piotr Gmytrasiewicz , Jeffrey S. Rosenschein, ”The Utility of Embedded Communications and the Emergence of Protocols”, Proceedings of the 13th International Distributed Artificial Intelligence Workshop, 1984
[26] Edmund Durfee , Jeffrey S. Rosenschein, ”Distributed Problem Solving and Multiagent Systems: Comparisons and Examples”, AAAI Technical Report WS-94-02,1994, pages:52-63.
[27] Carlos A. Iglesias, Mercedes Garijo, José C. González, and Juan R. Velasco. A method proposal for multiagent systems development extending CommonKADS., Proceedings of the 10th Banff Knowledge Acquisition for Knowledge-Based Systems Workshop, volume 1, pages 25–1/17,1996.
[28] Craig Boutilier, Sequential Optimality and Coordination in Multiagent Systems, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.478-485, July 31-August 06, 1999
[29] Goldman, C. V.,& Zilberstein, S.(2003).Optimizing information exchange in cooperative multiagent systems.In Proceedings of the second International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp.137-144, Melbourne, Australia
[30] K. Kuwabara, T. Ishida And N. Osato. Agentalk: Describing Multiagent Coordination Protocols With Inheritance. IEEE Conference On Tools With Artificial Intelligence (TAI-95), Pp.460-465, 1995.
[31] Beer, M., d'Inverno, M., Jennings, N. R., Luck, M., Preist, C. and Schroeder, M. (1999) Negotiation in Multi-Agent Systems. Knowledge Engineering Review, 14, (3), 285-289
[32] Vanderveken, D. 2005. Logic, Thought And Action. Springer’s Series In Logic, Epistemology And The Unity Of Science.

Select your language of interest to view the total content in your interested language
Post your comment

Share This Article

Relevant Topics

Article Usage

  • Total views: 11543
  • [From(publication date):
    July-2014 - Nov 18, 2017]
  • Breakdown by view type
  • HTML page views : 7797
  • PDF downloads : 3746
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2017-18
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

[email protected]

1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

[email protected]

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

[email protected]

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

[email protected]

1-702-714-7001Extn: 9037

Engineering Journals

James Franklin

[email protected]

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

[email protected]

1-702-714-7001Extn: 9042

General Science

Andrea Jason

[email protected]

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

[email protected]

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

[email protected]

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

[email protected]

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

[email protected]

1-702-714-7001Extn: 9039

Medical Journals

Nimmi Anna

[email protected]

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

[email protected]

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

[email protected]

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

[email protected]

1-702-714-7001Extn: 9042

 
© 2008- 2017 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version
adwords