Export this record: EndNote BibTex

Please use this identifier to cite or link to this item: http://tede2.pucrs.br/tede2/handle/tede/8102
Document type: Dissertação
Title: Constrained coalition formation among heterogeneous agents for the multi-agent programming contest
Author: Rodrigues, Tabajara Krausburg 
Advisor: Bordini, Rafael Heitor
Abstract (native): This work focuses on coalition formation among heterogeneous agents for the 2017 multiagent programming contest. An agent is a computer system that is capable of independent action to achieve its goals. In order to increase the effectiveness of the agents, we can organise them into coalitions, in which the agents collaborate with each other to achieve individual or common goals. We investigate and apply coalition structure generation (the first activity of the coalition formation process) in simulated scenarios, specifically the 2017 contest scenario, where the agents forming a competing team cooperate to solve logistic problems simulated on the map of a real city. In order to achieve our goal, we integrate coalition formation algorithms into the JaCaMo platform by means of a CArtAgO artefact, named CFArtefact. We use the implementation of the SMART JaCaMo team for experimenting with the coalition formation approach in the contest scenario. We experiment on three approaches in the contest domain with different configurations. In the first, we use only a taskallocation mechanism, while the other approaches use an optimal coalition formation algorithm and a heuristic coalition formation algorithm. We conducted several experiments to compare the advantages of each approach. Our results show that coalition formation algorithms can improve the performance of a participating team when dealing with low job rates (i.e., how quickly new jobs are created by the simulation). However, as we increase the job rate, the approach using only task allocation has better performance. Even a heuristic coalition formation approach has close performance to the optimal one in that case. Coalition formation can play an important role when we aim to balance each group of agents to accomplish some particular goal given a larger team of cooperating agents.
Abstract (english): Esta dissertação apresenta um estudo sobre formação de coalizões entre agentes heterogêneos para a competição de programação multiagente de 2017. Foi investigado e aplicado a formação de estruturas de coalizões entre agentes para resolver problemas logísticos simulados sobre o mapa de uma cidade real. A fim de atingir o objetivo deste trabalho, foram integrados algoritmos formadores de coalizões na plataforma JaCaMo por meio de um artefato CArtAgO chamado CFArtefact. Foi utilizada a implementação provida pelo time SMART-JaCaMo (time participante da competição multiagente), para experimentar a formação de coalizões na competição. Três abordagens foram avaliadas no domínio da competição em diferentes configurações. A primeira abordagem utiliza somente alocação de tarefas para resolver o problema. A segunda e a terceira abordagem utilizam a técnica de formação de coalizões anteriormente à alocação de tarefas; dentre estas abordagens, uma utiliza um algorítimo ótimo para resolver o problema e a outra um heurístico. As análises dos experimentos realizados mostram que algorítimos formadores de coalizões podem melhorar a performance do time participante da competição quando a taxa de trabalhos gerados pelo simulador é baixa. Entretanto, conforme a taxa de trabalhos aumenta, a abordagem que realiza somente alocação de tarefas obtém um desempenho melhor quando comparada as demais. Mesmo a abordagem heurística tem desempenho próximo à abordagem ótima para coalizões. Desta forma, é possível concluir que formação de coalizões possui grande valia para balancear os agentes para um conjunto de trabalhos que precisa ser completado.
Keywords: Coalition Formation
Multi-Agent Systems
JaCaMo
Multi-Agent Programming Contest
Formação de Coalizões
Sistemas Multiagents
Competição de Programação Multiagente
CNPQ Knowledge Areas: CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
Language: eng
Country: Brasil
Publisher: Pontifícia Universidade Católica do Rio Grande do Sul
Institution Acronym: PUCRS
Department: Escola Politécnica
Program: Programa de Pós-Graduação em Ciência da Computação
Access type: Acesso Aberto
Fulltext access restriction: Trabalho não apresenta restrição para publicação
URI: http://tede2.pucrs.br/tede2/handle/tede/8102
Issue Date: 26-Mar-2018
Appears in Collections:Programa de Pós-Graduação em Ciência da Computação

Files in This Item:
File Description SizeFormat 
TABAJARA_KRAUSBURG_RODRIGUES_DIS.pdfTABAJARA_KRAUSBURG_RODRIGUES_DIS3.95 MBAdobe PDFThumbnail

Download/Open Preview


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.