Compartilhe o registro |
|
Use este identificador para citar ou linkar para este item:
https://tede2.pucrs.br/tede2/handle/tede/8102
Tipo do documento: | Dissertação |
Título: | Constrained coalition formation among heterogeneous agents for the multi-agent programming contest |
Autor: | Rodrigues, Tabajara Krausburg |
Primeiro orientador: | Bordini, Rafael Heitor |
Resumo: | 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: | 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. |
Palavras-chave: | Coalition Formation Multi-Agent Systems JaCaMo Multi-Agent Programming Contest Formação de Coalizões Sistemas Multiagents Competição de Programação Multiagente |
Área(s) do CNPq: | CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO |
Idioma: | eng |
País: | Brasil |
Instituição: | Pontifícia Universidade Católica do Rio Grande do Sul |
Sigla da instituição: | PUCRS |
Departamento: | Escola Politécnica |
Programa: | Programa de Pós-Graduação em Ciência da Computação |
Tipo de acesso: | Acesso Aberto |
Restrição de acesso: | Trabalho não apresenta restrição para publicação |
URI: | http://tede2.pucrs.br/tede2/handle/tede/8102 |
Data de defesa: | 26-Mar-2018 |
Aparece nas coleções: | Programa de Pós-Graduação em Ciência da Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
TABAJARA_KRAUSBURG_RODRIGUES_DIS.pdf | TABAJARA_KRAUSBURG_RODRIGUES_DIS | 3,95 MB | Adobe PDF | Baixar/Abrir Pré-Visualizar |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.