Coordinated Construction

Robots assembling a structure in the Holodeck.

Coordinated Construction is focused on decentralized algorithms for the cooperative assembly of 3-dimensional objects that consist of multiple types of parts, using a networked team of robots. The algorithms are used to build truss-like objects using rods and connectors.

Theory

The main theory for Coordinated Construction is based on two principles, equal-mass partitioning and uniform delivery. The simulations shown below were developed in MATLAB, but actual implementation can be found below.

Equal-mass Partitioning

Density function for an A-shaped bridge and coverage by the equal-mass partitioning of 4, 6 and 10 robots. The blue circles are assembling robots. Yellow regions are denser.

The first principle ensures that each assembly robot has an equivalent amount of work to complete toward the overall structure.

To divide the structure in equally-sized substructures, we have developed and implemented an equal-mass partitioning controller, guaranteeing convergence of the cost function that is the product of the all the masses. The algorithm allocates to each assembly robot the same amount of assembly work. This condition ensures maximum parallelism.

Uniform delivery

The second principle ensures that the assembly robots receive their construction materials in a balanced way. That way, several robots can be working simultaneously instead of one being overloaded while the others wait for parts.

To ensure uniform delivery, we make use of probabilistic deployment and a gradient of the demanding masses. This maintains a balance among the substructures.

Once the assembly robots are in place according to the equal-mass partitioning controller, construction may begin. State machines drive the delivery robots and the assembly robots.

During construction we wish to distribute the source components (truss elements and connectors) to the assembly robots in a balanced way. Global balance is asymptotically achieved by a probabilistic target selection of delivering robots that uses \phi_t as a probability density function. For local balance, the delivering robots are driven by the gradient of demanding mass defined as the remaining structure to be assembled by the robot. Robots with more work left to do get parts before robots with less work left. Each assembling robot waits for a new truss element or connector and assembles it to the most demanding location in its Voronoi region. Therefore, construction is purely driven by the density functions regardless of the amount of the source components and it can be done without an explicit drawing of the target structure.

We ensure that all the processes of the controllers work in a distributed way and each robot needs to communicate only with neighbors.

Implementation

Systems

The theory is implemented on a team of iCreate robots with a four degree-of-freedom arm. They rely on the motion capture system in their environment to know where they are. The robots lack cameras, and but they do have several means of communication:

• Wifi (802.11) wireless networking (between each other)
• XBee (802.15.4) wireless networking (to receive location data)
• Infrared sensor (located in the gripper, to detect parts)

The robots assemble two different types of construction parts - trusses and connectors - to build structures. Each part is equipped with a smart part and beacon that broadcasts information about itself through an infrared transceiver. Even though the robot is "blind", it can use this information to know when it has found a part and what type of part it is.

To view the robots in action, click the screenshot above/left.

The navigation is an implementation of the algorithm described in Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions by Lindemann and LaValle[4].

Given a complete map of its surroundings (provided by the Holodeck and broadcasted over the XBee network), the robot breaks that map into cells, or convex polygons. We run breadth-first search on these cells to determine, from any cell, the fewest number of hops to get to the cell containing the goal point. We then calculate a potential field, using an interpolation of a potential field that always points toward the next cell in our path and a potential field that crosses the cell boundary into that field. Finally, once the robot is in the goal cell it uses a potential field that points it toward the goal.

The benefits of this approach are numerous. It is dynamic in that given the cell decomposition of the map, it is incredibly fast to calculate the potential field vector at the current location of the robot, so the robot can update its speed and direction very rapidly. A new cell decomposition is required every time that the map changes "significantly" - we take this to be any time that an obstacle moves more than few centimeters. This occurs very infrequently compared to the number of times the robots receive location updates, and the cell decomposition does not take long at all. Therefore, the robot dynamically updates its path information in effectively real-time.

Additionally, the path followed by the robot is much smoother than it would be if it were using other types of navigation algorithms, such as A*. Even though this causes the robot to traverse a path longer than the shortest path, the resulting smoothness does not result in a significant loss of time because there is no waiting for the robot to stop and turn directions suddenly. Also, it is much more visually appealing.

Logistics

There are lots of different pieces to the coordinated construction project, so it's important to manage all of them efficiently.

People

• Daniela Rus
• David Stein
• Ryan Schoen

Past

• Seungkook Yun
• Lauren White
• Matthew Faulkner

References

[1]

Seung-kookYun, Daniela Rus - Adaptation to robot failures and shape change in decentralized construction
Proceedings of IEEE International Conference on Robotics and Automation ,2010
Bibtex
Author : Seung-kookYun, Daniela Rus
Title : Adaptation to robot failures and shape change in decentralized construction
In : Proceedings of IEEE International Conference on Robotics and Automation -
Date : 2010

[2]

Seung-kookYun, Mac Schwager, Daniela Rus - Coordinating Construction of Truss Structures using Distributed Equal-mass Partitioning
Proc. of the 14th International Symposium on Robotics Research , Luzern, Switzerland, Aug 2009
Bibtex
Author : Seung-kookYun, Mac Schwager, Daniela Rus
Title : Coordinating Construction of Truss Structures using Distributed Equal-mass Partitioning
In : Proc. of the 14th International Symposium on Robotics Research -
Address : Luzern, Switzerland
Date : Aug 2009

[3]

Adrienne Bolger, Matthew Faulkner, David Stein, Lauren White, Seung-kook Yun, Daniela Rus - Experiments in Decentralized Robot Construction with Tool Delivery and Assembly Robots
IEEE/RSJ International Conference on Intelligent Robots and Systems ,2010
Bibtex
Author : Adrienne Bolger, Matthew Faulkner, David Stein, Lauren White, Seung-kook Yun, Daniela Rus
Title : Experiments in Decentralized Robot Construction with Tool Delivery and Assembly Robots
In : IEEE/RSJ International Conference on Intelligent Robots and Systems -
Date : 2010

[4]

Lindemann, Stephen R., Lavalle, Steven M. - Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions
Int. J. Rob. Res. 28(5):600--621, Thousand Oaks, CA, USA,2009
Bibtex
Author : Lindemann, Stephen R., Lavalle, Steven M.
Title : Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions
In : Int. J. Rob. Res. -
Address : Thousand Oaks, CA, USA
Date : 2009