Computer Science ETDs

Drew Levin

Publication Date

5-1-2016

Abstract

This dissertation investigates two natural systems that use distributed search algorithms and tests the hypothesis that the searchers' environment is a key constraint on an optimal algorithm. Natural instances of distributed autonomous systems of simple components exist in both biology and social systems. These systems have been honed through eons of evolution by natural selection to perform well in their environment. I examine two specific systems that use distributed methods to search and recruit individuals to locations of interest: T cells' search for pathogens in the human body and ants searching for food. Both systems are examples of time-constrained processes that require the distributed coordination of simple autonomous agents and interaction with their environment. Taking common principles from both domains, the dissertation examines three distributed search strategies: uninformed random search, origin-based local recruitment, and chemical-based pheromone recruitment. Using both numerical and agent-based models, it evaluates the effectiveness of these strategies across two environmental factors: the spatial clustering and temporal volatility of resources. The results demonstrate that both recruitment-based strategies (origin-based and chemical-based) suffer in environments of high resources dispersion and volatility. Conversely, uninformed random search performs better in these environments. The results are relevant to certain algorithmic issues in swarm robotics. For example, it is expensive to implement chemical trails in a distributed physical system, and the dissertation shows that strategies using only local recruitment perform similarly in all environments. Also, origin-only algorithms are much easier to implement in a robotics context. Further, because each strategy examined in this dissertation performs best at one extreme of resource spatial distribution, the results establish that the most difficult environments for search are likely those with intermediate levels of clustering. Finally, the dissertation classifies the exact nature of the environmental trade-offs and presents methods to determine the best search strategy given knowledge of the environment.

Language

English

Keywords

Distributed Systems, Distributed Search, Computational Biology, Theoretical Biology, Immunology, Virology, Myrmecology

Document Type

Dissertation

Degree Name

Computer Science

Level of Degree

Doctoral

Department Name

Department of Computer Science

First Committee Member (Chair)

Moses, Melanie

Second Committee Member

Tapia, Lydia

Third Committee Member

Cannon, Judy

Project Sponsors

National Institutes of Health, National Science Foundation, Defense Advanced Research Projects Agency, Howard Hughes Medical Institute, Program in Interdisciplinary Biological and Biomedical Sciences at UNM, Air Force Research Laboratory, Santa Fe Institute, James S. McDonnell Foundation

Download

Share

COinS