Response Threshold Based Task Allocation in Multi-Agent Systems

Collaborative processes in insect colonies such as foraging, scouting for food, and colony defense involve some form of task allocation among individual agents. This dissertation presents a novel response threshold based strategy for task allocation in multi-agent systems. It proves, using a well known result from the theory of global games, that under the constraints of imperfect knowledge of the environment and imperfect communication response threshold based task allocation leads to an equilibrium inducing strategy for the swarm system. This result provides both a hypothesis about the inner workings of a wide range of existing approaches with limited communication between agents in artificial swarm systems and also a formal explanation for threshold based task allocation in social insects. These game theory results lead to a novel continuous response threshold algorithm for multi-agent task allocation that generalizes fixed-group task allocation and stochastic team size task allocation. This allows variable team sizes to form at task sites within tolerance limits. Theory is validated by physical experiments using the Droplet swarm robot platform. Further simulation experiments provide a basis of comparison between optimal centralized approaches and hybrid approaches for task allocation where each robot decides whether to participate in a task based on its own noisy sensory input and imperfect knowledge from the system controller. It also shows that in many real world situations it is often impractical to rely on the assumption of perfect system information for controlling a swarm and that centralized task allocation becomes comparable to a response threshold based policy under the influence of noise.