Markov Localization using Correlation

Kurt Konolige, Ken ChouIJCAI 1999

Abstract

This paper introduces Correlation-Based Markov Localization (CBML), a significant optimization for robot self-localization. By adapting techniques from image processing, the authors transform the computationally intensive task of Markov Localization into a fast correlation operation. This approach achieves a 75-fold speedup over contemporary state-of-the-art methods, enabling real-time global localization and the ability to handle dynamic environment changes, such as opening doors, without pre-computation bottlenecks.

The Challenge of Real-Time Localization

In the late 1990s, Markov Localization (ML) was the standard for mobile robot navigation. It maintains a probability distribution over all possible robot poses (locations and orientations). However, "dense" ML—which utilizes every point in a laser scan—was historically slow. To achieve real-time performance, researchers often relied on pre-computing expected sensor readings for every map location. This led to two primary issues:

  1. Static Map Dependency: Pre-computed data became invalid if the environment changed (e.g., a door opening), causing robot confusion.
  2. Computational Overhead: Global localization—determining position with no prior knowledge—could take minutes of processing time.

Methods: Localization as Correlation

The core innovation of CBML is treating the robot's sensor scan as a small "patch" and the environment map as a large "image."

  • Correlation as Localization: Instead of calculating the probability of a specific laser reading for every pose, the system correlates the scan patch against the map. High correlation values indicate likely matches.
  • Log-Grid Updates: Calculations are performed in log-space, converting expensive multiplications into simple additions.
  • Hardware Acceleration (SIMD): The regularity of the correlation operation allows for the use of Single-Instruction, Multiple Data (SIMD) instructions, enabling the processor to calculate multiple poses simultaneously.
Figure 5: The CBML approach treats the sensor scan as a "patch" to be correlated against the larger map grid, similar to template matching in computer vision.

Key Insights and Handling Uncertainty

A major finding was that "blurring" the map (accounting for wall position uncertainty) is often more effective than blurring the sensor model alone. This approach better handles depth discontinuities, such as the edges of walls.

Figure 3: Illustration of sensor variance in relation to environment walls. CBML manages this uncertainty by correlating blurred representations.

Furthermore, the authors chose to break the visibility constraint. While standard ML strictly calculates distances to the nearest object, CBML ignores this constraint to gain massive speed. The authors demonstrated that this trade-off makes the system more robust to map errors without significantly sacrificing accuracy.

Key Results

  • Massive Speedup: On a 400 MHz Pentium II, CBML achieved a processing rate of <1 ns per pose-reading, compared to 75 ns for the best-optimized standard ML algorithms of the era.
  • Real-time Performance: The system could perform local tracking at "video rates" and complete a full global localization (searching through 20 million possible poses) in less than one second.
  • Dynamic Handling: The paper successfully demonstrated a robot localizing in a room where a door's state (open or closed) was unknown, using "disjunctive maps" that represent multiple possible states simultaneously.

Limitations and Future Work

While highly efficient, CBML can occasionally produce "spurious features" or ghost matches because it ignores visibility constraints (the robot might think it "sees" through a wall). Additionally, like all grid-based methods, memory requirements scale with map size and resolution. Future work suggests applying these correlation techniques to "close the loop" in SLAM (Simultaneous Localization and Mapping) by matching large chunks of previously mapped areas to detect return visits to known locations.

Summary updated

BibTeX
@inproceedings{konolige1999markov,
  author = {Kurt Konolige and Ken Chou},
  title = {{Markov Localization using Correlation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure