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.

Swarm robotics is a young multidisciplinary research field at the<p>intersection of disciplines such as distributed systems, robotics,<p>artificial intelligence, and complex systems. Considerable research<p>effort has been dedicated to the study of algorithms targeted to<p>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<p>community. The very nature of swarm robotics, in which systems may comprise large numbers of robots, forces the design to provide<p>runtimes that increase gracefully with increasing swarm sizes.<p><p>In this thesis, I argue that none of the existing simulators offers<p>satisfactory levels of accuracy, flexibility, and efficiency, due to<p>fundamental limitations of their design. To overcome these<p>limitations, I present ARGoS---a general, multi-robot simulator that<p>currently benchmarks as the fastest in the literature.<p><p>In the design of ARGoS, I faced a number of unsolved issues. First, in existing simulators, accuracy is an intrinsic feature of the<p>design. For single-robot applications this choice is reasonable, but<p>for the large number of robots typically involved in a swarm, it<p>results in an unacceptable trade-off between accuracy and<p>efficiency. Second, the prospect of swarm robotics spans diverse<p>potential applications, such as space exploration, ocean restoration,<p>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.<p><p>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.<p><p>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.<p><p>A further unique feature of ARGoS is the possibility to partition the<p>simulated space in regions managed by dedicated physics engines<p>running in parallel. This feature, besides enhancing parallelism,<p>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.<p><p>ARGoS is listed among the major results of the Swarmanoid<p>project. It is currently<p>the official simulator of 4 European projects<p>(ASCENS, H2SWARM, E-SWARM, Swarmix) and is used by 15<p>universities worldwide. While the core architecture of ARGoS is<p>complete, extensions are continually added by a community of<p>contributors. In particular, ARGoS was the first robot simulator to be<p>integrated with the ns3 network simulator, yielding a software<p>able to simulate both the physics and the network aspects of a<p>swarm. Further extensions under development include support for<p>large-scale modular robots, construction of 3D structures with<p>deformable material, and integration with advanced statistical<p>analysis tools such as MultiVeStA. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Thesis submitted in compliance with the requirements for the Master's Degree in Technology: Electrical Engineering - Light Current, Durban University of Technology, Department of Electronic Engineering, 2008. / Linear control systems can be easily tuned using classical tuning techniques such as the Ziegler-Nichols and Cohen-Coon tuning formulae. Empirical studies have found that these conventional tuning methods result in an unsatisfactory control performance when they are used for processes experiencing the negative destabilizing effects of strong nonlinearities. It is for this reason that control practitioners often prefer to tune most nonlinear systems using trial and error tuning, or intuitive tuning. A need therefore exists for the development of a suitable tuning technique that is applicable for a wide range of control loops that do not respond satisfactorily to conventional tuning. Emerging technologies such as Swarm Intelligence (SI) have been utilized to solve many non-linear engineering problems. Particle Swarm Optimization (PSO), developed by Eberhart and Kennedy (1995), is a sub-field of SI and was inspired by swarming patterns occurring in nature such as flocking birds. It was observed that each individual exchanges previous experience, hence knowledge of the “best position” attained by an individual becomes globally known. In the study, the problem of identifying the PID controller parameters is considered as an optimization problem. An attempt has been made to determine the PID parameters employing the PSO technique. A wide range of typical process models commonly encountered in industry is used to assess the efficacy of the PSO methodology. Comparisons are made between the PSO technique and other conventional methods using simulations and real-time control. / National Research Foundation

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. 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. 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.

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. 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. 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. 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. 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. 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. 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.

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.

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.

University of Macau / Faculty of Science and Technology. / Department of Computer and Information Science

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.

With the rapid growth of data and computational needs, distributed systems and computational Grids are gaining more and more attention. Grids are playing an important and growing role in today networks. The huge amount of computations a Grid can fulfill in a specificc time cannot be done by the best super computers. However, Grid performance can still be improved by making sure all the resources available in the Grid are utilized by a good load balancing algorithm. The purpose of such algorithms is to make sure all nodes are equally involved in Grid computations. This research proposes two new distributed swarm intelligence inspired load balancing algorithms. One is based on ant colony optimization and is called AntZ, the other one is based on particle swarm optimization and is called ParticleZ. Distributed load balancing does not incorporate a single point of failure in the system. In the AntZ algorithm, an ant is invoked in response to submitting a job to the Grid and this ant surfs the network to find the best resource to deliver the job to. In the ParticleZ algorithm, each node plays a role as a particle and moves toward other particles by sharing its workload among them. We will be simulating our proposed approaches using a Grid simulation toolkit (GridSim) dedicated to Grid simulations. The performance of the algorithms will be evaluated using several performance criteria (e.g. makespan and load balancing level). A comparison of our proposed approaches with a classical approach called State Broadcast Algorithm and two random approaches will also be provided. Experimental results show the proposed algorithms (AntZ and ParticleZ) can perform very well in a Grid environment. In particular, the use of particle swarm optimization, which has not been addressed in the literature, can yield better performance results in many scenarios than the ant colony approach.