Tech Report CS-97-04

Learning Hidden Markov Models with Geometric Information

Hagit Shatkay and Leslie Pack Kaelbling

April 1997

Abstract:

Hidden Markov models (\textsc{hmm}s) and partially observable Markov decision processes (\textsc{pomdp}s) provide a useful tool for modeling dynamical systems. They are particularly useful for representing environments such as road networks and office buildings, which are typical for robot navigation and planning. In a previous paper [Shatkay and Kaelbling 1997] we have empirically shown that by taking advantage of readily available odometric information, learning \textsc{hmm}s/\textsc{pomdp}s can be made faster and better. This paper extends our previous results in two ways. We show that our algorithm, which introduces an additional data structure and constraints to the standard \textsc{hmm} and extends the Baum-Welch algorithm to accommodate them, indeed converges to a local maximum of the likelihood function. In addition, we extend our empirical study, and show that the algorithm is robust in the face of reduction in the length of the training sequences. Thus, the use of local odometric information yields faster convergence to better solutions with less data.

(complete text in pdf or gzipped postscript)