Optimal distributed planning of multi-robot placement on a 3D truss

This paper considers the problem of allocating tasks among robots that operate on a 3D truss. Each robot is commanded to navigate to a different location for work. When the information about the robots´ initial and desired locations are centrally known, this problem reduced to a classical disjoint-path problem. In this paper we consider the distributed problem where each robot knows its own goals only and we wish to plan an optimal set of steps for each robot that minimizes energy while fulfilling the task requirements. The challenge is to cope with possible path collisions. We present and analyze a distributed algorithm. We describe a simulation of this algorithm and show data from a physical experiment.