Tech Report CS-98-11

Learning Models for Robot Navigation

Hagit Shatkay

December 1998


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. The work presented here describes a formal framework for incorporating readily available odometric information into both the models and the algorithm that learns them. By taking advantage of such information, learning \textsc{hmm}s/\textsc{pomdp}s can be made better and require fewer iterations, while being robust in the face of data reduction. That is, the performance of our algorithm does not significantly deteriorate as the training sequences provided to it become significantly shorter. Formal proofs for the convergence of the algorithm to a local maximum of the likelihood function are provided. Experimental results, obtained from both simulated and real robot data, demonstrate the effectiveness of the approach.

(complete text in pdf or gzipped postscript)