In nature animal species often exist in groups. We talk of insect swarms, flocks of birds, packs of lions, herds of wildebeest etc. These are characterised by individuals interacting by following their own rules, privy only to local information. Robotic swarms or simulations can be used explore such interactions. Mathematical formulations can be constructed that encode similar ideas and allow us to explore the emergent group behaviours. Some behaviours show characteristics reminiscent of the phenomena of criticality. A bird flock may show near instantaneous collective shifts in direction: velocity changes that appear to correlated over distances much larger individual separations. Here we examine swarm systems inspired by flocks of birds and the role played by criticality. The first system, Particle Swarm Optimisation (PSO), is shown to behave optimally when operating close to criticality. The presence of a critical point in the algorithm’s operation is shown to derive from the swarm’s properties as a random dynamical system. Empirical results demonstrate that the optimality lies on or near this point. A modified PSO algorithm is presented which uses measures of the swarm’s diversity as a feedback signal to adjust the behaviour of the swarm. This achieves a statistically balanced mixture of exploration and exploitation behaviours in the resultant swarm. The problems of stagnation and parameter tuning often encountered in PSO are automatically avoided. The second system, Swarm Chemistry, consists of heterogeneous particles combined with kinetic update rules. It is known that, depending upon the parametric configuration, numerous structures visually reminiscent of biological forms are found in this system. The parameter set discovered here results in a cell-division-like behaviour (in the sense of prokaryotic fission). Extensions to the swarm system produces a swarm that shows repeated cell division. As such, this model demonstrates a behaviour of interest to theories regarding the origin of life.

In swarm robotics, the control of a group of robots is often fully distributed and does not rely on any leader. In this thesis, we are interested in understanding how to design collective decision making processes in such groups. Our approach consists in taking inspiration from nature, and especially from self organization in social insects, in order to produce effective collective behaviors in robot swarms. We have devised four robotics experiments that allow us to study multiple facets of collective decision making. The problems on which we focus include cooperative transport of objects, robot localization, resource selection, and resource discrimination. <p><p>We study how information is transferred inside the groups, how collective decisions arise, and through which particular interactions. Important properties of the groups such as scalability, robustness, and adaptivity are also investigated. We show that collective decisions in robot swarms can effectively arise thanks to simple mechanisms of imitation and amplification. We experimentally demonstrate their implementation with direct or indirect information transfer, and with robots that can distinguish the available options partially or not at all. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

We investigate the use of self-assembly in a robotic system as a means of responding<p>to different environmental contingencies. Self-assembly is the mechanism through which<p>agents in a multi-robot system autonomously form connections with one another to create<p>larger composite robotic entities. Initially, we consider a simple response mechanism<p>that uses stochastic self-assembly without any explicit control over the resulting morphology<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

No description available.

<p>Swarm robotics and distributed control offer the promise of enhanced performance and robustness relative to that of individual and centrally-controlled robots, with decreased cost or time-to-completion for certain tasks. Having many degrees of freedom, swarm-related control and estimation problems are challenging specifically when the solutions depend on a great amount of communication among the robots. Swarm controllers minimizing communication requirements are quite desirable.</p><p>Swarms are inherently more robust to uncertainties and failures, including complete loss of individual agents, due to the averaging inherent in convergence and agreement problems. Exploitation of this robustness to minimize processing and communication complexity is desirable.</p><p>This research focuses on simple but robust controllers for swarming problems, maximizing the likelihood of objective success while minimizing controller complexity and specialized communication or sensing requirements.</p><p>In addition, it develops distributed solutions for swarm control by examining and exploiting graph theoretic constructs. Details of specific implementations, such as nonholonomic motion and and numerosity constraints, were explored with some unexpectedly positive results.</p><p>In summary, this research focused on the development of control strategies for the distributed control of a swarm of robots, and graph-theoretic analysis of these controllers. These control strategies specifically consider probabilistic connectivity functions, based on requirements for sensing or communication. The developed control strategies are validated in both simulation and experiment.</p> / Dissertation

Magíster en Ciencias, Mención Computación / Este trabajo de tesis está dedicado al diseño e implementación de algoritmos aproximados que permiten explorar las mejores soluciones para el problema de Clustering Balanceado, el cual consiste en dividir un conjunto de n puntos en k clusters tal que cada cluster tenga como m ́ınimo ⌊ n ⌋ puntos, k y éstos deben estar lo más cercano posible al centroide de cada cluster. Estudiamos los algoritmos existentes para este problema y nuestro análisis muestra que éstos podrían fallar en entregar un resultado óptimo por la ausencia de la evaluación de los resultados en cada iteración del algoritmo. Entonces, recurrimos al concepto de Particles Swarms, que fue introducido inicialmente para simular el comportamiento social humano y que permite explorar todas las posibles soluciones de manera que se aproximen a la óptima rápidamente. Proponemos cuatro algoritmos basado en Particle Swarm Optimization (PSO): PSO-Hu ́ngaro, PSO-Gale-Shapley, PSO-Aborci ́on-Punto-Cercano y PSO-Convex-Hull, que aprovechan la característica de la generación aleatoria de los centroides por el algoritmo PSO, para asignar los puntos a estos centroides, logrando una solución más aproximada a la óptima. Evaluamos estos cuatro algoritmos con conjuntos de datos distribuidos en forma uniforme y no uniforme. Se encontró que para los conjuntos de datos distribuidos no uniformemente, es impredecible determinar cuál de los cuatro algoritmos propuestos llegaría a tener un mejor resultado de acuerdo al conjunto de métricas (intra-cluster-distancia, índice Davies-Doublin e índice Dunn). Por eso, nos concentramos con profundidad en el comportamiento de ellos para los conjuntos de datos distribuidos en forma uniforme. Durante el proceso de evaluación se descubrió que la formación de los clusters balanceados de los algoritmos PSO-Absorcion-Puntos-Importantes y PSO-Convex-Hull depende fuertemente del orden con que los centroides comienzan a absorber los puntos más cercanos. En cambio, los algoritmos PSO-Hungaro y PSO-Gale-Shapley solamente dependen de los centroides generados y no del orden de los clusters a crear. Se pudo concluir que el algoritmo PSO-Gale-Shapley presenta el rendimiento menos bueno para la creación de clusters balanceados, mientras que el algoritmo PSO-Hungaro presenta el rendimiento más eficiente para lograr el resultado esperado. Éste último está limitado al tamaño de los datos y la forma de distribución. Se descubrió finalmente que, para los conjuntos de datos de tamaños grandes, independiente de la forma de distribución, el algoritmo PSO-Convex-Hull supera a los demás, entregando mejor resultado según las métricas usadas.

Inspired by nature, swarm robotics aims to increase system robustness while utilizing simple agents. In this work, we present a novel approach to achieve decentralized coordination of forces during collective manipulation tasks resulting in a highly scalable, versatile, and robust solution. In this approach, each robot involved in the collective object manipulation task relies on the behavior of a cooperative ``virtual teammate' in a fully decentralized architecture, regardless of the size and configuration of the real team. By regulating their actions with their corresponding virtual counterparts, robots achieve continuous pose control of the manipulated object, while eliminating the need for inter-agent communication or a leader-follower architecture. To experimentally study the scalability, versatility, and robustness of the proposed collective object manipulation algorithm, a new swarm agent, Δρ is introduced which is able to apply linear forces in any planar direction. Efficiency and effectiveness of the proposed decentralized algorithm are investigated by quantitative performance metrics of settling time, steady-state error, path efficiency, and object velocity profiles in comparison with a force-optimal centralized version that requires complete information. Employing impedance control during manipulation of an object provides a mean to control its dynamic interactions with the environment. The proposed decentralized algorithm is extended to achieve a desired multi-dimensional impedance behavior of the object during a collective manipulation without inter-agent communication. The proposed algorithm extension is built upon the concept of ``virtual coordination' which demands every agent to locally coordinate with one virtual teammate. Since the real population of the team is unknown to the agents, the resultant force applied to the manipulated object would be directly scaled with the team population. Although this scaling effect proves useful during position control of the object, it leads to a deviation from the desired dynamic response when employed in an impedance control scheme. To minimize such deviations, a gradient descent algorithm is implemented to determine a scaling parameter defined on the control action. The simulation results of a multi-robot system with different populations and formations verify the effectiveness of the proposed method in both generating the desired impedance response and estimating the population of the group. Eventually, as two case studies, the introduced algorithm is used in robotic collective manipulation and human- assistance scenarios. Simulation and experimental results indicate that the proposed decentralized communication- free algorithm successfully performs collective manipulation in all tested scenarios, and matches the performance of the centralized controller for increasing number of agents, demonstrating its utility in communication- limited systems, remote environments, and access-limited objects.

Robot swarms are often considered suitable for tasks that are large-scale and long-term. Large-scale missions force the robots to spread spatially. In these type of tasks, actively maintaining connectivity allows the swarm to coordinate. Similarly, long-term nature of the task requires robots to work for a long time. This is affected by the limited energy level of the robot. However current studies normally focus only on connectivity or energy awareness. Therefore, in this work, we propose an approach to tackle the problem of maintaining global connectivity (swarm-level property) considering finite battery life (individual property). We are specifically focusing on growing the communication network and keeping it alive for a long period. We construct a logical tree over the connectivity graph. The logical tree is constructed by using a subset of robots from the swarm. The tree is grown by adding robots as necessary. The tree is also periodically reconfigured to cope with dynamic robot motion. This enables the swarm to grow the tree efficiently. In addition, robots exchange their roles based on their available energy levels. This allows robots with low energy levels to navigate to dedicated charging stations for recharging thus allowing the swarm to maintain the communication network. We evaluate our approach in a wide set of experiments with a realistic robot simulator named ARGoS.

Human-swarm interaction is an important milestone for the introduction of swarm-intelligence based solutions into real application scenarios. One of the main hurdles towards this goal is the creation of suitable interfaces for humans to convey the correct intent to multiple robots. As the size of the swarm increases, the complexity of dealing with explicit commands for individual robots becomes intractable. This brings a great challenge for the developer or the operator to drive robots to finish even the most basic tasks. In our work, we consider a different approach that humans specify only the desired goal rather than issuing individual commands necessary to obtain this task. We explore this approach in a collaborative transport scenario, where the user chooses the target position of an object, and a group of robots moves it by adapting themselves to the environment. The main outcome of this thesis is the design of integration of a collaborative transport behavior of swarm robots and an augmented reality human interface. We implemented an augmented reality (AR) application in which a virtual object is displayed overlapped on a detected target object. Users can manipulate the virtual object to generate the goal configuration for the object. The designed centralized controller translate the goal position to the robots and synchronize the state transitions. The whole system is tested on Khepera IV robots through the integration of Vicon system and ARGoS simulator.

Thesis (M.S.)--Baylor University, 2005.