Automated Creation of Topological Maps in Unknown Environments Using a Swarm of Resource-Constrained Robots

Abstract

We address the development of the theory and algorithms that can enable a swarm of inexpensive robots or mobile sensors to create topological maps of unknown environments without explicitly requiring metric information. Topological maps are sparse and faithful representations of environments, and are useful constructions for efficient navigation in GPS-denied environments. However, in the absence of prior knowledge of the environment, with extremely limited sensing capabilities, and in an environment without localization, the construction of a topological map is a challenging problem that has not received much attention in the literature. In this letter, we present the algorithmic tools for constructing a topological map of an unknown GPS-denied environments using a swarm of resource-constrained robots. This method involves covering the free space, and then constructing an approximate generalized Voronoi graph of the covered environment. We demonstrate the algorithm using ROS, first with simulations, and then with experiments using a combination of real and virtual (simulated) robots.