Koalisyon kurulumu ile görev paylaşımı için bir çoklu etmen tabanlı yürütme ortamı
Multi-agent based execution environment for task allocation via coalition formation
Yazar: MERVE ÖZBEY
Danışman: PROF. DR. TAKUHİ NADİA ERDOĞAN
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2014
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Çoklu etmen sistemleri, birbirleriyle iletişim kuran ve işbirliğinde bulunan birden fazla akıllı otonom etmenin bir araya gelerek oluşturduğu sistemlerdir. Etmenler kendi yetenekleri ve bilgilerinin yeterli olmadığı problemleri bir araya gelerek oluşturdukları bu sistemlerle çözebilirler. Görev paylaşımı yaklaşımı ile etmenlerin görevleri birlikte yerine getirmesi, etmen koalisyonu olarak adlandırılmaktadır.
Bu çalışmada iş yapma yeteneği olan etmenler tanımlanan görevleri yerine getirmek üzere koalisyonlar kurarlar. Koalisyon kurma aşamasında gerçeklenen bir algoritma ile etkili bir şekilde tüm görevleri ya da tüm etmenleri kapsayacak şekilde koalisyonlar kurulur. Koalisyon kurma problemi taşımacılık şirketi problemi üzerinden uygulanmıştır.
Öncelikle sistemde olması gereken bileşenler belirlenmiştir: veri tabanı, veri tabanı işlerini yerine getirecek veri tabanı etmeni, sistemin genel koordinasyonunu sağlayacak denetçi etmen, sadece kendi koalisyonundan sorumlu olacak koalisyon yöneticisi etmenleri ve en başta belirlenen görevler için koalisyon kurulumunu yapıp bu görevleri yerine getirecek işçi etmenler. Her bir etmen çeşidi kendi uzmanlaştığı işleri yerine getirir, hangi etmenlerle iletişim kurması gerekiyorsa sadece o etmenlerin iletişim bilgilerine sahiptir. Koalisyonlar kurulmadan önce işçi etmenler birbirleriyle ve denetçi etmenle iletişim halindedir; koalisyonlar kurulduktan sonra ise aynı koalisyondaki işçi etmenler kendi içlerinde ve sadece o koalisyonun koalisyon yöneticisi etmeni ile iletişimde bulunurlar, denetçi etmenle ilişkileri kalmaz. Koalisyon kurulumu gerçekleşir gerçekleşmez her bir görev birer koalisyon tarafından yerine getirilir. Görevler tamamlandıktan sonra koalisyon yöneticisi etmenleri görevlerin tamamlandığını denetçi etmene bildirir, denetçi etmen de bu çalışmayla ilgili ayrıntıların veri tabanı etmeni aracılığıyla veri tabanına kaydedilmesini sağlar. 
Sistemin gerçeklenmesi sırasında etmenlerin yaratılmasını, yönetilmesini ve birbirleri ile haberleşmesini sağlayan araçlar ve yardımcı kütüphaneler sunan JADE platformu kullanılmıştır. JADE, etmen ve çoklu etmen sistemlerinin standartlarını belirleyen FIPA tarafında oluşturulan standartları destekleyen çoklu etmen geliştirme ortamı ve kütüphanesidir. Etmenler arası haberleşme ve etmenlerin davranışlarını kontrol etmek için esnek ve genişletilebilir bir yapı sunmaktadır. JADE'in bu özellikleri kullanılarak etkili bir şekilde koalisyon kurulumu yapan ve görevlerin bu koalisyonlar aracılığıyla yerine getirildiği bir çalışma ortaya çıkartılmıştır.
Yapılan deneyler sonucunda işçi etmen sayısındaki, görev sayısındaki ve en büyük koalisyon boyutundaki artışın koalisyon kurulum sürelerine etkisi incelenmiştir, her durumda koalisyon kurulum süresi beş saniyeyi geçmemiştir.
Bu çalışma ile etmenlerin koalisyon kurarak görev paylaşımı yapmaları sonucu ele alınan problemin çözümünde hızlı ve etkili bir şekilde görev paylaşımı yapılarak görevlerin yerine getirilmesi sağlanmıştır.

Abstract:
Multi-agent systems are systems of intelligent autonomous agents that communicate and collaborate with each other. Agents cooperate and solve problems on multi-agent systems when the capability and knowledge of each agent alone is not sufficient to solve the problems. Task execution via task allocation with agents' cooperation is defined as agent coalition. Coalition formation is an important method for cooperation in a multi-agent environment. It is a process where agents form coalitions and work together to solve a joint problem via cooperating or coordinating their actions within each coalition. Membership in a coalition may increase the agents ability to accomplish tasks, achieve its goals or maximize its utility.
In this research, agents that have task execution capabilities, form coalitions to execute predefined tasks. In the coalition formation phase, coalitions are formed efficiently performing an algorithm that covers all of the tasks or all agents. Coalition formation algorithm has been applied to a transportation problem.
In our system, agents cooperate to maximise the total outcome of the system and they are not concerned with their personal profits. There is no central authority for distribution of tasks among the agents. Autonomous agents form coalitions by themselves. Agents in the execution environment follow the Shehory-Kraus's algorithm to negotiate and decide on coalitions. There exist several variations of the algorithm, such as disjoint coalitions, overlapping coalitions and coalitions for tasks that have precedence orders. Our implementation focuses on disjoint coalitions, therefore an agent can join only one coalition at a time.  After a task is completed the members of the coalition can join new coalitions. Furthermore, agents cannot join an already formed coalition due to extra agent addition cost generated. Last assumption is that tasks to be performed have no precedence order and inter dependency.
The framework builds on various types of agents that are defined and implemented to handle different issues. In the design phase, we have determined the actors of the system, specifying their tasks and responsibilities. After associating each actor with an agent type, protocols that define in detail the interaction and coordination between agents were developed. In addition, an efficient and fast messaging infrastructure has been developed for effective agent communication.
In the framework, four different types of agents cooperate to provide the environment where coalitions are formed. Database agent that will perform database operations, controller agent that will control system's overall coordination, coalition manager agents that will be liable only its coalition and employee agents that will perform coalition formation on predefined tasks and execute those tasks. 
Before coalition formation, employee agents communicate with each other and the controller agent. After a coalition is formed employee agents in same coalition communicates with each other and the coalition manager agent responsible of that coalition but no longer with controller agent. Next, each task is performed by a coalition directly. After task execution is completed coalition manager agents inform the controller agent that task has been completed. With this information, the controller agent administers recording of that execution's details via the database agent.
For database component, native XML database eXist selected. XML Shema Definition (XSD) of all XML files are prepared and xQuery query language used for database queries. Employee agent definitions, task definitions, user definitions and execution reports are stored in XML files on database. In addition, XSD and xQuery files are stored on database.
Database agent is the only agent in our system that has the capability of executing database operations. The database agent accepts database requests, executes queries and delivers results. Only, the controller agent has direct communication with the database agent. If other agents need to query the database, they transmit their requests through the controller agent to database agent and get results in the same way. 
Employee agents are responsible for performing the coalition formation algorithm on predefined tasks and execute those tasks. These agents firstly register on active agent list announcing controller agent. After receiving the active agent list and the task list from controller agent, employee agents start coalition formation. Using coalition formation algorithm, they calculate which coalition they will join. One employee agent can join only one coalition at a time, because of disjoint coalitions assumption. Employee agents inform the controller about coalitions and then wait for coalition managers' starting messages. After getting the message, employee agents join their coalitions, execute their tasks and inform coalition manager agents that they have completed subtasks. If an error occurs during subtask execution, employee agents inform their own coalition manager agents.
Central management usually becomes a bottleneck; therefore the controller agent conveys some of its tasks to coalition manager agents as to decrease its work load.  The controller agent monitors agents' status and task control period. When a predefined task control period ends, the controller agent restarts coalition formation mechanism, therefore there is no need to reset the system after new tasks have been defined. 
Controller agent monitors coalition formation phases; after coalition formation is completed, the controller agent starts a new coalition manager agent for each coalition, sends them the employee agents' identifications and task's details. Next, controller agent waits for coalition managers' messages. After receiving all coalition managers' messages, prepares an execution report and sends it to database agent to insert into the database.
The controller agent is also responsible for information sharing. The controller agent provides the necessary information to other agents, for example, it sends employee agents and task details of a coalition to manager of that particular coalition. 
Furthermore, the controller agent is responsible for error checking; when an error message is received from a coalition manager agent, the controller agent updates the state of relevant task's state to "failed" on database through database agent. The failed task is executed on the next round. With this approach, our system becomes fault tolerant.
For every coalition, one coalition manager exists. Coalition manager agent is responsible of only its coalition and employee agents on that coalition. Coalition manager agent checks whether employee agents have completed subtasks; after a task is completed, the coalition manager informs the controller agent and shuts down itself. 
Coalition manager agent is responsible for error checking, similar to the controller agent. If a subtask execution results in error, coalition manager stops all other subtasks in the coalition and informs controller agent about error. In addition to error handling, the coalition manager checks employee agents at predefined periods to see if they are standing. If any employee agent is not standing, coalition manager stops all other subtasks in the coalition and informs controller agent about error. In both error cases, coalition manager shuts down itself as the coalition no longer exists.
To insert new task definitions to system, we need an interface. For this purpose, a web application has been developed using Primefaces library. The application starts with a login screen, and then continues with the task definition screen. A newly defined task waits the next task control period for execution.
The JADE platform is used for creating, managing and supporting the communication of the agents during the design and implementation of the coalition formation environment. The JADE environment and its library provides a rich set of tools for this purpose. JADE is a multi-agent system development environment and library which supports the standards defined by FIPA, an organization that defines the standards for multi-agent systems. JADE provides a flexible and extensible structure for agent communication and controlling behaviours of agents. Using JADE's properties, an agent based system which provides task allocation using coalition formation efficiently has been developed.
We tested our system approximately 3000 runs for different numbers of employee agents, for different numbers of tasks and for different values of maximum coalition sizes and have observed their effects on coalition formation time. Increases in the number of employee agents and coalition size increase coalition formation time fastly, however, the effect of variation in the number of tasks was different. Increase of task count increased coalition formation time up to three tasks. After three tasks, test results gave us approximately the same values. Coalition formation time did not exceed five seconds on any test.
Experimental results show that the framework fully provides the requirements for a negotiation environment for multi-agents to form coalitions and execute tasks. The framework can be used as a test bed for further research as well. 
In this study, we provide a solution to the problem of task allocation through coalition formation and implementation of a multi-agent based execution environment for this purpose. We show that task allocation and task execution can be performed quickly and efficiently via an application on a transportation problem.