O tamanho da representação de ações e estados conjuntos é um fator chave que limita o uso de algoritmos de apendizado por reforço multiagente em problemas complexos. Este trabalho propõe o opportunistic Coordination Learning (OPPORTUNE), um método de aprendizado por reforço multiagente para lidar com grandes cenários. Visto que uma solução centralizada não é praticável em grandes espaços de estado-ação, um modode reduzir a complexidade do problema é decompô-lo em subproblemas utilizando cooperação entre agentes independentes em algumas partes do ambiente. No método proposto, agentes independentes utilizam comunicação e um mecanismo de cooperação que permite que haja expansão de suas percepções sobre o ambiente e para que executem ações cooperativas apenas quando é melhor que agir de modo individual. O OPPORTUNE foi testado e comparado em dois cenários: jogo de perseguição e controle de tráfego urbano. / The size of the representation of joint states and actions is a key factor that limits the use oh standard multiagent reinforcement learning algorithms in complex problems. This work proposes opportunistic Coordination Learning (OPPORTUNE), a multiagent reinforcement learning method to cope with large scenarios. Because a centralized solution becomes impratical in large state-action spaces, one way of reducing the complexity is to decompose the problem into sub-problems using cooperation between independent agents in some parts of the environment. In the proposed method, independent agents use communication and cooperation mechanism allowing them to extended their perception of the environment and to perform cooperative actions only when this is better than acting individually. OPPORTUNE was tested and compared in twm scenarios: pursuit game and urban traffic control.

Atualmente pesquisadores de inteligência artificial buscam métodos para solucionar problemas de aprendizado por reforço que estão associados a uma grande quantidade de recursos computacionais. Em cenários multiagentes onde os espaços de estados e ações possuem alta dimensionalidade, as abordagens tradicionais de aprendizado por reforço são inadequadas. Como alternativa existem técnicas de generalização do espaço de estados que ampliam a capacidade de aprendizado através de abstrações. Desta maneira, o foco principal deste trabalho é utilizar as técnicas existentes de aprendizado por reforço com aproximação de funções através de tile coding para aplicação nos seguintes cenários: presa-predador, controle de tráfego veicular urbano e jogos de coordenação. Os resultados obtidos nos experimentos demonstram que a representação de estados por tile coding tem desempenho superior à representação tabular. / Nowadays, researchers are seeking methods to solve reinforcement learning (RL) problems in complex scenarios. RL is an efficient, widely used machine learning technique in single-agent problems. Regarding multiagent systems, in which the state space generally has high dimensionality, standard reinforcement learning approaches may not be adequate. As alternatives, it is possible to use techniques that generalize the state space to enhance the ability of the agents to learn through the use of abstraction. Thus, the focus of this work is to use an existing reinforcement learning technique, namely tile coding, that is a better form of state representation. This kind of method is key in scenarios where agents have a high number of states to explore. In the scenarios used to test and validate this approach, our experimental results indicate that the tile coding state representation outperforms the tabular one.

A representação do conhecimento de maneira mais fiel possível à realidade é uma meta histórica e não resolvida até o momento na área da Inteligência Artificial. Problemas são resolvidos e decisões são tomadas levando-se em conta diversos tipos de conhecimentos, os quais muitos são tendenciosos, inexatos, ambíguos ou ainda incompletos. A fim de tentar emular a capacidade de representação do conhecimento humano, levando-se em conta as diversas dificuldades inerentes, tem-se construído sistemas computacionais que armazenam o conhecimento das mais diversas formas. Dentro deste contexto, este trabalho propõe um experimento que utiliza duas formas distintas de representação do conhecimento: a simbólica, neste caso BDI, e a probabilística, neste caso Redes Bayesianas. Para desenvolvermos uma prova de conceito desta proposta de representação do conhecimento estamos utilizando exemplos que serão construídos através da tecnologia de programação voltada para agentes. Para tal, foi desenvolvida uma implementação de um Sistema MultiAgente, estendendo o framework Jason através da implementação de um plugin chamado COPA. Para a representação do conhecimento probabilístico, utilizamos uma ferramenta de construção de Redes Bayesianas, também adaptada a este sistema. Os estudos de caso mostraram melhorias no gerenciamento do conhecimento incerto em relação às abordagens de construções de agentes BDI clássicos, ou seja, que não utilizam conhecimento probabilístico. / Achieving faithful representation of knowledge is a historic and still unreached goal in the area of Artificial Intelligence. Problems are solved and decisions are made taking into consideration different kinds of knowledge, from which many are biased, inaccurate, ambiguous or still incomplete. Computational systems that store knowledge in many different ways have been built in order to emulate the capacity of human knowledge representation, taking into consideration the several inherent difficulties to it. Within this context, this paper proposes an experiment that utilizes two distinct ways of representing knowledge: symbolic, BDI in this case, and probabilistic, Bayesian Networks in this case. In order to develop a proof of concept of this propose of knowledge representation, examples that will be built through agent oriented programming technology will be used. For that, implementation of a MultiAgent System was developed, extending the Jason framework through the implementation of a plugin called COPA. For the representation of probabilistic knowledge, a Bayesian Network building tool, also adapted to this system, was used. The case studies showed improvement in the management of uncertain knowledge in relation to the building approaches of classic BDI agents, i.e., that do not use probabilistic knowledge.

O presente trabalho está focado na questão do equilíbrio dos valores de troca em sistemas multiagentes. A base para a formalização das interações sociais entre os agentes envolvidos é a Teoria Sociológica de Piaget, a partir da qual as relações sociais podem ser vistas como troca de serviços entre os indivíduos. A cada interação, corresponde um conjunto de valores de troca qualitativos, os quais podem ser materiais, correspondentes ao custo real do prestador do serviço e ao benefício real do beneficiário do serviço, ou virtuais, correspondentes aos créditos ou débitos que cada indivíduo assume para si próprio. Nesse contexto, o equilíbrio dos valores de troca reflete o cumprimento das normas da sociedade, sejam essas normas de caráter moral ou jurídico. Apresenta-se uma abordagem simples para o problema do equilíbrio social, a qual se baseia na comunicação entre os agentes e na avaliação do histórico de trocas passadas para a determinação dos valores adequados a cada nova troca. Verificou-se que esta abordagem apresenta resultados satisfatórios, ainda que aplicada somente durante parte das interações entre os agentes, demonstrando que, apesar de simples, é uma abordagem eficiente para o atingimento e manutenção do equilíbrio social. / This work focuses on the equilibrium of exchange values on multiagent systems. The basis to the formalization of social interaction is Piaget’s Sociological Theory, which states that social relationships can be seen as service exchanges between individuals. To each social interaction, there is a corresponding set of qualitative exchange values, that can be material, corresponding to real costs and benefits for the involved, or virtual, corresponding to credits and debits recognized by each individual. On this context, the equilibrium of exchange values reflects the obedience to society rules, that may be of moral or legal nature. We present a simple approach to the equilibrium problem, which is based on communication among agents and analysis of past interactions, in order to determinate the appropriate values for each new exchange. We show that this approach presents satisfactory results, demonstrating that, in spite of its simplicity, it is an efficient approach for reaching and sustaining social equilibrium.

Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos. / Distributed Constraint Optimization Problems (DCOP) have a significant importance in ComputerScience, due to its computationalcomplexity. The objective of this work is to compare the three most popular algorithms for DCOP (ADOPT,OptAPO and DPOP) in terms of computational efficiency and quality of the proposed solution. In arder to do that, a trafficcontrol scenario is used. This kind of problem is very important when considering an efficientadministration of the trafficnetwork,which involvesa lot of interdependencies among variables such as the occupation of the links and the split of the lights. The control strategies should be able to provide good results in terms of the domain application and consider the computational infrastructure available,matching exactly the objectives of the DCOP implementations. The present work is related to multiagent systems, constraint optimization and traffic light controI. The DCOP models are used in order to perfarm the comparison among the algorithms. The results show that is possible to improve the efficiency of the control over the c1assicapproaches of fixed traffic light timing. This is verifiedconsidering the utilization leveIof the network and the occurrence of trafficjams. Besides that, some computational issues are considered to compare the algorithms, for instance, the execution time.

Sistemas multiagente são construídos para atingir objetivos complexos e abrangentes, que estão além da capacidade de um único agente. Estes objetivos podem ser representados através de tarefas, que devem ser realizadas pelos agentes de forma a otimizar o desempenho do sistema. Em muitos ambientes reais, a escala do problema envolve tanto uma grande quantidade de agentes, quanto uma grande quantidade de tarefas. Além disto, os agentes devem lidar com informações incompletas, realizando tarefas em tempo hábil. O termo extreme teams foi introduzido na literatura para designar as seguintes quatro características da alocação de tarefas: oa ambientes são dinâmicos; os agentes podem realizar múltiplas tarefas; os agentes podem possuir funcionalidades sobrepostas; e podem existir interrelacionamentos entre tarefas, impondo, por exemplo, necessidade de realização simultânea. Abordagens existentes na literatura tratam, efetivamente, apenas as três primeiras características de extreme teams. Esta dissertação apresenta um algoritmo para alocação de tarefas, chamado eXtreme-Ants, que trata todas as quatro características de extreme teams. O algoritmo é inspirado no sucesso ecológico dos insetos sociais, e utiliza as metáforas de divisão de trabalho e recrutamento para transporte cooperativo. A metáfora de divisão de trabalho proporciona decisões rápidas e eficientes, atendendo as três primeiras características de extreme teams. O recrutamento permite formar grupos de agentes comprometidos com a realização simultânea de tarefas que exigem esforço conjunto, atendendo a quarta característica: inter-relacionamentos entre tarefas. Com isto, concretiza-se de fato o conceito completo de extreme teams. Experimentos foram realizados em dois ambientes distintos: um simulador independente de domínio e o simulador RoboCup Rescue. Os resultados obtidos demonstraram que a eficiência do eXtreme-Ants é balanceada com relação ao desempenho, quantidade de comunicação e esforço computacional. / Multiagent systems aim at achieving complex and broad goals, which are beyond the capability of a single agent. These goals can be represented by tasks, which must be performed by the agents in order to optimize the performance of the system. In many real-world environments, the scale of problems involves both a large number of agents and a large number of tasks. Besides, the agents must reason with incomplete and uncertain information, in a timely fashion. The expression extreme teams was introduced in the literature to describe the following four characteristics regarding task allocation: dynamic environments; agents may perform multiple tasks; agents can have overlapping functionality; and inter-task constraints (such as simultaneous execution requirements) may be present. Existing approaches effectively deal with just the three first characteristics of extreme teams. This dissertation presents an algorithm for allocating tasks to agents, called eXtreme- Ants, which deals with all the four characteristics of extreme teams. The algorithm is inspired in the ecological success of social insects, and uses the metaphors of division of labor and recruitment for cooperative transport. The metaphor provides fast and efficient decision-making, complying to the first three characteristics. The recruitment ensures the formation of groups of agents committed to the simultaneous execution of tasks that require joint efforts, complying to the fourth characteristic: inter-task constraints. Thus, the full concept of extreme teams is indeed realized. Experiments were performed in two distict environments: a domain independent simulator, and the RoboCup Rescue simulator. The results shown that eXtreme-Ants achieves a balanced efficiency regarding performance, communication, and computational effort.

Sistemas de transporte são sistemas complexos compostos de diferentes entidades que interagem entre si. A otimização do uso da infraestrutura de transporte existente, que é cada vez mais necessária dado o crescente aumento da demanda por mobilidade, passa pela simulação de novas tecnologias que podem vir a ser utilizadas no futuro, como a comunicação inter-veicular (IVC) e a tarifação viária adaptativa. Esta dissertação apresenta uma abordagem baseada em agentes para simulação de comunicação inter-veicular e tarifação viária adaptativa em sistemas de transporte. Motoristas são modelados como agentes minimizadores de custo, composto pelo tempo de viagem e pelas despesas com tarifas viárias. Os motoristas podem usar IVC para expandir seu conhecimento do estado da rede viária. Entre os motoristas que usam IVC, podem existir agentes maliciosos, que buscam afastar os demais de suas rotas, através da divulgação de informações falsas. Os agentes maliciosos podem ainda agir de maneira coordenada, de modo a divulgarem informações falsas sobre as rotas de todos os agentes do grupo. Pelo lado da infraestrutura, gerentes viários percebem o fluxo de veículos nas vias da rede viária e definem as tarifas a serem aplicadas através de um esquema de aprendizado por reforço. Nos experimentos realizados, empregamos um modelo microscópico de simulação de tráfego, o que permite observar o comportamento individual de cada entidade do sistema de transporte sob estudo. O cenário onde as simulações são executadas é uma rede viária com as principais vias arteriais da cidade de Porto Alegre, Brasil. Resultados experimentais indicam que um pequeno grupo coordenado de agentes maliciosos em cenários de IVC é capaz de causar prejuízos significativos aos demais motoristas. Embora na média o grupo não consiga reduzir seu tempo de viagem, alguns agentes maliciosos são beneficiados pela coordenação do grupo. Com relação à tarifação viária, os resultados experimentais indicam que o esquema de aprendizado por reforço não possui a mesma eficácia de um esquema de tarifação fixa quando se trata da maximização de fluxo de veículos na rede viária. Ambos os esquemas de tarifação são superados por um método de otimização de tráfego que assume conhecimento completo do estado da rede viária pelos motoristas. No aspecto individual, sob tarifação via aprendizado por reforço, os custos de deslocamento dos motoristas são superiores em comparação aos custos sob tarifação fixa. O modelo baseado em agentes apresentado nesta dissertação representa uma contribuição em direção à proposição de uma metodologia para integrar modelos comportamentais de usuários de sistemas de transporte que reagem aos padrões de tráfego e medidas de controle desses padrões, com foco em métodos descentralizados e distribuídos. / Transportation systems are complex systems composed of different interacting entities. The optimization of the existing transportation infrastructure usage, which becomes increasingly necessary given the increasing demand for mobility, requires simulation of new technologies that might be used in the future, such as inter-vehicular communication (IVC) and adaptive road pricing. This dissertation presents an agent-based approach for simulation of inter-vehicular communication and adaptive road pricing in transportation systems. Drivers are modeled as cost-minimizer agents, where the cost is composed by travel time and expenditure. Drivers can use IVC to expand their knowledge of the road network state. Among the IVC users, there might be malicious agents, which try to divert other drivers from their routes by spreading false information. The malicious agents can act in a coordinated way, by spreading false information about the routes of all the agents in the group. In the infrastructure side, link managers perceive the vehicular flow in the roads and define the prices to be applied by means of a reinforcement learning scheme. In the experiments, we employ a microscopic traffic simulation model, which allows us to observe the individual behavior of each entity in the studied transportation system. The scenario where the simulations are run is a road network with the main arterial roads of the city of Porto Alegre, Brazil. Experimental results indicate that a small group of coordinated malicious agents in IVC scenarios is able to cause significant losses to the other drivers. Although in average the group does not succeed in reducing their travel times, some agents are benefited by the coordination of the group. Regarding road pricing, experimental results indicate that the reinforcement learning scheme does not achieve the same effectiveness of a fixed pricing approach regarding the maximization of vehicular flow in the road network. Both pricing schemes are outperformed by an optimization method that assumes full knowledge of the road network state by the drivers. In the individual aspect, under pricing via reinforcement learning, drivers’ costs are higher compared to their costs under fixed pricing. The agent-based model presented in this dissertation is a contribution towards a methodology to integrate behavioral models of human travelers reacting to traffic patterns and control measures of these traffic patterns, focusing on distributed and decentralized methods.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Sistemas Multiagentes estão recebendo cada vez mais a atenção de pesquisadores e desenvolvedores de jogos virtuais. O uso de agentes permite controlar o desempenho do usuário, adaptando a interface e alterando automaticamente o nível de dificuldade das tarefas. Este trabalho descreve uma estratégia de integração de sistemas multiagentes e ambientes virtuais tridimensionais e exemplifica a viabilidade dessa integração através do desenvolvimento de um jogo com características de Serious game. Este jogo visa estimular as funções cognitivas, tais como atenção e memória e é voltado para pessoas portadoras de diferentes distúrbios neuropsiquiátricos. A construção do jogo foi apoiada em um processo de desenvolvimento composto por várias etapas: estudos teóricos sobre as áreas envolvidas, estudo de tecnologias capazes de apoiar essa integração, levantamento de requisitos com especialistas, implementação e avaliação com especialistas. O produto final foi avaliado por especialistas da área médica, que consideraram os resultados como positivos. / Multi-agent systems are receiving increasing attention from researchers and developers of virtual games. The use of agents can control the performance of the user, adapting the interface and automatically changing the difficulty level of the task. This paper describes a strategy for integration of multi-agent systems and three-dimensional virtual environments and demonstrates the feasibility of this integration through the development of a game featuring the Serious game. This game aims to stimulate cognitive functions such as attention and memory and is designed for people with different neuropsychiatric disorders. The game construction was supported in a development process that consists of several stages: theoretical studies of the involved areas, the study of technologies that support this integration, requirements gathering with experts, implementation and evaluation specialists. The final product was evaluated by medical experts, who considered the results as positive.

Made available in DSpace on 2014-11-10T11:09:41Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-07-30Bitstream added on 2014-11-10T11:58:46Z : No. of bitstreams: 1 000787312.pdf: 3890205 bytes, checksum: 8da919abeca178df298784b7faeb5bb6 (MD5) / Os avanços tecnológicos ocorridos nos últimos anos, principalmente em relação aos softwares e hardwares têm contribuído para o aumento da utilização de sensores e controladores pelas indústrias. Nesses ambientes, o grande desafio é o desenvolvimento de sistemas computacionais cada vez mais complexos para a integração dos componentes heterogêneos, o gerenciamento e a análise da grande quantidade de dados gerados, com a finalidade de automatizar as atividades dos operadores na supervisão e no controle dos processos envolvidos. Nesse contexto, a abordagem de sistemas multiagentes oferece um caminho promissor e inovador para entender, desenvolver, gerenciar e manter sistemas complexos. Assim, o objetivo desse trabalho consiste em especificar uma arquitetura utilizando a abordagem de sistemas multiagentes, de forma que essa arquitetura possa ser utilizada como um modelo de referência para o desenvolvimento de sistemas computacionais voltados para a supervisão e controle de processos. A arquitetura foi especificada a partir dos aspectos e requisitos analisados em um conjunto de trabalhos correlatos que utilizam a abordagem de sistema multiagente em aplicações no domínio de supervisão e controle. Utilizando a arquitetura proposta foi desenvolvido o protótipo de um sistema para supervisionar as operações de perfuração de poços de petróleo. No desenvolvimento do protótipo foi definida uma ontologia para descrever o conhecimento do domínio de perfuração de poços de petróleo, representando as operações, as anormalidades e os agentes. O protótipo foi testado utilizando um conjunto de dados reais, onde foi possível validar alguns dos aspectos da arquitetura proposta / The technological advances occurred in last years have contributed to increase the use of sensors and controllers in industries. In these environments, the major challenge is the development of complex computer systems to integrate heterogeneous components, to manage and analyze the large amount of produced data, in order to automate the operators’ activities to supervise and control involved processes. In this context, multi-agent approach offers a promising and innovative way to understand, develop, manage and maintain complex systems. The objective of this work is to specify a reference architecture using the multi-agent approach. The architecture was proposed to be used as a reference model for the development of computational systems for processes monitoring and control. The architecture has been specified through an analysis of the aspects and requirements found in a set of related works that use the multi-agent approach in the development of applications in the field of supervision and control. Based on the proposed architecture was developed a system prototype to supervise oil well drilling operations. In this prototype, an ontology was defined to describe knowledge of oil well drilling domain, in order to represent operations, abnormalities and agents. This prototype was tested using a real data set, with the tests was possible to validate some aspects of the proposed architecture

Problemas de otimização de restrições distribuídas (DCOP - Distributed Constraint Optimization Problem) formam uma classe de problemas de grande interesse de estudo na ciência da computação em função da complexidadecomputacionaL O presente trabalho tem o objetivo de comparar os três algoritmos mais populares em DCOP (ADOPT, OptAPO e DPOP) em termos de eficiência computacional e de solução proposta. Para tal estudo, é utilizado como domínio um problema de controle semafórico. Esse tipo de problema de controle é de fundamental importânciapara que se tenha uma administração eficiente do fluxo de veículos em uma malha viária. Além disso, envolve muitas interdependências entre variáveis da rede, como ocupação das vias e tempos de sinal verde dos semáforos, para que sejam determinadas as melhores configurações de controle. Nesse sentido, as estratégias devem fornecer bons resultados em nível de aplicação, e também em nível de computação, no que diz respeito ao uso da infra-estrutura computacional disponível, o que casa perfeitamente com os objetivos das implementações de DCOP. Ao longo deste trabalho, os temas relacionados à coordenação em sistemas multiagentes, otimização de restrições e controle de semáforos são estudados. Os modelos DCOP são utilizados com a finalidade de comparar os algoritmos.No que diz respeito aos resultados, percebe-se uma melhora no controle, obtida com o uso dos algoritmos DCOP em relação ao uso de controle fixo sincronizado e não sincronizado. Isso é verificado em nível de utilização das vias da rede. Além disso, outro tipo de resultado é verificado na execução dos algoritmos, tratando de questões como o tempo de execução. Foi possível estabelecer um comparativo entre os algoritmos e frente ao aumento do problema em quantidade de semáforos. / Distributed Constraint Optimization Problems (DCOP) have a significant importance in ComputerScience, due to its computationalcomplexity. The objective of this work is to compare the three most popular algorithms for DCOP (ADOPT,OptAPO and DPOP) in terms of computational efficiency and quality of the proposed solution. In arder to do that, a trafficcontrol scenario is used. This kind of problem is very important when considering an efficientadministration of the trafficnetwork,which involvesa lot of interdependencies among variables such as the occupation of the links and the split of the lights. The control strategies should be able to provide good results in terms of the domain application and consider the computational infrastructure available,matching exactly the objectives of the DCOP implementations. The present work is related to multiagent systems, constraint optimization and traffic light controI. The DCOP models are used in order to perfarm the comparison among the algorithms. The results show that is possible to improve the efficiency of the control over the c1assicapproaches of fixed traffic light timing. This is verifiedconsidering the utilization leveIof the network and the occurrence of trafficjams. Besides that, some computational issues are considered to compare the algorithms, for instance, the execution time.