Learning Geometrically-Constrained Hidden Markov Models for Robot Navigation: Bridging the Geometrical-Topological Gap
Hagit Shatkay, Leslie Pack Kaelbling · 2002
You will come to a place where the streets are not marked. Some windows are lighted but mostly they're darked. A place you could sprain both your elbow and chin! Do you dare to stay out? Do you dare to go in?... And if you go in, should you turn left or right... or right-and-three-quarters? or, maybe, not quite?... Simple it's not, I'm afraid you will nd, for a mind-maker-upper to make up his mind. Oh, the Places You'll Go, Dr. Seuss. 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 oce buildings, which are typical for robot navigation and planning. The work presented here describes a formal framework for incorporating readily available odometric infor-mation 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 eectiveness of the approach. 1