Um algoritmo distribuído para resolução do problema de geração de estruturas de coalizão com presença de externalidades

• Ano de defesa: 2013
• Autor(a) principal: Epstein, Daniel
• Orientador(a): Bazzan, Ana Lucia Cetertich
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Palavras-chave em Português: Inteligência artificial; Sistemas multiagentes
• Palavras-chave em Inglês: Artificial intelligence; Multi-agent system; Game theory; Distributed algorithms; Coalition structure generation; Externality
• Link de acesso: http://hdl.handle.net/10183/103391

Uma importante parte de um sistema multiagente é o seu mecanismo de coordenação que permite que os agentes possam agir de maneira coesa em direção aos seus objetivos, sejam eles individuais ou coletivos. Um agente pode optar por cooperar para atingir um determinado objetivo que seria inalcançável através de ações individuais, para realizar uma tarefa de maneira mais eficiente ou simplesmente porque ele foi projetado para tal. Em todos os casos, a formação de coalizões (grupos de agentes que concordam em coordenar suas ações em torno de um objetivo comum) é uma questão fundamental. O problema de geração de estruturas de coalizão entre agentes (conjunto de todas as combinações de coalizões) é um tópico de pesquisa que recebeu muita atenção principalmente na resolução do problema quando considerado como um jogo de função característica, onde o valor das coalizões independe dos agentes que não estão presentes nela. Essa abordagem, apesar de ser indicada para muitos tipos de problema, não cobre toda a área de pesquisa do assunto, visto que em muitos casos a criação de uma coalizão irá afetar os demais agentes do sistema. Quando o sistema possui agentes com objetivos sobrepostos ou contrários, uma coalizão cujos recursos são destinados a completar tais objetivos irá influenciar as demais coalizões desse sistema. Essa influência se chama externalidade e, nesses casos, o problema de formação de estruturas de coalizão deve ser tratado como um jogo de partição. Apesar das pesquisas na área de jogos de partição serem recentes, elas trazem resultados promissores e há alguns poucos algoritmos já desenvolvidos para buscar soluções a esse problema. A busca pela melhor estrutura de coalizão geralmente demanda que seja calculado o valor de todas possíveis coalizões, a fim de se encontrar aquele conjunto cuja soma dos valores das coalizões forneça o melhor resultado. Esse processo requer um alto número de computações e de memória, devido à natureza exponencial do problema. Assim, ao invés de apenas um agente central realizar todas as operações, é mais eficiente do ponto de vista do uso de recursos computacionais distribuir essas operações entres os diversos agentes presentes no sistema. Além dos benefícios computacionais, distribuir o processo de busca pela melhor estrutura de coalizão permitiria trabalhar com questões como privacidade e tolerância a falhas, tendo em vista que as informações não estão concentradas em um único agente. Apesar disso, não há na literatura qualquer algoritmo capaz de solucionar o problema de geração de estrutura de coalizão em ambientes distribuídos e que sejam modelados como jogos de partição. A proposta desse trabalho é utilizar a fundamentação teórica existente acerca do problema de formação de estruturas de coalizão (modelados tanto como jogos de função característica quanto como jogos de partição) para criar um algoritmo distribuído capaz de encontrar a estrutura de coalizão ótima em ambientes que possuam externalidade. Esse algoritmo utiliza como base a ordenação das coalizões e dos agentes para permitir a distribuição do cálculo dos limites superiores e inferiores de cada coalizão. Após, esses valores são utilizados para se encontrar o subespaço mais provável de conter a estrutura de coalizão ótima. Com base nos experimentos, percebe-se que o algoritmo encontrou a estrutura de coalizão ótima buscando em apenas uma pequena parte do espaço de busca. Para os experimentos com 16 agentes, o algoritmo foi capaz de encontrar a solução ótima procurando em apenas 0,01% do espaço de busca. Também, é demonstrado que em cenários com externalidade negativa os agentes necessitaram investigar um espaço de busca menor para encontrar a estrutura de coalizão ótima que em cenários com externalidade positiva. Experimentos também demonstram que o algoritmo não consegue encontrar a estrutura de coalizão ótima quando há falhas na comunicação entre os agentes.