Optimal role and position assignment in multi-robot freely reachable formations

Many multi-robot problems require the achievement of formations as part of the overall mission. This work considers a scenario in which unlabeled homogeneous robots must adopt a given formation pattern buildable anywhere in the environment. This involves finding the relative pose of the formation in regard to the initial robot positions, understood as a translation and a rotation; and the optimal assignment of the role of each robot within the formation. This paper provides an optimal solution for the combined parameters of translation, rotation and assignment that minimizes total displacement. To achieve this objective we first formally prove that the three decision variables are separable. Since computing the optimal assignment without accounting for the rotation is a computationally expensive problem, we propose an algorithm that efficiently computes the optimal roles together with the rotation. The algorithm is provably correct and finds the optimal solution in finite time. A distributed implementation is also discussed. Simulation results characterize the complexity of our solution and demonstrate its effectiveness.