A Rule Synthesis Algorithm for Programmable Stochastic Self-Assembly of Robotic Modules

Programmable self-assembly of modular robots offers promising means for structure formation at different scales. Rule-based approaches have been previously employed for distributed control of stochastic self-assembly processes. The assembly rate in the process directly depends on the concurrency level induced by the employed ruleset, i.e. the number of concurrent steps necessary to build one instance of the target structure. Our aim here is to design a formal synthesis algorithm to automatically derive rulesets of high concurrency for a given target structure composed of robotic modules. In the literature, self-assembly of (simulated or real) robotic modules has been realized through manually designed rulesets or manually adjusted rulesets generated by employing graph-grammar formalisms or metaheuristic methods. In this work, we employ an extended graph-grammar formalism, adapted for self-assembly of robotic modules, and propose a novel formal synthesis algorithm capable of generating rulesets for robotic modules by natively considering the morphology of their connectors. The synthesized rulesets induce a high level of concurrency in the self-assembly scheme by exploiting controlled information propagation, using solely local communication. Simulation results of microscopic (non-spatial) and submicroscopic (spatial) models of our robotic platform confirm higher performance of rulesets synthesized by our algorithm compared to related work in the literature