Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap

Leslie Pack Kaelbling, Hagit Shatkay

Abstract

Hidden Markov models (HMMs) and partially observable Markov decision processes (POMDPs) provide useful tools for modeling dynamical systems, particularly for representing the topology of environments like road networks and office buildings. This paper describes a formal framework for incorporating readily available odometric information and geometrical constraints into both the models and the learning algorithms. By leveraging such information, learning HMMs/POMDPs can generate superior solutions with fewer iterations while remaining robust in the face of data reduction. Experimental results from both simulated and real robot data demonstrate the effectiveness of this approach.

Introduction

In the field of robot navigation, researchers typically navigate a trade-off between two mapping paradigms: geometric maps and topological maps. Geometric maps provide fine-grained metric grids but are susceptible to "drift"—the accumulation of small errors in wheel encoders that compromises long-term positioning. Conversely, topological maps represent the environment as abstract graphs of states and transitions. While better for high-level planning, topological maps are notoriously difficult to learn from scratch due to perceptual aliasing, where distinct locations (e.g., two identical doors in different hallways) appear identical to sensors.

This research addresses the challenge of automatically learning topological models by treating noisy odometry not as absolute truth, but as a set of geometric constraints. By bridging the gap between metric and topological data, the proposed framework allows robots to learn more accurate maps with significantly less data.

The Augmented HMM Framework

The core innovation is the Augmented HMM. While a standard HMM models state transitions and observations, this model incorporates an "odometry vector" $(x, y, \theta)$ into every transition. To ensure the resulting map is physically plausible, the framework enforces three primary geometric consistency constraints:

  1. Zero Distance: The distance from a state to itself is defined as zero.
  2. Antisymmetry: The vector from state A to state B must be the negative of the vector from B to A.
  3. Additivity: The vector for a path $A \to B \to C$ must equal the vector for the direct transition $A \to C$.

Statistical and Algorithmic Refinements

To handle the unique nature of robotic sensor data, the authors introduced several technical refinements:

  • Circular Statistics: Standard Gaussian distributions fail for angular data (where $179^\circ$ and $-179^\circ$ are close). The model utilizes the von Mises distribution to accurately model heading changes.
  • Lag-Behind EM: To address the complex interdependencies between mean and variance during the Expectation-Maximization (EM) process, a "lag-behind" update rule is used to ensure convergence to a local maximum.
  • Tag-Based Initialization: Rather than starting with a random map, the algorithm uses a heuristic clustering of odometry data to create an initial "guess" of the environment's layout, preventing the model from getting stuck in poor local maxima.

Experimental Evaluation

The approach was evaluated using two distinct datasets:

  1. Simulated Hallway Environment: A 44-state model of a complex office layout used for rigorous statistical testing.
  2. Real Robot Data ("Ramona"): Data collected from a modified RWI B21 robot navigating a real office building, testing the algorithm's resilience to real-world sensor noise and non-perpendicular geometry.

Key Results

The inclusion of geometric constraints yielded dramatic improvements over the standard Baum-Welch (HMM) learning algorithm:

  • Accuracy: The error (measured via KL-divergence) was 5 to 8 times lower than models learned without odometry.
  • Convergence Speed: The algorithm required 4 to 5 times fewer iterations to reach a solution.
  • Data Efficiency: The constrained model maintained high performance even when the training sequence was reduced to just 200 data points, a threshold where standard HMM performance typically collapses.
  • Qualitative Mapping: Resulting maps closely resembled physical floor plans, whereas unconstrained HMMs often produced topologically incorrect "spaghetti" graphs.

Discussion and Future Work

The research demonstrates that consistency is often more valuable than absolute accuracy. Even noisy odometry acts as a powerful regularizer, providing the context needed to solve perceptual aliasing. If two locations look identical but are separated by 50 meters of travel, the geometrically-constrained HMM correctly identifies them as distinct states.

However, some challenges remain. The computational cost of von Mises densities (involving Bessel functions) is higher than standard HMM calculations, though this can be mitigated with lookup tables. Additionally, there is a risk of "over-constraining" the model in very large environments, where strict additivity might trap the algorithm in locally consistent but globally incorrect solutions. Future work may explore automatically adjusting the state count ($N$) during learning and applying these geometric constraints to other domains, such as molecular modeling or air traffic pattern analysis.

Summary updated

Abstract

Hidden Markov models (HMMs) and partially observable Markov decision processes (POMDPs) provide useful tools for modeling dynamical systems. They are particularly useful for representing the topology of environments such as road networks and office buildings, which are typical for robot navigation and planning. The work presented here describes a formal framework for incorporating readily available odometric information and geometrical constraints into both the models and the algorithm that learns them. By taking advantage of such information, learning HMMs/POMDPs can be made to generate better solutions and require fewer iterations, while being robust in the face of data reduction. Experimental results, obtained from both simulated and real robot data, demonstrate the effectiveness of the approach.
BibTeX
@article{kaelbling2002learning,
  author = {Leslie Pack Kaelbling and Hagit Shatkay},
  title = {{Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Topological-Geometrical Gap}},
  journal = {J. Artif. Intell. Res.},
  year = {2002},
  url = {https://openreview.net/forum?id=C5wJEqktaRcZ},
}
Figure