Sequences of coalition structures in multi-agent systems applied to disaster response

Abstract

A formação de coalizões é um tópico de interesse da comunidade científica que estuda sistemas multiagentes devido aos desafios emergentes na utilização dessa técnica em aplicações práticas, assim como em virtude da complexidade envolvida para computar uma solução para o problema. Uma coalizão é uma organização de curta duração de agentes formada para atingir um objetivo em comum de seus integrantes. A teoria dos jogos cooperativos estabelece um mecanismo formal para análise dos grupos formados por diferentes agentes: as coalizões. Assim, o problema é modelado utilizando jogos de funções características (do inglês Characteristic- Function Game (CFG)) no qual o produto final de tal jogo é chamado de estrutura de coalizões: uma partição de um conjunto de agentes em coalizões. Entretanto, nem todos os problemas encontrados na prática podem ser resolvidos eficientemente utilizando uma única estrutura de coalizões. Por exemplo, pode ser necessário a formação de uma hierarquia de grupos na qual uma estrutura de coalizões é requerida por nível hierárquico. Na presente tese, problemas de formação de coalizões que são interdependentes são investigados. Especificamente, jogos de formação de coalizões são resolvidos individualmente e existe uma interdependência entre as soluções dos diferentes jogos. Visto a escassez de trabalhos científicos nesse tópico, um novo jogo é proposto, chamado de jogos sequenciais de funções características (do inglês Sequential Characteristic-Function Game (SCFG)), o qual visa modelar o relacionamento entre estruturas de coalizões subsequentes para o problema descrito por uma sequência de CFGs correspondente. O novo jogo proposto é estendido para modelar restrições induzidas sobre cada CFG na sequência de jogos. Além disso, por meio de uma análise teórica conclui-se que o problema subjacente ao SCFG é PSPACE-completo. Considerando uma perspectiva algorítmica, um algoritmo exato para computar soluções de instancias SCFG, assim como dois algoritmos heurísticos, são propostos. O desafio final do presente trabalho é modelar uma operação de resposta a desastres que emprega o sistema de comando de incidentes (do inglês incident command system), utilizando as técnicas e algoritmos propostos.