A Distributed Market-Based Algorithm for the Multi-Robot Assignment Problem

Assigning tasks to a set of robots is a fundamental problem in robotics. It consists in finding the best task assignment to the available robots. In this paper, we present two distributed market-based algorithms to solve the assignment problem where n robots compete for n tasks with the assumption that each robot can be assigned to only one task. The first algorithm, called DMB, represents a Distributed Market-Based algorithm where each robot bids for every task. The second algorithm is an extension of the DMB. It consists in swapping tasks between robots in order to improve the efficiency of the whole assignment. We conducted both real-world experimental testing, and MATLAB simulations to evaluate performance of the proposed algorithms and compare them against the centralized Hungarian algorithm in terms of traveled distance. Simulation results show that the IDMB algorithm produces near optimal solutions and in several cases it gives the optimal solution. In addition, we demonstrated the feasibility of our algorithms through real-world experimentation on robots. (C) 2014 Published by Elsevier B.V.