Learning and Using Hierarchical Maps in Robot Navigation

Graduate

Noisy sensor readings, uncertain action outcomes, and different locations in the environment that look the same make it difficult for a robot to know exactly where it is in its environment. Nevertheless, we can solve the robot navigation problem by modeling all this uncertainty using a probabilistic map, such as a Hidden Markov Model (HMM). In this probabilistic map the robot does not need to know exactly where it is, but instead it keeps track of a probability distribution of all the possible positions it could be in. The number of possible probability distributions however, is infinite and it is computationally infeasible to find a mapping from every probability distribution to the best action that will help the robot get to its goal. To make this problem feasible, we investigate a hierarchical map representation using the framework of hierarchical hidden Markov models (HHMM). The Hierarchical framework allows us to abstract low level robot positions (such as one meter positions in the environment) to high level states such as "corridors" and "intersections" and therefore making the number of probability distributions at the high level considerably less, while at the same time keeping track of the low level probability distributions. We trained different families of HHMMs (learned the model parameters) on a sample navigation problem using a real robot testbed and performed various experiments that compare hierarchical and flat models. The models are compared in terms of their ability to localize the robot (state estimation), goodness of fit to the data, speed of learning, quality of the learned map, ability to use previously learned submodels and ability to infer the abstract structure of the environment. We also constructed simulated robot environments where we experimented with a new planning solution that is motivated by the structure of HHMMs. Our results show that hierarchical HMM models provide a robust framework for learning and using multi-scale spatial models for robot navigation that outperform flat models.

Return to Workshop Listing