Extended Stigmergy

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.

Publications

Main Ideas:

  • 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.