A Survey of Clustering Algorithms for Self-Reconfiguration on Programmable Matter

Self-reconfiguration is a challenge for the deployment of modular robotics. Building a large number of self-configurable robots consisting of a bunch of modules is the ideal approach to implement programmable matter. The latter is a set of particles or modules that combine to form a desired object. It is composed of a set of micro-robots, mobile computers of millimetric size that will have the ability to move around each other, communicate, change colors and lock on other micro-robots to form different shapes. It is applied in several fields such as surgery, construction, nuclear, environment, … These particles are deployed in unmonitored environments, or the modules cannot be charged, so size and energy constraints are the most critical issues to consider before deploying the system. Clustering modules in modular robots is a challenge to facilitate self-reconfiguration. Self-configuration clustering algorithms are used to overcome communication problems, energy limits, aggregation modules during auto-configuration. In this paper, after reviewing clustering algorithms in sensor networks and graphs, we study self-configuration based on clustering algorithms for existing modular robot systems. After a comparative study of algorithms, the proposed solutions try to facilitate communication, reduce execution time and the number of messages exchanged during the self-configuration process.