In this thesis, we investigate the problem of path formation and prey retrieval in a swarm of robots. We present two swarm intelligence control mechanisms used for distributed robot path formation. In the first, the robots form linear chains. We study three variants of robot chains, which vary in the degree of motion allowed<p>to the chain structure. The second mechanism is called vectorfield. In this case,<p>the robots form a pattern that globally indicates the direction towards a goal or<p>home location. Both algorithms were designed following the swarm robotics control<p>principles: simplicity of control, locality of sensing and communication, homogeneity<p>and distributedness.<p><p>We test each controller on a task that consists in forming a path between two<p>objects—the prey and the nest—and to retrieve the prey to the nest. The difficulty<p>of the task is given by four constraints. First, the prey requires concurrent, physical<p>handling by multiple robots to be moved. Second, each robot’s perceptual range<p>is small when compared to the distance between the nest and the prey; moreover,<p>perception is unreliable. Third, no robot has any explicit knowledge about the<p>environment beyond its perceptual range. Fourth, communication among robots is<p>unreliable and limited to a small set of simple signals that are locally broadcast.<p><p>In simulation experiments we test our controllers under a wide range of conditions,<p>changing the distance between nest and prey, varying the number of robots<p>used, and introducing different obstacle configurations in the environment. Furthermore,<p>we tested the controllers for robustness by adding noise to the different sensors,<p>and for fault tolerance by completely removing a sensor or actuator. We validate the<p>chain controller in experiments with up to twelve physical robots. We believe that<p>these experiments are among the most sophisticated examples of self-organisation<p>in robotics to date. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

In this thesis, we propose an approach to achieve autonomous task partitioning in swarms of robots. Task partitioning is the process by which tasks are decomposed into sub-tasks and it is often an advantageous way of organizing work in groups of individuals. Therefore, it is interesting to study its application to swarm robotics, in which groups of robots are deployed to collectively carry out a mission. The capability of partitioning tasks autonomously can enhance the flexibility of swarm robotics systems because the robots can adapt the way they decompose and perform their work depending on specific environmental conditions and goals. So far, few studies have been presented on the topic of task partitioning in the context of swarm robotics. Additionally, in all the existing studies, there is no separation between the task partitioning methods and the behavior of the robots and often task partitioning relies on characteristics of the environments in which the robots operate.<p>This limits the applicability of these methods to the specific contexts for which they have been built. The work presented in this thesis represents the first steps towards a general framework for autonomous task partitioning in swarms of robots. We study task partitioning in foraging, since foraging abstracts practical real-world problems. The approach we propose in this thesis is therefore studied in experiments in which the goal is to achieve autonomous task partitioning in foraging. However, in the proposed approach, the task partitioning process relies upon general, task-independent concepts and we are therefore confident that it is applicable in other contexts. We identify two main capabilities that the robots should have: i) being capable of selecting whether to employ task partitioning and ii) defining the sub-tasks of a given task. We propose and study algorithms that endow a swarm of robots with these capabilities. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

In this thesis, we examine algorithms for the division of labour in a group of robot. The algorithms make no use of direct communication. Instead, they are based only on the interactions among the robots and between the group and the environment.<p><p>Division of labour is the mechanism that decides how many robots shall be used to perform a task. The efficiency of the group of robots depends in fact on the number of robots involved in a task. If too few robots are used to achieve a task, they might not be successful or might perform poorly. If too many robots are used, it might be a waste of resources. The number of robots to use might be decided a priori by the system designer. More interestingly, the group of robots might autonomously select how many and which robots to use. In this thesis, we study algorithms of the latter type.<p><p>The robotic literature offers already some solutions, but most of them use a form of direct communication between agents. Direct, or explicit, communication between the robots is usually considered a necessary condition for co-ordination. Recent studies have questioned this assumption. The claim is based on observations of animal colonies, e.g. ants and termites. They can effectively co-operate without directly communicating, but using indirect forms of communication like stigmergy. Because they do not rely on communication, such colonies show robust behaviours at group level, a condition that one wishes also for groups of robots. Algorithms for robot co-ordination without direct communication have been proposed in the last few years. They are interesting not only because they are a stimulating intellectual challenge, but also because they address a situation that might likely occur when using robots for real-world out-door applications. Unfortunately, they are still poorly studied.<p><p>This thesis helps the understanding and the development of such algorithms. We start from a specific case to learn its characteristics. Then we improve our understandings through comparisons with other solutions, and finally we port everything into another domain.<p><p>We first study an algorithm for division of labour that was inspired by ants' foraging. We test the algorithm in an application similar to ants' foraging: prey retrieval. We prove that the model used for ants' foraging can be effective also in real conditions. Our analysis allows us to understand the underlying mechanisms of the division of labour and to define some way of measuring it.<p><p>Using this knowledge, we continue by comparing the ant-inspired algorithm with similar solutions that can be found in the literature and by assessing their differences. In performing these comparisons, we take care of using a formal methodology that allows us to spare resources. Namely, we use concepts of experiment design to reduce the number of experiments with real robots, without losing significance in the results.<p><p>Finally, we apply and port what we previously learnt into another application: Sensor/Actor Networks (SANETs). We develop an architecture for division of labour that is based on the same mechanisms as the ants' foraging model. Although the individuals in the SANET can communicate, the communication channel might be overloaded. Therefore, the agents of a SANET shall be able to co-ordinate without accessing the communication channel. / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

A swarm intelligence system is a type of multiagent system with the following distinctive characteristics: (i) it is composed of a large number of agents, (ii) the agents that comprise the system are simple with respect to the complexity of the task the system is required to perform, (iii) its control relies on principles of decentralization and self-organization, and (iv) its constituent agents interact locally with one another and with their environment. <p><p>Interactions among agents, either direct or indirect through the environment in which they act, are fundamental for swarm intelligence to exist; however, there is a class of interactions, referred to as "interference", that actually blocks or hinders the agents' goal-seeking behavior. For example, competition for space may reduce the mobility of robots in a swarm robotics system, or misleading information may spread through the system in a particle swarm optimization algorithm. One of the most visible effects of interference in a swarm intelligence system is the reduction of its efficiency. In other words, interference increases the time required by the system to reach a desired state. Thus, interference is a fundamental problem which negatively affects the viability of the swarm intelligence approach for solving important, practical problems.<p><p>We propose a framework called "incremental social learning" (ISL) as a solution to the aforementioned problem. It consists of two elements: (i) a growing population of agents, and (ii) a social learning mechanism. Initially, a system under the control of ISL consists of a small population of agents. These agents interact with one another and with their environment for some time before new agents are added to the system according to a predefined schedule. When a new agent is about to be added, it learns socially from a subset of the agents that have been part of the system for some time, and that, as a consequence, may have gathered useful information. The implementation of the social learning mechanism is application-dependent, but the goal is to transfer knowledge from a set of experienced agents that are already in the environment to the newly added agent. The process continues until one of the following criteria is met: (i) the maximum number of agents is reached, (ii) the assigned task is finished, or (iii) the system performs as desired. Starting with a small number of agents reduces interference because it reduces the number of interactions within the system, and thus, fast progress toward the desired state may be achieved. By learning socially, newly added agents acquire knowledge about their environment without incurring the costs of acquiring that knowledge individually. As a result, ISL can make a swarm intelligence system reach a desired state more rapidly. <p><p>We have successfully applied ISL to two very different swarm intelligence systems. We applied ISL to particle swarm optimization algorithms. The results of this study demonstrate that ISL substantially improves the performance of these kinds of algorithms. In fact, two of the resulting algorithms are competitive with state-of-the-art algorithms in the field. The second system to which we applied ISL exploits a collective decision-making mechanism based on an opinion formation model. This mechanism is also one of the original contributions presented in this dissertation. A swarm robotics system under the control of the proposed mechanism allows robots to choose from a set of two actions the action that is fastest to execute. In this case, when only a small proportion of the swarm is able to concurrently execute the alternative actions, ISL substantially improves the system's performance. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

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.

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