Swarm robotics is the study of developing and controlling large groups of robots. Collectives of robots possess advantages over single robots such as being robust to mission failures due to single-robot errors. Experimental research in swarm robotics is currently limited by swarm robotic technology. Current swarm robotic systems are either small groups of sophisticated robots or large groups of simple robots due to manufacturing overhead, functionality-cost dependencies, and their need to avoid collisions, amongst others. It is therefore useful to develop a swarm robotic system that is easy to manufacture, that utilises its sensors beyond standard usage, and that allows for physical interactions. In this work, I introduce a new type of low-friction locomotion and show its first implementation in the HoverBot system. The HoverBot system consists of an air-levitation and magnet table, and a HoverBot agent. HoverBots are levitating circuit boards which are equipped with an array of planar coils and a Hall-effect sensor. HoverBot uses its coils to pull itself towards magnetic anchors that are embedded into a levitation table. These robots consist of a Printed Circuit Board (PCB), surface mount components, and a battery. HoverBots are easily manufacturable, robots can be ordered populated; the assembly consists of plugging in a battery to a robot. I demonstrate how HoverBot's low-cost hardware can be used beyond its standard functionality. HoverBot's magnetic field readouts from its Hall-effect sensor can be associated with successful movement, robot rotation and collision measurands. I build a time series classifier based on these magnetic field readouts, I modify and apply signal processing techniques to enable the online classification of the time-variant magnetic field measurements on HoverBot's low-cost microcontroller. This method allows HoverBot to detect rotations, successful movements, and collisions by utilising readouts from its single Hall-effect sensor. I discuss how this classification method could be applied to other sensors and demonstrate how HoverBots can utilise their classifier to create an occupancy grid map. HoverBots use their multi-functional sensing capabilities to determine whether they moved successfully or collided with a static object to map their environment. HoverBots execute an "explore-and-return-to-nest" strategy to deal with their sensor and locomotion noise. Each robot is assigned to a nest (landmark); robots leave their nests, move n steps, return and share their observations. Over time, a group of four HoverBots collectively builds a probabilistic belief over its environment. In summary, I build manufacturable swarm robots that detect collisions through a time series classifier and map their environment by colliding with their surroundings. My work on swarm robotic technology pushes swarm robotics research towards studies on collision-dependent behaviours, a research niche that has been barely studied. Collision events occur more often in dense areas and/or large groups, circumstances that swarm robots experience. Large groups of robots with collision-dependent behaviours could become a research tool to help invent and test novel distributed algorithms, to understand the dependencies between local to global (emergent) behaviours and more generally the science of complex systems. Such studies could become tremendously useful for the execution of large-scale swarm applications such as the search and rescue of survivors after a natural disaster.

<p>The Ph.D. thesis addresses a comprehensive study of the bee colony<br />optimization meta-heuristic method (BCO). Theoretical analysis of the<br />method is conducted with the tools of probability theory. Necessary and<br />sufficient conditions are presented that establish convergence of the BCO<br />method towards an optimal solution. Three parallelization strategies and five<br />corresponding implementations are proposed for BCO for distributed-memory<br />systems. The influence of method&rsquo;s parameters on the performance of the<br />BCO algorithm for two combinatorial optimization problems is analyzed<br />through the experimental study.</p> / <p>Докторска дисертације се бави испитивањем метахеуристичке методе<br />оптимизације колонијом пчела. Извршена је теоријска анализа<br />асимптотске конвергенције методе посматрањем конвергенције низа<br />случајних променљивих. Установљени су довољни и потребни услови<br />за које метода конвергира ка оптималном решењу. Предложене су три<br />стратегије паралелизације и пет одговарајућих имплементација конст-<br />руктивне варијанте методе за рачунаре са дистрибуираном меморијом.<br />Извршено је експериментално испитивање утицаја параметара методе<br />на њене перформансе за два различита комбинаторна проблема:<br />проблем распоређивања и проблем задовољивости.</p> / <p>Doktorska disertacije se bavi ispitivanjem metaheurističke metode<br />optimizacije kolonijom pčela. Izvršena je teorijska analiza<br />asimptotske konvergencije metode posmatranjem konvergencije niza<br />slučajnih promenljivih. Ustanovljeni su dovoljni i potrebni uslovi<br />za koje metoda konvergira ka optimalnom rešenju. Predložene su tri<br />strategije paralelizacije i pet odgovarajućih implementacija konst-<br />ruktivne varijante metode za računare sa distribuiranom memorijom.<br />Izvršeno je eksperimentalno ispitivanje uticaja parametara metode<br />na njene performanse za dva različita kombinatorna problema:<br />problem raspoređivanja i problem zadovoljivosti.</p>

Worldwide concern about the environmental problems and a possible energy crisis has led to increasing interest in clean and renewable energy generation. Among various renewable energy sources, wind power is the most rapidly growing one. Therefore, how to provide efficient, reliable, and high-performance wind power generation and distribution has become an important and practical issue in the power industry. In addition, because of the new constraints placed by the environmental and economical factors, the trend of power system planning and operation is toward maximum utilization of the existing infrastructure with tight system operating and stability margins. This trend, together with the increased penetration of renewable energy sources, will bring new challenges to power system operation, control, stability and reliability which require innovative solutions. Flexible ac transmission system (FACTS) devices, through their fast, flexible, and effective control capability, provide one possible solution to these challenges. To fully utilize the capability of individual power system components, e.g., wind turbine generators (WTGs) and FACTS devices, their control systems must be suitably designed with high reliability. Moreover, in order to optimize local as well as system-wide performance and stability of the power system, real-time local and wide-area coordinated control is becoming an important issue. Power systems containing conventional synchronous generators, WTGs, and FACTS devices are large-scale, nonlinear, nonstationary, stochastic and complex systems distributed over large geographic areas. Traditional mathematical tools and system control techniques have limitations to control such complex systems to achieve an optimal performance. Intelligent and bio-inspired techniques, such as swarm intelligence, neural networks, and adaptive critic designs, are emerging as promising alternative technologies for power system control and performance optimization. This work focuses on the development of advanced optimization and intelligent control algorithms to improve the stability, reliability and dynamic performance of WTGs, FACTS devices, and the associated power networks. The proposed optimization and control algorithms are validated by simulation studies in PSCAD/EMTDC, experimental studies, or real-time implementations using Real Time Digital Simulation (RTDS) and TMS320C6701 Digital Signal Processor (DSP) Platform. Results show that they significantly improve electrical energy security, reliability and sustainability.

Le concept du « smart » envahit de plus en plus notre vie quotidienne. L’exemple type est sans doute le smartphone. Celui-ci est devenu au fil des ans un appareil incontournable. Bientôt, c’est la ville, la voiture, la maison qui seront « intelligentes ». L’intelligence se manifeste par une capacité d’interaction et de prise de décision entre l’environnement et l’utilisateur. Ceci nécessite des informations sur les changements d’états survenus des deux côtés. Les réseaux de capteurs permettent de collecter ces données, de leur appliquer des pré-traitements et de les transmettre aux applications. Ces réseaux de par certaines de leurs caractéristiques se rapprochent de l’intelligence collective, dans le sens, où des entités de faibles capacités se coordonnent automatiquement, sans intervention humaine, de façon décentralisée et distribuée pour accomplir des tâches complexes. Ces méthodes bio-inspirées ont servi à la résolution de plusieurs problèmes, surtout l’optimisation, ce qui nous a encouragé à étudier la possibilité de les utiliser pour les problèmes liés à l’Ambient Assisted Living ou AAL et à la classification automatique de données. L’AAL est un sous-domaine des services dits basés sur le contexte, et a pour objectifs de faciliter la vie des personnes âgées et handicapées dans leurs défis quotidiens. Pour ce faire, il détermine le contexte et, sur cette base, propose divers services. Deux éléments du contexte nous ont intéressé : le handicap et la position. Bien que la détermination de la position (localisation, positionnement) se fasse à l’extérieur des bâtiments avec des précisions très satisfaisantes, elle rencontre plusieurs difficultés à l’intérieur des bâtiments, liées à la propagation des ondes électromagnétiques dans les milieux difficiles, aux coûts des systèmes, à l’interopérabilité, etc. Nos travaux se sont intéressés au positionnement des personnes handicapées à l’intérieur de bâtiments en utilisant un réseau de capteurs afin de déterminer les caractéristiques de l’onde électromagnétique (puissance, temps, angle) pour estimer la position par méthodes géométriques (triangulation, latération), méthodes de fingerprinting (k plus proches voisins), par des filtres baysiens (filtre de Kalman). L’application est d’offrir des services types AAL tel que la navigation. Nous avons élargi la notion de réseau de capteurs pour prendre en compte tout appareil capable d’émettre et de recevoir une onde électromagnétique et se trouvant dans l’environnement. Nous avons aussi appliqué l’algorithme API sur la classification automatique de données. Enfin, nous avons proposé une architecture à middleware pour la localisation indoor. / The concept of « smart » invades more and more our daily life. A typical example is the smartphone, which becames by years an essential device. Soon, it’s the city, the car and the home which will become « smart ». The intelligence is manifested by the ability for the environment to interact and to take decisons in its relationships with users and other environments. This needs information on state changes occurred on both sides. Sensor networks allow to collect these data, to apply on them some pre-processings and to transmit them. Sensor network, towards some of their caracteristics are closed to Swarm Intelligence in the sense that small entities with reduced capababilities can cooperate automatically, in unattended, decentralised and distributed manner in order to accomplish complex tasks. These bio-inspired methods have served as basis for the resolution of many problems, mostly optimization and this insipired us to apply them on problems met in Ambient Assisted Living and on the data clustering problem. AAL is a sub-field of context-aware services, and its goals are to facilitate the everyday life of elderly and disable people. These systems determine the context and then propose different kind of services. We have used two important elements of the context : the position and the disabilty. Although positioning has very good precision outdoor, it faces many challenges in indoor environments due to the electromagnetic wave propagation in harsh conditions, the cost of systems, interoperabilty, etc. Our works have been involved in positioning disabled people in indoor environment by using wireless sensor network for determining the caracteristics of the electromagnetic wave (signal strenght, time, angle) for estimating the position by geometric methods (triangulation, lateration), fingerprinting methods (k-nearest neighbours), baysiens filters (Kalman filter). The application is to offer AAL services like navigation. Therefore we extend the definition of sensor node to take into account any device, in the environment, capable of emiting and receiving a signal. Also, we have studied the possibility of using Pachycondylla Apicalis for data clustering and for indoor localization by casting this last problem as data clustering problem. Finally we have proposed a system based on a middleware architecture.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto. / Many applications of Swarm Robotic Systems (SRSs) require that a robot is able to discover its position. The location information of the robots is required, for example, to allow them to be correctly positioned within a predefined swarm formation. Similarly, when the robots act as mobile sensors, the position information is needed to allow the identification of the location of the measured events. Due to the size, cost and energy source restrictions of these devices, or even limitations imposed by the operating environment, the straightforward solution, i.e. the use of a Global Positioning System (GPS), is often not feasible. The method proposed in this work allows the estimation of the absolute positions of a set of unknown nodes, based on the coordinates of a set of reference nodes and the distances measured between nodes. The solution is achieved by means of a distributed processing strategy, where each unknown node estimates its own position and helps its neighbors to compute their respective coordinates. The solution makes use of a new method called Multi-hop Collaborative Min-Max Localization (MCMM), herein proposed, aiming to improve the quality of the initial positions estimated by the unknown nodes in case of failure during the recognition of the reference nodes. The positions refinement is achieved based on the Backtracking Search Optimization Algorithm (BSA) and the Particle Swarm Optimization (PSO), whose performances are compared. To compose the objective function, a new method to compute the confidence factor of the network nodes is introduced, the Min-max Area Confidence Factor (MMA-CF), which is compared with the existing Hops to Anchor Confidence Factor (HTA-CF). Based on the proposed localization method, four algorithms were developed and further evaluated through a set of simulations in MATLABr and experiments in swarms of type Kilobot robots. The performance of the algorithms is evaluated on problems with different topologies, quantities of nodes and proportion of reference nodes. The performance of the algorithms is also compared with the performance of other localization algorithms, showing improvements between 40% to 51%. The simulations and experiments outcomes demonstrate the effectiveness of the proposed method.

Petrobras / A inspeção radiográfica de juntas soldadas de tubulações é a atividade minuciosa e cuidadosa de observar imagens radiográficas de juntas soldadas em busca de pequenos defeitos e descontinuidades que possam comprometer a resistência mecânica dessas juntas. Como toda atividade que requer atenção constante, a inspeção radiográfica está sujeita a erros principalmente devido a fadiga visual e distrações naturais devido a repetitividade e monotonia inerentes à essa atividade. No presente trabalho, apresentam-se duas metodologias que têm por objetivo o auxílio e a automação da atividade de inspeção: a detecção automática dos cordões de solda nas radiografias e o realce das descontinuidades; compondo entre outras funcionalidades, um aplicativo completo de auxílio na inspeção radiográfica que agrega ainda a possibilidade de automação do processamento dessas imagens através da construção de rotinas e sua posterior aplicação a um conjunto de imagens semelhantes. Os resultados obtidos na detecção automática do cordão de solda são promissores, sendo possível, através da metodologia proposta, detectar cordões provenientes diferentes técnicas de ensaios radiográficos usuais. Quanto aos resultados do realce das descontinuidades, apesar de estes ainda não levarem a uma inspeção completamente autônoma e não supervisionada, apresentam resultados melhores do que aqueles existentes atualmente na literatura, principalmente quanto a correlação entre contraste visual do resultado do realce e a probabilidade de ocorrência de descontinuidades nas regiões demarcadas. Por fim, o realce das descontinuidades em conjunto com um aplicativo completo e iterativo contribui para uma maior leveza na atividade de inspeção, com o que se espera uma expressiva redução das taxas de erro devido à fadiga visual e um aumento considerável da produtividade através da automação das rotinas mais repetitivas de processamento digital a que as imagens radiográficas são submetidas durante sua inspeção. / The weld bead radiographic inspection is the activity of meticulously observe a radiographic image looking for small defects and discontinuities in the welded joints that can compromise the mechanical resistance of that joints. As any other activity than requires constant attention, the weld bead inspection is error prone due to visual fatigue, repetition and others distractions inherent to these activity. In this work, two new methodologies for help in the inspection activities are presented: the automatic detection of the weld bead and the highlighting of the weld bead discontinuities. Those that, among others functionalities, are included in a complete software solution for help in the weld bead inspection. Including the feature of macro programing for automation of the most common image processing routines and further processing bath of images in an automatic way. The results from the automatic weld bead detection is beyond the satisfactory, detecting weld bead from all the usual radiographic techniques. About the results of the highlight of the discontinuities, although that are not suited for a complete non supervised weld bead inspection, their correlation among intensity and the probability of the presence of a discontinuity is very well suited for discontinuities highlighting, a helpful tool in weld bead inspection. In conclusion, the proposed methodologies. combined with a fully featured interactive software solution, a lot contribute for the weld bead inspection activity, a decreased error rate due to visual fatigue and a better overall performance due to the automation of the most common procedures involved in this activity.

A Inteligência de Enxame (Swarm Intelligence) é uma área de estudos que busca soluções para problemas de otimização utilizando-se de técnicas computacionais inspiradas no comportamento social emergente encontrado na biologia. A metaheurística Particle Swarm Optimization (PSO) é relativamente nova e foi inspirada no comportamento social de bandos de pássaros. PSO tem apresentado bons resultados em alguns trabalhos recentes de otimização discreta, apesar de ter sido concebido originalmente para a otimização de problemas contínuos. Este trabalho trata o Problema de Atribuição de Tarefas - Task Assignment Problem (TAP), e apresenta uma aplicação: o problema de alocação de táxis e clientes, cujo objetivo da otimização está em minimizar a distância percorrida pela frota. Primeiramente, o problema é resolvido em um cenário estático, com duas versões do PSO discreto: a primeira abordagem é baseada em codificação binária e a segunda utiliza permutações para codificar as soluções. Os resultados obtidos mostram que a segunda abordagem é superior à primeira em termos de qualidade das soluções e tempo computacional, e é capaz de encontrar as soluções ótimas para o problema nas instâncias para as quais os valores ótimos são conhecidos. A partir disto, o algoritmo é adaptado para a otimização do problema em um ambiente dinâmico, com a aplicação de diferentes estratégias de resposta às mudanças. Os novos resultados mostram que a combinação de algumas abordagens habilita o algoritmo PSO a obter boas soluções ao longo da ocorrência de mudanças nas variáveis de decisão problema, em todas as instâncias testadas, com diferentes tamanhos e escalas de mudança. / Swarm Intelligence searches for solutions to optimization problems using computational techniques inspired in the emerging social behavior found in biology. The metaheuristic Particle Swarm Optimization (PSO) is relatively new and can be considered a metaphor of bird flocks. PSO has shown good results in some recent works of discrete optimization, despite it has been originally designed for continuous optimization problems. This paper deals with the Task Assignment Problem (TAP), and presents an application: the optimization problem of allocation of taxis and customers, whose goal is to minimize the distance traveled by the fleet. The problem is solved in a static scenario with two versions of the discrete PSO: the first approach that is based on a binary codification and the second one which uses permutations to encode the solution. The obtained results show that the second approach is superior than the first one in terms of quality of the solutions and computational time, and it is capable of achieving the known optimal values in the tested instances of the problem. From this, the algorithm is adapted for the optimization of the problem in a dynamic environment, with the application of different strategies to respond to changes. The new results show that some combination of approaches enables the PSO algorithm to achieve good solutions along the occurrence of changes in decision variables problem, in all instances tested, with different sizes and scales of change.

Este trabalho insere-se na área de pesquisa de sistemas de transporte inteligente e mobilidade urbana buscando um cenário onde a infraestrutura rodoviária é capaz de monitorar um tráfego exclusivo de veículos inteligentes que não dependem de motoristas para serem guiados. A principal contribuição do trabalho é o desenvolvimento de uma solução matemática para otimizar o gerenciamento microscópico centralizado do tráfego de veículos inteligentes em trechos (segmentos) de rodovia. Para isto é apresentado um modelo de otimização baseado em Programação Linear Inteira Mista (MILP), que determina um plano ótimo de trajetórias individuais dos veículos em uma evolução de tráfego. O objetivo é reduzir o tempo de viagem individualmente e assegurar fluidez do tráfego. O modelo considera componentes essenciais do sistema dinâmico viário como topografia da pista, regras de trânsito e a curva de aceleração máxima de cada veículo. São contempladas várias situações de tráfego, tais como ultrapassagens, inclinação na pista, obstáculos e redutores de velocidade. Os resultados indicaram uma média de 20,5 segundos para o cálculo de um cenário com 6 veículos e 11 intervalos de tempo. Como o modelo MILP não tem solução em tempo computacional aceitável para aplicação real, também é proposto um algoritmo de simulação baseado em heurísticas o qual busca reduzir esse tempo de cálculo em detrimento da otimalidade da solução. O algoritmo reproduz o comportamento de um motorista que tenta manter sempre um valor de velocidade escolhido previamente, e por isso é forçado a ultrapassar outros veículos quando obstruído ao longo do trajeto. O resultado do algoritmo tem importância adicional, pois serve de referência para resolver o problema da prioridade nas ultrapassagens. Também são propostos novos indicadores para a avaliação microscópica de qualidade de tráfego. Finalmente, são apresentados resultados de testes em simulações a fim de avaliar e validar o modelo e o algoritmo. / This work focus on the research area of intelligent transportation systems and urban mobility. It considers a scenario where the roadside infrastructure is capable of monitoring traffic composed by 100% of intelligent vehicles that do not rely on drivers to be guided. The main contribution of this work is the development of a mathematical solution to optimize the centralized management of intelligent microscopic vehicular traffic in parts (segments) of highway. Therefore an optimization model based on Mixed Integer Linear Programming (MILP) is presented. The model determines individual trajectories plans of vehicles in a traffic evolution. The objective is to reduce the travel time individually and ensure traffic flow. The model considers essential components of the dynamic highway system, such as, topography of the lane, traffic rules and acceleration curve for each vehicle. Many traffic situations are considered, such as, overtaking, slopes, obstacles and speed reducers. The results indicated an average of 20.5 seconds to calculate a scenario with 6 vehicles and 11 time intervals. As the MILP model has no solution in acceptable computational time for real application, it is proposed an algorithm based on heuristic simulation which seeks to reduce the computation time at the expense of optimality of the solution. The algorithm reproduces the behavior of a driver who always tries to maintain a preselected velocity value, and is therefore forced to overtake other vehicles when blocked along the path. The result of the algorithm has additional importance because it serves as a reference for solving the problem of priority when overtaking. New indicators for microscopic evaluation of quality traffic are also proposed. Finally, test results are presented on simulations to evaluate and validate the model and algorithm.

Esta tese apresenta um novo protocolo de roteamento voltado para as Redes Tolerantes a Atrasos que exibem comportamentos complexos e dinâmicos. O protocolo proposto chama-se Cultural GrAnt (do inglês Cultural Greedy Ant) uma vez que este utiliza um sistema híbrido composto por um Algoritmo Cultural (AC) e uma versão gulosa da meta-heurística de Otimização por Colônia de Formigas (ACO). No Cultural GrAnt, o ACO representa o espaço populacional de um AC e utiliza uma regra de transição gulosa de modo a intensificar bons caminhos já encontrados ou explorar novos caminhos através da seleção, dentre um conjunto de candidatos, dos nós encaminhadores de mensagens mais promissores. A principal motivação para o uso do ACO é tirar proveito da sua busca baseada em população de indivíduos e da adaptação da sua estrutura de aprendizado. O AC obtém informações durante o processo evolucionário e as utiliza para guiar a população e, então, acelerar o aprendizado enquanto provê soluções mais eficientes. Considerando informações de funções heurísticas, concentração de feromônio e conhecimentos armazenados no espaço de crenças do AC, o protocolo Cultural GrAnt inclui três módulos: roteamento; escalonamento; e gerenciamento de buffer. Esse é o primeiro protocolo de roteamento que emprega ACO e AC de modo a: inferir os melhores encaminhadores de mensagens através de informações oportunistas sobre a conectividade social entre os nós; determinar os melhores caminhos que uma mensagem deve seguir para eventualmente alcançar o seu destino final, enquanto limita o número de replicações e descartes de mensagens na rede; determinar a ordem de escalonamento das mensagens; e gerenciar o espaço de armazenamento do buffer dos nós. O protocolo Cultural GrAnt é comparado com os protocolos Epidêmico e PROPHET em dois cenários de mobilidade distintos: um modelo de movimento baseado em atividades, onde simula-se o dia-a-dia de pessoas em suas atividades de trabalho, lazer e descanso; e um modelo de movimento baseado em comunidades de pessoas. Os resultados de simulações obtidos através do simulador ONE mostram que em ambos os cenários, o protocolo Cultural GrAnt alcança uma taxa mais alta de entrega de mensagens, uma replicação menor de mensagens e um número menor de mensagens descartadas se comparado com os protocolos Epidêmico e PROPHET. / This work presents a new routing protocol for complex and dynamic Delay Tolerant Networks (DTN). The proposed protocol is called Cultural GrAnt (Greedy Ant), as it uses a hybrid system composed of a Cultural Algorithm and a greedy version of the Ant Colony Optimization (ACO) metaheuristic. In Cultural GrAnt, ACO represents the population space of the cultural algorithm and uses a greedy transition rule to either exploit previously found good paths or explore new paths by selecting, among a set of candidates, the most promising message forwarders. The main motivation for using ACO is to take advantage of its population-based search and adaptive learning framework. Conversely, CA gathers information during the evolutionary process and uses it to guide the population and thus accelerate learning while providing more efficient solutions. Considering information from heuristic functions, pheromone concentration, and knowledge stored in the CA belief space, the Cultural GrAnt protocol includes three modules: routing, scheduling, and buffer management. To the best of our knowledge, this is the first routing protocol that employs both ACO and CA to infer the best message forwarders using opportunistic information about social connectivity between nodes, determine the best paths a message must follow to eventually reach its destination while limiting message replications and droppings, and perform message transmission scheduling and buffer space management. Cultural GrAnt is compared to the Epidemic and PROPHET protocols in two different mobility scenarios: an activity-based movement model, which simulates the daily lives of people in their work, leisure and rest activities; and a community-based movement model. Simulation results obtained by the ONE simulator show that, in both scenarios, Cultural GrAnt achieves a higher delivery ratio, lower message replication, and fewer dropped messages than Epidemic and PROPHET.

Fundação de Amparo à Pesquisa do Estado do Rio de Janeiro / Diversas das possíveis aplicações da robótica de enxame demandam que cada robô seja capaz de estimar a sua posição. A informação de localização dos robôs é necessária, por exemplo, para que cada elemento do enxame possa se posicionar dentro de uma formatura de robôs pré-definida. Da mesma forma, quando os robôs atuam como sensores móveis, a informação de posição é necessária para que seja possível identificar o local dos eventos medidos. Em virtude do tamanho, custo e energia dos dispositivos, bem como limitações impostas pelo ambiente de operação, a solução mais evidente, i.e. utilizar um Sistema de Posicionamento Global (GPS), torna-se muitas vezes inviável. O método proposto neste trabalho permite que as posições absolutas de um conjunto de nós desconhecidos sejam estimadas, com base nas coordenadas de um conjunto de nós de referência e nas medidas de distância tomadas entre os nós da rede. A solução é obtida por meio de uma estratégia de processamento distribuído, onde cada nó desconhecido estima sua própria posição e ajuda os seus vizinhos a calcular as suas respectivas coordenadas. A solução conta com um novo método denominado Multi-hop Collaborative Min-Max Localization (MCMM), ora proposto com o objetivo de melhorar a qualidade da posição inicial dos nós desconhecidos em caso de falhas durante o reconhecimento dos nós de referência. O refinamento das posições é feito com base nos algoritmos de busca por retrocesso (BSA) e de otimização por enxame de partículas (PSO), cujos desempenhos são comparados. Para compor a função objetivo, é introduzido um novo método para o cálculo do fator de confiança dos nós da rede, o Fator de Confiança pela Área Min-Max (MMA-CF), o qual é comparado com o Fator de Confiança por Saltos às Referências (HTA-CF), previamente existente. Com base no método de localização proposto, foram desenvolvidos quatro algoritmos, os quais são avaliados por meio de simulações realizadas no MATLABr e experimentos conduzidos em enxames de robôs do tipo Kilobot. O desempenho dos algoritmos é avaliado em problemas com diferentes topologias, quantidades de nós e proporção de nós de referência. O desempenho dos algoritmos é também comparado com o de outros algoritmos de localização, tendo apresentado resultados 40% a 51% melhores. Os resultados das simulações e dos experimentos demonstram a eficácia do método proposto. / Many applications of Swarm Robotic Systems (SRSs) require that a robot is able to discover its position. The location information of the robots is required, for example, to allow them to be correctly positioned within a predefined swarm formation. Similarly, when the robots act as mobile sensors, the position information is needed to allow the identification of the location of the measured events. Due to the size, cost and energy source restrictions of these devices, or even limitations imposed by the operating environment, the straightforward solution, i.e. the use of a Global Positioning System (GPS), is often not feasible. The method proposed in this work allows the estimation of the absolute positions of a set of unknown nodes, based on the coordinates of a set of reference nodes and the distances measured between nodes. The solution is achieved by means of a distributed processing strategy, where each unknown node estimates its own position and helps its neighbors to compute their respective coordinates. The solution makes use of a new method called Multi-hop Collaborative Min-Max Localization (MCMM), herein proposed, aiming to improve the quality of the initial positions estimated by the unknown nodes in case of failure during the recognition of the reference nodes. The positions refinement is achieved based on the Backtracking Search Optimization Algorithm (BSA) and the Particle Swarm Optimization (PSO), whose performances are compared. To compose the objective function, a new method to compute the confidence factor of the network nodes is introduced, the Min-max Area Confidence Factor (MMA-CF), which is compared with the existing Hops to Anchor Confidence Factor (HTA-CF). Based on the proposed localization method, four algorithms were developed and further evaluated through a set of simulations in MATLABr and experiments in swarms of type Kilobot robots. The performance of the algorithms is evaluated on problems with different topologies, quantities of nodes and proportion of reference nodes. The performance of the algorithms is also compared with the performance of other localization algorithms, showing improvements between 40% to 51%. The simulations and experiments outcomes demonstrate the effectiveness of the proposed method.