Coordination In Multiagent-based University

Coordination in Multiagent-Based University Architecture Thiri Haymar Kyaw and Ni Lar Thein University of Computer Studies, Yangon. Hlaing Township, Yangon, Myanmar.

ABSTRACT We present a token-based coordination approach in hierarchical composite multiagent architecture. There are many heterogeneous composite agents and two types of coordinator agents. A composite agent is composed of multiple individual agents. When any agent has a task or request or information, it creates a token and sends to Intelligent Coordinator agent (ICo) through Assistant Coordinator agent (ACo). Each composite agent has one ACo that is responsible for selecting correct individual agent, passing the token to addressed agent within the same composite agent and communicating with ICo. ICo provides efficient coordination between composite agents for information sharing and task allocation, etc. Coordinator agents use Matching Inference Engine (MIE) to route the tokens to correct receiver agents efficiently and directly. Token passing algorithms called coordinator algorithms for ICo and ACo have been developed in this paper. We described a multiagent-based university system as a proof of concept application. The proposed approach gives efficient coordination between automated entities in university with very little communication. We show the results comparing with simple point-to-point multiagent architecture. Keywords: Multiagent System, Token-based Coordination, Composite Agents and Intelligent Coordinator.

1.

INTRODUCTION

Coordination is a complex and open problem for large multiagent systems and especially if the agents represent the organizational entities due to the requirements of inter and intra agent communication with coperative, efficient and effective coordinated behavior. Automated coordination is still a very active research area because it can decrease operational cost, risk, time and human activities while increasing efficiency, flexibility and cooperation performance. Coordination is the process of managing the possible interaction between activities and process. Coordination between multiple agents requires to perform several various functions including messages passing, tasks allocation, resources sharing, and negotiation to reach the common goal.

tokens are passed to where. In previous, token-based algorithms use the local models for token movement and a token is routed to all agents within the teams. In this approach, coordinator agents provide token movement decisions by using token passing algorithms called coordinator algorithms. In this paper, we show a multiagent architecture for a university and apply the coordination approach for informing and task allocation between agents. This concept offers a range of coordinated services, tasks allocation and access to resources through the coordinator agents and supports on the fundamental computerized subsystems for the university’s administrative, teaching, library and student affairs. Multiagent system approach has been widely used in the development of large and complex systems. Multiagent approach is appropriate for university architecture while coordinating and cooperating between agents effectively support for the university system. In our multiagent architecture, each subsystem is constructed as a composite agent. Intelligent Coordinator agent (ICo) communicates and coordinates among composite agents. A composite agent is composed of several individual agents. If any agent appears a new task or information or request, it creates a token and sends to ICo through the Assistant Coordinator agent (ACo). ACo has responsibilities of passing the token to correct destination agent within the same composite agent and uses coordinator algorithm. ICo determines when and where to pass the token directly using its coordinator algorithm with the help of Matching Inference Engine (MIE). MIE is a simple rule based reasoning engine. The main purpose of this approach is to provide efficient and effective coordination among large agent teams with very little communication. In the rests of the paper, we review the previous approaches related to multiagent coordination in section 2. We discuss the proposed hierarchical composite multiagent architecture and university architecture in section 3. Token-based coordination with proposed coordinator algorithms for ICo and ACo is described in section 4. We present how to work coordination in the prototype university system in section 5 and show the emprical results in section 6. Finally, in section 7, we conclude the paper with discussion and our future work.

2. There are many widely used coordination approaches such as auction based coordination, token-based coordination and hybrid approach, etc. Some approaches have extra routings that tokens may be passed to unrelated agents or unnecessary bids. The proposed approach uses token-based hierarchical coordination because hierarchical coordination gives the best results for large-scale systems and token-based approach finds the reasonable solution rather than searching for the optimal. New coordination algorithms are developed to determine the

RELATED WORKS

Efficient and effective coordination between large agent teams promises for performing complex and distributed tasks successfully. P. Scerri et al. have developed an integrated token based algorithm for scalable coordination [15], [17], [18], [19]. They used tokens to encapsulate anything that needs to be shared by the team, including information, tasks, and resources. The tokens are efficiently routed with decentralized manner through the team via the use of local

decision model that determines what to do with the tokens in order to maximize expected utility. The token movement model they used is a Partially Observable Markov Decision Process (POMDP) because agents in a large team may not know the states of their teammates or that of the environment. In auction based called market-based approach [20], one agent acts as auctioneer and both tasks and resources are treated as merchandise. Agents bid for either single items or combinatorial sets of items in order to maximize their own utilities. The auctioneer maximizes its utility by selling their merchandise. It develops a complete knowledge of how agents will use a task or resource if located because the auctioneer’s position is centralized. When early determination was infeasible, agents are allowed to bid for resources after tasks have been allocated. J. M. Vidal [7] presented a multiagent coordination approach using combinatorial auctions for the reason of other previous approaches that require all agents to send their bids to a centralized auctioneer. Every agent performs the task of the auctioneer. All bids are broadcast and when an agent receives a bid from another agent it updates the set of best bids and determines if the new bid is better than the current winning bid. It guaranteed to find the bid which maximizes the agent’s utility given the outstanding best bids. M. Ham and G. Agha [10] presented the market-based mechanisms for dynamic coordinated task assignment in large scale multiagent systems and described the simulations of homogeneous agents that provide insight about the interaction between the strategy used by individual agents and the market mechanism.

is responsible for selecting appropriate agents to pass the token and communicating within CAi. Intelligent Coordinator agent (ICo) is responsible for token movement decisions between composite agents for message informing, task allocation, negotiation, requesting and resource allocation. ICo token messages

ACo

A1 A2

Multiagent system architecture is a typical system architecture that has intelligent agents as the system components and social communication as the interactions. Hierarchical architecture is a typical control-oriented architecture of multiagent system. It well matches human organization management procedures and provides effective feedback and control ways [6]. In this multiagent architecture, there have many heterogeneous composite agents and one coordinator agent. Coordination in hierarchical composite multiagent architecture based on [14] is shown in Fig 1. We create a composite agent team CA = {CA1, CA2, …, CAn} and CAi is composed of one Assistant Coordinator agent (ACo) and member agents, CAi = {ACo, A1, A2, …, An}. ACo

… A3

A1

…

ACo

A2

A3

A1

…

A2

…

3.1 Multiagent University Architecture Multiagent system approach is effective for tackling the management of the entire university system. The abstract structure of multiagent university architecture is shown in Fig 2.

  HIERARCHICAL COMPOSITE MULTIAGENT ARCHITECTURE

ACo

Fig.1. Coordination in Hierarchical Composite Multiagent Architecture.

The recent researches have been applied multiagent approach to the medicine fields [8]. A. Aldea. et. al. [1] proposed a multiagent architecture to coordinate the Spanish activity in organ transplants. It is structured in four levels: national, zonal, regional and hospital level which constructed as agents and two other agents: Emergency Coordinator and Historical Agent. When there is a new organ available for transplant in a hospital addresses in the first place the needs of patients that have reached an extremely critical stage; if no patients, it tries to find an appropriate recipient as close as possible to the donor’s hospital in order to minimize both the financial costs to transport the organ and length of transport time.

3.

token messages token messages

 

Fig.2. The general Architecture of Multiagent University. There are six composite agents: AdminAgent, StuAffairsAgent, DeptAgent, FinanceAgent, LibraryAgent and StudentAgent. AdminAgent includes administrator’s office and admin department. It performs administrative tasks, staff management, initiation for task assignment, etc. AdminAgent is composed of ACo, administrator agent and other staff agents. Most of tokens are created by AdminAgent, for example, task for assigning courses to teachers, informing meeting, etc. Some databases such as Teachers-Service-Books, StaffProfiles, etc, are located in this site. StuAffairsAgent represents the Student Affairs department. It is composed of ACo and other individual agents. Its tasks are student registration, examination, inquiring student information, creating and updating students’ records including attendance. DeptAgent represents Faculties in the university. It performs teaching,

supervising, scheduling courses or timetabling classes and planning lectures, etc. DeptAgent is composed of ACo and teacher agents in faculties. It handles some databases such as TeacherProfiles, Courses, etc. Teacher agents represent teachers who are recorded in TeacherProfiles and active as an agent during the time DeptAgent’s interface is active and they attend to their departments. LibraryAgent represents the library system in the university. Its own tasks are member registration, book reservation, book lending, etc. FinanceAgent represents Finance department. It provides preparation of budget, financial statements and reports, payments and payroll system. StudentAgent is on behalf of all students in the university. ICo also provide as the coordinator between different university multiagent systems. 3.2 Structure of Coordinator Agents Intelligent Coordinator (ICo) works with three components: ICo, Matching Inference Engine (MIE) and AgentList schema. ICo is a program implementing token passing algorithm also called coordinator algorithm that determines where to pass the token with the help of MIE. The abstract structure of ICo is shown in Fig 3. The structure of Assistant Coordinator (ACo) is similar to ICo and it uses another inference engine called Assistant MIE instead of MIE.  

and localName according to [13] [14]. AgentList is updated automatically whenever any one agent record is changed.

4.

TOKEN-BASED COORDINATION USING COORDINATOR ALGORITHMS

Coordination in the activities of the agents in a multiagent system is a key element of Multiagent System organization. Token-based algorithms have been developed by [2], [16]. A token encapsulates control and information needed for message passing, task allocation, and resources sharing and so on. The screen format of a token used in our approach is shown in Fig 5. There are five types of tokens: inform token, task allocation token, resource token, request token and negotiate token. A token form includes TokenID, Title content, Detail Description, Sender, Receiver, Replyto, Deadline, Signature and Reply. TokenID is types of the token. Sender, Receiver and Replyto include names and addresses which provide in the JADE [4]. Deadline is needed for task and resource tokens. Reply field is required for task allocation token and default is 1. Signature is used to show the authorized identity. It may be a digital signature.

  Fig.3. The abstract structure of Coordinator agent. MIE is a simple rule based reasoning engine that works with AgentList database. Several matching functions are performed by MIE. The detail rule explanations of MIE depend on the specific application and may be changed according to the nature of the application. An example title matching in MIE is shown in Fig 4.

Fig.4. An Example Title Matching. AgentList schema is a knowledge base that contains the data of all individual agents in this case study multiagent system. An agent record includes: AgentName, CompositeAgent, AgentID, Address, TeamName, Role, Skill, Current Assigned Task and Task Schedule. AgentID is combined with platform

Fig.5. The screen format of a token. In this approach, Intelligent Coordinator agent (ICo) provides coordination and communication among Composite Agents. Each Composite Agent (CA) has one Assistant Coordinator agent (ACo) that is responsible for interactions among individual agents within the same CA. ICo and ACo use token based coordination with coordinator algorithms shown in Fig 6 and 7. The algorithm gives the token passing decision for all type of tokens to pass where. token t = getToken(t); if ( t.tokenID = 1 ) // Inform token //composite agents { for CAi ∈ CA { replicate t; t.Receiver.Add ( CAi ) ; } Send all replicas t to CAi ∈ CA }

if ( t.tokenID = 2 ) // Task allocation token { SCA = φ ; // selected CA for all CAi ∈ CA SCA = TitleMatching(t.TitleContent) t.Receiver = CAi; send t to SCA ; } if ( t.tokenID = 3 ) // Resource token { if ( CheckRequestedCA ( ) = 1 ) { t. Receiver = RCAi ; send t to RCAi ; } else if ( CheckRequestedCA ( ) > 1 ) if( task . Priority = MAX) { t. Receiver = RCAi ;send t to RCAi ; } } if ( t.tokenID = 4 ) // Request token { for { if ( SearchResourceAvailable( t.Title ) ) send t to CAi , take Resource AND return; } reply t to requested agents; } if ( t.tokenID = 5 ) // Negotiate token { NRule=TitletoNegotiateRule(t.TitleContent); Append NRule to t.DetailDescription; reply t to t.Sender; } Fig. 6. Coordinator Algorithm for ICo token t = getToken(t); if ( t.tokenID = 1 ) {

// Inform

for ∀ Ag ∈ AG i send t to Agi ;

; AGi ∈ CA

}

if ( t.tokenID = 4 ) // Request { if (CheckResourceAvail(t.titleContent)=true ) { t.Attachment = Resource OR Data; send t to senderAgi ; } else send t to ICo ; } if ( t.tokenID = 5 ) // Negotiate { while ( negotiateResult ≠ OK ) { send t to Agent AND Negotiate ( ); } t.Reply = negotiateResult; send t to ICo; } Fig. 7. Coordinator Algorithm for ACo

5.

COORDINATION IN PROTOTYPE UNIVERSITY ARCHITECTURE

We developed a prototype university architecture based on Java Agent Development Environment (JADE) using java programming and mySQL database. Currently, we created four composite agents: AdminAgent, DeptAgent, StuAffairAgent LibraryAgent and coordinator agent (AgentICo). Each composite agent has one ACo with an interface which allows adding and deleting individual agents in the same team. We run our system in five personal computers (Pentium (R), 3.20 GHz and 1 GB memory) with java Sun SDK 1.5, MySQL Server 5.0 and JADE version 3.4.1. AdminAgent, DeptAgent, StuAffairAgent, LibraryAgent and AgentICo are run in different computers and mySQL server is located in one computer which run AgentICo. This approach promises to reach the message or task or resource directly to the receiver agent with low cost and little communication. 5.1 Inform Token

if ( t.tokenID = 2 ) { SAg = φ ;

// Task allocation

for ∀ Ag ∈ AG i if ( TitleToRoleMatching ( ) = 1 ) SAg = SAg Υ Agi ; if (SAg > required no. of agents) SAg = SelectOptimal( ); for ∀ Ag i ∈ AG Send t to Agi ; if (Agi reject the task ) Negotiate( ); else Assign Task and Update Workload; } if ( t.tokenID = 3 ) // Resource { if ( CheckRequestedAgents ( ) = 1 ) send t to Agi; else if ( CheckRequestedAgents ( ) > 1 ) if( task . Priority = MAX) send t to Agi ; else send t to ICo ; }

When AgentICo receives an inform token, which title is “Meeting for all teachers and staffs”, it’s MIE checks the title and sends to all related composite agents (Admin, Dept, StuAffair and Library). When ACo in each composite agent receives this inform token, it passes to all related individual agents in its team. When AgentICo receives an inform token, which title is “To attend Seminar”, it’s MIE checks the title and sends to related composite agent (DeptAgent). When ACo in DeptAgent receives this inform token, it passes to related teacher agents in its team. 5.2 Task Assignment Token AdminAgent creates a token for course assignment and send to ICo. When ICo receives the token, it resets the correct receiver agent according to the Matching function in MIE and sends to the related DeptAgent. When DeptAgent receives the task token, its ACo chooses appropriate teachers for each courses based on the preferences and other profile facts of the teachers. After selecting the appropriate agents, it dynamically generates the individual teacher agents and adds their addresses as the receiver addresses. Then, it sends the task assignment token to selected teacher agents for assigning the

course. Each receiver agent receives the task assigned token and reply accept or reject. If any conflicts arise, they are resolved by sending negotiate tokens each other.

shows the comparison results about token passing time for three different models. Table. 1. Comparison Results for Three Models.

5.3 Requesting the Resource Individual agents may request the resource to perform their tasks, for example, request a scanner or web cam or books in the library. When ICo receives a request token, ICo checks the availability of the resource using MIE which searches the detail facts of the resource in the related databases and checks whether the other agents currently used or not. If the resource is available, the resource is packed into the attachment and the token is sent to the agent that requested the resource. If the resource is not available currently, the requested agent is inserted into the request list. When ICo receives the resource token, ICo searches the requested agents. If there are more than one requested agents, ICo checks the tasks’ priorities that each agent have to do using this resource and chooses one agent that has maximum priority of the task. Then ICo sends the resource token to the selected composite agent and ACo passes the token to the requested agent. If there is more than one, ACo chooses appropriate agent based on the task’s priority like ICo. 5.4 Other Features of Prototype System

6.

EMPRICAL RESULTS

In order to test the coordination and communication between multiple agents in our prototype university architecture, we developed three communication models. First is point to point communication model in which agents are run in different computers and communicates each other passing token message to all agents until reaching the correct receiver agent. Without having coordinator agent, each sender agent cannot know information about all agents and most of tokens may reach unrelated agents. In Second model, multiple agents that run in different computers, communicate through coordinator agent (ICo). Third model is the proposed approach which uses two coordinator agents (ICo and ACo). Each composite agent runs in one computer. Different composite agents and ICo are run in different computers. Coordinator agents act as the middle agents that forward the token messages given by sender agents to the correct receiver agents. So, sender agent doesn’t need to know about the information of the receiver agent. Table. 1

The results show that the proposed approach takes less time for message passing than the first and second model. There is a slightly increase in total message passing time in accordance with the number of agent increases in our approach. So, it reduces communication time for interaction between multiple agents and intends to scalability for large agent teams. It also reduces the total number of messages and has no extra routing to unrelated agents. All sending messages reach to the intended agents so coordination is efficient for all types of tokens. In our implementation, we tested the performance of coordinator algorithms for different types of tokens. There is a linear increase in total number of messages for inform token to all agents in the team. For task token total number of messages is somewhat step-up according to the required number of appropriate agents to allocate the task. The number of messages for request and resource token is stable for all agents while the available resource token is sent to high priority requested agent. 80 Total Number of Messages

DeptAgent interface provides course timetable for all classes, teachers’ information and course information. StuAffairAgent provides exam scheduling and showing staff’s information. LibraryAgent handles Booklist and Memberlist database and perform reserving and lending the books in the library. All ACo agents stored the sending and receiving messages in the message queue in the running time. AgentICo handles the AgentProfiles for selecting the correct receiver agent. Using this system not only provides coordination in university subsystems but also all students can see the course information, timetables, exam information and easy access to the library.

Inform Task Assignment Request Resource

70 60 50 40 30 20 10 0 5

10

15 20 25 30 35 40 Number of composite agents

45

50

55

Fig.8. The Number of Messages for Different Types of Tokens.

7.

CONCLUSION

We presented a token-based coordination approach for multiagent university architecture through middle coordinator agents. In this paper, coordinator algorithms are developed for reaching the tokens directly to the destination agents and finishing the tasks in time. Our proposed multiagent system architecture includes many heterogeneous composite agents and two coordinator agents: Intelligent Coordinator (ICo) and Assistant Coordinator (ACo). ICo takes the duty of coordination and inter agent communication between composite agents. ACo provides the intra communication between individual agents within the same composite agent. Coordinator agents work with coordinator algorithms and Matching Inference Engine (MIE) to determine where destination to pass the token. MIE has several rule functions to work with required databases. The performed experiments show that the proposed approach is able to reach the token directly to the correct receiver agent without extra routing to other agents and reduce message passing time for coordination. Integrating the proposed coordination with the university architecture can reduce human involvements in processes and accelerates university workflows. As a future work an interesting extension would be to communicate and coordinate between different multiagent university architectures through ICo for different types of tokens. Moreover, other activities of university would make to be automated performing by agents.

[10]

[11]

[12]

[13] [14] [15]

[16]

[17]

REFERENCES [1] A. Aldea, B. Lopez, A. Moreno, D. Riano and A. Valls, “A Multi-Agent System for Organ Transplant Coordination”, Proc. of the Eighth Conference on AI in Medicine, Europe, 2001. [2] A. Farinelli, L. Iocchi, D. Nardi and V. A. Ziparo, "Assignment of Dynamically Perceived Tasks by Token Passing in Multi-Robot Systems", Proceedings of the IEEE, Vol. 94, Issue 7, July 2006, pp. 1271-1288. [3] E. Babkin, H. Adbulrab and T. Babkina, AgentTime: “A Distributed Multi-agent Software System for University’s Timetabling”, Emergent Properties in Natural and Artificial Complex Systems, EPNACS, Germany, 2007. [4] F. Bellifemine, G. Caire and D. Greenwood, “Developing Multi-agent Systems with JADE”, Wiley Series in Agent Technology, 2007, ISBN: 978-0-470-05747-6. [5] F. Lin, D. H. Norrie, R.A. Flores and R. Kremer, “Incorporating Conversation Managers into Multi-agent Systems”, 2000. [6] H. Tianfield, J. Tian and X. Yao, "On the Architectures of Complex Multi-Agent Systems", Proceedings of the Workshop on Knowledge Grid and Grid Intelligence, IEEE/WIC International Conference on Web Intelligent/ Intelligent Agent Technology, Oct, 2003, pp. 195-206. [7] J. M. Vidal, “Multiagent Coordination Using a Distributed Combinatorial Auction”, AAAI Workshop on Auction Mechanisms for Robot Coordination, 2006. [8] J. Tian and H. Tianfield, “A Multi-agent Approach to the Design of an E-medicine System”, Lecture Notes in Computer Science, Springer Berlin/ Heidelberg, 2003, pp. 85-94. [9] M. Dastani, F. Arbab and F. de Boer, “Coordination and

[18]

[19]

[20]

Composition in Multi-Agent Systems”, Proc. of the Fourth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’05), 2005. M. Ham, G. Agha, "Market-based Coordination Strategies for Large-scale Multi-Agent Systems", System and Information Sciences Notes, Vol. 2, No. 1, pp. 126-131), 2007. M. Oprea, MAS_UP_UCT: “A Multi-Agent System for University Course Timetable Scheduling”, International Journal of Computers, Communications and Control. vol. 2, no. 1. pp. 94-102, 2007. M-W. Jang, "Efficient Communication and Coordination For Large-Scale Multi-Agent Systems", Ph.D Thesis, University of Illinois at Urbana-Champain, 2006. M. Wooldridge, "An Introduction to Multiagent Systems", John Wiley & Sons, 2002. N. Bensaid and Ph. Mathieu, “Integration of hypothetical reasoning in hierarchical multi-agent architecture”, 1996. P. Scerri, Y. Xu, J. Polvichai, B. Yu, S. Okamoto, M. Lewis, and K. Sycara, “Challenges in Building Very Large Teams”, Lecture Notes in Economics and Mathematical Systems, Vol. 558, Springer Berlin Heidelberg, 2007, pp. 197-228. P. Scerri, A. Farinelli, S. Okamoto and M. Tambe, "Token Approach for Role Allocation in Extreme Teams: analysis and experimental evaluation", 2003. P. Scerri, J. A. Giampapa, K. P. Sycara.: Techniques and Directions for Building Very Large Agent Teams. International Conference on Integration of Knowledge Intensive Multi-Agent Systems (KIMAS’05). (2005) 7984. Y.Xu, P.Scerri, B.Yu, S. Okamoto, M. Lewis, and K. Sycara, “An integrated Token-Based Algorithm for Scalable Coordination”, Proc. of the Fourth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’05), 2005, pp. 407 – 414. Y. Xu, P. Scerri, B. Yu, S. Okamoto, M. Lewis, and K. Sycara.: A POMDP Approach to Token-Based Team Coordination. Proc. of the Fourth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’05). (2005) Y. Xu, P. Scerri, K. Sycara and M. Lewis, “Comparing Market and Token-Based Coordination”, Proc. of the Fifth International Conference on Autonomous Agents and Multiagent Systems (AAMAS’06), 2006.