TY - CONF AB - Consider n nodes connected to a single coordinator. Each node receives an individual online data stream of numbers and, at any point in time, the coordinator has to know the k nodes currently observing the largest values, for a given k between 1 and n. We design and analyze an algorithm that solves this problem while bounding the amount of messages exchanged between the nodes and the coordinator. Our algorithm employs the idea of using filters which, intuitively speaking, leads to few messages to be sent, if the new input is "similar" to the previous ones. The algorithm uses a number of messages that is on expectation by a factor of O((log {\Delta} + k) log n) larger than that of an offline algorithm that sets filters in an optimal way, where {\Delta} is upper bounded by the largest value observed by any node. AU - Mäcker, Alexander AU - Malatyali, Manuel AU - Meyer auf der Heide, Friedhelm ID - 16460 T2 - Proceedings of the 29th International Parallel and Distributed Processing Symposium (IPDPS) TI - Online Top-k-Position Monitoring of Distributed Data Streams ER - TY - JOUR AU - Degener, Bastian AU - Kempkes, Barbara AU - Kling, Peter AU - Meyer auf der Heide, Friedhelm ID - 16391 JF - ACM Transactions on Parallel Computing SN - 2329-4949 TI - Linear and Competitive Strategies for Continuous Robot Formation Problems ER - TY - GEN AB - In the gathering problem, n autonomous robots have to meet on a single point. We consider the gathering of a closed chain of point-shaped, anonymous robots on a grid. The robots only have local knowledge about a constant number of neighboring robots along the chain in both directions. Actions are performed in the fully synchronous time model FSYNC. Every robot has a limited memory that may contain one timestamp of the global clock, also visible to its direct neighbors. In this synchronous time model, there is no limited view gathering algorithm known to perform better than in quadratic runtime. The configurations that show the quadratic lower bound are closed chains. In this paper, we present the first sub-quadratic---in fact linear time---gathering algorithm for closed chains on a grid. AU - Abshoff, Sebastian AU - Andreas Cord-Landwehr, Andreas AU - Jung, Daniel AU - Meyer auf der Heide, Friedhelm ID - 16397 T2 - ArXiv: 1501.04877 TI - Towards Gathering Robots with Limited View in Linear Time: The Closed Chain Case ER - TY - CONF AU - Hamann, Heiko AU - Karsai, Istvan AU - Schmickl, Thomas AU - Hilbun, Allison ID - 20007 T2 - Symposium on Biomathematics and Ecology: Education and Research TI - The common stomach: Organizing task allocation in wasp societies ER - TY - CONF AU - Hamann, Heiko AU - Valentini, Gabriele ID - 20008 SN - 0302-9743 T2 - Ninth Int. Conf. on Swarm Intelligence (ANTS 2014) TI - Swarm in a Fly Bottle: Feedback-Based Analysis of Self-organizing Temporary Lock-ins ER - TY - JOUR AB - A grand challenge in the field of artificial life is to find a general theory of emergent self-organizing systems. In swarm systems most of the observed complexity is based on motion of simple entities. Similarly, statistical mechanics focuses on collective properties induced by the motion of many interacting particles. In this article we apply methods from statistical mechanics to swarm systems. We try to explain the emergent behavior of a simulated swarm by applying methods based on the fluctuation theorem. Empirical results indicate that swarms are able to produce negative entropy within an isolated subsystem due to frozen accidents. Individuals of a swarm are able to locally detect fluctuations of the global entropy measure and store them, if they are negative entropy productions. By accumulating these stored fluctuations over time the swarm as a whole is producing negative entropy and the system ends up in an ordered state. We claim that this indicates the existence of an inverted fluctuation theorem for emergent self-organizing dissipative systems. This approach bears the potential of general applicability. AU - Hamann, Heiko AU - Schmickl, Thomas AU - Crailsheim, Karl ID - 20120 IS - 1 JF - Artificial Life TI - Analysis of Swarm Behaviors Based on an Inversion of the Fluctuation Theorem VL - 20 ER - TY - CONF AB - Collective decision making in self-organized systems is challenging because it relies on local perception and local communication. Globally defined qualities such as consensus time and decision accuracy are both difficult to predict and difficult to guarantee. We present the weighted voter model which implements a self-organized collective decision making process. We provide an ODE model, a master equation model (numerically solved by the Gillespie algorithm), and agent-based simulations of the proposed decision-making strategy. This set of models enables us to investigate the system behavior in the thermodynamic limit and to investigate finite-size effects due to random fluctuations. Based on our results, we give minimum requirements to guarantee consensus on the optimal decision, a minimum swarm size to guarantee a certain accuracy, and we show that the proposed approach scales with system size and is robust to noise. AU - Dorigo, Marco AU - Hamann, Heiko AU - Valentini, Gabriele AU - Lomuscio, Alessio AU - Scerri, Paul AU - Bazzan, Ana AU - Huhns, Michael ID - 20121 T2 - Proceedings of the 13th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2014) TI - Self-Organized Collective Decision Making: The Weighted Voter Model ER - TY - CONF AU - Hamann, Heiko ID - 20126 T2 - Int. Conf. on Genetic and Evolutionary Computation (GECCO 2014) TI - Evolving Prediction Machines: Collective Behaviors Based on Minimal Surprisal ER - TY - CONF AU - Birattari, Mauro AU - Dorigo, Marco AU - Hamann, Heiko AU - Garnier, Simon AU - Montes de Oca, Marco AU - Solnon, Christine AU - Stuetzle, Thomas AU - Ding, Hongli ID - 20127 T2 - Ninth Int. Conf. on Swarm Intelligence (ANTS 2014) TI - Sorting in Swarm Robots Using Communication-Based Cluster Size Estimation VL - 8667 ER - TY - CHAP AU - Khaluf, Yara AU - Dorigo, Marco AU - Hamann, Heiko AU - Valentini, Gabriele AU - Bartz-Beielstein, T. ID - 20128 T2 - 13th International Conference on Parallel Problem Solving from Nature (PPSN 2014) TI - Derivation of a Micro-Macro Link for Collective Decision-Making Systems: Uncover Network Features Based on Drift Measurements VL - 8672 ER -