Linear Distributed Clustering Algorithm for Modular Robots Based Programmable Matter

Modular robots are defined as autonomous kinematic machines with variable morphology. They are composed of several thousands or even millions of modules which are able to coordinate in order to behave intelligently. Clustering the modules in modular robots has many benefits, including scalability, energy-efficiency, reducing communication delay and improving the self-configuration processes that focuses on finding a sequence of reconfiguration actions to convert robots from an initial configuration to a goal one. The main idea is to divide the nodes in an initial shape into some clusters based on the final goal shape in order to reduce the time complexity and enhance the self-reconfiguration tasks. In this paper, we propose a robust clustering approach based on a distributed density-cut graph algorithm to divide the networks into a pre-defined number of clusters based on the final goal shape. The result is an algorithm with linear complexity that scales to large modular robot systems. We implement and demonstrate our algorithm on a real Blinky Blocks system and evaluate it in simulation on networks of up to 30,000 modules.