Search

Hierarchical frameworks—a special class of directed frameworks with a layer-by-layer architecture—can be an effective mechanism to coordinate robot swarms. Their effectiveness was recently demonstrated by the mergeable nervous systems paradigm (Mathews et al., 2017), in which a robot swarm can switch dynamically between distributed and centralized control depending on the task, using self-organized hierarchical frameworks. New theoretical foundations are required to use this paradigm for formation control of large swarms. In particular, the systematic and mathematically analyzable organization and reorganization of hierarchical frameworks in a robot swarm is still an open problem. Although methods for framework construction and formation maintenance via rigidity theory exist in the literature, they do not address cases of hierarchy in a robot swarm. In this article, we extend bearing rigidity to directed topologies and extend the Henneberg constructions to generate self-organized hierarchical frameworks with bearing rigidity. We investigate three-key self-reconfiguration problems: 1) framework merging; 2) robot departure; and 3) framework splitting. We also derive the mathematical conditions of these problems and then develop algorithms that preserve rigidity and hierarchy using only local information. Our approach can be used for formation control generally, as in principle it can be coupled with any control law that makes use of bearing rigidity. To demonstrate and validate our proposed hierarchical frameworks and methods, we apply them to four scenarios of reactive formation control using an example control law.

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.12.005 Byline: Prasanna Balaprakash, Mauro Birattari, Thomas Stutzle, Marco Dorigo Abstract: The probabilistic traveling salesman problem (PTSP) is a central problem in stochastic routing. Recently, we have shown that empirical estimation is a promising approach to devise highly effective local search algorithms for the PTSP. In this paper, we customize two metaheuristics, an iterated local search algorithm and a memetic algorithm, to solve the PTSP. This customization consists in adopting the estimation approach to evaluate the solution cost, exploiting a recently developed estimation-based local search algorithm, and tuning the metaheuristics parameters. We present an experimental study of the estimation-based metaheuristic algorithms on a number of instance classes. The results show that the proposed algorithms are highly effective and that they define a new state-of-the-art for the PTSP. Author Affiliation: IRIDIA, CoDE, Universite Libre de Bruxelles, Brussels, Belgium

We examine the ability of a swarm robotic system to transport cooperatively objects of different shapes and sizes. We simulate a group of autonomous mobile robots that can physically connect to each other and to the transported object. Controllers – artificial neural networks – are synthesised by an evolutionary algorithm. They are trained to let the robots self-assemble, that is, organise into collective physical structures and transport the object towards a target location. We quantify the performance and the behaviour of the group. We show that the group can cope fairly well with objects of different geometries as well as with sudden changes in the target location. Moreover, we show that larger groups, which are made of up to 16 robots, make possible the transport of heavier objects. Finally, we discuss the limitations of the system in terms of task complexity, scalability and fault tolerance and point out potential directions for future research.

This article illustrates the methods and results of two sets of experiments in which a group of mobile robots, called s-bots, are required to physically connect to each other, that is, to self-assemble, to cope with environmental conditions that prevent them from carrying out their task individually. The first set of experiments is a pioneering study on the utility of self-assembling robots to address relatively complex scenarios, such as cooperative object transport. The results of our work suggest that the s-bots possess hardware characteristics which facilitate the design of control mechanisms for autonomous self-assembly. The control architecture we developed proved particularly successful in guiding the robots engaged in the cooperative transport task. However, the results also showed that some features of the robots' controllers had a disruptive effect on their performances. The second set of experiments is an attempt to enhance the adaptiveness of our multi-robot system. In particular, we aim to synthesise an integrated (i.e., not-modular) decision-making mechanism which allows the s-bot to autonomously decide whether or not environmental contingencies require self-assembly. The results show that it is possible to synthesize, by using evolutionary computation techniques, artificial neural networks that integrate both the mechanisms for sensory-motor coordination and for decision making required by the robots in the context of self-assembly.

In this article, we analyze the behavior of a group of robots involved in an object retrieval task. The robots' control system is inspired by a model of ants' foraging. This model emphasizes the role of learning in the individual. Individuals adapt to the environment using only locally available information. We show that a simple parameter adaptation is an effective way to improve the efficiency of the group and that it brings forth division of labor between the members of the group. Moreover, robots that are best at retrieving have a higher probability of becoming active retrievers. This selection of the best members does not use any explicit representation of individual capabilities. We analyze this system and point out its strengths and its weaknesses.

A number of methodological papers published during the last years testify that a need for a thorough revision of the research methodology is felt by the operations research community – see, for example, [Barr et al., J. Heuristics1(1995) 9–32; Eiben and Jelasity, Proceedings of the 2002 Congress on Evolutionary Computation (CEC'2002)582–587; Hooker, J. Heuristics1(1995) 33–42; Rardin and Uzsoy, J. Heuristics7(2001) 261–304]. In particular, the performance evaluation of nondeterministic methods, including widely studied metaheuristics such as evolutionary computation and ant colony optimization, requires the definition of new experimental protocols. A careful and thorough analysis of the problem of evaluating metaheuristics reveals strong similarities between this problem and the problem of evaluating learning methods in the machine learning field. In this paper, we show that several conceptual tools commonly used in machine learning – such as, for example, the probabilistic notion of class of instances and the separation between the training and the testing datasets – fit naturally in the context of metaheuristics evaluation. Accordingly, we propose and discuss some principles inspired by the experimental practice in machine learning for guiding the performance evaluation of optimization algorithms. Among these principles, a clear separation between the instances that are used for tuning algorithms and those that are used in the actual evaluation is particularly important for a proper assessment.

A number of methodological papers published during the last years testify that a need for a thorough revision of the research methodology is felt by the operations research community ? see, for example, [Barr et al., J. Heuristics 1 (1995) 9?32; Eiben and Jelasity, Proceedings of the 2002 Congress on Evolutionary Computation (CEC'2002) 582?587; Hooker, J. Heuristics 1 (1995) 33?42; Rardin and Uzsoy, J. Heuristics 7 (2001) 261?304]. In particular, the performance evaluation of nondeterministic methods, including widely studied metaheuristics such as evolutionary computation and ant colony optimization, requires the definition of new experimental protocols. A careful and thorough analysis of the problem of evaluating metaheuristics reveals strong similarities between this problem and the problem of evaluating learning methods in the machine learning field. In this paper, we show that several conceptual tools commonly used in machine learning ? such as, for example, the probabilistic notion of class of instances and the separation between the training and the testing datasets ? fit naturally in the context of metaheuristics evaluation. Accordingly, we propose and discuss some principles inspired by the experimental practice in machine learning for guiding the performance evaluation of optimization algorithms. Among these principles, a clear separation between the instances that are used for tuning algorithms and those that are used in the actual evaluation is particularly important for a proper assessment.

The swarm intelligence paradigm has proven to have very interesting properties such as robustness, flexibility and ability to solve complex problems exploiting parallelism and self-organization. Several robotics implementations of this paradigm confirm that these properties can be exploited for the control of a population of physically independent mobile robots. The work presented here introduces a new robotic concept called swarm-botin which the collective interaction exploited by the swarm intelligence mechanism goes beyond the control layer and is extended to the physical level. This implies the addition of new mechanical functionalities on the single robot, together with new electronics and software to manage it. These new functionalities, even if not directly related to mobility and navigation, allow to address complex mobile robotics problems, such as extreme all-terrain exploration. The work shows also how this new concept is investigated using a simulation tool (swarmbot3d) specifically developed for quickly designing and evaluating new control algorithms. Experimental work shows how the simulated detailed representation of one s-bothas been calibrated to match the behaviour of the real robot.

In this paper, we introduce a self-assembling and self-organizing artifact, called a swarm-bot, composed of a swarm of s-bots, mobile robots with the ability to connect to and to disconnect from each other. We discuss the challenges involved in controlling a swarm-botand address the problem of synthesizing controllers for the swarm-botusing artificial evolution. Specifically, we study aggregation and coordinated motion of the swarm-botusing a physics-based simulation of the system. Experiments, using a simplified simulation model of the s-bots, show that evolution can discover simple but effective controllers for both the aggregation and the coordinated motion of the swarm-bot. Analysis of the evolved controllers shows that they have properties of scalability, that is, they continue to be effective for larger group sizes, and of generality, that is, they produce similar behaviors for configurations different from those they were originally evolved for. The portability of the evolved controllers to real s-botsis tested using a detailed simulation model which has been validated against the real s-botsin a companion paper in this same special issue.

The development of the new TOGA (titration and off-gas analysis) sensor for the detailed study of biological processes in wastewater treatment systems is outlined. The main innovation of the sensor is the amalgamation of titrimetric and off-gas measurement techniques. The resulting measured signals are: hydrogen ion production rate (HPR), oxygen transfer rate (OTR), nitrogen transfer rate (NTR), and carbon dioxide transfer rate (CTR). While OTR and NTR are applicable to aerobic and anoxic conditions, respectively, HPR and CTR are useful signals under all of the conditions found in biological wastewater treatment systems, namely, aerobic, anoxic and anaerobic. The sensor is therefore a powerful tool for studying the key biological processes under all these conditions. A major benefit from the integration of the titrimetric and off-gas analysis methods is that the acid/base buffering systems, in particular the bicarbonate system, are properly accounted for. Experimental data resulting from the TOGA sensor in aerobic, anoxic, and anaerobic conditions demonstrates the strength of the new sensor. In the aerobic environment, carbon oxidation (using acetate as an example carbon source) and nitrification are studied. Both the carbon and ammonia removal rates measured by the sensor compare very well with those obtained from off-line chemical analysis. Further, the aerobic acetate removal process is examined at a fundamental level using the metabolic pathway and stoichiometry established in the literature, whereby the rate of formation of storage products is identified. Under anoxic conditions, the denitrification process is monitored and, again, the measured rate of nitrogen gas transfer (NTR) matches well with the removal of the oxidised nitrogen compounds (measured chemically). In the anaerobic environment, the enhanced biological phosphorus process was investigated. In this case, the measured sensor signals (HPR and CTR) resulting from acetate uptake were used to determine the ratio of the rates of carbon dioxide production by competing groups of microorganisms, which consequently is a measure of the activity of these organisms. The sensor involves the use of expensive equipment such as a mass spectrometer and requires special gases to operate, thus incurring significant capital and operational costs. This makes the sensor more an advanced laboratory tool than an on-line sensor. © 2003 Wiley Periodicals, Inc. Biotechnol Bioeng 81: 482–495, 2003.

In this paper we present the results of an investigation of the possibilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial optimization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical structure for the objective function, and of the neighborhood search operators which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to the specific case of the generation of a school timetable. We compare the results obtained by simu lated annealing, tabu search and two versions, with and without local search, of the genetic algorithm. Our results show that GA with local search and tabu search based on temporary problem relaxations both outperform simulated annealing and handmade timetables.

In this article we investigate the feasibility of using learning classifier systems as a tool for building adaptive control systems for real robots. Their use on real robots imposes efficiency constraints which are addressed by three main tools: parallelism, distributed architecture, and training. Parallelism is useful to speed up computation and to increase the flexibility of the learning system design. Distributed architecture helps in making it possible to decompose the overall task into a set of simpler learning tasks. Finally, training provides guidance to the system while learning, shortening the number of cycles required to learn. These tools and the issues they raise are first studied in simulation, and then the experience gained with simulations is used to implement the learning system on the real robot. Results have shown that with this approach it is possible to let the AutonoMouse, a small real robot, learn to approach a light source under a number of different noise and lesion conditions.

This article is concerned with training an agent to perform sequential behavior. In previous work, we have been applying reinforcement learning techniques to control a reactive agent. Obviously, a purely reactive system is limited in the kind of interactions it can learn. In particular, it can learn what we call pseudosequences—that is, sequences of actions in which each action is selected on the basis of current sensory stimuli. It cannot learn proper sequences, in which actions must be selected also on the basis of some internal state. Moreover, it is a result of our research that effective learning of proper sequences is improved by letting the agent and the trainer communicate. First, we consider trainer-to-agent communication, introducing the concept of reinforcement sensor, which lets the learning robot explicitly know whether the last reinforcement was a reward or a punishment. We also show how the use of this sensor makes error recovery rules emerge. Then we introduce agent-to-trainer communication, which is used to disambiguate ambiguous training situations—that is, situations in which the observation of the agent's behavior does not provide the trainer with enough information to decide whether the agent's move is right or wrong. We also show an alternative solution to the problem of ambiguous situations, which involves learning to coordinate behavior in a simpler, unambiguous setting and then transferring what has been learned to a more complex situation. All the design choices we make are discussed and compared by means of experiments in a simulated world.

It is well known that standard learning classifier systems, when applied to many different domains, exhibit a number of problems: payoff oscillation, difficulty in regulating interplay between the reward system and the background genetic algorithm (GA), rule chains' instability, default hierarchies' instability, among others. ALECSYS is a parallel version of a standard learning classifier system (CS) and, as such, suffers from these same problems. In this paper we propose some innovative solutions to some of these problems. We introduce the following original features. Mutespecis a new genetic operator used to specialize potentially useful classifiers. Energyis a quantity introduced to measure global convergence to apply the genetic algorithm only when the system is close to a steady state. Dynamic adjustmentof the classifiers set cardinality speeds up the performance phase of the algorithm. We present simulation results of experiments run in a simulated two-dimensional world in which a simple agent learns to follow a light source.

We introduce zePPeLIN, a distributed system designed to address the challenges of path planning in large, cluttered, dynamic environments. The objective is to define a sequence of instructions to precisely move a ground object (e.g., a mobile robot) from an initial to a final configuration in an environment. zePPeLIN is based on a set of wirelessly networked overhead cameras. While each camera only covers a limited environment portion, the camera set fully covers the environment through the union of its fields of view. Path planning is performed in a fully distributed and cooperative way, based on potential diffusion over local Voronoi skeletons and local message exchanging. Additionally, the control of the moving object is fully distributed: it receives movement instructions from each camera when it enters that camera's field of view. The overall task is made particularly challenging by intrinsic errors in the overlap in cameras' fields of view. We study the performance of the system as a function of these errors, as well as its scalability for the size and density of the camera network. We also propose a few heuristics to improve performance and computational and communication efficiency. The reported results include both extensive simulation experiments and validation using a real camera network planning for a two-robot system.

The improvement of odometry systems in collective robotics remains an important challenge for several applications. Social odometry is an online social dynamics which confers the robots the possibility to learn from the others. Robots neither share any movement constraint nor access to centralized information. Each robot has an estimate of its own location and an associated confidence level that decreases with distance traveled. Social odometry guides a robot to its goal by imitating estimated locations, confidence levels and actual locations of its neighbors. This simple online social form of odometry is shown to produce a self-organized collective pattern which allows a group of robots to both increase the quality of individuals' estimates and efficiently improve their collective performance.