Hierarchical Map Learning For Robot Navigation
In this paper we investigate learning a hierarchy of maps at di erent spatial scales using the framework of hierarchical hidden Markov models (HHMM). This framework provides a formal mechanism to explicitly model stochastic processes at varying temporal abstraction, and hence gives a rigorous framework for constructing hierarchical models for applications such as autonomous oÆce navigation. Our research is also motivated by both cognitive science and engineering considerations. Animal and human navigation studies suggest they represent the external world at di erent spatial scales and use hierarchical planning strategies for navigation. However, existing robot navigation systems primarily learn at uniform resolution models, which are unlikely to scale to large environments. Our long-term goal is to use hierarchical maps as a basis for more eÆcient learning and planning algorithms that reuse already learned maps (and policies) in larger maps. Di erent families of HHMMs are trained on a sample navigation problem using a real robot testbed. We provide a detailed set of experiments comparing hierarchical models, hierarchical models with reuse, and at models. The models are compared in terms of their ability to localize the robot (state estimation), goodness of t to the data, speed of learning, quality of the learned map, and ability to use previously learned submodels and also infer the abstract structure of the environment. Overall, the results show hierarchical HMM models provide a robust framework for learning multiscale spatial models of real environments.