Todd Wareham
Department of Computer Science
Memorial University of Newfoundland

Educating Genghi: A Complexity Perspective on Designing Reactive Swarms

Department of Computer Science
Thursday, November 28, 2013, 1:00 p.m., Room EN-2022

---

Abstract

A swarm is a collection of simple autonomous entities that communicate locally and without global co-ordination to perform tasks. Given the robustness of swarms in the face of changes to swarm membership, environmental fluctuations, and changes in the nature of the tasks being performed, robot swarms are finding an increasing number of applications. There are a variety of ways in which swarms can be designed, ranging from the selection of swarms from libraries of available robots to the modification of given or selected swarms relative to libraries of robot components. Though there are a number of proof of concept systems for designing swarms, it is not obvious if any algorithm can perform efficient design in general or, if not, under which conditions (if any) such efficient design might be possible.

In this talk, we present the initial results of a computational complexity analysis of the problem of designing swarms of reactive robots that is being carried out to answer these two questions. Our main result is that even for a rather simple world, task, and swarm architecture, designing a swarm of reactive robots to perform that task in a given world is NP-hard. Additional parameterized results in turn delimit those conditions under which efficient design is possible, e.g., we show that swarms consisting of reactive robots with limited sensory and perceptual abilities can be efficiently designed.