Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-28T12:31:15Z No. of bitstreams: 1 TABAJARA_KRAUSBURG_RODRIGUES_DIS.pdf: 4049392 bytes, checksum: 154302eff9df959cfa74d6c0faec5d4e (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-06-06T13:05:51Z (GMT) No. of bitstreams: 1 TABAJARA_KRAUSBURG_RODRIGUES_DIS.pdf: 4049392 bytes, checksum: 154302eff9df959cfa74d6c0faec5d4e (MD5) / Made available in DSpace on 2018-06-06T13:35:29Z (GMT). No. of bitstreams: 1 TABAJARA_KRAUSBURG_RODRIGUES_DIS.pdf: 4049392 bytes, checksum: 154302eff9df959cfa74d6c0faec5d4e (MD5) Previous issue date: 2018-03-26 / 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. / 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.