A distributed algorithm for 2D shape duplication with smart pebble robots

We present our digital fabrication technique for manufacturing active objects in 2D from a collection of smart particles. Given a passive model of the object to be formed, we envision submerging this original in a vat of smart particles, executing the new shape duplication algorithm described in this paper, and then brushing aside any extra modules to reveal both the original object and an exact copy, side-by-side. Extensions to the duplication algorithm can be used to create a magnified version of the original or multiple copies of the model object. Our novel duplication algorithm uses a distributed approach to identify the geometric specification of the object being duplicated and then forms the duplicate from spare modules in the vicinity of the original. This paper details the duplication algorithm and the features that make it robust to (1) an imperfect packing of the modules around the original object; (2) missing communication links between neighboring modules; and (3) missing modules in the vicinity of the duplicate object(s). We show that the algorithm requires O(1) storage space per module and that the algorithm exchanges O(n) messages per module. Finally, we present experimental results from 60 hardware trials and 150 simulations. These experiments demonstrate the algorithm working correctly and reliably despite broken communication links and missing modules.

Authors

• Kyle Gilpin
• Daniela Rus

Keywords

• Shape
• Robot sensing systems
• Routing
• Robustness
• Manufacturing
• Distributed Algorithm
• 2D Shape
• Communication Links
• Missing Link
• Original Objective
• Passive Model
• 2D Object
• Broken Links
• Replica
• Bounding Box
• Low Identity
• Object Shape
• System Modulation
• Computational Capabilities
• Shape Descriptors
• Routing Algorithm
• Multiple Duplications
• Self-assembled Systems
• Passive Objects
• Duplication Process
• Programmable System
• Leader Election