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

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.

Automated summary

This paper addresses the problem of collectively transporting multiple objects using air-ground multirobot teams. The objective is to minimize the energy of the overall system by finding the optimal matching between the objects and aerial/ground robots. The authors propose a combination of branch and bound algorithm with a negative-cycle canceling algorithm (NCCA) that proves to be an efficient solution for this combinatorial problem, providing the globally optimal solution. Numerical experiments demonstrate the practical performance of the proposed algorithm.