Simultaneous Optimization of Assignments and Goal Formations for Multiple Robots

Abstract

This paper presents algorithms to simultaneously compute the optimal assignments and formation parameters for a team of robots from a given initial formation to a variable goal formation (where the shape of the goal formation is given, and its scale and location parameters must be optimized). We assume the nn robots are identical spheres. We use the sum of squared travel distances as the objective function to be minimized, which also ensures that the trajectories are collision free. We show that this assignment with variable goal formation problem can be transformed to a linear sum assignment problem (LSAP) with pseudo costs that we establish are independent of the formation parameters. The transformed problem can then be solved using the Hungarian algorithm in O (n3) time. Thus the assignment problem with variable goal formations using this new approach has the same O (n3) time complexity as the standard assignment problem with fixed goal formations. Results from simulations on 200 and 600 robots are presented to show the algorithm is sufficiently fast for practical applications.