Efficient multi-robot formations using distributed optimization

Abstract

This paper studies the problem of multi-robot formations by means of distributed optimization. In order to reach a desired configuration, robots can adjust two elements, the set of desired positions and the particular role of each robot within the formation. Although the two problems, positions and assignment, have been deeply studied separately, there are few solutions that consider both of them together. The main contribution of this paper is a distributed algorithm that computes the optimal solution for both parameters simultaneously, accompanied by proof that the set of optimal positions is independent of the assignment of the team of robots to those positions. This demonstration also allows us to compute the optimal positions by means of a standard distributed averaging method. In order to solve the assignment problem, we consider an existing distributed simplex algorithm and propose a modification that takes into account the variations in costs generated by the averaging algorithm. The whole method is provably correct to achieve the optimal solution.