Optimal distributed planning for self assembly of modular manipulators

Abstract

We describe algorithms to build self-assembling robot systems composed of active modular robots and passive bars. The distributed algorithms are based on locally optimal matching. We demonstrate how to build an active structure by the cooperative aggregation and disassembly of modular robotic manipulators. A target structure is modeled as a dynamic graph. We prove that the same optimality - quadratic competitive ratio - as for the static graph can be achieved for the algorithms. We demonstrate how this algorithm can be used to build truss-like structures.