Optimal Positioning Strategies for Shape Changes in Robot Teams

In this paper, we consider the task of repositioning a formation of robots to a new shape while minimizing either the maximum distance that any robot travels, or the total distance traveled by the formation. We show that optimal solutions in SE (2) can be achieved for either metric through second-order cone programming (SOCP) techniques. For the case where the orientation of the new formation shape is fixed, we obtain optimal solutions in both R²and R³. The latter also allows for complete regulation of the formation size via constraints on the shape scale. We expect that these results will prove useful for extending the mission lives of robot formations and mobile ad-hoc networks (MANETs).