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

Authors José Guerrero Sastre | Gabriel Oliver Codina
In Multi-Robot Systems, Trends and Development, InTech, Toshiyuki Yasuda, pp. 437-456, 2011.
ISBN 978-953-307-425-2

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.

Uso de cookies

Este sitio web utiliza cookies para que usted tenga la mejor experiencia de usuario. Si continúa navegando está dando su consentimiento para la aceptación de las mencionadas cookies y la aceptación de nuestra política de cookies, pinche el enlace para mayor información.