Automatic synthesis of rulesets for programmable stochastic self-assembly of rotationally symmetric robotic modules

Bahar Haghighat*, Alcherio Martinoli

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)


Programmable stochastic self-assembly of modular robots provides promising means to formation of structures at different scales. One way to address the design of dedicated control rulesets for self-assembling robotic modules is to leverage formalisms based on graph grammar. While these tools are powerful and allow for formal analysis of the resulting controllers, expressing the embodiment of the robotic modules and therefore the physical structure of assemblies of such modules is not readily possible with such formalisms. This typically results in inefficient representation of ruleset controllers and poses limitations on automatizing ruleset synthesis methods, requiring manual design or tuning of the rules before deployment on the robotic modules. In this work, we consider robotic modules endowed with identical latching connectors arranged in a rotationally symmetric configuration. We extend a grammar formalism based on graphs and propose a new encoding of the modules' internal states. This allows for formulating formal methods capable of automatically deriving the rules based on the morphology of the robotic modules, in particular their number of connectors. The derived rules are directly applicable to robotic modules with no further tuning. In addition, we show that our method allows for a reduced complexity in the rulesets, a particularly welcome feature in the case of limited on-board storage, computation, and communication resources. In order to illustrate the application of our method, we extend two synthesis algorithms from the literature, namely Singleton and Linchpin, to automatically synthesize rules applicable to our resource-constrained robotic modules. In order to increase the prototyping speed and the thoroughness of the validation for the synthesis algorithms, we leverage two complementary simulation frameworks capturing the system at different levels of abstraction. Finally, employing the generated rulesets, we conduct experiments with our robotic platform to demonstrate several assemblies.

Original languageEnglish
Pages (from-to)243-270
Number of pages28
JournalSwarm intelligence
Issue number3-4
Publication statusPublished - Dec-2017
Externally publishedYes


  • Programmable stochastic self-assembly
  • Modular robots
  • Graph grammar
  • Ruleset controller

Cite this