Stochastic Search with Locally Clustered Targets: Learning from T Cells

Searching a space with locally clustered targets (think picking apples from trees) leads to an optimization problem: When should the searcher leave the current region, and invest the time to travel to another one? We consider here a model of such a search process: infection screening by T cells in the immune system. Taking an AIS perspective, we ask whether this model could provide insight for similar problems in computing, for example Las Vegas algorithms with expensive restarts or agent-based intrusion detection systems. The model is simple, but presents a rich phenomenology; we analytically derive the optimal behavior of a single searcher, revealing the existence of two characteristic regimes in the search parameter space. Moreover, we determine the impact of perturbations and imprecise knowledge of the search space parameters, as well as the speedup gained by searching in parallel. The results provide potential new directions for developing tools to tune stochastic search algorithms.