Auction-based task allocation scheme for dynamic coalition formations in limited robotic swarms with heterogeneous capabilities

摘要

Task allocation is one of the main issues to be addressed in the domain of multi-robot systems, in which it is determined which robot(s) should execute which task(s) so that overall system goal is achieved. Such collective decision making process is of great significance during complex task execution by swarm of simple robots with heterogeneous capabilities. This work targets the issue of coalition formations in a limited swarm of robots to perform a task requiring multiple single-task robots (ST-MR-IA) depending upon their heterogeneous capability conditions. Capabilities of individual robots may vary to different certain levels in a dynamic environment during task execution which can further affect the coalition formed to execute a specific complex task requiring certain level of collective/group capability. This study aims to suggest an algorithm for task allocations through auction mechanism to form a new or modify a coalition underway, where individual robots may gain or lose their task capabilities at certain time instants. Effectiveness of proposed algorithm in terms of task-execution time and utility of coalitions is analyzed through simulations.