Parallelizing Depth-First Search for Robotic Graph Exploration

Abstract

The collective behavior of robot swarms outfits them for comprehensive search of an environment, which is useful for terrain mapping, crop pollination, and related applications. We study efficient mapping of an obstacle-ridden environment by a collection of robots. We model the environment as an undirected, connected graph and require robots to explore the graph—to visit all nodes and traverse all edges. In this thesis, we present a graph exploration algorithm that parallelizes depthfirst search, so that each robot completes a roughly equal part of exploration. Through simulation, we show our parallel algorithm attains close to linear speedup when robots are able to disperse in the graph. We also provide experimental validation of a result from percolation theory.