Augmented Markov Models

Dani Goldberg and Maja J. Mataric

This technical report presents augmented Markov models (AMMs), and provides detailed descriptions of their structure and one model construction algorithm. Augmented Markov models are essentially probabilistic transition networks similar to hidden Markov models (HMMs), except that the hidden state assumption is removed. Additional statistics (augmentations) are maintained in the links and nodes of AMMs and may be employed in model construction and utilization. The model construction algorithm we present is designed to have relatively low computational and space overheads, and provide useful models on-line and in real-time.