Topology Provides Tools for Intrusion Detection with Robot Swarms

Institute: IMA     June 2014

Robotic swarms are increasingly being designed for tasks deemed too difficult, time-consuming, or hazardous for humans, such as underwater exploration, wildlife sampling, surveillance, and search and rescue. These cheap, simple robots move using collective behaviors that emerge from local interactions with each other and their environment, functioning much like social insects. One use of robot swarms is intrusion detection, in which an intruder is detected if it is seen by any of the robots. Intrusion detection becomes increasingly difficult if the robots aren’t equipped with a global localization system, i.e., GPS devices, for then one can’t create a map of the region seen by the robots.

In cases where GPS is unavailable, the mathematical field of topology provides useful tools for intrusion detection. Like geometry, topology studies shapes. However, topology ignores some aspects of shape that are important in geometry, such as distances and coordinates—precisely the aspects of shape measured by GPS devices. Vin de Silva of Pomona College and Robert Ghrist of the University of Pennsylvania were among the first to apply topology to robot swarms. They created an algorithm for mobile robots without GPS devices which, if no moving robot sees an intruder, can often guarantee there was no intruder in the region.

A downside to the algorithm of de Silva and Ghrist is that it isn’t streaming. Data must be stored from when the robots start moving until they stop. Hence, it becomes computationally expensive for robotic swarms moving over extended periods of time. IMA postdoctoral fellow Henry Adams and Gunnar Carlsson of Stanford University have taken this work a step further by creating a more efficient streaming algorithm where data can be measured, processed, and then discarded in real time.

As a graduate student, Adams first learned about applications of topology to robot swarms during a lecture given by Ghrist at the 2009 IMA Short Course on Applied Algebraic Topology. Adams wrote his Ph.D. thesis on this topic and then returned to the IMA as a postdoctoral fellow for the 2013-2014 IMA thematic year on Scientific and Engineering Applications of Algebraic Topology,Âť co-organized by Carlsson and Ghrist and attended by de Silva. In May 2014, the work of Adams and Carlsson was accepted for publication by the International Journal of Robotics Research. This research, using the sophisticated concepts of topology, is a significant step forward in developing and deploying robotic swarms for intrusion detection.