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

Bahar Haghighat*, Alcherio Martinoli

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationDistributed Autonomous Robotic Systems
Subtitle of host publicationThe 13th International Symposium
PublisherSpringer Science and Business Media B.V.
Number of pages15
ISBN (Electronic)978-3-319-73008-0
ISBN (Print)978-3-319-73006-6
Publication statusPublished - 2018
Externally publishedYes

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

Cite this