This thesis introduces a design combining an emerging area in robotics with a well established mathematical research topic: swarm intelligence and Voronoi tessellations, respectively. The main objective for this research is to design an economical and robust swarm system to achieve distributed control. This research combines swarm intelligence with Voronoi tessellations to localize a source and create formations. Extensive software coding must be implemented for this design, such as the development of a discrete centroidal Voronoi tessellation (CVT) algorithm. The ultimate purpose of this research is to advance the existing Mobile Actuator and Sensor Network (MASnet) platform to eventually develop a cooperative robot team that can sense, predict, and nally neutralize a diusion process. Previous work on the MASnet platform has served as a foundation for this research. While growing closer to the MASnet goal, results also provide stimulating discoveries for mathematical and swarm research areas.

Uma tendência crescente entre os pesquisadores da Robótica Móvel é a elaboração de sistemas robóticos descentralizados denominados enxames de robôs, nos quais a ação conjunta de cada agente leva à execução de tarefas de maneira mais robusta que quando realizada por um único robô. Um acréscimo adicional à robustez é conveniente em tais sistemas para que eles sejam de maior confiabilidade no mundo real. Neste trabalho, uma rede neural hierárquica desenvolvida para o aprendizado em tempo real inicialmente elaborada para o aprendizado de navegação de um único robô será estendida para controlar um enxame de robôs. O sistema realiza um balanceamento da influência de comportamentos implementados previamente em um robô de acordo com conhecimentos obtidos através da interação do mesmo com o ambiente. Cada robô possui sua própria rede neural, adquirindo seu conhecimento tanto independentemente quanto com o compartilhamento de informações com outros robôs. Espera-se que o uso de tal arquitetura permita uma adaptação mais rápida dos robôs ao ambiente, permitindo uma mudança em tempo real de seus parâmetros de acordo com as peculiaridades do ambiente no qual os robôs estão inseridos. A tarefa de escolta de um robô pelos demais é adotada para a avaliação de desempenho do modelo de rede neural proposto. Dois comportamentos são ponderados pela rede neural hierárquica: o de manutenção de uma distância preestabelecida a um agente e um outro de cobertura de área baseado em Diagramas Centroidais de Voronoi. Os testes foram feitos nos ambientes Player/Stage e indicam que a rede neural hierárquica torna os robôs capazes não apenas de aprender à medida que interagem com ambiente como de utilizar este conhecimento em tempo real para realizar a escolta de forma bem sucedida / A growing trend among Mobile Robotics researchers is developing robot swarms, in which a decentralized robot team solves tasks by combining simple behaviors. It is convenient to have mechanisms to increase a robot systems robustness. In this work, a neural network inspired in behavioral analysis is used to make robots from a swarm to learn how to act propoerly. This network combines two innate behaviors and, according to its experience, learns with the robots mistakes how to make this combination. Each robot has access to its own independent neural network, and can share its knowledge with neighboring robots. It is expected that such architecture learns by itself when to stimulate or supress each behaviors influence as it interacts with the environment. The task chosen to evaluate the proposed system is the escorting of a mobile agent. Two behaviors are balanced to achieve an escorting behavior: maintenance of a minimum distance between a robot and the escort target and an area coverage method based on Centroidal Voronoi Tessellations. Tests were meade using the Player/Stage simulator, and they show that the robots not only are capable of adapting themselves but also are able to use the stored knowledge to improve their effectiveness in doing the desired task

Cette thèse traite du problème de la tessellation volumétrique à partir des formes en trois dimensions, c’est-à-dire, étant donné une forme tridimensionnelle qui est habituellement représentée par sa surface au bord, comment subdiviser l’intérieur de la surface en formes plus petites, appelées cellules, de manière optimale selon plusieurs critères concernant l’exactitude, l’uniformité et la régularité. Nous considérons la tessellation de Voronoi centroidale qui est une approche efficace pour construire des tessellations volumétriques uniformes et régulières.Une tessellation de Voronoi centroidale (CVT) d’une forme peut être considérée comme une subdivision optimale avec les cellules dont les centres de masse, appelés centroides, sont répartis de manière optimale l’intérieur de la forme. CVTs ont été largement utilisés dans la vision par ordinateur et l’infographie en raison de leurs propriétés d’uniformité et de régularité qui sont indépendantes des variations de la forme. Cependant, les problèmes tels que comment évaluer la régularité d’une CVT et comment construire une CVT à partir des formes de types différents restent un défi.Nous proposons, comme contribution de cette thèse, que des critères de régularité basés sur des moments de second ordre normalisés des cellules. Ces critères de régularité permettent d’évaluer les tessellations volumétriques, et surtout, de comparer la régularité des différents CVTs sans l’hypothèse que leur forme et leur nombre de sites devraient être les mêmes. Nous proposons également une approche hiérarchique basée sur un schéma de subdivision qui préserve la régularité des cellules et l’optimalité locale des CVTs. Les résultats expérimentaux montrent que notre approche construit de manière plus efficace des CVTs plus régulières que les méthodes de l’état de l’art selon les critères de régularité.Une autre contribution est un nouvel algorithme de CVT pour les formes implicites et une comparaison approfondie entre l’algorithme Marching Cubes (MC), le raffinement de Delaunay et notre algorithme. L’idée clé de notre algorithme est l’utilisation des enveloppes convexes et l’amélioration locale pour construire des cellules au bord précises. Nous présentons une comparaison des trois algorithmes avec des critères différents, y compris la précision, la régularité et la complexité sur un grand nombre de données variantes. Les résultats montrent que MC est le plus rapide et que le notre construit les tessellations volumétriques les plus précises et les plus régulières.Nous explorons aussi les applications comme, par exemple, un framework d’animation des formes basées sur CVTs qui génère des animations plausibles avec une réelle dynamique. Le code source de l’ensemble des travaux de cette thèse est disponible en ligne dans le but de la recherche future. / This thesis addresses the problem of volumetric tessellations from three-dimensional shapes, i.e., given a three-dimensional shape that is usually represented by its boundary surface, how to optimally subdivide the interior of the surface into smaller shapes, called cells, according to several criteria concerning accuracy, uniformity and regularity. We consider centroidal Voronoi tessellation that is an effective approach for building uniform and regular volumetric tessellations.A centroidal Voronoi tessellation (CVT) of a shape can be viewed as an optimal subdivision with the cells whose centers of mass, called centroids, are optimally distributed inside the shape. CVTs have been widely used in computer vision and graphics because of their properties of uniformity and regularity that are immune to shape variations. However, the problems such as how to evaluate the regularity of a CVT and how to build a CVT from different types of shapes remain a challenge.One contribution of this thesis is that we propose regularity criteria based on the normalized second order moments of the cells. These regularity criteria allow evaluating volumetric tessellations and specially comparing the regularity of different CVTs without the assumption that their shape and number of sites should be the same. Meanwhile, we propose a hierarchical approach based on a subdivision scheme that preserves cell regularity and the local optimality of CVTs. Experimental results show that our approach performs more efficiently and builds more regular CVTs according to the regularity criteria than state-of-the-art methods.Another contribution is a novel CVT algorithm for implicit shapes and an extensive comparison of Marching Cubes, Delaunay refinement and our algorithm. The key of our algorithm is using convex hulls and the local improvement to build accurate boundary cells. We present a comparison of these three algorithms with different criteria including accuracy, regularity and complexity on a large number of variant data. The results show that Marching Cubes is the fastest one and our algorithm build more accurate and regular volumetric tessellations than the others.We also explore the applications such as a shape animation framework based on CVTs that generates plausible animations with real dynamics. And the source code of the whole work of this thesis is available online for the purpose of further research.

Uma tendência crescente entre os pesquisadores da Robótica Móvel é a elaboração de sistemas robóticos descentralizados denominados enxames de robôs, nos quais a ação conjunta de cada agente leva à execução de tarefas de maneira mais robusta que quando realizada por um único robô. Um acréscimo adicional à robustez é conveniente em tais sistemas para que eles sejam de maior confiabilidade no mundo real. Neste trabalho, uma rede neural hierárquica desenvolvida para o aprendizado em tempo real inicialmente elaborada para o aprendizado de navegação de um único robô será estendida para controlar um enxame de robôs. O sistema realiza um balanceamento da influência de comportamentos implementados previamente em um robô de acordo com conhecimentos obtidos através da interação do mesmo com o ambiente. Cada robô possui sua própria rede neural, adquirindo seu conhecimento tanto independentemente quanto com o compartilhamento de informações com outros robôs. Espera-se que o uso de tal arquitetura permita uma adaptação mais rápida dos robôs ao ambiente, permitindo uma mudança em tempo real de seus parâmetros de acordo com as peculiaridades do ambiente no qual os robôs estão inseridos. A tarefa de escolta de um robô pelos demais é adotada para a avaliação de desempenho do modelo de rede neural proposto. Dois comportamentos são ponderados pela rede neural hierárquica: o de manutenção de uma distância preestabelecida a um agente e um outro de cobertura de área baseado em Diagramas Centroidais de Voronoi. Os testes foram feitos nos ambientes Player/Stage e indicam que a rede neural hierárquica torna os robôs capazes não apenas de aprender à medida que interagem com ambiente como de utilizar este conhecimento em tempo real para realizar a escolta de forma bem sucedida / A growing trend among Mobile Robotics researchers is developing robot swarms, in which a decentralized robot team solves tasks by combining simple behaviors. It is convenient to have mechanisms to increase a robot systems robustness. In this work, a neural network inspired in behavioral analysis is used to make robots from a swarm to learn how to act propoerly. This network combines two innate behaviors and, according to its experience, learns with the robots mistakes how to make this combination. Each robot has access to its own independent neural network, and can share its knowledge with neighboring robots. It is expected that such architecture learns by itself when to stimulate or supress each behaviors influence as it interacts with the environment. The task chosen to evaluate the proposed system is the escorting of a mobile agent. Two behaviors are balanced to achieve an escorting behavior: maintenance of a minimum distance between a robot and the escort target and an area coverage method based on Centroidal Voronoi Tessellations. Tests were meade using the Player/Stage simulator, and they show that the robots not only are capable of adapting themselves but also are able to use the stored knowledge to improve their effectiveness in doing the desired task

This thesis is devoted to the problem of finding a suitable geometrical de- scription of the domain for the Finite Element Method (FEM). We present the most important methods used in generation and improvement of unstructured triangular meshes (grids) for two dimensional FEM. Possible measures of mesh quality are discussed with respect to their usage in linear Lagrange FEM. The relationship between mesh geometry (especially angles of particular triangles), discretization error and stiffness matrix condition number is examined. Two methods of mesh improvement, based on Centroidal Voronoi Tessellations (CVT) and Optimal Delaunay Triangulations (ODT), are discussed in detail and some results on convergence of CVT based methods are reviewed. Some aspects of these methods, e.g. the relation between density of boundary points and interior mesh vertices and the treatment of the boundary triangles is reconsidered in a new way. We have implemented these two methods and we discuss possible im- provements and new algorithms. A geometrically very interesting idea of recent alternative to FEM, Isogeometric Analysis (IGA), is outlined and demonstrated on a simple example. Several numerical tests are made in order to the compare the accuracy of solutions of isotropic PDEs obtained by FEM on bad mesh, mesh improved...