Research in swarm robotics focuses mostly on how robots interact and cooperate to perform tasks, rather than on the details of task execution. As a consequence, researchers often consider abstract tasks in their experimental work. For example, foraging is often studied without physically handling objects: the retrieval of an object from a source to a destination is abstracted into a trip between the two locations---no object is physically transported. Despite being commonly used, so far task abstraction has only been implemented in an ad hoc fashion.<p><p>In this dissertation, I propose a collection of tools for flexible and reproducible task abstraction. At the core of this collection is a physical device that serves as an abstraction of a single-robot task to be performed by an e-puck robot. I call this device the TAM, an acronym for "task abstraction module". A complex multi-robot task can be abstracted using a group of TAMs by first modeling the task as the set of its constituent single-robot subtasks and then representing each subtask with a TAM. I propose a novel approach to modeling complex tasks and a framework for controlling a group of TAMs such that the behavior of the group implements the model of the complex task.<p><p>The combination of the TAM, the modeling approach, and the control framework forms a collection of tools for conducting research in swarm robotics. These tools enable research on cooperative behaviors and complex tasks with simple, cost-effective robots such as the e-puck - research that would be difficult and costly to conduct using specialized robots or ad hoc solutions to task abstraction. I present proof-of-concept experiments and several studies that use the TAM for task abstraction in order to illustrate the variety of tasks that can be studied with the proposed tools.<p> / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

The goal of the research activities presented in this thesis is the design of intelligent behaviours for a complex robotic system, which is composed of a swarm of autonomous units. Inspired by the organisational skills of social insects, we are particularly interested in the study of collective behaviours based on self-organisation.<p><p>The problem of designing self-organising behaviours for a swarm of robots is tackled resorting to artificial evolution, which proceeds in a bottom-up direction by first defining the controllers at the individual level and then testing their effect at the collective level. In this way, it is possible to bypass the difficulties encountered in the decomposition of the global behaviour into individual ones, and the further encoding of the individual behaviours into the controllers' rules. In the experiments presented in this thesis, we show that this approach is viable, as it produces efficient individual controllers and robust self-organising behaviours. To the best of our knowledge, our experiments are the only example of evolved self-organising behaviours that are successfully tested on a physical robotic platform.<p><p>Besides the engineering value, the evolution of self-organising behaviours for a swarm of robots also provides a mean for the understanding of those biological processes that were a fundamental source of inspiration in the first place. In this perspective, the experiments presented in this thesis can be considered an interesting instance of a synthetic approach to the study of collective intelligence and, more in general, of Cognitive Science.<p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

Although traditionally Wireless Sensor Network (WSNs) have been regarded as static sensor arrays used mainly for environmental monitoring, recently, its applications have undergone a paradigm shift from static to more dynamic environments, where nodes are attached to moving objects, people or animals. Applications that use WSNs in motion are broad, ranging from transport and logistics to animal monitoring, health care and military. These application domains have a number of characteristics that challenge the algorithmic design of WSNs. Firstly, mobility has a negative effect on the quality of the wireless communication and the performance of networking protocols. Nevertheless, it has been shown that mobility can enhance the functionality of the network by exploiting the movement patterns of mobile objects. Secondly, the heterogeneity of devices in a WSN has to be taken into account for increasing the network performance and lifetime. Thirdly, the WSN services should ideally assist the user in an unobtrusive and transparent way. Fourthly, energy-efficiency and scalability are of primary importance to prevent the network performance degradation. This thesis contributes toward the design of a new hybrid optimization algorithm; ENAMS (Energy optimizatioN Algorithm for Mobile Sensor networks) which is based on the Evolutionary Computation and Swarm Intelligence to increase the life time of mobile wireless sensor networks. The presented algorithm is suitable for large scale mobile sensor networks and provides a robust and energy- efficient communication mechanism by dividing the sensor-nodes into clusters, where the number of clusters is not predefined and the sensors within each cluster are not necessary to be distributed in the same density. The presented algorithm enables the sensor nodes to move as swarms within the search space while keeping optimum distances between the sensors. To verify the objectives of the proposed algorithm, the LEGO-NXT MIND-STORMS robots are used to act as particles in a moving swarm keeping the optimum distances while tracking each other within the permitted distance range in the search space.

The field of swarm robotics has been growing fast over the last few years. Using a swarm of simple and cheap robots has advantages in various tasks. Apart from performance gains on tasks that allow for parallel execution, simple robots can also be smaller, enabling them to reach areas that can not be accessed by a larger, more complex robot. Their ability to cooperate means they can execute complex tasks while offering self-organised adaptation to changing environments and robustness due to redundancy. In order to keep individual robots simple, a control algorithm has to keep expensive communication to a minimum and has to be able to act on little information to keep the amount of sensors down. The number of sensors and actuators can be reduced even more when necessary capabilities are spread out over different agents that then combine them by cooperating. Self-organised differentiation within these heterogeneous groups has to take the individual abilities of agents into account to improve group performance. In this thesis it is shown that a homogeneous group of versatile agents can not be easily replaced by a heterogeneous group, by separating the abilities of the versatile agents into several specialists. It is shown that no composition of those specialists produces the same outcome as a homogeneous group on a clustering task. In the second part of this work, an adaptation mechanism for a group of foragers introduced by Labella et al. (2004) is analysed in more detail. It does not require communication and needs only the information on individual success or failure. The algorithm leads to self-organised regulation of group activity depending on object availability in the environment by adjusting resting times in a base. A possible variation of this algorithm is introduced which replaces the probabilistic mechanism with which agents determine to leave the base. It is demonstrated that a direct calculation of the resting times does not lead to differences in terms of differentiation and speed of adaptation. After investigating effects of different parameters on the system, it is shown that there is no efficiency increase in static environments with constant object density when using a homogeneous group of agents. Efficiency gains can nevertheless be achieved in dynamic environments. The algorithm was also reported to lead to higher activity of agents which have higher performance. It is shown that this leads to efficiency gains in heterogeneous groups in static and dynamic environments.

D.Phil. / A modern day N-P complete problem is the assigning of frequencies to transmitters in a cellular network in such a manner that, ideally, no two transmitters in the same cell or neighbouring cells use the same frequency. Considering that an average cellular network provider has over 29 000 transmitters and only 55 frequencies, choosing these frequencies in an optimal way is a very difficult computational problem. Swarm intelligence allows the acceptable minimization and optimization of the frequency assignment problem (FAP). Swarm intelligence is a concept modelling the processes in natural systems such as ant colonies, beehives, human immune systems and the human brain. These systems are selforganizational and display high efficiency in the execution of their tasks. A number of simple automated agents interacting with each other and the environment form a collective. Specifically, there is no "central agent" directing the others. A collective can display surprising intelligence which emerges out of the interaction of the individual agents. This collective intelligence, referred to as swarm intelligence, is displayed in ant colonies when ants build elaborate nests, regulate nest temperature and efficiently search for food in very complex environments. In this thesis a proposal is made to utilize swarm intelligence to build a swarm automatic frequency planner (swarm AFP). The swarm AFP produces frequency plans that are better, or on par with existing frequency planning tools, and in a fraction of the time. A swarm AFP is presented through an in-depth investigation into complex adaptive systems, agent architectures and emergence. Based on an understanding of these concepts, a swarm intelligence model called ACEUS is constructed. ACEUS forms the platform of the swarm AFP. It is a contribution to multi-agent technology as it is a new multi-agent framework that exhibits swarm intelligence and complex distributed computation. What differentiates ACEUS from other multi-agent technologies is that ACEUS works on the basis that the tasks or constructions that have been created by the agents actually guide the agents in their endeavours. There is no centralised agent controlling or guiding the process. The agents in ACEUS receive information and stimulation from their tasks or constructions in the environment. As these constructions or tasks alter the environment, the agents receive stimulus from the changing environment and then react to the changing environment. The changing environment acts as an emergent guiding force to the agents. This is the important contribution that stigmergy contributes to ACEUS. Utilizing this concept, ACEUS is used to create a swarm AFP. The swarm AFP is benchmarked against the COST 259 Siemens benchmarks. In all the COST 259 Siemens scenarios the swarm AFP produced the best results in the shortest time. The swarm AFP was also tested in a real cellular network and the resulting statistics before and after the swarm AFP implementation are presented.

This thesis investigates how collective decisions in bird flocks arise from simple rules, the factors that give some birds more influence over a flock's direction, and how travelling as a flock affects spatial learning. I used GPS loggers to track pigeons homing alone and in flocks, and applied mathematical modelling to explore the mechanisms underlying group decisions. Across several experiments, the key results were as follows: Flying home with a more experienced individual not only gave a pigeon an immediate advantage in terms of taking a more direct route, but the followers also learned homing routes just as accurately as pigeons flying alone. This shows that using social cues did not interfere with learning about the landscape during a series of paired flights. Pigeons that were faster during solo homing flights also tended to fly at the front of flocks, where they had more influence over the direction taken. Analysis of momentary interactions during paired flights and simulations of pair trajectories support the conclusion that speed increases the likelihood of leading. A pigeon's solo homing efficiency before flock flights did not correlate with leadership in flocks of ten, but leaders did have more efficient solo tracks when tested after a series of flock flights. A possible explanation is that leaders attended more to the landscape and therefore learned faster. Flocks took straighter routes than pigeons flying alone, as would be expected if they effectively pooled information. In addition, pigeons responded more strongly to the direction of several neighbours, during flock flights, than to a single neighbour during paired flights. This behaviour makes sense adaptively because social information will be more reliable when following several conspecifics compared to one. Through a combination of high-resolution tracking and mathematical modelling, this thesis sheds light on the mechanisms of flocking and its navigational consequences.

Title: Disruption of movement or cohesion of groups through individuals Author: Jiří Vejmola Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor of the master thesis: Mgr. Roman Neruda, CSc., Institute of Computer Science of the ASCR, v. v. i. Abstract: Just a few of informed and like-minded individuals, guides, are needed to lead otherwise naive group. We look at some of the possible changes that can be caused by the presence of another informed individual with different intentions, an intruder. It is implied that he cannot cause anything significant under normal circumstances. To counter that and to increase his chances of success we intruduce a new parameter - credibility. We explore how it changes the overall behaviour. We show that by applying it to the intruder his influence over others increases. This in turn makes naive individuals more willing to follow him. We show that if the right conditions are met he can eventually become the one who leads the group. Keywords: multi-agent system, swarm intelligence, emergence, credibility

This work deals with swarm intelligence, strictly speaking particle swarm intelligence. It shortly describes questions of optimization and some optimization techniques. Part of this work is recherché of variants of particle swarm optimization algorithm. These algorithms are mathematically described. Their advantages or disadvantages in comparison with the basic PSO algorithm are mentioned. The second part of this work describes mQPSO algorithm and created modification mQPSOPC. Described algorithms are compared with each other and with another evolution algorithm on several tests.

In this thesis, I introduce two new algorithms: Ant Brood Clustering-Intelligent Ants (ABC-INTE) and Ant Brood Clustering-Polymorphic Ants (ABC-POLY) for the graph clustering problem. ABC-INTE uses techniques such as hopping ants, relaxed drop function, ants with memories, stagnation control, and addition of k-means cluster retrieval process, as an improvement of the basic ABC-KLS algorithm. ABC-POLY uses two types of ants, inspired by the division of labour between the major and minor ants in Pheidole genus, as an improvement of ABC-INTE. For comparison purpose, I also implement MMAS, an ACO clustering algorithm. When tested on the benchmark networks, ABC-POLY outperforms or achieves the same modularity values as MMAS and ABC-INTE on 7 out of 10 networks and is robust against different graphs. In practice, the speed of ABC-POLY is at least 10 times faster than MMAS, making it a scalable algorithm compared to MMAS. ABC-POLY also outputs a direct visual representation of the natural clusters on the graph that is appealing to human observation. This thesis opens an interesting research topic to apply polymorphic ants for graph clustering in the ABC-POLY algorithm. The distributive and self-organization nature of ABC-POLY makes it a candidate for analyzing clusters in more complex and dynamic graphs. / May 2016

A primeira parte deste trabalho lida com o problema de posicionar um grupo de agentes retransmissores (relays) de forma a dar conectividade a um segundo grupo de agentes ativos (pursuers). A primeira abordagem apresentada consiste em modelar o cenário como um problema de programação quadrática (PPQ) com restrições lineares, usando uma estrutura de conectividade fixa. Para resolver o modelo proposto, foi implementada uma rede neural recorrente a qual converge rapidamente para a solução ótima do problema, mesmo em instâncias razoavelmente grandes. Como forma de avaliação, realizou-se um comparativo entre o solver de PPQ da plataforma Matlab e a rede proposta, também implementada na mesma plataforma. Na segunda abordagem foi proposto o uso de uma estimativa da conectividade algébrica do grafo de proximidade gerado pela rede, para direcionar o grupo de relays e pursuers, usando-se apenas as informações da vizinhança de cada agente. Nesta abordagem a estrutura do grafo é dinâmica, além disso, como proposta de paralelização, a esta solução distribuída foi acoplada um algoritmo de escalonamento por reversão de arestas (SER). Além do mais, as metaheurísticas Simulated Annealing, Genetic Algorithms, Particle Swarm Optimization e Backtracking Search Algorithm foram implementadas como alternativas de soluções ao problema. As soluções são avaliadas em um cenário de perseguição de alvos, os quais podem possuir comportamentos reativos (tais como fugir dos perseguidores). A segunda parte deste trabalho investiga o problema de rastreamento de múltiplos objetos em tempo real. Como solução, foi proposto um algoritmo que se baseia em memória de curto e longo prazo usando redes neurais sem peso. / The first part of this work deals with the problem of positioning a swarm of relay agents with the objective of providing connectivity to a second group of active agents (pursuers). The first approach consists of modelling the considered scenario as a quadratic programming problem (QP) with linear restrictions, using a fixed graph structure. In order to solve such model, a recurrent neural network is proposed with fast convergence rate to the optimal solution, even with reasonably big size instances. In addition, a comparison with the Matlab QP solver has been conducted in some experimental simulations. In the second approach, it is proposed an estimation of the algebraic connectivity of the underlying graph generated by the network. Over this estimation, it is proposed a metric to direct the group of relays and pursuers, using only local neighbourhood information of each agent. On this approach, the graph structure is dynamic and it is also proposed the use of the schedule by edge reversal (SER) as a solution to ordering the parallelization of the robot positioning computation. Moreover, the meta-heuristics Simulated Annealing, Genetic Algorithms, Particle Swarm Optimization and Backtracking Search Algorithm have been applied as alternative solution providers. The proposed solutions have been applied in a target pursuit scenario, for which the targets are deployed in different spots and may have some reactive behaviours (such as escape from the pursuers).The second part of this work investigates the visual tracking of shape shift objects in real time. As a solution, it is proposed a short- and long-time memories tracker which uses a weightless neural network for training and retraining the objects patterns.