Heurística para formação de estruturas de coalizão no simulador Robocup Rescue

Abstract

Um dos objetivos principais de um sistema multiagentes é atingir objetivos que estão além da capacidade de um único agentes. Estes objetivos podem ser tarefas que um único agente não tem condições de realizar sozinho, necessitando assim que outros agentes trabalhem junto com ele. Nesses casos, o mecanismo de coordenação de um sistema multiagentes é parte fundamental para o bom funcionamento do sistema, pois permite que os agentes possam agir de maneira coesa em direção aos seus objetivos, sejam eles individuais ou coletivos. A formação de coalizões (grupos de agentes que concordam em coordenar suas ações por um objetivo comum) é uma questão fundamental nesses sistemas, pois serve de mecanismo de coordenação entre os agentes. Essa tarefa de formação de coalizões entre agentes é um tópico de pesquisa muito ativo que recebe atenção de pesquisadores de diversas áreas. Um dos grandes problemas associados à formação de coalizão de agentes e que representa um importante gargalo no processo, é estabelecer uma partição dos agentes em coalizões denominada de estrutura de coalizão. O que significa, em outras palavras, determinar quais coalizões devem ser formadas de maneira a maximizar a utilidade do sistema. Neste trabalho, é apresentada uma maneira eficiente de criar estruturas de coalizão no simulador Robocup Rescue. Através de uma série de restrições e um conjunto de regras, demonstra-se como realizar uma busca eficiente por uma CS durante a execução do Simulador. Cada agente do simulador conta com um conjunto de regras e restrições que podem ser trabalhados de forma individual em cada coalizão. Esse conjunto de regras e restrições formam uma heurística para a busca de uma CS que seja satisfatória no contexto do simulador. Além disso, são apresentados experimentos realizados no simulador e uma medição da eficiência desta heurística. Comparando a eficiência e o resultado final desse processo com um algoritmo que não utiliza nenhum tipo de restrição no processo de coalizão, é demonstrado que o aumento na eficiência e diminuição do tempo de processamento não afetam de maneira significativa o resultado final.

One of the main goals of a multiagent system is to achieve goals that are beyond the capacity of a single agent. These goals can be tasks that a single agent is unable to accomplish alone, thus requiring that other agents work with him. In such cases, the coordination of a multiagent system is a key to the smooth functioning of the system because it allows agents to act in a manner united toward their goals, whether individual or collective. The formation of coalitions (groups of agents that agree to coordinate their actions toward a common goal) is a key issue in such systems, once it serves as a coordinating mechanism among agents. This task of coalition formation among agents is a very active research topic receiving attention from researchers in different areas. A major problem associated with the formation of coalition and that represents a major bottleneck in the process is to establish a partition of agents into coalitions called the coalition structure. Which means, in other words, determine which coalitions must be formed so as to maximize the usefulness of the system. In this paper, we present an efficient way to create structures coalition in RoboCup Rescue simulator. Through a series of restrictions and a set of rules, we show how to perform an efficient search for a CS during the execution of the Simulator Each agent simulator has a set of rules and restrictions that can be worked individually in each coalition. This set of rules and restrictions form a heuristic for finding a CS that is satisfactory in the context of the simulator. Furthermore, we present experiments conducted in the simulator and a measurement of the efficiency of this heuristic. Comparing the efficiency and outcome of this process with an algorithm that does not use any type of restriction in the process of coalition, is shown to increase efficiency and decrease processing time does not significantly affect the final result.