Alocação de tarefas de desastre na plataforma RMASBench : uma abordagem baseada em passagem de mensagens e formação de grupos

Abstract

Em ambientes de desastre urbano, grupos de agentes de resgate devem resolver tarefas de modo a minimizar os danos que podem ocorrer na cidade. Tais ambientes são dinâmicos e parcialmente observáveis, com características que dizem respeito à distância espacial, quantidade de recursos, à dificuldade da tarefa de desastre e à capacidade do agente de atendê-la. A comunicação entre os agentes pode ser ruidosa ou inexistente. Os sistemas multiagente são desenvolvidos para resolver problemas complexos e abrangentes, que estão além da capacidade de um único agente. Nesse contexto, os agentes são elementos computacionais autônomos que são responsáveis por uma parte da solução do problema. Os agentes são situados em um ambiente e podem ter habilidade social, interagindo com outros agentes para resolver as tarefas. Comumente, o domínio de desastre urbano é formalizado como um problema de alocação de tarefas e modelado como um problema de otimização de restrições distribuídas entre agentes heterogêneos, onde eles têm que escolher as tarefas que maximizam suas utilidades individuais ou minimizem seus custos individuais. Essa dissertação de mestrado propõe um modelo para formação de grupos de agentes baseado na minimização de uma métrica de distância. O modelo é formalizado como um problema de otimização de restrições distribuídas, usando algoritmos para troca de mensagens entre os agentes. O modelo chamado Formação de Grupos pela Minimização da Distância (FGMD) tem agentes autônomos que tem a capacidade de se auto-organizar sem a necessidade de um controle centralizado. Aplicamos o FGMD na plataforma RMASBench, que é um simulador para situações de desastre urbano. Comparou-se o FGMD com os algoritmos mais recentes de passagem de mensagens, tendo sido verificado que o FGMD use menos computação não-paralela. Com respeito a minimização dos danos na cidade, mostrou-se que é possível obter resultados melhores que as abordagens do estado-da-arte com leve aumento no esforço computacional.

In urban disaster environments, groups of rescue agents must solve tasks in order to minimize the damage that can occur in a city. Such environments are dynamic and partially observable, with features that correspond to spatial distance, amount of resources, difficulty of the disaster task, and the capability of the agent to handle it. The communication between the agents can be noisy or non-existent. Multiagent systems are developed to solve complex and comprehensive problems, that are beyond the capability of one single agent. In this context, the agents are autonomous computational elements that are responsible for a piece of the solution of the problem. The agents are situated in an environment, and may have social ability, interacting with other agents to solve the tasks. Commonly, the urban disaster domain is formalized as a task allocation problem, and modelled as a constraint optimization problem distributed among heterogeneous agents, where they have to choose the tasks that maximize their individual utilities or minimize their individual costs. This master thesis proposes a model for formation of groups of agents based in the minimization of a distance. The model is formalized as a distributed constraint optimization problem, using algorithms to exchange messages between agents. The model called Formation of Groups by Minimization of Distance (FGMD) has self-organizing autonomous agents without a centralized control. We applied the FGMD in the RMASBench platform, that is a simulator for urban disaster situations. We compare the FGMD with the most recent message passing algorithms, verifying that FGMD uses less non-parallel computation. With respect to the minimization of the damage in the city, we show that it is possible to obtain better results than the state-of-art approaches, with slightly increase of computational effort.