Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2017. / Submitted by Raquel Almeida (raquel.df13@gmail.com) on 2018-03-06T16:26:14Z No. of bitstreams: 1 2017_LeonardoHenriqueMoreira.pdf: 1690592 bytes, checksum: e6528f291ca601089ce0d3f64309f5ca (MD5) / Approved for entry into archive by Raquel Viana (raquelviana@bce.unb.br) on 2018-03-07T15:45:35Z (GMT) No. of bitstreams: 1 2017_LeonardoHenriqueMoreira.pdf: 1690592 bytes, checksum: e6528f291ca601089ce0d3f64309f5ca (MD5) / Made available in DSpace on 2018-03-07T15:45:35Z (GMT). No. of bitstreams: 1 2017_LeonardoHenriqueMoreira.pdf: 1690592 bytes, checksum: e6528f291ca601089ce0d3f64309f5ca (MD5) Previous issue date: 2018-03-07 / Planejamento multiagente é um tema desafiador e atual na área de pesquisa de Inteligência Artificial. A complexidade e necessidade de interação entre os agentes tem como consequência elevados valores para métricas relacionadas ao tempo de execução e volume de comunicação. Considerando esses fatores como interessantes questões de pesquisa, esse trabalho propõe um modelo de planejamento multiagente com verificação, transformação e validação de planos. O modelo proposto foi denominado LCMAP - Lightweigth Coordination Multiagent Planning, por utilizar um modelo de coordenação eficiente reduzindo o nível de troca de mensagens entre os agentes. No LCMAP a verificação e transformação do problema são realizadas em uma fase inicial, com o intuito de facilitar o processo de planejamento diminuindo a interação entre os agentes. As capacidades dos agentes são analisadas quanto à possibilidade de atingirem os objetivos de forma total ou parcial. Para simplificar o problema original, o mesmo é transformado em um conjunto de instâncias menores através da atribuição dos objetivos aos agentes com as capacidades necessárias. Desta forma, o processo de planejamento é realizado de maneira individual, minimizando o tempo necessário e o volume de mensagens trocadas. Por fim, os planos calculados são validados, garantindo que suas execuções possam ocorrer de maneira paralela. As principais contribuições do trabalho incluem: (i) realização de testes antes da fase de planejamento para avaliar a possibilidade de encontrar uma solução; (ii) utilização de técnicas de execução paralela, sendo este aspecto pouco explorado nos trabalhos relacionados; e (iii) alocação eficiente dos recursos disponíveis através de estratégias que visam minimizar o número de agentes ou balancear a carga entre os mesmos. / Multiagent planning is a challenging and modern theme in the Artificial Intelligence research area. The complexity and requirements of interactions among agents lead to high values of metrics related to execution time and communication volume. Concerning these points as interesting research questions, this work proposes a multiagent planning model with plan verification, transformation, and validation. The proposal was defined as LCMAP - Lightweight Coordination Multiagent Planning due to its use of an efficient coordination process that aims to reduce the message exchanged level among agents. In LCMAP, the problem verification and validation are carried out in an initial phase in order to ease the planning process by diminishing agent interactions. The agent’s capabilities are analyzed about the possibility of reaching the goals in a total or partial way. The original problem is transformed to smaller instances set by assigning goals to agents with the required capabilities. In this sense, the planning process is performed in an individual way, minimizing the necessary time and the message exchanged volume. Finally, the plans found are validated in order to grant that their executions can occur parallel. The main contributions of these works include: (i) tests carried out before the planning phase in order to evaluate the possibility of finding a solution; (ii) use of parallel execution techniques, which are rarely exploited in related works; and (iii) efficient allocation of available resources using strategies that aim to minimize the number of agents or balance the load among them.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-05-08T18:37:11Z No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) / Approved for entry into archive by Caroline Xavier (caroline.xavier@pucrs.br) on 2018-05-15T19:07:36Z (GMT) No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) / Made available in DSpace on 2018-05-15T19:14:18Z (GMT). No. of bitstreams: 1 RAFAEL_CAU?_CARDOSO_TES.pdf: 14431785 bytes, checksum: 227194ed28a9e55c3ab1fbedebf06922 (MD5) Previous issue date: 2018-03-27 / Sistemas multiagentes freq?entemente cont?m ambientes complexos e din?micos, nos quais os planos dos agentes podem falhar a qualquer momento durante a execu??o do sistema. Al?m disso, novos objetivos podem aparecer para os quais n?o existem nenhum plano dispon?vel. T?cnicas de planejamento s?o bem adequadas para lidar com esses problemas. H? uma quantidade extensa de pesquisa em planejamento centralizado para um ?nico agente, por?m, at? ent?o planejamento multiagente n?o foi completamente explorado na pr?tica. Plataformas multiagentes tipicamente proporcionam diversos mecanismos para coordena??o em tempo de execu??o, frequentemente necess?rios em planejamento online. Neste contexto, planejamento multiagente descentralizado pode ser eficiente e eficaz, especialmente em dom?nios fracamente acoplados, al?m de garantir algumas propriedades importantes em sistemas de agentes como privacidade e autonomia. N?s abordamos esse problema ao apresentar uma t?cnica para planejamento multiagente online que combina aloca??o de objetivos, planejamento individual utilizando rede de tarefas hier?rquicas (HTN), e coordena??o em tempo de execu??o para apoiar a realiza??o de objetivos sociais em sistemas multiagentes. Especificamente, n?s apresentamos um framework chamado Decentralised Online Multi-Agent Planning (DOMAP). Experimentos com tr?s dom?nios fracamente acoplados demonstram que DOMAP supera quatro planejadores multiagente do estado da arte com respeito a tempo de planejamento e tempo de execu??o, particularmente nos problemas mais dif?ceis. / Multi-agent systems often contain dynamic and complex environments where agents? course of action (plans) can fail at any moment during execution of the system. Furthermore, new goals can emerge for which there are no known plan available in any of the agents? plan library. Automated planning techniques are well suited to tackle both of these issues. Extensive research has been done in centralised planning for singleagents, however, so far multi-agent planning has not been fully explored in practice. Multi-agent platforms typically provide various mechanisms for runtime coordination, which are often required in online planning (i.e., planning during runtime). In this context, decentralised multi-agent planning can be efficient as well as effective, especially in loosely-coupled domains, besides also ensuring important properties in agent systems such as privacy and autonomy. We address this issue by putting forward an approach to online multi-agent planning that combines goal allocation, individual Hierarchical Task Network (HTN) planning, and coordination during runtime in order to support the achievement of social goals in multi-agent systems. In particular, we present a planning and execution framework called Decentralised Online Multi-Agent Planning (DOMAP). Experiments with three loosely-coupled planning domains show that DOMAP outperforms four other state-of-the-art multi agent planners with regards to both planning and execution time, particularly in the most difficult problems.