Dissertations / Theses on the topic 'Swerm intelligensie'

Groups of starlings can form impressive shapes as they travel northward together in the springtime. This is among a group of natural phenomena based on swarm behaviour. The research field of artificial intelligence in computer science, particularly the areas of robotics and image processing, has in recent decades given increasing attention to the underlying structures. The behaviour of these intelligent swarms has opened new approaches for face detection as well. G. Beni and J. Wang coined the term “swarm intelligence” to describe this type of group behaviour. In this context, intelligence describes the ability to solve complex problems. The objective of this project is to automatically find exactly one face on a photo or video material by means of swarm intelligence. The process developed for this purpose consists of a combination of various known structures, which are then adapted to the task of face detection. To illustrate the result, a 3D hat shape is placed on top of the face using an example application program.

Lo studio che si ha in informatica ha come obiettivo la scoperta di algoritmi sempre più efficienti per riuscire, con componenti semplici, a svolgere compiti complessi, con il minore carico di lavoro possibile. Le applicazioni di tale studio trovano risultati anche nel campo del controllo adattativo di robot. Si vogliono confrontare tramite questo studio le osservazioni più importanti riguardati queste caratteristiche rese note dalla scienza e applicarle ai campi sopra citati per dimostrare l'effettivo valore e affidabilità che si guadagnano andando a utilizzare degli algoritmi che rispecchiano le stesse caratteristiche che si possono notare nel regno animale. La metodologia di interesse usata come caso di studio è quella del recupero di oggetti. Esistono numerose soluzioni a questo problema che possono trovare uso in molte realtà utili all'uomo. Ne verranno presentate e confrontate due all'interno di questo elaborato, studiando le caratteristiche positive e negative di entrambe. Questi due approcci sono chiamati a soglia fissa e a soglia variabile. Entrambe sono tipologie di adattamento che prendono spunto dal comportamento che hanno le colonie di formiche quando si muovono alla ricerca di cibo. Si è deciso di analizzare queste due metodologie partendo da una panoramica generale di come cooperano gli insetti per arrivare al risultato finale, per poi introdurre nello specifico le caratteristiche di entrambe analizzando per ognuna i risultati ottenuti tramite grafici, e confrontandoli tra di loro.

Groups of starlings can form impressive shapes as they travel northward together in the springtime. This is among a group of natural phenomena based on swarm behaviour. The research field of artificial intelligence in computer science, particularly the areas of robotics and image processing, has in recent decades given increasing attention to the underlying structures. The behaviour of these intelligent swarms has opened new approaches for face detection as well. G. Beni and J. Wang coined the term “swarm intelligence” to describe this type of group behaviour. In this context, intelligence describes the ability to solve complex problems. The objective of this project is to automatically find exactly one face on a photo or video material by means of swarm intelligence. The process developed for this purpose consists of a combination of various known structures, which are then adapted to the task of face detection. To illustrate the result, a 3D hat shape is placed on top of the face using an example application program.:1 Introduction 1.1 Face Detection 1.2 Swarm Intelligence and Particle Swarm Optimisation Fundamentals 3 Face Detection by Means of Particle Swarm Optimisation 3.1 Swarms and Particles 3.2 Behaviour Patterns 3.2.1 Opportunism 3.2.2 Avoidance 3.2.3 Other Behaviour Patterns 3.3 Stop Criterion 3.4 Calculation of the Solution 3.5 Example Application 4 Summary and Outlook

One of the major difficulties met in image segmentation lies in the varying degrees of homogeneousness of the different regions in a given image. Hence, it is more efficient to adopt adaptive threshold type methodologies to identify the regions in the images. Throughout the last decade, many image processing tools and techniques have emerged based on the former technology which we called conventional and new technologies such as intelligent-based image processing techniques and algorithm. In some cases, a combination of both technologies is adapted to form a hybrid image processing technique. Intelligent-based techniques are increasing nowadays. Due to the rapid growth of agent-based technology's environments which are adopting numerous agent-based applications, tools, models and softwares to enhance and improve the quality of the agent based approach. In case of intelligent techniques to doing image processing; swarm intelligence techniques rarely have been used in term of image segmentation or boundary detection. However, there are many factors that make this task challenging. These factors include not only the limited such increasing number of agents in the environment, and the presence of techniques., but also how to efficiently find the right threshold in the image, develop a flexible design, and fully autonomous system that support different platform. A flexible architecture and tools need to be defined that overcomes these problems and permits a smooth and valuable image processing based on these new techniques in image processing. It would satisfy the needs of end users. This thesis illustrates the theoretical background, design, swarm based intelligent techniques and implementation of a fully agent-based model system that is called SIBIS (Swarm Intelligent Based Image Segmentation).

In this report, we have explored swarm intelligence through a box-pushing taskwith physical robots called e-pucks. Research on social insects has been presentedtogether with dierent ways of controlling autonomous robots, where combiningthis knowledge has been essential in our quest to make a biological plausible antretrieving system.Inspired by ants and behavior-based robotics, we have created the system CRABS.It is based on Brooks' subsumption architecture to control six dierent behaviors,from a xed input-output scheme. The system is designed to easily handle addingor removal of behavior layers. Behavior modules can also be used separately andported to other software or hardware platforms.During this project we came across several hardware and software challenges in-vestigating cooperative behavior. With the use of the simulation tool Webots, wewere able to determine e-pucks' capabilities, and through this knowledge able todesign and construct an articial food source. This operated as the box-item in thebox-pushing task.Based on two types of sensors and two actuators (wheels), we had a strategy toaccomplish the box-pushing task following the biological principles of social insects.The guidelines of the ant retrieving model made CRABS a self-organized systemthat given three or more e-pucks, will always succeed in retrieving the box back tothe wall. The most remarkable view on this accomplishment is that is done throughthe use of only stigmergy and positive/negative feedback.One of the things we've experienced throughout this thesis is that hardware is a morework demanding and inconsistent platform than your usual software simulation.Everything is not given, and although Webots provided helpful shortcuts, a lot oftime and hard work was put down in order to get the system up and running. Withthat being said, we are pleased that we took the hardware rout and were able totest and validate our system on physical robots.

This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.

Can robots of a swarm cooperate to solve together a complex cognitive problem that none of them can solve alone? TS-Swarm is a robot swarm that autonomously sequences tasks at run time and can therefore operate even if the correct order of execution is unknown at design time. The ability to sequence tasks endows robot swarms with unprecedented autonomy and is an important step towards the uptake of swarm robotics in a range of practical applications.
Doctorat en Sciences de l'ingénieur et technologie
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.

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.

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.

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

Swarm robotics is a young multidisciplinary research field at the

intersection of disciplines such as distributed systems, robotics,

artificial intelligence, and complex systems. Considerable research

effort has been dedicated to the study of algorithms targeted to

specific problems. Nonetheless, implementation and comparison remain difficult due to the lack of shared tools and benchmarks. Among the tools necessary to enable experimentation, the most fundamental is a simulator that offers an adequate level of accuracy and flexibility to suit the diverse needs of the swarm robotics

community. The very nature of swarm robotics, in which systems may comprise large numbers of robots, forces the design to provide

runtimes that increase gracefully with increasing swarm sizes.

In this thesis, I argue that none of the existing simulators offers

satisfactory levels of accuracy, flexibility, and efficiency, due to

fundamental limitations of their design. To overcome these

limitations, I present ARGoS---a general, multi-robot simulator that

currently benchmarks as the fastest in the literature.

In the design of ARGoS, I faced a number of unsolved issues. First, in existing simulators, accuracy is an intrinsic feature of the

design. For single-robot applications this choice is reasonable, but

for the large number of robots typically involved in a swarm, it

results in an unacceptable trade-off between accuracy and

efficiency. Second, the prospect of swarm robotics spans diverse

potential applications, such as space exploration, ocean restoration,

deep-underground mining, and construction of large structures. These applications differ in terms of physics (e.g. motion dynamics) and available communication means. The existing general-purpose simulators are not suitable to simulate such diverse environments accurately and efficiently.

To design ARGoS I introduced novel concepts. First, in ARGoS accuracy is framed as a property of the experimental setup, and is tunable to the requirements of the experiment. To achieve this, I designed the architecture of ARGoS to offer unprecedented levels of modularity. The user can provide customized versions of individual modules, thus assigning computational resources to the relevant aspects. This feature enhances efficiency, since the user can lower the computational cost of unnecessary aspects of a simulation.

To further decrease runtimes, the architecture of ARGoS exploits the computational resources of modern multi-core systems. In contrast to existing designs with comparable features, ARGoS allows the user to define both the granularity and the scheduling strategy of the parallel tasks, attaining unmatched levels of scalability and efficiency in resource usage.

A further unique feature of ARGoS is the possibility to partition the

simulated space in regions managed by dedicated physics engines

running in parallel. This feature, besides enhancing parallelism,

enables experiments in which multiple regions with different features are simulated. For instance, ARGoS can perform accurate and efficient simulations of scenarios in which amphibian robots act both underwater and on sandy shores.

ARGoS is listed among the major results of the Swarmanoid

project. It is currently

the official simulator of 4 European projects

(ASCENS, H2SWARM, E-SWARM, Swarmix) and is used by 15

universities worldwide. While the core architecture of ARGoS is

complete, extensions are continually added by a community of

contributors. In particular, ARGoS was the first robot simulator to be

integrated with the ns3 network simulator, yielding a software

able to simulate both the physics and the network aspects of a

swarm. Further extensions under development include support for

large-scale modular robots, construction of 3D structures with

deformable material, and integration with advanced statistical

analysis tools such as MultiVeStA.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

In the post-9/11 world, new and improved surveillance and information-gathering technologies have become a high-priority problem to be solved. Surveillance systems are often needed in areas too hostile or dangerous for a direct human presence. The field of robotics is being looked to for an autonomous mobile surveillance system. One major problem is the control and coordination of multiple cooperating robots. Researchers have looked to the distributed control strategies found in nature in the form of social insects as an inspiration for new control schemes. Swarm intelligence research centers around the interactions of such systems and how they can be applied to contemporary problems. In this thesis, a surveillance system of mobile autonomous robots based on the principles of swarm intelligence is presented.
Master of Science

The Ant Colony Optimization and Particle Swarm Optimization are two Swarm Intelligence algorithms often utilized for optimization. Swarm Intelligence relies on agents that possess fragmented knowledge, a concept not often utilized in games. The aim of this study is to research whether there are any benefits to using these Swarm Intelligence algorithms in comparison to standard algorithms such as A* for pathfinding in a game. Games often consist of dynamic environments with mobile agents, as such all experiments were conducted with dynamic destinations. Algorithms were measured on the length of their path and the time taken to calculate that path. The algorithms were implemented with minor modifications to allow them to better function in a grid based environment. The Ant Colony Optimization was modified in regards to how pheromone was distributed in the dynamic environment to better allow the algorithm to path towards a mobile target. Whereas the Particle Swarm Optimization was given set start positions and velocity in order to increase initial search space and modifications to increase particle diversity. The results obtained from the experimentation showcased that the Swarm Intelligence algorithms were capable of performing to great results in terms of calculation speed, they were however not able to obtain the same path optimality as A*. The algorithms' implementation can be improved but show potential to be useful in games.

D. Tech. Electrical Engineering.
Particle Swarm Optimisation (PSO) is based on a metaphor of social interaction such as birds flocking or fish schooling to search a space by adjusting the trajectories of individual vectors, called "particles" conceptualized as moving points in a multidimensional space. This thesis presents several algorithms/techniques to improve the PSO's global search ability. Simulation and analytical results confirm the efficiency of the proposed algorithms/techniques when compared to the other state of the art algorithms.

Thesis (M.S.) -- University of Maryland, College Park, 2003.
Thesis research directed by: Dept. of Mechanical Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

As formigas são criaturas fascinantes que, além dos avanços na biologia também inspiraram pesquisas sobre teoria da informação. Em particular, o estudo resultou na criação da Teoria da Forragem de Informação, que descreve como os agentes de buscam informações em seu ambiente. Esta teoria também explica fenômenos recentes e bem-sucedidos, como crowd sourcing. Crowdsourcing tem sido aplicado a muitas atividades em engenharia de software, incluindo desenvolvimento, tradução e testes, mas uma atividade parece resistir: depuração. No entanto, os desenvolvedores sabem que a depuração pode exigir dedicação, esforço, longas horas de trabalho, por vezes, para mudar uma linha de código único. Nós introduzimos o conceito de Depuração em Enxame, para trazer crowd sourcing para a atividade de depuração. Através de crowd sourcing, pretendemos ajudar os desenvolvedores, capitalizando a sua dedicação, esforço e longas horas de trabalho para facilitar atividades de depuração. Mostramos que a depuração enxame requer uma abordagem específica para recolher informações relevantes, e descrevemos sua infra-estrutura. Mostramos também que a depuração em enxame pode reduzir o esforço desenvolvedores. Concluímos com as vantagens e limitações atuais de depuração enxame, e sugerir caminhos para superar estas limitações e ainda mais a adoção de crowd sourcing para atividades de depuração.
Ants are fascinating creatures that beyond the advances in biology have also inspired research on information theory. In particular, their study resulted in the creation of the Information Foraging Theory, which describes how agents forages for information in their environment. This theory also explains recent and fruitful phenomena, such as crowdsourcing. Many activities in software engineering have applied crowdsourcing, including development, translation, and testing, but one action seems to resist: debugging. Developers know that debugging can require dedication, effort, long hours of work, sometimes for changing one line of code only. We introduce the concept of Swarm Debugging, to bring crowdsourcing to the activity of debugging. Through crowdsourcing, we aim at helping developers by capitalizing on their dedication, effort, and long hours of work to ease debugging activities of their peers or theirs, on other bugs. We show that swarm debugging requires a particular approach to collect relevant information, and we describe the Swarm Debugging Infrastructure. We also show that swarm debugging minimizes developers effort. We conclude with the advantages and current limitations of swarm debugging and suggest directions to overcome these limitations and further the adoption of crowdsourcing for debugging activities.

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.

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.

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.

Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

The main contributions of this thesis are located in the domain of wireless sensor netorks. More in detail, we introduce energyaware algorithms and protocols in the context of the following topics: self-synchronized duty-cycling in networks with energy harvesting capabilities, distributed graph coloring and minimum energy broadcasting with realistic antennas. In the following, we review the research conducted in each case. We propose a self-synchronized duty-cycling mechanism for sensor networks. This mechanism is based on the working and resting phases of natural ant colonies, which show self-synchronized activity phases. The main goal of duty-cycling methods is to save energy by efficiently alternating between different states. In the case at hand, we considered two different states: the sleep state, where communications are not possible and energy consumption is low; and the active state, where communication result in a higher energy consumption. In order to test the model, we conducted an extensive experimentation with synchronous simulations on mobile networks and static networks, and also considering asynchronous networks. Later, we extended this work by assuming a broader point of view and including a comprehensive study of the parameters. In addition, thanks to a collaboration with the Technical University of Braunschweig, we were able to test our algorithm in the real sensor network simulator Shawn (http://shawn.sf.net). The second part of this thesis is devoted to the desynchronization of wireless sensor nodes and its application to the distributed graph coloring problem. In particular, our research is inspired by the calling behavior of Japanese tree frogs, whose males use their calls to attract females. Interestingly, as female frogs are only able to correctly localize the male frogs when their calls are not too close in time, groups of males that are located nearby each other desynchronize their calls. Based on a model of this behavior from the literature, we propose a novel algorithm with applications to the field of sensor networks. More in detail, we analyzed the ability of the algorithm to desynchronize neighboring nodes. Furthermore, we considered extensions of the original model, hereby improving its desynchronization capabilities.To illustrate the potential benefits of desynchronized networks, we then focused on distributed graph coloring. Later, we analyzed the algorithm more extensively and show its performance on a larger set of benchmark instances. The classical minimum energy broadcast (MEB) problem in wireless ad hoc networks, which is well-studied in the scientific literature, considers an antenna model that allows the adjustment of the transmission power to any desired real value from zero up to the maximum transmission power level. However, when specifically considering sensor networks, a look at the currently available hardware shows that this antenna model is not very realistic. In this work we re-formulate the MEB problem for an antenna model that is realistic for sensor networks. In this antenna model transmission power levels are chosen from a finite set of possible ones. A further contribution concerns the adaptation of an ant colony optimization algorithm --currently being the state of the art for the classical MEB problem-- to the more realistic problem version, the so-called minimum energy broadcast problem with realistic antennas (MEBRA). The obtained results show that the advantage of ant colony optimization over classical heuristics even grows when the number of possible transmission power levels decreases. Finally we build a distributed version of the algorithm, which also compares quite favorably against centralized heuristics from the literature.
Las principles contribuciones de esta tesis se encuentran en el domino de las redes de sensores inalámbricas. Más en detalle, introducimos algoritmos y protocolos que intentan minimizar el consumo energético para los siguientes problemas: gestión autosincronizada de encendido y apagado de sensores con capacidad para obtener energía del ambiente, coloreado de grafos distribuido y broadcasting de consumo mínimo en entornos con antenas reales. En primer lugar, proponemos un sistema capaz de autosincronizar los ciclos de encendido y apagado de los nodos de una red de sensores. El mecanismo está basado en las fases de trabajo y reposo de las colonias de hormigas tal y como estas pueden observarse en la naturaleza, es decir, con fases de actividad autosincronizadas. El principal objectivo de este tipo de técnicas es ahorrar energía gracias a alternar estados de forma eficiente. En este caso en concreto, consideramos dos estados diferentes: el estado dormido, en el que los nodos no pueden comunicarse y el consumo energético es bajo; y el estado activo, en el que las comunicaciones propician un consumo energético elevado. Con el objetivo de probar el modelo, se ha llevado a cabo una extensa experimentación que incluye tanto simulaciones síncronas en redes móviles y estáticas, como simulaciones en redes asíncronas. Además, este trabajo se extendió asumiendo un punto de vista más amplio e incluyendo un detallado estudio de los parámetros del algoritmo. Finalmente, gracias a la colaboración con la Technical University of Braunschweig, tuvimos la oportunidad de probar el mecanismo en el simulador realista de redes de sensores, Shawn (http://shawn.sf.net). La segunda parte de esta tesis está dedicada a la desincronización de nodos en redes de sensores y a su aplicación al problema del coloreado de grafos de forma distribuida. En particular, nuestra investigación está inspirada por el canto de las ranas de árbol japonesas, cuyos machos utilizan su canto para atraer a las hembras. Resulta interesante que debido a que las hembras solo son capaces de localizar las ranas macho cuando sus cantos no están demasiado cerca en el tiempo, los grupos de machos que se hallan en una misma región desincronizan sus cantos. Basado en un modelo de este comportamiento que se encuentra en la literatura, proponemos un nuevo algoritmo con aplicaciones al campo de las redes de sensores. Más en detalle, analizamos la habilidad del algoritmo para desincronizar nodos vecinos. Además, consideramos extensiones del modelo original, mejorando su capacidad de desincronización. Para ilustrar los potenciales beneficios de las redes desincronizadas, nos centramos en el problema del coloreado de grafos distribuido que tiene relación con diferentes tareas habituales en redes de sensores. El clásico problema del broadcasting de consumo mínimo en redes ad hoc ha sido bien estudiado en la literatura. El problema considera un modelo de antena que permite transmitir a cualquier potencia elegida (hasta un máximo establecido por el dispositivo). Sin embargo, cuando se trabaja de forma específica con redes de sensores, un vistazo al hardware actualmente disponible muestra que este modelo de antena no es demasiado realista. En este trabajo reformulamos el problema para el modelo de antena más habitual en redes de sensores. En este modelo, los niveles de potencia de transmisión se eligen de un conjunto finito de posibilidades. La siguiente contribución consiste en en la adaptación de un algoritmo de optimización por colonias de hormigas a la versión más realista del problema, también conocida como broadcasting de consumo mínimo con antenas realistas. Los resultados obtenidos muestran que la ventaja de este método sobre heurísticas clásicas incluso crece cuando el número de posibles potencias de transmisión decrece. Además, se ha presentado una versión distribuida del algoritmo, que también se compara de forma bastante favorable contra las heurísticas centralizadas conocidas.

This thesis presents investigations into development of modelling and control of flexible structures using swarm intelligence optimisation techniques. A smart flexible beam structure is used in this work as a candidate application. The smart flexible beam model is developed using finite difference method and a methodology of incorporating piezoelectric patch actuator into finite difference model is presented. The simulation model is developed in MATLAB/SIMULINK environment as a platform for test and verification of the control approaches developed in this work. Many heuristic search algorithms have been inspired by nature such as genetic algorithm (natural evolution), artificial neural network (biological neuron) and artificial immune system (immune system) where the algorithms try to mimic the biological process. Addition to nature inspired algorithms is the swarm intelligence method which has been inspired by the natural behaviour of a group of insects like foraging, flocking and schooling in ants, bees, fish and birds where particle swam optimisation (PSO) and ant colony optimisation (ACO) are the most popular methods. The study of parameter setting for PSO and continuous ACO (ACOr) is studied through parametric modelling of the beam. The performance of each algorithm in terms of computational time and convergence is discussed. In this study, vibration control of a flexible beam structure is developed based on the principle of wave interference, to result in optimal cancellation with adaptive model-based control and adaptive direct control. A single objective optimisation algorithm is developed and implemented using PSO and continuous ACO considering two conditions; optimisation of controller with pre-selected location of sensor and actuator and simultaneous optimisation of controller parameters and sensor and actuator location in single-input-single-output and single-input-multiple-output configurations. While single objective optimisation provides only one solution, the use of multi-objective optimisation results in several solutions to choose for implementation. An approach of multi-objective optimisation of controllers' parameters and sensor/actuator location is developed based on minimising vibration energy and minimising actuator force. Multi-objective PSO and multi-objective ACOr algorithms are developed in finding optimal system setup and controller parameters for AYC of the beam. Both PSO and ACO based algorithms are tested and their performances assessed in vibration control of the beam.

Collective robotic behavior poses significant advantages over classical control methods such as system response and robustness. Biological cooperative communities have provided great insights for development of many control algorithms. Localized chemical signaling within bacterial communities is used for directed movement and dynamic density measurements. Both individual and population scale models have been created to adequately model community dynamics. These dynamics, including directed motion due to chemotaxis and density controlled functionality from quorum sensing, are modeled through an individual scale in a community scale environment. This modeling provides both a platform for analyzing the BacteriaBot engineered system as well as inspires decentralized stochastic control techniques for solving bacteria-like collaborative control problems.
Master of Science

Ant Colony Optimization (ACO) algorithms which belong to metaheuristic algorithms and swarm intelligence algorithms have been the focus of much attention in the quest to solve optimization problems. These algorithms are inspired by colonies of ants foraging for food from their nest and have been considered state-of-art methods for solving both discrete and continuous optimization problems. One of the most important phases of ACO algorithms is the construction phase during which an ant builds a partial solution and develops a state transition strategy. There have been a number of studies on the state transition strategy. However, most of the research studies look at how to improve pheromone updates rather than at how the ant itself makes a decision to move from a current position to the next position. The aim of this research is to develop a novel state transition strategy for Ant Colony Optimization algorithms that can improve the overall performance of the algorithms. The research has shown that the state transition strategy in ACO can be improved by introducing non-rational decision-making. The new proposed algorithm is called Cognitive Ant Colony Optimization and uses a new concept of decision-making taken from cognitive behaviour theory. In this proposed algorithm, the ACO has been endowed with non-rational behaviour in order to improve the overall optimization behaviour of ants during the process. This new behaviour will use a non-rational model named prospect theory (Kahneman & Tversky, 1979) to select the transition movements of the ants in the colony in order to improve the overall search capability and the convergence of the algorithm. The new Cognitive Ant Colony Optimization framework has been tested on the Travelling Salesman Problem (TSP), Water Distribution System and Continuous optimization problems. The results obtained show that our algorithm improved the performance of previous ACO techniques considerably.

Thesis (Ph. D.) -- University of Maryland, College Park, 2007.
Thesis research directed by: Computer Science. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

The purpose of this thesis is to investigate the suitability and effectiveness of the Particle Swarm Optimization (PSO) technique when applied to the University Examination Timetabling problem. We accomplished this by analyzing experimentally the performance profile-the quality of the solution as a function of the execution time-of the standard form of the PSO algorithm when brought to bear against the University Examination Timetabling problem. This study systematically investigated the impact of problem and algorithm factors in solving this particular timetabling problem and determined the algorithm's performance profile under the specified test environment. Keys factors studied included problem size (i.e., number of enrollments), conflict matrix density, and swarm size. Testing used both real world and fabricated data sets of varying size and conflict densities. This research also provides insight into how well the PSO algorithm performs compared with other algorithms used to attack the same problem and data sets. Knowing the algorithm's strengths and limitations is useful in determining its utility, ability, and limitations in attacking timetabling problems in general and the University Examination Timetabling problem in pal1icular. Finally, two additional contributions were made during the course of this research: a better way to fabricate examination timetabling data sets and the introduction of the PSO-No Conflicts optimization approach. Our new data set fabrication method produced data sets that were more representative of real world examination timetabling data sets and permitted us to construct data sets spanning a wide range of sizes and densities.· The newly derived PSO-No Conflicts algorithm permitted the PSO algorithm to perform searches while still satisfying constraints.

Many real-world problems could be formulated in a way to fit the necessary form for discrete optimization. Discrete optimization problems can be solved by numerous different techniques that have developed over time. Some of the techniques provide optimal solution(s) to the problem and some of them give â good enoughâ solution(s). The fundamental reason for developing techniques capable of producing solutions that are not necessarily optimal is the fact that many discrete optimization problems are NP-complete. Metaheuristic algorithms are a common name for a set of general-purpose techniques developed to provide solution(s) to the problems associated with discrete optimization. Mostly the techniques are based on natural metaphors. Discrete optimization could be applied to countless problems in transportation engineering. Recently, researchers started studying the behavior of social insects (ants) in an attempt to use the swarm intelligence concept to develop artificial systems with the ability to search a problemâ s solution space in a way that is similar to the foraging search by a colony of social insects. The development of artificial systems does not entail the complete imitation of natural systems, but explores them in search of ideas for modeling. This research is partially devoted to the development of a new system based on the foraging behavior of bee colonies â Bee System. The Bee System was tested through many instances of the Traveling Salesman Problem. Many transportation-engineering problems, besides being of combinatorial nature, are characterized by uncertainty. In order to address these problems, the second part of the research is devoted to development of the algorithms that combine the existing results in the area of swarm intelligence (The Ant System) and approximate reasoning. The proposed approach â Fuzzy Ant System is tested on the following two examples: Stochastic Vehicle Routing Problem and Schedule Synchronization in Public Transit.
Ph. D.

This thesis proposes different approaches to address routing and security of MANETs using swarm technology. The mobility and infrastructure-less of MANET as well as nodes misbehavior compose great challenges to routing and security protocols of such a network. The first approach addresses the problem of channel assignment in multichannel ad hoc networks with limited number of interfaces, where stable route are more preferred to be selected. The channel selection is based on link quality between the nodes. Geographical information is used with mapping algorithm in order to estimate and predict the links’ quality and routes life time, which is combined with Ant Colony Optimization (ACO) algorithm to find most stable route with high data rate. As a result, a better utilization of the channels is performed where the throughput increased up to 74% over ASAR protocol. A new smart data packet routing protocol is developed based on the River Formation Dynamics (RFD) algorithm. The RFD algorithm is a subset of swarm intelligence which mimics how rivers are created in nature. The protocol is a distributed swarm learning approach where data packets are smart enough to guide themselves through best available route in the network. The learning information is distributed throughout the nodes of the network. This information can be used and updated by successive data packets in order to maintain and find better routes. Data packets act like swarm agents (drops) where they carry their path information and update routing information without the need for backward agents. These data packets modify the routing information based on different network metrics. As a result, data packet can guide themselves through better routes. In the second approach, a hybrid ACO and RFD smart data packet routing protocol is developed where the protocol tries to find shortest path that is less congested to the destination. Simulation results show throughput improvement by 30% over AODV protocol and 13% over AntHocNet. Both delay and jitter have been improved more than 96% over AODV protocol. In order to overcome the problem of source routing introduced due to the use of the ACO algorithm, a solely RFD based distance vector protocol has been developed as a third approach. Moreover, the protocol separates reactive learned information from proactive learned information to add more reliability to data routing. To minimize the power consumption introduced due to the hybrid nature of the RFD routing protocol, a forth approach has been developed. This protocol tackles the problem of power consumption and adds packets delivery power minimization to the protocol based on RFD algorithm. Finally, a security model based on reputation and trust is added to the smart data packet protocol in order to detect misbehaving nodes. A trust system has been built based on the privilege offered by the RFD algorithm, where drops are always moving from higher altitude to lower one. Moreover, the distributed and undefined nature of the ad hoc network forces the nodes to obligate to cooperative behaviour in order not to be exposed. This system can easily and quickly detect misbehaving nodes according to altitude difference between active intermediate nodes.

In this report I propose a method of navigation for differentially wheeled robots inspired by path integration in certain social insects like bees and ants. It is a very simple method, intended for use in low-tech robots with very limited hardware, such as swarm robots. Path integration is essentially dead reckoning as used by animals, calculating the relative position based on the movements made since the last known position. It is a tried and true method of navigation that also has significant flaws, especially in that inaccuracies accumulate and magnify over time. In this report I want to examine whether communication and information sharing between robots in a swarm can alleviate some of the drawbacks, and make it a viable method for navigation for swarm robots over relatively short distances.

We investigate the use of self-assembly in a robotic system as a means of responding

to different environmental contingencies. Self-assembly is the mechanism through which

agents in a multi-robot system autonomously form connections with one another to create

larger composite robotic entities. Initially, we consider a simple response mechanism

that uses stochastic self-assembly without any explicit control over the resulting morphology

Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

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.

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

Population-based global optimization algorithms including Particle Swarm Optimization (PSO) have become popular for solving multi-optima problems much more efficiently than the traditional mathematical techniques. In this research, we present and evaluate a new parallel PSO algorithm that provides a significant performance improvement as compared to the serial PSO algorithm. Instead of merely assigning parts of the task of serial version to several processors, the new algorithm places multiple swarms on the available nodes in which operate independently, while collaborating on the same task. With the reduction of the communication bottleneck as well the ability to manipulate the individual swarms independently, the proposed approach outperforms the original PSO algorithm and still maintains the simplicity and ease of implementation.

In my doctoral dissertation, I tackled two of the main open problems in swarm robotics: design and verification. I did so by using model checking.

Designing and developing individual-level behaviors to obtain a desired swarm-level goal is, in general, very difficult, as it is difficult to predict and thus design the non-linear interactions of tens or hundreds individual robots that result in the desired collective behavior. In my dissertation, I presented my novel contribution to the top-down design of robot swarms: property-driven design. Property-driven design is based on prescriptive modeling and model checking. Using property-driven design it is possible to design robot swarms in a systematic way, realizing systems that are "correct by design". I demonstrated property-driven design on two case-studies: aggregation and foraging.

Developing techniques to analyze and verify a robot swarm is also a necessary step in order to employ swarm robotics in real-world applications. In my dissertation, I explored the use of model checking to analyze and verify the properties of robot swarms. Model checking allows us to formally describe a set of desired properties of a system, in a more powerful and precise way compared to other mathematical approaches, and verify whether a given model of a system satisfies them. I explored two different approaches: the first based on Bio-PEPA and the second based on KLAIM.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

Simultaneous localization and mapping (SLAM) is a challenging and vital problem in robotics. It is important in tasks such as disaster response, deep-sea and cave exploration, in which robots must construct a map of an unknown terrain, and at the same time localize themselves within the map. The issue with single- robot SLAM is the relatively high rate of failure in a realistic application, as well as the time and energy cost. In this work, we propose a new approach to decentralized multi-robot SLAM which uses a robot swarm to map the environment. This system is capable of mapping an environment without human assistance and without the need for any additional infrastructure. We assume that 1) no robot possesses sufficient memory to store the entire map of the environment, 2) the communication range of the robots is limited, and 3)there is no infrastructure present in the environment to assist the robot in communicating with others. To cope with these limitations, the swarm system is designed to work as an independent entity. The swarm can deploy new robots towards the region that is yet to be explored, coordinate the communication between the robots by using itself as the communication network and replace any malfunctioning robots. The proposed method proves to be a reliable and robust exploration algorithm. It is shown to be a self-growing mapping network that is able to coordinate among numerous robots and replace any broken robots hence reducing the chance of system failure.

A swarm is a group of uninformed individuals that exhibit collective behaviors. Without any information about the external world, a swarm has limited ability to achieve complex goals. Prior work on human-swarm interaction methods allow a human to influence these uninformed individuals through either leadership or predation as informed agents that directly interact with humans. These methods of influence have two main limitations: (1) although leaders sustain influence over nominal agents for a long period of time, they tend to cause all collective structures to turn in to flocks (negating the benefit of other swarm formations) and (2) predators tend to cause collective structures to fragment. In this thesis, we present the use of mediators as a novel form for human-swarm influence and use mediators to shape the perimeter of a swarm. The mediator method uses special agents that operate from within the spatial center of a swarm. This approach allows a human operator to coordinate multiple mediators to modulate a rotating torus into various shapes while sustaining influence over the swarm, avoiding fragmentation, and maintaining the swarm's connectivity. The use of mediators allows a human to mold and adapt the torus' behavior and structure to a wide range of spatio-temporal tasks such as military protection and decontamination tasks. Results from an experiment that compares previous forms of human influence with mediator-based control indicate that mediator-based control is more amenable to human influence for certain types of problems.

Thesis (M.S.)--Missouri University of Science and Technology, 2009.
Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed January 22, 2009) Includes bibliographical references (p. 135-137).

In this dissertation, we propose and study methods for information transfer within a swarm of mobile robots that coordinately move, or flock, in a common direction. We define information transfer as the process whereby robots share directional information in order to coordinate their heading direction. We identify two paradigms of information transfer: explicit information transfer and implicit information transfer.

In explicit information transfer, directional information is transferred via communication. Explicit information transfer requires mobile robots equipped with a a communication device. We propose novel communication strategies for explicit information transfer, and we perform flocking experiments in different situations: with one or two desired directions of motion that can be static or change over time. We perform experiments in simulation and with real robots. Furthermore, we show that the same explicit information transfer strategies can also be applied to another collective behavior: collective transport with obstacle avoidance.

In implicit information transfer, directional information is transferred without communication. We show that a simple motion control method is sufficient to guarantee cohesive and aligned motion without resorting to communication or elaborate

sensing. We analyze the motion control method for its capability to achieve flocking with and without a desired direction of motion, both in simulation and using real robots. Furthermore, to better understand its underlying mechanism, we study this

method using tools of statistical physics, showing that the process can be explained in terms of non-linear elasticity and energy-cascading dynamics.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished

In this dissertation, we consider the clustering problem in data sets with unknown number of clusters having arbitrary shapes, intracluster and intercluster density variations. We introduce a clustering methodology which is composed of three methods that ensures extraction of local density and connectivity properties, data set reduction, and clustering. The first method constructs a unique neighborhood for each data point using the connectivity and density relations among the points based upon the graph theoretical concepts, mainly Gabriel Graphs. Neighborhoods subsequently connected form subclusters (closures) which constitute the skeleton of the clusters. In the second method, the external shape concept in computational geometry is adapted for data set reduction and cluster visualization. This method extracts the external shape of a non-convex n-dimensional data set using Delaunay triangulation. In the third method, we inquire the applicability of Swarm Intelligence to clustering using Ant Colony Optimization (ACO). Ants explore the data set so that the clusters are detected using density break-offs, connectivity and distance information. The proposed ACO-based algorithm uses the outputs of the neighborhood construction (NC) and the external shape formation. In addition, we propose a three-phase clustering algorithm that consists of NC, outlier detection and merging phases. We test the strengths and the weaknesses of the proposed approaches by extensive experimentation with data sets borrowed from literature and generated in a controlled manner. NC is found to be effective for arbitrary shaped clusters, intracluster and intercluster density variations. The external shape formation algorithm achieves significant reductions for convex clusters. The ACO-based and the three-phase clustering algorithms have promising results for the data sets having well-separated clusters.