Seminars & Colloquia

Erik Demaine


"Replicators, Transformers, and Robot Swarms:
Science Fiction through Geometric Algorithms "

Tuesday February 18, 2014 03:30 PM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)

This talk is part of the Theory Seminar Series



Science fiction is a great inspiration for science.  How can we build reconfigurable robots like Transformers or Terminator 2?  How can we build Star Trek-style replicators that duplicate or mass-produce a given shape at the nano scale?  How can we orchestrate the motion of a large swarm of robots? Recently we've been exploring possible answers to these questions through computational geometry. 

Reconfigurable robots are made up of many components that can move/rotate around each other, enabling an overall shape change.  What is the best way to transform such a robot from one shape (e.g. humanoid) into another (e.g. vehicle)?  We will describe several algorithms developed for this problem for various models of geometric robots, both when the robots are independent units, and when they are connected together into a single robot, making either a self-folding origami sheet or hinged chain.  Ultimately the goal is programmable matter: a single piece of material that can dynamically change its shape into anything desired, in principle allowing us to download and execute geometry in the same way we download and execute software. 

Robot swarms are similar in that they involve many individual components, but different in the components are not attached to each other. How can a swarm of moving robots communicate locally and still measure its own shape?  How can a swarm of simple particles be transformed from one configuration to another, given just a global signal like 'everyone move left until hitting something', as might be provided by a strong external magnet.  We will describe algorithms and hardness results developed for these problems. 

Self-assembly is an exciting approach to constructing complex 3D objects out of simple, nano-scale such as DNA (each much less powerful than a typical robot).  Staged assembly is a relatively new approach to self-assembly, which models not only the parts but also the experimenter who creates and combines the parts.  This more algorithmic approach enables substantially more efficient and practical constructions of arbitrary desired shapes. Another surprising result is a general-purpose replicator, which takes an unknown physical object as input, and produces arbitrarily many copies of it using just a constant amount of experimental operations.  Along the way, we show efficient ways to build nano-scale biological computers.


Short Bio:

Erik Demaine is a Professor in Computer Science at the Massachusetts Institute of Technology. Demaine's research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games. He received a MacArthur Fellowship as a “computational geometer tackling and solving difficult problems related to folding and bending—moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter�. He appears in the recent origami documentary Between the Folds, cowrote a book about the theory of folding (Geometric Folding Algorithms), and a book about the computational complexity of games (Games, Puzzles, and Computation). Together with his father Martin, his interests span the connections between mathematics and art, including curved-crease sculptures in the permanent collections of the Museum of Modern Art in New York, and the Renwick Gallery in the Smithsonian.

Host: Blair D. Sullivan, Computer Science, NC State University

Back to Seminar Listings
Back to Colloquia Home Page