New Models of Self-Organized Multi-Robot Clustering

Abstract

For self-organized multi-robot systems, one of the widely studied task domains is object clustering, which involves gathering randomly scattered objects into a single pile. Earlier studies have pointed out that environment boundaries influence the cluster formation process, generally causing clusters to form around the perimeter rather than centrally within the workspace. Nevertheless, prior analytical models ignore boundary effects and employ the simplifying assumption that clusters pack into rotationally symmetric forms. In this study, we attempt to solve the problem of the boundary interference in object clustering. We propose new behaviors, twisting and digging, which exploit the geometry of the object to detach objects from the boundaries and cover different regions within the workplace. Also, we derive a set of conditions that is required to prevent boundaries causing perimeter clusters, developing a mathematical model to explain how multiple clusters evolve into a single cluster. Through analysis of the model, we show that the time-averaged spatial densities of the robots play a significant role in producing conditions which ensure that a single central cluster emerges and validate it with experiments. We further seek to understand the clustering process more broadly by investigating the problem of clustering in settings involving different object geometries. We initiate a study of this important area by considering a variety of rectangular objects that produce diverse shapes according to different packing arrangements. In addition, on the basis of the observation that cluster shape reflects object geometry, we develop cluster models that describe clustering dynamics across different object geometries. Also, we attempt to address the question of how to maximize the system performance by computing a policy for altering the robot division of labor as a function of time. We consider a sequencing strategy based on the hypothesis that since the clustering performance is influenced by the division of labor, it can be improved by sequencing different divisions of labor. We develop a stochastic model to predict clustering behavior and propose a method that uses the model's predictions to select a sequential change in labor distribution. We validate our proposed method that increases clustering performance on physical robot experiments.