nach oben

2016 | Buch

Swarm Intelligence

10th International Conference, ANTS 2016, Brussels, Belgium, September 7-9, 2016, Proceedings

herausgegeben von: Marco Dorigo, Mauro Birattari, Xiaodong Li, Manuel López-Ibáñez, Kazuhiro Ohkura, Carlo Pinciroli, Thomas Stützle

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the proceedings of the 10th International Conference on Swarm Intelligence, ANTS 2016, held in Brussels, Belgium, in September 2016.
The 18 full papers and 7 short papers presented in this volume were carefully reviewed and selected from 47 submissions. They are devoted to the field of swarm intelligence as a whole, without any bias towards specific research directions.

Inhaltsverzeichnis

Frontmatter

Full Papers

Frontmatter

A Bearing-Only Pattern Formation Algorithm for Swarm Robotics

Abstract

Pattern formation is a useful behaviour for a swarm of robots in order to maximize their efficiency at tasks such as surveying. Previous pattern formation algorithms have relied upon various combinations of measurements (bearing, distance, heading, unique identity) of swarm mates as inputs. The ability to measure distance, heading, and identity requires significant sensory and computational capabilities which may be beyond those of a swarm of simple robots. Furthermore, the use of unique identities reduces the scalability, flexibility and robustness of the algorithm. This paper introduces a decentralized pattern formation algorithm using bearing-only measurements to anonymous neighbours as input. Initial results indicate the proposed algorithm improves upon the performance, scalability, flexibility, and robustness when compared to a benchmark algorithm.

Nicholi Shiell, Andrew Vardy

A Macroscopic Privacy Model for Heterogeneous Robot Swarms

Abstract

To date, the issues of privacy and security remain poorly addressed within robotics at large. In this work, we provide a foundation for analyzing the privacy of swarms of heterogeneous robots. Our premise is that information pertaining to individual robot types must be kept private in order to preserve the security and resilience of the swarm system at large. A main contribution is the development of a macroscopic privacy model that can be applied to swarms. Our privacy model draws from the notion of differential privacy that stems from the database literature, and that provides a stringent statistical interpretation of information leakage. We combine the privacy model with a macroscopic abstraction of the swarm system, and show how this enables an analysis of the privacy trends as swarm parameters vary.

Amanda Prorok, Vijay Kumar

A New Continuous Model for Segregation Implemented and Analyzed on Swarm Robots

Abstract

T.C. Schelling’s Dynamic Model of Segregation might be one of the most known agent based models. Macroscopic segregation is caused by microscopic preference for a specific feature in the local neighborhood. Based on Schelling’s original work we derive a spatiotemporal continuous segregation model which is implemented on a swarm of thirty Elisa-3 robots. To define the neighborhood between the entities we use the density-based spatial clustering algorithm DBSCAN. Furthermore we expand the binary decision criterion to a probabilistic approach to produce a more realistic behavior. The evaluation of our extensive experiments with the swarm of robots show that a segregation effect can be reproduced with our model similar to the observations Schelling made in his work.

Benjamin Reh, Felix Aller, Katja Mombaur

A Study of Archiving Strategies in Multi-objective PSO for Molecular Docking

Abstract

Molecular docking is a complex optimization problem aimed at predicting the position of a ligand molecule in the active site of a receptor with the lowest binding energy. This problem can be formulated as a bi-objective optimization problem by minimizing the binding energy and the Root Mean Square Deviation (RMSD) difference in the coordinates of ligands. In this context, the SMPSO multi-objective swarm-intelligence algorithm has shown a remarkable performance. SMPSO is characterized by having an external archive used to store the non-dominated solutions and also as the basis of the leader selection strategy. In this paper, we analyze several SMPSO variants based on different archiving strategies in the scope of a benchmark of molecular docking instances. Our study reveals that the SMPSOhv, which uses an hypervolume contribution based archive, shows the overall best performance.

José García-Nieto, Esteban López-Camacho, María Jesús García Godoy, Antonio J. Nebro, Juan J. Durillo, José F. Aldana-Montes

Ant Colony Optimisation-Based Classification Using Two-Dimensional Polygons

Abstract

The application of Ant Colony Optimization to the field of classification has mostly been limited to hybrid approaches which attempt at boosting the performance of existing classifiers (such as Decision Trees and Support Vector Machines (SVM)) — often through guided feature reductions or parameter optimizations.

In this paper we introduce PolyACO: A novel Ant Colony based classifier operating in two dimensional space that utilizes ray casting. To the best of our knowledge, our work is the first reported Ant Colony based classifier which is non-hybrid, in the sense, that it does not build on any legacy classifiers. The essence of the scheme is to create a separator in the feature space by imposing ant-guided random walks in a grid system. The walks are self-enclosing so that the ants return back to the starting node forming a closed classification path yielding a many edged polygon. Experimental results on both synthetic and real-life data show that our scheme is able to perfectly separate both simple and complex patterns, without utilizing “kernel tricks” and outperforming existing classifiers, such as polynomial and linear SVM. The results are impressive given the simplicity of PolyACO compared to other approaches such as SVM.

Morten Goodwin, Anis Yazidi

Collective Perception of Environmental Features in a Robot Swarm

Abstract

In order to be effective, collective decision-making strategies need to be not only fast and accurate, but sufficiently general to be ported and reused across different problem domains. In this paper, we propose a novel problem scenario, collective perception, and use it to compare three different strategies: the DMMD, DMVD, and DC strategies. The robots are required to explore their environment, estimate the frequency of certain features, and collectively perceive which feature is the most frequent. We implemented the collective perception scenario in a swarm robotics system composed of 20 e-pucks and performed robot experiments with all considered strategies. Additionally, we also deepened our study by means of physics-based simulations. The results of our performance comparison in the collective perception scenario are in agreement with previous results for a different problem domain and support the generality of the considered strategies.

Gabriele Valentini, Davide Brambilla, Heiko Hamann, Marco Dorigo

Communication Diversity in Particle Swarm Optimizers

Abstract

Since they were introduced, Particle Swarm Optimizers have suffered from early stagnation due to premature convergence. Assessing swarm spatial diversity might help to mitigate early stagnation but swarm spatial diversity itself emerges from the main property that essentially drives swarm optimizers towards convergence and distinctively distinguishes PSO from other optimization techniques: the social interaction between the particles. The swarm influence graph captures the structure of particle interactions by monitoring the information exchanges during the search process; such graph has been shown to provide a rich overall structure of the swarm information flow. In this paper, we define swarm communication diversity based on the component analysis of the swarm influence graph. We show how communication diversity relates to other measures of swarm spatial diversity as well as how each swarm topology leads to different communication signatures. Moreover, we argue that swarm communication diversity might potentially be a better way to understand early stagnation since it takes into account the (social) interactions between the particles instead of properties associated with individual particles.

Marcos Oliveira, Diego Pinheiro, Bruno Andrade, Carmelo Bastos-Filho, Ronaldo Menezes

Continuous Time Gathering of Agents with Limited Visibility and Bearing-only Sensing

Abstract

A group of mobile agents, identical, anonymous, and oblivious (memoryless), having the capacity to sense only the relative direction (bearing) to neighboring agents within a finite visibility range, are shown to gather to a meeting point in finite time by applying a very simple rule of motion. The agents’ rule of motion is: set your velocity vector to be the sum of the two unit vectors in \(\mathbb {R}^2\) pointing to your “extremal” neighbours determining the smallest visibility disc sector in which all your visible neighbors reside, provided it spans an angle smaller than \(\pi \), otherwise, since you are “surrounded” by visible neighbors, simply stay put. Of course, the initial constellation of agents must have a visibility graph that is connected, and provided this we prove that the agents gather to a common meeting point in finite time, while the distances between agents that initially see each other monotonically decreases.

Levi Itzhak Bellaiche, Alfred Bruckstein

Design and Analysis of Proximate Mechanisms for Cooperative Transport in Real Robots

Abstract

This paper describes a set of experiments in which a homogeneous group of real e-puck robots is required to coordinate their actions in order to transport cuboid objects that are too heavy to be moved by single robots. The agents controllers are dynamic neural networks synthesised through evolutionary computation techniques. To run these experiments, we designed, built, and mounted on the robots a new sensor that returns the agent displacement on the x/y plane. In this object transport scenario, this sensor generates useful feedback on the consequences of the robot actions, helping the robots to perceive whether their pushing forces are aligned with the object movement. The results of our experiments indicated that the best evolved controller can effectively operate on real robots. The group transport strategies turned out to be robust and scalable to effectively operate in a variety of conditions in which we vary physical characteristics of the object and group cardinality. From a biological perspective, the results of this study indicate that the perception of the object movement could explain how natural organisms manage to coordinate their actions to transport heavy items.

Muhanad H. Mohammed Alkilabi, Aparajit Narayan, Elio Tuci

Dynamic Task Partitioning for Foraging Robot Swarms

Abstract

Dead reckoning error is a common problem in robotics that can be caused by multiple factors related to sensors or actuators. These errors potentially cause landmarks recorded by a robot to appear in a different location with respect to the actual position of the object. In a foraging scenario with a swarm of robots, this error will ultimately lead to the robots being unable to return successfully to the food source. In order to address this issue, we propose a computationally low-cost finite state machine strategy with which robots divide the total travelling distance into a variable number of segments, thus decreasing accumulated dead-reckoning error. The distance travelled by each robot changes according to the success and failure of exploration. Our approach is more flexible than using a previously used fixed size approach for the travel distance, thus allowing swarms greater flexibility and scaling to larger areas of operation.

Edgar Buchanan, Andrew Pomfret, Jon Timmis

Human-Robot Swarm Interaction with Limited Situational Awareness

Abstract

This paper studies how an operator with limited situational awareness can collaborate with a swarm of simulated robots. The robots are distributed in an environment with wall obstructions. They aggregate autonomously but are unable to form a single cluster due to the obstructions. The operator lacks the bird’s-eye perspective, but can interact with one robot at a time, and influence the behavior of other nearby robots. We conducted a series of experiments. They show that untrained participants had marginal influence on the performance of the swarm. Expert participants succeeded in aggregating 85 % of the robots while untrained participants, with bird’s-eye view, succeeded in aggregating 90 %. This demonstrates that the controls are sufficient for operators to aid the autonomous robots in the completion of the task and that lack of situational awareness is the main difficulty. An analysis of behavioral differences reveals that trained operators learned to gain superior situational awareness.

Gabriel Kapellmann-Zafra, Nicole Salomons, Andreas Kolling, Roderich Groß

Monotonicity in Ant Colony Classification Algorithms

Abstract

Classification algorithms generally do not use existing domain knowledge during model construction. The creation of models that conflict with existing knowledge can reduce model acceptance, as users have to trust the models they use. Domain knowledge can be integrated into algorithms using semantic constraints to guide model construction. This paper proposes an extension to an existing ACO-based classification rule learner to create lists of monotonic classification rules. The proposed algorithm was compared to a majority classifier and the Ordinal Learning Model (OLM) monotonic learner. Our results show that the proposed algorithm successfully outperformed OLM’s predictive accuracy while still producing monotonic models.

James Brookhouse, Fernando E. B. Otero

Observing the Effects of Overdesign in the Automatic Design of Control Software for Robot Swarms

Abstract

We present the results of an experiment in the automatic design of control software for robot swarms. We conceived the experiment to corroborate a hypothesis that we proposed in a previous publication: the reality gap problem bears strong resemblance to the generalization problem faced in supervised learning. In particular, thanks to this experiment we observe for the first time a phenomenon that we shall call overdesign. Overdesign is the automatic design counterpart of the well known overfitting problem encountered in machine learning. Past an optimal level of the design effort, the longer the design process is protracted, the better the performance of the swarm becomes in simulation and the worst in reality. Our results show that some sort of early stopping mechanism could be beneficial.

Mauro Birattari, Brian Delhaisse, Gianpiero Francesca, Yvon Kerdoncuff

Parameter Selection in Particle Swarm Optimisation from Stochastic Stability Analysis

Abstract

Particle swarm optimisation is a metaheuristic algorithm which finds reasonable solutions in a wide range of applied problems if suitable parameters are used. We study the properties of the algorithm in the framework of random dynamical systems (RDS) which, due to the quasi-linear swarm dynamics, yields exact analytical results for the stability properties in the single particle case. The calculated stability region in the parameter space extends beyond the region determined by earlier approximations. This is also evidenced by simulations which indicate that the algorithm performs best in the asymptotic case if parameterised near the margin of instability predicted by the RDS approach.

Adam Erskine, Thomas Joyce, J. Michael Herrmann

Population Coding: A New Design Paradigm for Embodied Distributed Systems

Abstract

Designing embodied distributed systems, such as multi-robot systems, is challenging especially if the individual components have limited capabilities due to hardware restrictions. In self-organizing systems each component has only limited information and a global, organized system behavior (macro-level) has to emerge from local interactions only (micro-level). A general, structured design approach to self-organizing distributed systems is still lacking. We develop a general approach based on behaviorally heterogeneous systems. Inspired by the concept of population coding from neuroscience, we show in two case studies how designing an embodied distributed system is reduced to picking the right components from a predefined set of controller types. In this way, the design challenge is reduced to an optimization problem that can be solved by a variety of optimization techniques. Our approach is applicable to scenarios that allow for representing the component behavior as (probabilistic) finite state machine. We anticipate the paradigm of population coding to be applicable to a wide range of distributed systems.

Heiko Hamann, Gabriele Valentini, Marco Dorigo

Random Walks in Swarm Robotics: An Experiment with Kilobots

Abstract

Random walks represent fundamental search strategies for both animal and robots, especially when there are no environmental cues that can drive motion, or when the cognitive abilities of the searching agent do not support complex localisation and mapping behaviours. In swarm robotics, random walks are basic building blocks for the individual behaviour and support the emergent collective pattern. However, there has been limited account for the correct parameterisation to be used in different search scenarios, and the relationship between search efficiency and information transfer within the swarm has been often overlooked. In this study, we analyse the efficiency of random walk patterns for a swarm of Kilobots searching a static target in two different environmental conditions entailing a bounded or an open space. We study the search efficiency and the ability to spread information within the swarm through numerical simulations and real robot experiments, and we determine what kind of random walk best fits each experimental scenario.

Cristina Dimidov, Giuseppe Oriolo, Vito Trianni

Synthesizing Rulesets for Programmable Robotic Self-assembly: A Case Study Using Floating Miniaturized Robots

Abstract

Programmable stochastic self-assembly of modular robots provides promising means to formation of structures at different scales. Formalisms based on graph grammars and rule-based approaches have been previously published for controlling the self-assembly process. While several rule-synthesis algorithms have been proposed, formal synthesis of rulesets has only been shown for self-assembly of abstract graphs. Rules deployed on robotic modules are typically tuned starting from their abstract graph counterparts or designed manually. In this work, we extend the graph grammar formalism and propose a new encoding of the internal states of the robots. This allows formulating formal methods capable of automatically deriving the rules based on the morphology of the robots, in particular the number of connectors. The derived rules are directly applicable to robotic modules with no further tuning. In addition, our method allows for a reduced complexity in the rulesets. In order to illustrate the application of our method, we extend two synthesis algorithms from the literature, namely Singleton and Linchpin, to synthesize rules applicable to our floating robots. A microscopic simulation framework is developed to study the performance and transient behavior of the two algorithms. Finally, employing the generated rulesets, we conduct experiments with our robotic platform to demonstrate several assemblies.

Bahar Haghighat, Brice Platerrier, Loic Waegeli, Alcherio Martinoli

Using Ant Colony Optimization to Build Cluster-Based Classification Systems

Abstract

Learning cluster-based classification systems is the process of partitioning a training set into data subsets (clusters), and then building a local classifier for each data cluster. The class of a new instance is predicted by first assigning the instance to its nearest cluster, and then using that cluster’s local classification model to predict the instance’s class. In this paper, we use the Ant Colony Optimization (ACO) meta-heuristic to optimize the data clusters based on a given classification algorithm in an integrated cluster-with-learn manner. The proposed ACO algorithms use two different clustering solution representation approaches: instance-based and medoid-based, where in the latter the number of clusters is optimized as part of the ACO algorithm’s execution. In our experiments, we employ three widely-used classification algorithms, k-nearest neighbours, Ripper, and C4.5, and evaluate performance on 30 UCI benchmark datasets. We compare the ACO results to the traditional c-means clustering algorithm, where the data clusters are built prior to learning the local classifiers.

Khalid M. Salama, Ashraf M. Abdelbar

Short Papers

Frontmatter

A Swarm Intelligence Approach in Undersampling Majority Class

Abstract

Over the years, machine learning has been facing the issue of imbalance dataset. It occurs when the number of instances in one class significantly outnumbers the instances in the other class. This study investigates a new approach for balancing the dataset using a swarm intelligence technique, Stochastic Diffusion Search (SDS), to undersample the majority class on a direct marketing dataset. The outcome of the novel application of this swarm intelligence algorithm demonstrates promising results which encourage the possibility of undersampling a majority class by removing redundant data whist protecting the useful data in the dataset. This paper details the behaviour of the proposed algorithm in dealing with this problem and investigates the results which are contrasted against other techniques.

Haya Abdullah Alhakbani, Mohammad Majid al-Rifaie

Optimizing PolyACO Training with GPU-Based Parallelization

Abstract

A central part of Ant Colony Optimisation (ACO) is the function calculating the quality and cost of solutions, such as the distance of a potential ant route. This cost function is used to deposit an opportune amount of pheromones to achieve an apt convergence, and in an active ACO implementation a significant part of the runtime is spent in this part of the code. In some cases, the cost function accumulates up towards 94 % in its run time making it a performance bottle neck.

In this paper we parallelize and move the central parts of the cost function to Graphics Processing Unit (GPU). We further test and measure the performance using the ACO classification approach PolyACO. This GPU based parallelization has a tremendous impact on the performance. The duration of the cost function is reduced to 0.5 % of its original runtime. The over all performance of PolyACO implementation is reduced down towards a remarkable 7 % of its original running time — an improvement factor of 14.

Torry Tufteland, Guro Ødesneltvedt, Morten Goodwin

Motion Reconstruction of Swarm-Like Self-organized Motor Bike Traffic from Public Videos

Abstract

The process of modeling swarm behaviour based on natural phenomena usually involves the comparison to real world motion data. Our research focuses on analyzing and reproducing realistic behavior of self-organized traffic of motorbikes as it can be observed in some Asian metropoles such as Hanoi or Ho Chi Minh City. We introduce a semi-automatic method to extract motion trajectories of motorbikes in dense traffic situations from public video material. This technique can also be applied to other scenarios with a high density of entities that are only partialally visible on the video frame. To reconstruct these motions as trajectories on the ground plane, the camera pose is estimated using hints found in the videos. In addition we introduce a geometrical model for the locomotion of bikes which enables us to reconstruct the steering angle from the trajectories which gives more insight to the decision making process of the driver. A controlled experiment presented in this paper verifies the validity of our methods.

Benjamin Reh, Katja Mombaur

On Heterogeneity in Foraging by Ant-Like Colony: How Local Affects Global and Vice Versa

Abstract

In this paper, we discuss influence of heterogeneity in ant-like colony, i.e., how the ratio of individuals (ants) obeying two different action rules affects the behavior of whole colony. For this purpose, we focus on the foraging task – searching the field for food sources, transporting the food packets to the nest. The two types of ants include what we call hard-working and lazy ants, and we perform statistical analyses to show that moderate existence of the lazy ants would boost efficient food transportation; in particular, we point out that the lazy ants play as explorer of newly emerged food sources, but also as global sensor to capture global information through their local experience, thanks to their moving-around behavior. Based on these observations, we propose a distributed estimation method of global information, i.e., to estimate the global mixture ratio by local encounter frequency with other lazy ants. Finally, we expand the estimation method to distributed control strategy of the global mixture ratio, called on-line switching strategy, where every ant dynamically alternates its obeying rules from the hard-working to the lazy and vice versa, based on its local encounter experience.

Yuichiro Sueoka, Kazuki Nakayama, Masato Ishikawa, Yasuhiro Sugimoto, Koichi Osuka

On Stochastic Broadcast Control of Swarms

Abstract

We present a model for controlling swarms of mobile agents via a broadcast control, detected by a random number of agents in the swarm. The agents that detect the control signal become the ad-hoc leaders of the swarm, while they detect the exogenous control. The agents are assumed to be velocity controlled, identical, anonymous, oblivious units with unlimited visibility. Assuming unlimited visibility decouples the problem of emergent behavior in a swarm from that of keeping the visibility graph complete, which has been thoroughly discussed in [10]. Each agent applies a linear local gathering control, based on the relative position of its neighbors. The detected exogenous control is superimposed by the leaders on the local gathering control. We show that in each time interval of a piecewise constant system, where the system evolves as a time-independent dynamic linear system, the swarm asymptotically aligns on a line in the direction of the exogenous control and all the agents move with identical speed. The speed of the swarm is set by the ratio between the numbers of agents receiving the control signal and the total number of agents in the swarm. A new time interval is triggered by a change in the broadcast control signal or in the agents detecting it, i.e. the “leadership team”.

Ilana Segall, Alfred Bruckstein

Route Assignment for Autonomous Vehicles

Abstract

We demonstrate a self-organizing, multi-agent system to generate approximate solutions to the route assignment problem for a large number of vehicles across many origins and destinations. Our algorithm produces a set of mixed strategies over the set of paths through the network, which are suitable for use by autonomous vehicles in the absence of centralized control or coordination. Our approach combines ideas from co-evolutionary dynamics in which many species coordinate and compete for efficient navigation, and ideas from swarm intelligence in which many simple agents self-organize into successful behavior using limited inter-agent communication. Experiments demonstrate a marked improvement of both individual and total travel times as compared to greedy uncoordinated strategies, and we analyze the differences in outcomes for various routes as the simulation progresses.

Nick Moran, Jordan Pollack

Stealing Items More Efficiently with Ants: A Swarm Intelligence Approach to the Travelling Thief Problem

Abstract

The travelling thief problem (TTP) is an academic combinatorial optimisation problem in which its two components, namely the travelling salesperson problem (TSP) and the knapsack problem, interact. The goal is to provide to a thief a tour across all given cities and a packing plan that defines which items should be taken in which city. The combining elements are the knapsack’s renting rate that is to be paid for the travel time, and the thief’s slowdown with increasing knapsack use. Previously, successful algorithms focussed almost exclusively on constructing packing plans for near-optimal TSP tours. Even though additional hill-climbers are used at times, this strong initial bias prevents them from finding better solutions that require longer tours that can give rise to more profitable packing plans. Our swarm intelligence approach shifts the focus away from good TSP tours to good TTP tours. In our study we observe that this is effective and computationally efficient, as we outperform state-of-the-art approaches on instances with up to 250 cities and 2000 items, sometimes by more than 10 %.

Markus Wagner

Backmatter

Titel: Swarm Intelligence
herausgegeben von: Marco Dorigo
Mauro Birattari
Xiaodong Li
Manuel López-Ibáñez
Kazuhiro Ohkura
Carlo Pinciroli
Thomas Stützle
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-44427-7
Print ISBN: 978-3-319-44426-0
DOI: https://doi.org/10.1007/978-3-319-44427-7