Collective construction using lego robots

Crystal Schuil, Matthew Valente, Justin Werfel, Radhika Nagpal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


Social insects, such as ants and termites, collectively build large and complex structures, with many individuals following simple rules and no centralized control or planning [Theraulaz and Bonabeau 1995, Camazine et al. 2002]. Such swarm systems have many desirable properties: a high level of parallelism, cheap and expendable individuals, and robustness to loss, addition, and errors of individual insects. Our goal is to design systems for automating construction that are similarly adaptive and robust, but build what we want. Automated construction will impact our ability to operate in inhospitable habitats, from outer space to under water, and allow automated disassembly and repair. Recently, our group has developed a family of decentralized algorithms by which identically-programmed autonomous agents can collectively and reliably build user-specified solid 2D configurations from building blocks, [Werfel et al. 2006]. In that system, the agents act without explicit communication, instead relying on the partially built structure as a form of indirect coordination similar to stigmergy in insects. The extended stigmergy approach is to enhance the environment (in this case, the building blocks) to store and process information. We showed that adding even simple capabilities to blocks, e.g. writeable state using RFID tags, can significantly increase the robustness, speed and simplicity of the system as a whole. The building process is robust to variable numbers of agents, asynchronous agent timing, and addition/loss of agents. The algorithms and analysis are available in [Werfel et al. 2006]. An important concern with the design of algorithms for mobile robots is their feasibility when implementing them in the real world. Our algorithms rely on simple robot behaviors, such as following the perimeter of building blocks and carrying and placing self-aligning blocks. The system does not rely on wireless communication, globally available position information, or perfect manipulation/ movement, which are challenging to implement in mobile robot systems. The algorithms are simple enough to be implemented on current low-cost robot hardware. In order to demonstrate the feasibility of the system, we have developed two hardware prototypes: (1) an Evolution Robotics ER1 based mobile robot (presented in [Werfel et al. 2006]) and (2) LEGO Mindstorms based robots. In this exhibition we will present a demonstration of the LEGO Mindstorms based prototype. Our current system has two robots, which autonomously construct 2D structures from flat building building blocks. The LEGO Mindstorms robot implements the basic behaviors of the algorithm using its limited set of sensors. It can (a) locate the station for new blocks (b) find the existing structure (c) navigate the perimeter of a partially constructed structure and (d) recognize right and left corners in the perimeter. These behaviors are sufficient to implement an algorithm whereby robots always construct a contiguous structure free of gaps and tunnels. In order to implement these behaviors, the robot relies on two light sensors mounted in the front that can distinguish light from dark. The blocks are white and contrast with the black field. The robots are programmed using NQC, a C-syntax derivative specifically created for the LEGO Mindstorms platform. The basic algorithm is as follows: the robot starts at the perimeter of the field and searches until it finds the station for new blocks. It grabs a block and then heads towards the structure. It follows the perimeter of the structure until it finds an appropriate location to place the block. After placing the block it heads back to the perimeter of the working area and repeats the process. The robot uses feedback from rotation sensors and light sensors to correct errors in movement, and can robustly follow a complicated perimeter. The limited sensor/motor interface of the LEGO Mindstorms control unit (RCX), made it necessary to use two units per robot. The two RCX units control different aspects of the robot behavior and communicate with each other through infrared transmissions relayed off of a reflective surface. The robot has a manipulating arm with which it can grab, raise and lower blocks. This arm is implemented using pneumatic cylinders and a worm-gear driven grabbing mechanism. A pneumatic pump connected to an air tank provides the pressurization of a series of pneumatic cylinders. A servo-controlled valve controls the air-flow to the bank of cylinders. When a block is detected, the grabbing mechanism closes until the pressure on the clutch gear is exceeded. The servo is then activated and the pneumatic cylinders raise the arm. In order to place the block, the robot simply reverses this process. The building blocks themselves are constructed from foam and have embedded magnets. The magnets make the blocks self-aligning. This automatically corrects for small errors in block placement and frees the robot from having to align blocks with high precision. The robot design is modular and can be easily extended and replicated. The LEGO robot system has many advantages: it is easy to extend the mechanical design to incorporate new capabilities, and it is easy to program using NQC. At the same time the limited sensors pose some difficulties. For example, the robot can only distinguish dark and light, but not variations in color, which limits the environment in which the robot can operate. Also the limited interface makes it difficult to add new sensor capabilities, such as a camera or RFID reader. The ER1 robot implements a more complete system. The robot uses a camera for block and field recognition, which allows it to operate in a more unconstrained environment. It also has a RFID reader and the building blocks have simple low cost writeable RFID tags ($1/tag). Using this hardware, the ER1 robot is capable of implementing extended stigmergy and can assemble a large class of user-specified 2D structures. We will show movies of the ER1 in operation. Our current systems form only 2D structures, yet insects form complex 3D structures that are well adapted to their environmental surroundings. In the future we plan to focus on building walled compounds and 3D structures, as well as building structures whose shape is partially determined by the environment. These systems pose many research challenges, in both algorithm design and implementation. This research is supported by the National Science Foundation (NSF) and a Clark Grant from Harvard University.

Original languageEnglish (US)
Title of host publicationProceedings of the 21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Number of pages2
StatePublished - 2006
Externally publishedYes
Event21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06 - Boston, MA, United States
Duration: Jul 16 2006Jul 20 2006

Publication series

NameProceedings of the National Conference on Artificial Intelligence


Other21st National Conference on Artificial Intelligence and the 18th Innovative Applications of Artificial Intelligence Conference, AAAI-06/IAAI-06
Country/TerritoryUnited States
CityBoston, MA

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence


Dive into the research topics of 'Collective construction using lego robots'. Together they form a unique fingerprint.

Cite this