Date of Award

Spring 1-1-2015

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Computer Science

First Advisor

Nikolaus Correll

Second Advisor

Sriram Sankaranarayanan

Third Advisor

Gabe Sibley

Fourth Advisor

Ani Hsieh

Fifth Advisor

Behrouz Touri

Abstract

One of the most elusive but important goals of swarm robotics is to reproduce the emergent collaborative behavior observed in natural swarming systems through the use of simple decision rules. Examples of collaborative processes in insect colonies such as foraging, scouting (finding shortest paths) for food, and colony defense involve some form of task allocation among individual agents. The robustness of task completion even after major environmental changes is also observed in natural swarm systems. Ants and bees are often unphased by the fact that the magnitude of a task --- such as carrying a heavy piece of food --- is unknown to every individual and manage to complete the task elegantly even without such critical knowledge. This robustness property is of paramount importance when recreating natural behavior in artificial systems and I believe the use of decentralized agent based task allocation rules is closely related to this property. I therefore present a novel response threshold based strategy for task allocation in multi-agent systems in this dissertation. I prove, 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. The importance of this result is to provide a formal mathematical basis for the phenomenological justification currently provided in the field of swarm robotics to mimic biological systems. This result therefore 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 (stick-pulling experiment) and stochastic team size task allocation. This allows variable team sizes to form at task sites within tolerance limits thereby providing a trade-off between exploration and exploitation. The claims made by theoretical proofs for response threshold based task allocation are backed up 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. I show 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.

Share

COinS