Multi-Agent Task Allocation in Complementary Teams: A Hunter and Gatherer Approach

Consider a dynamic task allocation problem, where tasks are unknowingly distributed over an environment . This paper considers ea ch task comprised of two sequential subtasks: detection and completion, where e ach subtask can only be carried out by a certain type of agent . We address th is problem using a novel natur e - inspired approach called "hunter and gathere r" . Th e proposed method employs two complementary teams of agents: one agile in detecting (hunters) and another dexterous in completing (gathere r s) the tasks . To minimize the collective cost of task accomplishments in a distributed manner, a game - theor etic solution is introduced to couple agents from complementary teams . We utiliz e market - based negotiation models to develop incentive - based decision - making algorithms rely ing on innovative notions of " certainty and uncertainty profit margins " . The simulation results demonstrate that employing two complementary teams of hunters and gatherers can effectually improve the number of tasks completed by agents compared to conventional methods, while the collec tive cost of accomplishments is minimized . In addition, t he stability and efficacy of the proposed solutions are studied using Nash equilibrium analysis and statistical analysis respectively . It is also numerically show n that the proposed solution s function fairly, i.e. for each type of agent, the overall w orkload is distributed equally . Index Terms -- Distributed multiagent system, dynamic task allocation, game theory, negotiation. Multirobot systems are expected to undertake imperative roles in a wide variety of fields such as urban search and rescue (USAR) [1, 2], agricultural field operations [3], security patrols [4, 5], environmental monitoring [6], and industrial procedures [7] . Studies have shown that multi - robot systems have advantage over single - robot systems by offering more reliability, redundancy, and time efficiency when the nature of the tasks is inherently dist ributed [8] . Nonetheless, the problem of multi - robot task - allocation (MRTA) poses many critical challenges that has called for investigation in the past two decades [9 - 11] . In this regards, t he complexity of MRTA problems increases significantly in a dynamic environment, where the number and location of tasks are unknown for agents [12, 13] . Thus, robot s need to explore the environment to find tasks before accomplishing them.