Ant colony optimization is a metaheuristic approach belonging to the class of model-based search algorithms. In this paper, we propose a new framework for implementing ant colony optimization ...algorithms called the hyper-cube framework for ant colony optimization. In contrast to the usual way of implementing ant colony optimization algorithms, this framework limits the pheromone values to the interval 0,1. This is obtained by introducing changes in the pheromone value update rule. These changes can in general be applied to any pheromone value update rule used in ant colony optimization. We discuss the benefits coming with this new framework. The benefits are twofold. On the theoretical side, the new framework allows us to prove that in the ant system, the ancestor of all ant colony optimization algorithms, the average quality of the solutions produced increases in expectation over time when applied to unconstrained problems. On the practical side, the new framework automatically handles the scaling of the objective function values. We experimentally show that this leads on average to a more robust behavior of ant colony optimization algorithms.
We prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant /spl epsiv/ > 0 and for a sufficiently large number of ...algorithm iterations t, the probability of finding an optimal solution at least once is P*(t) /spl ges/ 1 - /spl epsiv/ and that this probability tends to 1 for t/spl rarr//spl infin/. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t/spl rarr//spl infin/, any fixed ant will produce the optimal solution during the tth iteration with probability P /spl ges/ 1 /spl epsiv//spl circ/(/spl tau//sub min/, /spl tau//sub max/), where /spl tau//sub min/ and /spl tau//sub max/ are the minimum and maximum values that can be taken by pheromone trails.
One of the essential benefits of swarm robotic systems is redundancy. In case one robot breaks down, another robot can take steps to repair the failed robot or take over the failed robot's task. ...Although fault tolerance and robustness to individual failures have often been central arguments in favor of swarm robotic systems, few studies have been dedicated to the subject. In this paper, we take inspiration from the synchronized flashing behavior observed in some species of fireflies. We derive a completely decentralized algorithm to detect non-operational robots in a swarm robotic system. Each robot flashes by lighting up its on-board light-emitting diodes (LEDs), and neighboring robots are driven to flash in synchrony. Since robots that are suffering catastrophic failures do not flash periodically, they can be detected by operational robots. We explore the performance of the proposed algorithm both on a real-world swarm robotic system and in simulation. We show that failed robots are detected correctly and in a timely manner, and we show that a system composed of robots with simulated self-repair capabilities can survive relatively high failure rates.
In this paper, we review half a century of research on the design of systems displaying (physical) self-assembly of macroscopic components. We report on the experience gained in the design of 21 such ...systems, exhibiting components ranging from passive mechanical parts to mobile robots. We present a taxonomy of the systems and discuss design principles and functions. Finally, we summarize the main achievements and indicate potential directions for future research.
This paper introduces the ant colony system (ACS), a distributed algorithm that is applied to the traveling salesman problem (TSP). In the ACS, a set of cooperating agents called ants cooperate to ...find good solutions to TSPs. Ants cooperate using an indirect form of communication mediated by a pheromone they deposit on the edges of the TSP graph while building solutions. We study the ACS by running experiments to understand its operation. The results show that the ACS outperforms other nature-inspired algorithms such as simulated annealing and evolutionary computation, and we conclude comparing ACS-3-opt, a version of the ACS augmented with a local search procedure, to some of the best performing algorithms for symmetric and asymmetric TSPs.
During the last decade, many variants of the original particle swarm optimization (PSO) algorithm have been proposed. In many cases, the difference between two variants can be seen as an algorithmic ...component being present in one variant but not in the other. In the first part of the paper, we present the results and insights obtained from a detailed empirical study of several PSO variants from a component difference point of view. In the second part of the paper, we propose a new PSO algorithm that combines a number of algorithmic components that showed distinct advantages in the experimental study concerning optimization speed and reliability. We call this composite algorithm Frankenstein's PSO in an analogy to the popular character of Mary Shelley's novel. Frankenstein's PSO performance evaluation shows that by integrating components in novel ways effective optimizers can be designed.
This paper introduces AntNet, a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based Monte Carlo system that was inspired ...by recent work on the ant colony metaphor for solving optimization problems. AntNet's agents concurrently explore the network and exchange collected information. The communication among the agents is indirect and asynchronous, mediated by the network itself. This form of communication is typical of social insects and is called stigmergy. We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority.
Research in social insect behaviour has provided computer scientists with powerful methods for designing distributed control and optimization algorithms. These techniques are being applied ...successfully to a variety of scientific and engineering problems. In addition to achieving good performance on a wide spectrum of 'static' problems, such techniques tend to exhibit a high degree of flexibility and robustness in a dynamic environment.
Celotno besedilo
Dostopno za:
DOBA, IJS, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
9.
Autonomous Self-Assembly in Swarm-Bots Gross, R.; Bonani, M.; Mondada, F. ...
IEEE transactions on robotics,
12/2006, Letnik:
22, Številka:
6
Journal Article
Recenzirano
Odprti dostop
In this paper, we discuss the self-assembling capabilities of the swarm-bot, a distributed robotics concept that lies at the intersection between collective and self-reconfigurable robotics. A ...swarm-bot is comprised of autonomous mobile robots called s-bots. S-bots can either act independently or self-assemble into a swarm-bot by using their grippers. We report on experiments in which we study the process that leads a group of s-bots to self-assemble. In particular, we present results of experiments in which we vary the number of s-bots (up to 16 physical robots), their starting configurations, and the properties of the terrain on which self-assembly takes place. In view of the very successful experimental results, swarm-bot qualifies as the current state of the art in autonomous self-assembly
Teamwork in Self-Organized Robot Colonies Nouyan, S.; Gross, R.; Bonani, M. ...
IEEE transactions on evolutionary computation,
08/2009, Letnik:
13, Številka:
4
Journal Article
Recenzirano
Odprti dostop
Swarm robotics draws inspiration from decentralized self-organizing biological systems in general and from the collective behavior of social insects in particular. In social insect colonies, many ...tasks are performed by higher order group or team entities, whose task-solving capacities transcend those of the individual participants. In this paper, we investigate the emergence of such higher order entities. We report on an experimental study in which a team of physical robots performs a foraging task. The robots are "identical" in hardware and control. They make little use of memory and take actions purely on the basis of local information. Our study advances the current state of the art in swarm robotics with respect to the number of real-world robots engaging in teamwork (up to 12 robots in the most challenging experiment). To the best of our knowledge, in this paper we present the first self-organized system of robots that displays a dynamical hierarchy of teamwork (with cooperation also occurring among higher order entities). Our study shows that teamwork requires neither individual recognition nor differences between individuals. This result might also contribute to the ongoing debate on the role of these characteristics in the division of labor in social insects.
PDF
