Analysis of Collective Behavior in Robot Swarms

Abstract

This thesis develops new mathematical tools to aid in the design of robot swarmsconsisting of large numbers of simple robots. It develops new ways of measuring these systems, mechanisms to understand how these “simple” systems can nonetheless act intelligently, and models for predicting their behavior under different conditions. Using this tools, future robotic systems will be are more understandable and have better guarantees of individual and collective behavior. The contributions of this thesis are fourfold. First, metrics for quantifying the observable swarm properties of self- organization, scalability, flexibility to changing external environments, and robustness to internal system stimuli, such as sensor and actuator noise and robot failures, are derived. Researcher intuitions about comparative algorithm performance are shown to be well supported by the quantitative results obtained using the derived metrics. Second, the origin of emergent intelligence in task allocating swarms is investigated. Task allocation within the context of relational task graphs with different average node centralities is used to compare an optimal (under constraints) greedy method, which disregards task dependencies, with a non-optimal dependency-aware method which emphasizes collective learning of graph structure. Results show that swarm emergent intelligence is (a) positively correlated with average node centrality and performance, and (b) arises out of learning and exploitation of graph connectivity, rather than content. Third, we determine that the underlying collective dynamics of object gathering in robot swarms can (sometimes) be captured using Poisson-based modeling even when the phenomena modeled are not Poisson distributed, thereby establishing better limits on when Poisson-based modeling can be applied to swarm behaviors. Fourth, we develop some initial properties for graphs representing 3D structures as a partial solution to the parallel bricklayer problem. With these properties, we prove the existence of an appropriate algorithm with which a swarm of N robots can provably construct a 3D structure starting from an empty state.