Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-25T14:26:59Z No. of bitstreams: 2 Dissertação - Walisson Gobbo de Aguas - 2018.pdf: 21788863 bytes, checksum: f0bc1f69408a7740ea628458461baf2d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-10-25T14:28:33Z (GMT) No. of bitstreams: 2 Dissertação - Walisson Gobbo de Aguas - 2018.pdf: 21788863 bytes, checksum: f0bc1f69408a7740ea628458461baf2d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-10-25T14:28:33Z (GMT). No. of bitstreams: 2 Dissertação - Walisson Gobbo de Aguas - 2018.pdf: 21788863 bytes, checksum: f0bc1f69408a7740ea628458461baf2d (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-09-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The development of new technologies is mainly related to the construction of devices that aim in some way to assist the human being in his tasks, making them faster, easier and more precise. Since the discovery of the transistor, more than 70 years ago by John Bardeen and Walter Brattain, there has been a huge revolution, and new research areas have been created, especially in cooperative robotics and multi-agent. With the steady increase in the number of robots in an industrial environment, scientists and technologists have often faced problems of cooperation and coordination between different robots and their self-control in a workspace. This led to the evolution of autonomous multirobotic cooperative systems. Developers of multi-robotic autonomous systems needed a model to test the proposed theories in terms of effectiveness and efficiency. Not surprisingly, they began to focus on robot soccer. Robots soccer players have great demands in all areas of robot technology, mechanics, sensors and artificial intelligence. Thus, the objective of this work is to develop a small multi-agent system (7.5x7.5x7.5cm) intended to play soccer in a predetermined dynamic environment. A prototype will be developed for comparison purposes with a previously developed robot focusing on improvements to the multiagent controller system and the physical structure of the hardware. / O desenvolvimento de novas tecnologias está ligado principalmente à construção de dispositivos que visam de alguma forma auxiliar o ser humano em suas tarefas, tornando-as mais rápidas, fáceis e precisas. Desde a descoberta do transistor, a mais de 70 anos por John Bardeen e Walter Brattain, ocorreu uma revolução enorme, fazendo com que novas áreas de pesquisas fossem criadas, principalmente em robótica cooperativa e multiagentes. Com o aumento constante do número de robôs em um ambiente industrial, cientistas e tecnólogos frequentemente enfrentaram problemas de cooperação e coordenação entre diferentes robôs e seu autocontrole em um espaço de trabalho. Isso levou à evolução dos sistemas autônomos cooperativos multi-robóticos. Os desenvolvedores de sistemas autônomos multi-robóticos precisavam de um modelo para testar as teorias propostas em termos de eficácia e eficiência. Não é uma surpresa que eles começaram a se concentrar no futebol de robôs. Os robôs jogadores de futebol possuem grandes demandas em todas as áreas da tecnologia de robôs, mecânica, sensores e de inteligência artificial. Dessa forma o objetivo desse trabalho é desenvolver um sistema multiagente de dimensões reduzidas (7,5x7,5x7,5cm) destinado a jogar futebol em um ambiente dinâmico pré determinado. Um protótipo será desenvolvido para fins de comparação com um robô já desenvolvido anteriormente tendo como foco melhorias no sistema controlador do multiagente e na estrutura física do hardware.

Real-Time Optimization (RTO) is a family of techniques that pursue to improve the performance of chemical processes. As general scheme, the method reevaluates the process conditions in a frequent basis and tries to adjust some selected variables, taking into account the plant state, actual operational constraints and optimization objectives. Several RTO approaches have born from the academy research and industrial practices, at the same time that more applications have been implemented in real facilities. Between the main motivations to apply RTO are the dynamic of markets, the seek for quality in the process results and environmental sustainability. That is why the interest on deeply understand the phases and steps involved in an RTO application has increased in recent years. Nevertheless, the fact that most of the existing RTO systems have been developed by commercial organizations makes it difficult to meet that understanding. This work studies the nature of RTO systems from a software point of view. Software requirements for a generic system are identied. Based on that, a software architecture is proposed that could be adapted for specfic cases. Benefits of the designed architecture are listed. At the same time, the work proposes a new approach to implement that architecture as a Multi-Agent System (MAS). Two RTO system prototypes were developed then, one for a well-know academic case study and the other oriented to be used in a real unit. The benefits of the MAS approach and the architecture, for researching on the RTO field and implementation on real plants, are analyzed in the text. A sub-product of the development, a software framework covering main concepts from the RTO ontology, is proposed as well. As the framework was designed to be generic, it can be used in new applications development and extended to very specific scenarios. / Otimização em Tempo Real (OTR) é uma família de técnicas que buscam melhorar o desempenho dos processos químicos. Como esquema geral, o método reavalia frequentemente as condições do processo e tenta ajustar algumas variáveis selecionadas, levando em considera ção o estado da planta, restrições operacionais e os objetivos da otimização. Várias abordagens para OTR t^em surgido da pesquisa acadêmica e das práticas industriais, ao mesmo tempo em que mais aplicações têm sido implementadas em plantas reais. As principais motivações para aplicar OTR são: a dinâmica dos mercados, a busca de qualidade nos resultados dos processos e a sustentabilidade ambiental. É por isso que o interesse em entender as fases e etapas envolvidas em uma aplicação OTR cresceu nos últimos anos. No entanto, o fato de que a maioria dos sistemas OTR em operação foram desenvolvidos por organizações comerciais dificulta o caminho para chegar nesse entendimento. Este trabalho analisa a natureza dos sistemas OTR desde o ponto de vista do software. Os requerimentos para um sistema genérico são levantados. Baseado nisso, é proposta uma arquitetura de software que pode ser adaptada para casos específicos. Os benefícios da arquitetura projetada foram listados. Ao mesmo tempo, o trabalho propõe uma nova abordagem para implementar essa arquitetura: Sistema Multi-Agentes (SMA). Dois protótipos de sistema OTR foram desenvolvidos. O primeiro aplicado num estudo de caso bem conhecido na literatura acadêmica. O segundo voltado para ser usado em uma unidade industrial. Os benefícios da abordagem SMA e da arquitetura, tanto na pesquisa relacionada com OTR, quanto na implementação em plantas reais, são analisados no texto. Um arcabouço de software que abrange os principais conceitos da ontologia OTR é proposto como resultado derivado do desenvolvimento. O arcabouço foi projetado para ser genérico, possibilitando seu uso no desenvolvimento de novas aplicações OTR e sua extensão a cenários muito específicos.

Neste trabalho apresentamos um modelo para ambientes inteligentes baseado em organizações de agentes, onde interações entre entidades são associadas a espaços físicos, pessoas carregam dispositivos e se movimentam entre diferentes espaços físicos e cada espaço físico contém definições de interações (comportamentos definidos por normas) próprias do seu contexto. São definidos três componentes deste modelo: (1) modelo conceitual, (2) linguagem de especificação e (3) ambiente de execução. A separação do modelo nestes três componentes traz como principais conseqüências: (1) a ativação de um ambiente inteligente é feita através de um mecanismo de alto nível, (2) a especificação de um ambiente inteligente é independente do domínio de aplicação e (3) as especificações podem ser executadas em mecanismos diferentes de execução. / We introduce a conceptual model for smart environments based on agent organizations where interactions between entities are associated with physical spaces, people (carrying mobile devices) move between different physical spaces and these physical spaces contain definitions of interactions (behaviors defined by norms) related to each context. This model defines three components: (1) conceptual model, (2) language specification, and (3) execution environment. The separation in these three components brings as main consequences: (1) activation of a smart environment is performed through a high-level mechanism, (2) specification of a smart environment is independent of the application domain, and (3) specifications can be performed on different mechanisms of execution.

A falta de informação e de confiança entre os agentes em sistemas de recomendação que lidam com domínios dinâmicos podem ser fatores que contribuem para que os agentes gerem resultados de baixa qualidade. Na falta de informação para gerar recomendações, é necessário que os agentes sejam capazes de assumir ou compartilhar informações, criem laços de confiança entre si e que se adaptem às mudanças do estado do conhecimento para que sejam capazes de resolver os problemas. Esta tese apresenta a abordagem MATRES - uma abordagem multiagente baseada em suposições com mecanismo de confiança aplicada em um sistema de recomendação multiagente. Na abordagem MATRES, os agentes são capazes de lidar com conhecimento distribuído. Cada agente trabalha como especialista e é capaz de compartilhar seu conhecimento com os demais, de acordo com seus índices de confiança. Para a solução de um problema, diferentes tarefas são distribuídas entre os agentes. Algumas tarefas apresentam uma relação de dependência, fazendo com que uma tarefa dependa do resultado de outra. Nesta situação, o agente possui um componente de manutenção da verdade que permite a utilização de suposições para a realização das tarefas de forma assíncrona. Na falta de informação proveniente de outra tarefa, o agente é capaz de manipular suposições, sendo capaz de executar sua tarefa. Além disto, o componente de manutenção da verdade auxilia na manutenção da integridade das bases de conhecimento dos agentes. A abordagem MATRES foi validada em um cenário de recomendação de pacotes turísticos. Casos reais de uma agência de viagem foram utilizados na validação da abordagem e os resultados obtidos corroboram a hipótese de que que a abordagem proposta aumenta a assertividade das recomendações geradas pelos agentes em ambientes distribuídos e dinâmicos. / The lack of trust and information among agents in dynamic domains may contribute to the generation of poor results in multiagent recommender systems. These domains requires that agents exchange information, establishing bonds of trust among themselves and adapting the modification of the status of the knowledge to be able to solve problems. In systems where the knowledge is distributed among several agents, the exchange of information is essential for improving the performance of the agents and maybe leading to inconsistencies when the information exchanged has different status. This thesis presents the MATRES approach - a multiagent Assumption-Based recommender approach with a trust mechanism. In this approach agents are able to deal with distributed knowledge. Each agent works as an expert and is able to share its knowledge with other agents, according to its trust degree. In order to solve a problem, different tasks are distributed among the agents. Some tasks are interdependent, which means that to solve a task it is necessary to use the result from other one. In this situation, the agent has a truth maintenance component that allows using assumptions to perform tasks in a assynchronous ways and helps the maintenance of the integrity of the knowledge bases of the agents. TheMATRES approach was validated in the travel recommendation scenario. The results show that the proposal increases the assertiveness of the recommendations provided by the agents in this dynamic domain.

Este trabalho descreve a implementação de um sistema multi agente usando Redes de Comportamento configurada por Algoritmos Genéticos. O sistema utiliza o jogo de computador Quake II como o ambiente simulado para os agentes. Redes de Comportamento são utilizadas como o mecanismo de tomada de decisão. Um Algoritmo Genético é utilizado para configurar os parâmetros da Rede de Comportamento. Cada agente é um programa independente que se conecta ao servidor do jogo para realizar tarefas e trocar material genético a fim de evoluir. Os resultados obtidos mostram um ambiente multi agente dinamicamente configurado capaz de evoluir e se adaptar apropriadamente conforme o andamento do jogo. / This work describes the implementation of a multi-agent system using Behavior Networks configured by Genetic Algorithms. The system uses the computer game Quake II as the simulated environment for the agents. Behavior Networks are used as the decision making mechanism. The Genetic Algorithm is used to configure the parameters of the Behavior Network. Each agent of the system is an independent program that connects to the game server to perform tasks and to exchange genetic material in order to evolve. The results obtained indicate a dynamically configured multi-agent system that can evolve and adapt accordingly throughout the course of the game.

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.

Agentes atuando em sociedade devem agir de maneira coerente para atingir um objetivo comum. A coordenação nos sistemas multiagente previne o comportamento caótico dos agentes, permite que o sistema lide com restrições globais e a interdependência entre os agentes, e faz com que o sistema possa ser composto por agentes com diferentes competências. A coordenação pode ser baseada na estrutura organizacional, onde a comunidade de agentes atua a favor de um objetivo comum através da forma como estão organizados. Em ambientes dinâmicos a organização dos agentes deve se adaptar a mudanças nos objetivos do sistema, na disponibilidade de recursos, nos relacionamentos entre os agentes, e assim por diante. Esta flexibilidade é um problema chave nos sistemas multiagente e está relacionada a modelos de adaptação como os observados nos insetos sociais. O presente trabalho propõe uma abordagem para a geração e adaptação da organização de um sistema multiagente, em tempo de execução, utilizando como base os modelos teóricos de organização das colônias de insetos sociais. Esta abordagem enfoca a alocação e o escalonamento dinâmicos de tarefas distribuídos entre agentes com diferentes competências e em ambientes de larga escala. Dois cenários principais são utilizados para experimentar e validar a abordagem proposta. Estes cenários estão baseados em problemas de pesquisa operacional denominados Resource-Constrained Project Scheduling Problem (RCPSP) e o Generalized Assignment Problem (GAP). Este trabalho contribui para o avanço do estado-da-arte no estudo e desenvolvimento de sistemas multiagente e na modelagem e aplicação de técnicas de inteligência de enxames em problemas computacionais. A abordagem proposta para coordenação de agentes em cenários complexos é nova, eficaz e robusta. De maneira geral, esta abordagem contribui para busca da solução de problemas de coordenação de sistemas multiagente aplicados a problemas reais. / A community of individual agents must work in a coherent manner to reach some common goal. The coordination process in multiagent systems prevents chaotic behavior of agents, makes the system able to deal with global constraints and inter-agents dependencies, and allows the system to be composed of agents with different capabilities. This process is normally based on the organizational structure, where the community of agents works towards the system goal through the manner they are organized. However, in dynamic environments, agents must be able to adapt to the changing goals of the system, to the resources available, to their relationships with another agents, to changes on the environment and so on. This problem is a key one in multiagent systems and relates to models of adaptation, such as those observed among social insects. This work proposes a new approach to generate and adapt the multiagent organization on the fly based on the theoretical models of social insects colonies organization. This approach focuses on distributed dynamic scheduling and task allocation using agents with different capabilities in large scale environments. Two main scenarios have been used to experiment and validate the proposed approach: the Resource-Constrained Project Scheduling Problem (RCPSP) and the Generalized Assignment Problem (GAP). This work contributes to advancing the state-of-the-art in the study and development of multiagent systems and in the modeling and application of swarm intelligence techniques. The proposed approach to coordinate agents in complex scenarios is novel, effective and robust. This approach contributes to the search of coordination solutions to multiagent systems real applications.

Esta tese situa-se na área de IA (Inteligência Artificial) aplicada à educação incluindo características interdisciplinares tanto da própria IA como de IE (informática na Educação). Faz-se também necessário constarem, aspectos referentes à Ciência da Computação e Educação a fim de melhor situar a complexidade e a dimensão do trabalho desenvolvido. A utilização de técnicas de IA na elaboração e no desenvolvimento de ambientes de ensino-aprendizagem computadorizados tem se constituído em objeto de investigação por parte dos pesquisadores da área de Informática aplicada à Educação, devido as suas potencialidades. A utilização de agentes na modelagem e no projeto de STI permite-nos resgatar antigos problemas em aberto, como por exemplo a melhoria da interação entre tutor e aluno e a possibilidade de investigação dos processos mentais em nível mais estratificado. A arquitetura descrita nesta tese utiliza a metodologia que vem sendo aplicada ao projeto de STI, onde são contempladas diferentes formas de se trabalhar com um determinado conhecimento (estratégias de ensino e táticas associadas), levando-se em consideração o tipo de usuário que está interagindo com o sistema. A arquitetura, elaborada segundo uma abordagem construtivista, prevê que o tutor seja menos diretivo e menos controlador das ações do aluno. O controle é feito na forma de monitoração para que o tutor funcione como um parceiro, ou seja, como facilitador do trabalho do aluno. Contudo, devido às características da modalidade escolhida para construção do protótipo (jogo educacional), precisamos ter algumas atitudes no tutor que garantam que o sistema não entre em colapso. O que inviabilizaria o trabalho do aluno. Nestas situações críticas, o tutor vai se comportar de maneira mais diretiva. Cabe salientar que a abordagem construtivista não significa dar liberdade total ao aluno nem privá-lo de qualquer tipo de assistência. Portanto, o que deve ser destacado é o grau de interferência do tutor, i.e., o quanto ele interfere no trabalho do aluno e se ele permite ou não que o aluno siga um caminho alternativo àquele que ele tem como o ideal para resolver o problema (heurísticas do tutor sobre o problema e forma de solução). Além destes aspectos educacionais inerentes a todo o projeto de software educacional (necessários num trabalho desta natureza), esta tese está inserida no contexto da pesquisa em agentes cognitivos modelados através de seus estados mentais. É importante salientar que os estados mentais utilizados neste trabalho (crenças, desejos, intenções e expectativas) funcionam como uma metáfora dos estudos mentais humanos. Por exemplo, quando se coloca a crença de um aluno a respeito de "lago", na realidade está se colocando a crença que temos a respeito da crença que o aluno possui a respeito de "lago". O mesmo acontece com os outros estados mentais aqui utilizados. Os diálogos reais foram registrados através de observação direta e posteriormente analisados a fim de se identificar os estados mentais relacionados. Perguntas adicionais foram feitas no sentido de obterem-se mais elementos para auxiliar na inferência do conjunto de estados mentais que o aluno possui naquele momento em que estava jogando. Após a observação de vários alunos jogando, identificou-se um certo padrão nas suas atitudes quando executavam uma ação. Observações sucessivas permitiram delinear o conjunto de estados mentais associados à ação do aluno. Tal conjunto foi utilizado como base para elaboração da coreografia. Estes dados servem de entrada para a construção do modelo do aluno mediante a interação com o tutor. No presente trabalho, nós apresentamos a modelagem de um STI através do uso da tecnologia de agentes utilizando a arquitetura de SMA (Sistemas Multiagentes). O STI é concebido como um SMA híbrido composto por um ambiente reativo (SMAR - Sistema Multiagente Reativo) e um "kernel" cognitivo (SMAC - Sistema Multiagente Cognitivo). O SMAR e o SMAC interagem entre si de para ampliar as informações quantitativas e qualitativas oferecidas aos alunos que utilizam o sistema. Estas informações disponíveis é que irão permitir ao tutor selecionar estratégias de ensino mais adequadas a um determinado tipo de aluno. A principal contribuição desta tese está centrada no "kernel" cognitivo. Nós propomos uma arquitetura para o tutor que permitirá a monitoração de dois alunos trabalhando conjuntamente. Além disso, propomos uma forma de selecionar o comportamento do tutor para oferecer auxílio personalizado aos alunos considerando o perfil de cada um. Esta arquitetura pretende ser uma alternativa de solução para uma questão importante na área de STI: Como o tutor pode selecionar, entre várias estratégias de ensino, a mais adequada para cada perfil de aluno? O grupo de pesquisa no qual este trabalho está inserido (GIA/UFRGS, sob orientação da Prof.a. Rosa Maria Viccari) tem realizado algumas avaliações experimentais, usando STI tradicionais e STI projetados e modelados através de sistemas multiagentes As contribuições científicas listadas no texto deste trabalho possibilitaram que o grupo avançasse sua pesquisa na abordagem mentalística através da criação de uma arquitetura para o tutor e favorecesse a integração do trabalho desenvolvido por Móra et al. [MOR97; MOR98]. A utilização do modelo computacional de agentes criado por Móra et al. gerou a implementação do "kernel" cognitivo. Os desafios inerentes a implementação da arquitetura proposta para o tutor ampliaram as características do ambiente criado por Móra et al. e favorecem a junção de dois trabalhos de tese supervisionados pela mesma orientadora [MOR99]. Portanto, a nova arquitetura proporcionou ganhos tanto para tais pesquisas, como para o avanço das pesquisas desenvolvidas pelo nosso grupo. / The present thesis has been elaborated within the AI (Artificial Intelligence) applied to Education realm, and it brings specific contributions to the STI (Intelligent Tutoring System) area. The use of AI techniques has been investigated by researchers of Computer Science applied to Education, due to its potentialities to improve educational systems. The agents' techniques used in the design of STI allow us to solve old problems opened in the area. For instance, the improvement of the interaction between tutor and student, and the possibility of tracing the mental processes in a more stratified way. The architecture described in this thesis uses the methodology applied to the modern STI projects: multiple strategies for the tutor (i.e., teaching strategies and associated tactics). This approach considers different forms of working with a certain piece of knowledge, and is taken into consideration to create the user profile, as well as to monitor the student interaction with the system. The architecture, designed according to a constructivist approach, expects the tutor to be less directive, and less controller of the student's actions. The control is made by an observation of students' actions by the tutor. The tutor works either as a student's partner or as a facilitator. However, due to the characteristics of the modality chosen for construction of the prototype (educational game), we needed to take some attitudes in the tutor in order to avoid the system to collapse. What would make unfeasible the student's work. In these critical situations, the tutor will behave in more directive way. It fits to point out that the construtivist approach does not mean to give total freedom to the student or to deprive it of any kind of attendance. Therefore, what should be note here is the degree of the tutor's interference, i.e., how it interferes with the student's work using its own set of heuristics. Besides these educational aspects, inherent to a project of Educational software, this thesis is inserted in the context of the research in cognitive agents modelled through their mental states (Believe, Desire, Intention, and Expectation). It is important to point out that the mental states used in this work are as a metaphor of the human mental states. For example, when the student's has a believe regarding "lake", in fact we area talking about belief that we have regarding the belief that the student possesses regarding about "lake". The same happens here with the other mental states used. The real dialogues were registered through direct observation in real situation (students playing with the game). They were analysed in order to identify the mental states connected with the student's actions. Additional questions were asked to obtain more elements to aid us to inference the group of mental states possessed by the student when he/she was playing. Successive observations allowed us to delineate the group of mental states associated to the student's action. Such group was used as a base for the choreography. These data were used as input for the construction to the student's model during the interaction with the tutor. In this work, we have presented the design of an STI with the use of architecture of MAS (Multi-agent System Architecture). The ITS is conceived as a hybrid MAS composed by a RMAS (Reactive Multi-agent System) and a "cognitive kernel" using the CMAS (Cognitive Multi-agent System). The RMAS and the CMAS interact with each other to enlarge the quantitative and qualitative information offered to the students that uses the system. These available information allow the tutor to select teaching strategies more adapted to a certain student type. The main contribution of this thesis is centred in the "cognitive kernel". We propose an architecture for the tutor that will allow the two students to work together. Besides, we propose a way to select the tutor behaviour in order to aid the students considering their personal profile. This architecture intends to be an alternative solution for an important question in ITS research: How can the tutor select, among several teaching strategies, the one that is more suitable for each student profile? The research group in which this work is placed (GIA/UFRGS - Artificial Intelligence Group), under the supervision of Profa. Rosa Maria Viccari, has been doing executing some experimental evaluations, using traditional ITS and ITS modelled through multi-agents systems techniques. The scientific contributions listed in this work allow the group to achive some interesting results in the research of STI using a mental approach. The tutor architecture favoured the integration of the X-BDI (eXecutable Belief Desire, and Intention model)) developed by Móra et al. The use the X-BDI allowed us to implement the "cognitive kernel". The inherent challenges posed by the implementation of the architecture of the tutor refined the XBDI environment. It favours the junction of two thesis works supervised done under the same supervisor[MOR99]. Therefore, the new architecture provided many gains for both researches, as well as for the progress of the research developed by our group.

Agrupamento de dados é o processo que consiste em dividir um conjunto de dados em grupos de forma que dados semelhantes entre si permaneçam no mesmo grupo enquanto que dados dissimilares sejam alocados em grupos diferentes. Técnicas tradicionais de agrupamento de dados têm sido usualmente desenvolvidas de maneira centralizada dependendo assim de estruturas que devem ser acessadas e modificadas a cada passo do processo de agrupamento. Além disso, os resultados gerados por tais métodos são dependentes de informações que devem ser fornecidas a priori como por exemplo número de grupos, tamanho do grupo ou densidade mínima/máxima permitida para o grupo. O presente trabalho visa propor o bee clustering, um algoritmo distribuído inspirado principalmente em técnicas de inteligência de enxames como organização de colônias de abelhas e alocação de tarefas em insetos sociais, desenvolvido com o objetivo de resolver o problema de agrupamento de dados sem a necessidade de pistas sobre o resultado desejado ou inicialização de parâmetros complexos. O bee clustering é capaz de formar grupos de agentes de maneira distribuída, uma necessidade típica em cenários de sistemas multiagente que exijam capacidade de auto-organização sem controle centralizado. Os resultados obtidos mostram que é possível atingir resultados comparáveis as abordagens centralizadas. / Clustering can be defined as a set of techniques that separate a data set into groups of similar objects. Data items within the same group are more similar than objects of different groups. Traditional clustering methods have been usually developed in a centralized fashion. One reason for this is that this form of clustering relies on data structures that must be accessed and modified at each step of the clustering process. Another issue with classical clustering methods is that they need some hints about the target clustering. These hints include for example the number of clusters, the expected cluster size, or the minimum density of clusters. In this work we propose a clustering algorithm that is inspired by swarm intelligence techniques such as the organization of bee colonies and task allocation among social insects. Our proposed algorithm is developed in a decentralized fashion without any initial information about number of classes, number of partitions, and size of partition, and without the need of complex parameters. The bee clustering algorithm is able to form groups of agents in a distributed way, a typical necessity in multiagent scenarios that require self-organization without central control. The performance of our algorithm shows that it is possible to achieve results that are comparable to those from centralized approaches.

Uma importante parte de um sistema multiagente é o seu mecanismo de coordenação que permite que os agentes possam agir de maneira coesa em direção aos seus objetivos, sejam eles individuais ou coletivos. Um agente pode optar por cooperar para atingir um determinado objetivo que seria inalcançável através de ações individuais, para realizar uma tarefa de maneira mais eficiente ou simplesmente porque ele foi projetado para tal. Em todos os casos, a formação de coalizões (grupos de agentes que concordam em coordenar suas ações em torno de um objetivo comum) é uma questão fundamental. O problema de geração de estruturas de coalizão entre agentes (conjunto de todas as combinações de coalizões) é um tópico de pesquisa que recebeu muita atenção principalmente na resolução do problema quando considerado como um jogo de função característica, onde o valor das coalizões independe dos agentes que não estão presentes nela. Essa abordagem, apesar de ser indicada para muitos tipos de problema, não cobre toda a área de pesquisa do assunto, visto que em muitos casos a criação de uma coalizão irá afetar os demais agentes do sistema. Quando o sistema possui agentes com objetivos sobrepostos ou contrários, uma coalizão cujos recursos são destinados a completar tais objetivos irá influenciar as demais coalizões desse sistema. Essa influência se chama externalidade e, nesses casos, o problema de formação de estruturas de coalizão deve ser tratado como um jogo de partição. Apesar das pesquisas na área de jogos de partição serem recentes, elas trazem resultados promissores e há alguns poucos algoritmos já desenvolvidos para buscar soluções a esse problema. A busca pela melhor estrutura de coalizão geralmente demanda que seja calculado o valor de todas possíveis coalizões, a fim de se encontrar aquele conjunto cuja soma dos valores das coalizões forneça o melhor resultado. Esse processo requer um alto número de computações e de memória, devido à natureza exponencial do problema. Assim, ao invés de apenas um agente central realizar todas as operações, é mais eficiente do ponto de vista do uso de recursos computacionais distribuir essas operações entres os diversos agentes presentes no sistema. Além dos benefícios computacionais, distribuir o processo de busca pela melhor estrutura de coalizão permitiria trabalhar com questões como privacidade e tolerância a falhas, tendo em vista que as informações não estão concentradas em um único agente. Apesar disso, não há na literatura qualquer algoritmo capaz de solucionar o problema de geração de estrutura de coalizão em ambientes distribuídos e que sejam modelados como jogos de partição. A proposta desse trabalho é utilizar a fundamentação teórica existente acerca do problema de formação de estruturas de coalizão (modelados tanto como jogos de função característica quanto como jogos de partição) para criar um algoritmo distribuído capaz de encontrar a estrutura de coalizão ótima em ambientes que possuam externalidade. Esse algoritmo utiliza como base a ordenação das coalizões e dos agentes para permitir a distribuição do cálculo dos limites superiores e inferiores de cada coalizão. Após, esses valores são utilizados para se encontrar o subespaço mais provável de conter a estrutura de coalizão ótima. Com base nos experimentos, percebe-se que o algoritmo encontrou a estrutura de coalizão ótima buscando em apenas uma pequena parte do espaço de busca. Para os experimentos com 16 agentes, o algoritmo foi capaz de encontrar a solução ótima procurando em apenas 0,01% do espaço de busca. Também, é demonstrado que em cenários com externalidade negativa os agentes necessitaram investigar um espaço de busca menor para encontrar a estrutura de coalizão ótima que em cenários com externalidade positiva. Experimentos também demonstram que o algoritmo não consegue encontrar a estrutura de coalizão ótima quando há falhas na comunicação entre os agentes. / An important part of a multi-agent system is its coordination mechanism that allows the agents to act cohesively towards their goals, whether individual or collective. An agent can choose to cooperate to achieve a certain goal that would be unattainable through individual actions, to perform a task more efficiently or simply because it was designed to do so. In all cases, the formation of coalitions (group of agents that agree to coordinate their actions around a common goal) is a key issue. The problem of generating coalition structures between agents (set of all combinations of coalitions) is a research topic that has received much attention mostly on solving the problem when considered as a characteristic function game, where the value of coalitions is independent of agents that are not part of it. This approach, although suitable for many types of problem, does not cover the whole area of research on the subject, since in many cases the creation of a coalition will affect the other agents of the system. When the system has agents with overlapping goals or opposing goals, a coalition whose resources are devoted to completing these objectives will influence the other coalitions of that system. This influence is called externality, and in these cases, the problem of formation of coalition structures should be treated as a partition function game. Although research in the area of partition games is recent, it brings promising results and there are few algorithms already developed to find solutions to this problem. The search for the best coalition structure generally requires computation of the value of all possible coalitions in order to find the set that the sum of the values of the coalitions provides the best result. This process requires a large number of computations and memory due to the exponential nature of the problem. Hence, instead of just one central agent performing all operations, it is more efficient to distribute those operations among several agents. Besides the computational benefits, distributing the search process for the best coalition structure would address issues such as privacy and fault tolerance, given that the information is not concentrated in a single agent. Nevertheless, in the literature there is not algorithm capable of solving the problem of coalition structure generation in decentralized environments and modeled as partition function game. The purpose of this work is to use the existing theoretical foundations for solving the coalition structure generation problem (modeled both as a characteristic function game and as a partition function game) to create a distributed algorithm capable of finding the optimal coalition structure in environments that have externality. This algorithm uses as a base the ordering of coalitions and agents to distribute the calculation of the upper and lower limits for each coalition. Afterwards, these values are used to find the subspace more likely to contain the optimal coalition structure. Based on experiments, the algorithm found the optimal coalition structure searching only a small part of the search space. For the experiments with 16 agents, the algorithm was able to find the solution looking at just 0.0001%of the search space. Also, it is shown that in scenarios with negative externality agents need to investigate a smaller search space to find the optimal coalition structure than in scenarios with positive externality. Experiments also show that the algorithm can not find the optimal coalition structure when there are failures in the communication among the agents.