Coordinated Construction

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.

The main theory for Coordinated Construction is based on two principles, equal-mass partitioning and uniform delivery.

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.

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.

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.

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.

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.