A temporally abstracted Viterbi algorithm

摘要

Hierarchical problem abstraction, when ap plicable, may offer exponential reductions in computational complexity. Previous work on coarse-to-fine dynamic programming (CFDP) has demonstrated this possibility us ing state abstraction to speed up the Viterbi algorithm. In this paper, we show how to ap ply temporal abstraction to the Viterbi prob lem. Our algorithm uses bounds derived from analysis of coarse timescales to prune large parts of the state trellis at finer timescales. We demonstrate improvements of several or ders of magnitude over the standard Viterbi algorithm, as well as significant speedups over CFDP, for problems whose state vari ables evolve at widely differing rates.