Shape Formation by Self-Disassembly in Programmable Matter Systems


Event Speaker: 

Kyle W. Gilpin, CSAIL

Event Location: 

Stata Center, Patil/Kiva Room, 32-G449

Event Date/Time: 

Thursday, May 31, 2012 - 10:00am

Research Area: 

Programmable matter systems are composed of small, intelligent modules able to form a variety of macroscale objects with specific material properties in response to external commands or stimuli. While many programmable matter systems have been proposed in fiction, (Barbapapa, Changelings from StarTrek, the Terminator, and Transformers), and academia, a lack of suitable hardware and accompanying algorithms prevents their full realization. With this thesis research, we aim to create a system of sand-grain-sized modules that can form arbitrary structures on demand. We develop autonomous centimeter-scale modules capable of bonding to and communicating with their immediate neighbors. In order to accomplish our long-standing goal of shape formation, we develop a suite of provably-correct distributed algorithms that allow shape formation through sculpting, magnification, replication, and duplication. Given that a programmable matter system is a large network of autonomous processors, these algorithms have applicability in a variety of routing, sensor network, and distributed computing applications. While our hardware system provides a 50-module testbed for the algorithms, we show, by using a unique simulator, that they continue to function as the number of modules in the system rises into the hundreds or thousands. Finally, we perform hundreds of experiments using both the simulator and hardware to show how the algorithms and hardware operate in practice.