Global Localization and Topological Map-Learning for Robot Navigation

David Filliat, Jean-Arcady Meyer2002

TL;DR

This paper presents a novel robot navigation system that autonomously builds a topological map of its environment while simultaneously localizing itself within that map. It achieves this using simple sensors and algorithms inspired by biological navigation, enabling robust operation even when the robot is passively moved.

What Problem Does This Paper Address?

Navigating autonomously in an unknown environment is a fundamental challenge for robots. This involves three key problems: map-learning (building a representation of the environment), localization (determining the robot's position within that map), and path planning (finding a route to a goal). A major hurdle is the "chicken and egg" problem: you need a map to localize, but you need to know your position to build a map. Existing methods often struggle with either autonomy (requiring initial positioning) or robustness, especially when dealing with perceptual aliasing (where different locations look similar). This paper tackles the challenge of achieving both global localization and on-line map-learning autonomously, without relying on complex metrical sensor models, drawing inspiration from how animals navigate.

Methods

The core of the system is a topological map where nodes represent distinct locations and links represent the relative positions (distance and direction) between them. The system uses a multiple-hypothesis tracking (MHT) approach, inspired by Partially Observable Markov Decision Processes (POMDPs), to maintain a probability distribution over possible robot locations.

Key algorithmic components include:

  • Allothetic Sensor Integration: Sonar and visual sensor data are used to compare current perceptions with stored data in the map. A probability function Po(OM/OP) quantifies the similarity between current and perceived data.
  • Idiothetic Sensor Integration: Odometry data (robot's own movement estimates) is used to update the probability of transitioning between map nodes. This is modeled by PD(AB/od).
  • Activity Updates: The probability distribution over map nodes (node activities) is updated iteratively. This involves integrating both allothetic and idiothetic sensor information.
  • Position Estimation & Map Updates: A novel heuristic based on the sum of node activities (Sa) is used to determine if the robot is within the mapped area. If Sa >= 1, the most probable node is chosen as the current position. If Sa < 1, it suggests the robot might be outside the mapped area, and a temporary single-hypothesis tracking method is employed until it re-enters. New nodes are created if the robot is in an unmapped area.
  • Map Consistency: A relaxation algorithm is used to ensure the consistency of the topological map, making relative positions between nodes more accurate.
  • Exploration Strategy: The system prioritizes exploring less-mapped areas to ensure coverage. When the robot is temporarily lost (outside the mapped area), it retraces its steps to re-enter the mapped region.
  • Path Planning: A spreading-activation algorithm is used to plan paths to goals, and a detour mechanism handles unforeseen obstacles.

A significant methodological choice is the avoidance of metrical sensor models. This allows the system to use a wider range of sensory inputs (like colors or odors) and makes it more generalizable, akin to biological navigation.

Datasets

The paper describes experiments conducted on a real Pioneer 2 mobile robot in a laboratory environment (corridors). The data used for evaluation was collected from this real-world setup. No specific public datasets are mentioned, and the paper focuses on the performance of the system in its own experimental environment.

Key Insights and Ideas

  • Autonomous Map-Learning and Localization: The system's ability to build a map and localize itself simultaneously without human intervention is a significant achievement, addressing a core challenge in robotics.
  • Robustness without Metrical Models: By avoiding metrical sensor models, the system gains generality and can leverage simpler sensors, making it more adaptable and potentially more akin to biological systems. This is achieved through clever heuristics and MHT.
  • Heuristic for Map Boundary Detection: The novel heuristic based on the sum of node activities (Sa) to detect when the robot leaves the mapped area is crucial for maintaining robustness and deciding when to switch between global localization and temporary tracking.
  • Biological Inspiration: The work draws strong parallels to biological navigation systems (e.g., place cells in the hippocampus), suggesting that probabilistic frameworks and MHT might be fundamental to how animals navigate.

Key Results

  • The system successfully built a dense topological map of a laboratory environment.
  • The robot's position could be estimated with a precision of approximately 50 cm, which is considered sufficient for many navigation tasks.
  • The system demonstrated effective global localization, even after being passively moved to a new location.
  • The heuristic for detecting when the robot leaves the mapped area proved robust, though real-world experiments showed some limitations due to sensor noise and perceptual aliasing.
  • Path planning experiments showed successful goal reaching, with final positions within 80 cm of the target in most trials.

Limitations and Future Work

  • Perceptual Aliasing in Real-World Scenarios: The real robot's vision system was noisier than simulated systems, leading to increased perceptual aliasing and temporary inefficiencies in re-localization, especially when similar-looking corridors were involved.
  • Direction Estimation: The current system relies on odometry for direction estimation, with periodic manual correction. Automating this by learning to associate landmarks with orientation is a key area for future work.
  • Exploration Strategy: While local exploration is emphasized for robustness, an active navigation strategy that guides the robot towards areas where re-localization is more efficient is suggested for future improvement.
  • Omnidirectional Camera: The use of a directional camera led to longer processing times. Using an omnidirectional camera is proposed to significantly reduce mapping time.
  • Wider Environments: Further experiments in more open environments are planned to assess the system's performance beyond corridors.
  • Biological Parallels: The authors suggest that further investigation into how the hippocampus might implement global localization could be fruitful.

Summary updated

Abstract

This paper describes a navigation system implemented on a real mobile robot. Using simple sonar and visual sensors, it makes possible the autonomous construction of a dense topological map representing the environment. At any time during the mapping process, this system is able to globally localize the robot, i.e. to estimate the robot&amp;apos;s position even if the robot is passively moved from one place to another within the mapped area. This is achieved using algorithms inspired by Hidden Markov Models adapted to the on-line building of the map. Advantages and drawbacks of the system are discussed, along with its potential implications for the understanding of biological navigation systems.
BibTeX
@misc{filliat2002global,
  author = {David Filliat and Jean-Arcady Meyer},
  title = {{Global Localization and Topological Map-Learning for Robot Navigation}},
  year = {2002},
}
Figure