Computer Science ETDs

Publication Date

Spring 5-13-2017

Abstract

This work investigates effective search and resource collection algorithms for swarms. Deterministic spiral algorithms and L ́evy search processes have been shown to be optimal for single searchers. We extend these strategies to swarms of robots and populations of T cells and measure performance under a variety of conditions.

Search extent and intensity lie on a continuum: more intensive patterns search thoroughly in the local area, while extensive patterns cover more area but may miss targets nearby. We show that the most efficient trade-off between search intensity and extent for swarms depends strongly on the distribution of targets, swarm size and the rate of collision among searchers (Fricke et al., 2016a). The optimal trade-off is also influenced by the target detection error rate. The search can, therefore, be tuned to match conditions common in real-world robot search tasks.

We also demonstrate that our swarm spiral algorithm is an effective strategy for resource collection. Deterministic spiral search strategies for single searchers have been considered unsuitable in the presence of localisation error (Reynolds et al., 2007), but the swarm algorithm performs well even in the presence of localisation error. Since the spiral strategy is effective and easily analysed it makes an ideal benchmark against which to compare stochastic search processes.

Collective search by T cells is a critical component of the adaptive immune re- sponse. We characterise T cell search patterns and find that they balance the need to search extensively for rare antigen while maintaining local contacts with antigen- presenting cells. We perform two analyses that demonstrate that T cells interact with their environment during search. We also measure the interaction between T cells and Dendritic cells using mutual information and demonstrate non-random spatial association between T cells and their targets.

Language

English

Keywords

swarms, search, Levy, spiral, robots, T cells

Document Type

Dissertation

Degree Name

Computer Science

Level of Degree

Doctoral

Department Name

Department of Computer Science

First Committee Member (Chair)

Melanie E. Moses

Second Committee Member

Judy L. Cannon

Third Committee Member

David H. Ackley

Fourth Committee Member

Helen J. Wearing

Download

Share

COinS