Distributed Size-constrained Clustering Algorithm for Modular Robot-based Programmable Matter

International audienceModular robots are defined as autonomous kinematic machines withvariable morphology. They are composed of several thousands or evenmillions of modules that are able to coordinate to behaveintelligently. Clustering the modules in modular robots has manybenefits, including scalability, energy-efficiency, reducingcommunication delay, and improving the self-reconfiguration processthat focuses on finding a sequence of reconfiguration actions toconvert robots from an initial shape to a goal one. The main ideaof clustering is to divide the modules in an initial shape into anumber of groups based on the final goal shape to enhance theself-reconfiguration process by allowing clusters to reconfigure inparallel. In this work, we prove that the size-constrainedclustering problem is NP-complete, and we propose a new tree-basedsize-constrained clustering algorithm called “SC-Clust.” To showthe efficiency of our approach, we implement and demonstrate ouralgorithm in simulation on networks of up to 30000 modules and onthe Blinky Blocks hardware with up to 144 modules