Globally Optimal Assignment Algorithm for Collective Object Transport Using Air–Ground Multirobot Teams

Abstract

We consider the problem of collectively transporting multiple objects using air–ground multirobot teams. The objective is to find the optimal matching between the objects and aerial/ground robots that minimizes the energy of the overall system. We reveal the local optimality criteria for this combinatorial problem and prove that combining a branch and bound algorithm with a negative-cycle canceling algorithm (NCCA) yields an efficient algorithm that provides the globally optimal solution of the problem. Numerical experiments demonstrate the performance on practical problems.