Thinning-based topological exploration using position possibility of topological nodes

Tae Bum Kwon, Jae Bok Song

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


A grid map can be efficiently used in navigation, but this type of map requires a large amount of memory in proportion to the size of the environment. As an alternative, a topological map can be used to represent the environment in terms of discrete nodes with edges connecting them. It is usually constructed by Voronoi-like graphs, but in this paper the topological map is built based on the local grid map by using a thinning algorithm. This new approach can easily extract the topological information in real-time and be robustly applicable to the real environment, and this map can be autonomously built by exploration. The position possibility is defined to evaluate the quantitative reliability of the topological map and then a new exploration scheme based on the position possibility is proposed. From the position possibility information, the robot can determine whether or not it needs to visit a specific end node, which node will be the next target and how much of the environment has yet been explored. Various experiments showed that the proposed map-building and exploration methods can accurately build a local topological map in real-time and can guide a robot safely even in a dynamic environment.

Original languageEnglish
Pages (from-to)339-359
Number of pages21
JournalAdvanced Robotics
Issue number2-3
Publication statusPublished - 2008 Mar 1


  • Mobile robot
  • Position possibility
  • Thinning
  • Topological exploration
  • Topological map building

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Human-Computer Interaction
  • Hardware and Architecture
  • Computer Science Applications


Dive into the research topics of 'Thinning-based topological exploration using position possibility of topological nodes'. Together they form a unique fingerprint.

Cite this