Collective Construction by Simple Robots using Implicit Coordination
Social insects, such as ants and termites,
collectively build large and complex structures. These animals achieve
tremendous complexity, parallelism and robustness, even though the
individuals are small, simple, and expendable. One question is whether
we can achieve the same kind of collective intelligence with robots:
can a group of simple robots collectively build complex user-specified
structures, in a similarly adaptive and robust fashion?
We have developed a family of decentralized
algorithms by which simple robots -- without wireless communication or
GPS/localization -- can cooperate to build a large classes of
user-specified structures out of modular blocks. Some of the main
themes and contributions of our work are:
Simple Robots & Extended Stigmergy: Simple robots, without
GPS or wireless, can coordinate indirectly by storing information in
the environment -- an idea inspired by social insects like termites
and ants. In our case, the "blocks" provide a means for both
localization and coordination, e.g. by providing a grid-like
environment and by allowing the robots to store information
(e.g.embedded writeable RFID tags).
Coherent Structure Through Local Rules:
We consider the construction process as a type of lattice
self-assembly. This allows us to leverage ideas from
programmable/algorithmic self-assembly to automatically generate local
rules for complex 2D shapes. The local rules provably create
correct structure even though the assembly may proceed in many
possible decentralized orders and some steps may fail; they also take
into account movement and manipulation constraints of the robots.
Algorithms and Theory: This approach shows
that collective construction is algorithmically closely related to
other kinds of self-assembly, from DNA self-assembly to modular
robotics, even though it exists at a very different size scale. The
algorithms generalize to other implementations
(e.g,. self-reconfigurable robots) and some related tasks (e.g. 3D
structures and disassembly). There are still many open algorithmic
challenges, especially in environmentally-adaptive structures.
Robot Hardware: Another important thrust
has been the design of physical prototypes. We have built several
robots that construct 2D structures, using simple but autonomous
robots (ER1 and lego platforms) and RFID-tagged blocks. Our hardware
implementations demonstrate the level of autonomy and coherent
behavior that can be achieved by simple robots, and also demonstrate
how the co-design of the blocks (e.g. using self-aligning connectors,
RFID tags) can allow the robots to achieve more complex tasks by
manipulating the environment.
Distributed Construction by Mobile Robots with Enhanced Building Blocks,
Justin Werfel, Yaneer Bar-Yam, Daniela Rus, and Radhika Nagpal,
IEEE International Conference on Robotics and Automation (ICRA),
May 2006. (pdf)
Extended Stigmergy in Collective Construction
Justin Werfel, Radhika Nagpal,
IEEE Intelligent Systems 21(2): 20-28 (2006).
(pdf)
Anthills Built to Order: Automating Construction with Artificial Swarms
Justin Werfel, PhD thesis, Massachusetts Institute of Technology, May 2006.
(pdf)
[ICRA 2006] introduces the main algorithmic ideas, including how to
achieve coherent structures with passive, RFID-labelled or
communicating blocks, and ER1 robot results. [IEEEIS 2006] presents
theoretical results around these algorithms, e.g. best/worst-case
parallelism achieved and achievable by any algorithm. The PhD
dissertation covers these aspects and several more complex tasks (see later papers).
Robot Hardware Implementations:
(ER1 Robot) Distributed Construction by Mobile Robots with Enhanced Building Blocks,
Justin Werfel, Yaneer Bar-Yam, Daniela Rus, and Radhika Nagpal,
IEEE International Conference on Robotics and Automation (ICRA),
May 2006. (pdf)
(Lego Robots) Collective Construction Using Lego Robots, Crystal
Schuil, Matthew Valente, Justin Werfel, Radhika Nagpal, Robot
Exhibition, Natl. Conference on Artificial Intelligence (AAAI) July
2006. (pdf) Received Technical Innovation Award for "elegant connection of theory and
design".
These two papers discuss our two hardware implementations, using
the ER1 Robot platform and the Lego mindstorms platform.
Collective Construction for Different Types of Structures:
Building Patterned Structures with Robot Swarms,
Justin Werfel, Yaneer Bar-Yam, Radhika Nagpal,
Intl. Joint Conference on Artificial Intelligence (IJCAI '05), Aug 2005.
(pdf)
Three-dimensional construction with mobile robots and modular blocks.
Justin Werfel and Radhika Nagpal, International
Journal of Robotics Research, 27 (3-4): 463-479 (2008), (pdf)
(Workshop paper, Self-Reconfigurable Modular
Robots, RSS Sept 2006
(pdf))
Collective Construction of Environmentally-Adaptive Structures
Justin Werfel, Donald Ingber, Radhika Nagpal,
IEEE Conference on Intelligent Robots and Systems
(IROS),
Oct, 2007 (pdf)
These papers describe how the algorithms and proofs generalize to
other kinds of structures, for example structures where the blocks are
different colors/types [IJCAI 05] and arbitrary 3d structures without
gravity constraints [IJRR 08]. The last paper describes work towards
structures that must conform to an unknown environment [IROS 07].
Overview of different classes of structures that can be
self-assembled using collective construction algorithms.
Overview of autonomous robot demonstrations (ER1 and Lego) for 2D
construction.
