A Hierarchical Structure For Finite Horizon Dynamic Programming Problems

Chang Zhang and J.S. Baras

Number: CSHCN TR 2000-19, Year: 2000, Advisor: John S. Baras

Abstract

In dynamic programming (Markov decision) problems, hierarchicalstructure (aggregation) is usually used to simplify computation. Most research on aggregation ofMarkov decision problems is limited to the infinite horizon case, which has good tracking ability. However, in reallife, finite horizon stochastic shortest path problems are oftenencountered.

In this paper, we propose a hierarchical structure to solve finite horizon stochastic shortest pathproblems in parallel. In general, the approach reducesthe time complexity of the original problem to a logarithm level, which hassignificant practical meaning.