Auction and Swarm Multi-Robot Task Allocation Algorithms in Real Time Scenarios

Task allocation is one of the main problems in multi-robot systems, very especially when the tasks must be executed before deadlines, that is, in real-time scenarios. In most cases this problem is an NP-hard problem, and therefore, there is not any algorithm that in a reasonable computing time gives the optimal tasks allocation. The work presents and study three auction-like strategies based on existing ones: Sequential Unordered Auction (SUA), Earliest Deadline First Auction (EDFA) and Sequential Best Pair Auction (SBPA). In all these cases there is a central auctioneer who receives the bids from all the robots and decides the allocation of the tasks. These strategies differ between them on the way the auctioneer announces the tasks to the robots and on the robots’ answers are processed. Besides the auction methods, a classical swarm strategy has been taken into account. The results show that in most cases the most complex algorithm(SPBA) outperforms the other auction based procedures. Besides EDFA is better than the simple SUA strategy. Finally, swarm strategy is better than EDFA or SUA when the number of robots and tasks is not very large.