Graph Grammars for Self Assembling Robotic Systems

In this paper we define a class of graph grammars that can be used to model and direct distributed robotic assembly or formation forming processes. We focus on the problem of synthesizing a grammar so that it generates a given, prespecified assembly. In particular, to generate an acyclic graph we synthesize a binary grammar (rules involve at most two parts), and for a general graph we synthesize a ternary grammar (rules involve at most three parts). We then show a general result that implies that no binary grammar can generate a unique stable assembly. We conclude the paper with a discussion of how graph grammars can be used to direct the synthesis of parts floating in a fluid or for self-motive robotic parts.

Authors

• Eric Klavins
• Robert Ghrist
• David Lipsky

Keywords

• Robotic assembly
• Aggregates
• Assembly systems
• Tree graphs
• Protocols
• Robots
• Microorganisms
• Shape
• Mathematics
• Complexity theory
• Self-assembly
• Graph Grammar
• Grammar Rules
• Part Of The Robot
• Left Side
• Triangulation
• Scope Of This Paper
• Alphabet
• Set Of Rules
• Infinite Number
• Root Node
• Communication Protocol
• Communication Cost
• Recursive Algorithm
• Assembly Model
• Stable Set
• Distributed Fashion
• Arbitrary Graph
• Part Of Rule