A Probabilistic Approach to Automated Construction of Topological Maps using a Stochastic Robotic Swarm

Abstract

In this paper, we present a novel procedure for constructing a topological map of an unknown environment from data collected by a swarm of robots with limited sensing capabilities and no communication or global localization. Topological maps are sparse roadmap representations of environments that can be used to identify collision-free trajectories for robots to navigate through a domain. Our method uses uncertain position data obtained by robots during the course of random exploration to construct a probability function over the explored region that indicates the presence of obstacles. Techniques from topological data analysis, in particular the concept of persistent homology, are applied to the probability map to segment the obstacle regions. Finally, a graph-based wave propagation algorithm is applied to the obstacle-free region to construct the topological map of the domain in the form of an approximate generalized Voronoi diagram. We demonstrate the effectiveness of our approach in a variety of simulated domains and in multirobot experiments on a domain with two obstacles.