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

Ragesh K. Ramachandran, Sean Wilson, Spring Berman

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number7805135
Pages (from-to)616-623
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number2
StatePublished - Apr 1 2017


  • mapping
  • probability and statistical methods
  • Swarms

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Human-Computer Interaction
  • Biomedical Engineering
  • Mechanical Engineering
  • Control and Optimization
  • Artificial Intelligence
  • Computer Science Applications
  • Computer Vision and Pattern Recognition


Dive into the research topics of 'A Probabilistic Approach to Automated Construction of Topological Maps Using a Stochastic Robotic Swarm'. Together they form a unique fingerprint.

Cite this