Fast Value Iteration for Goal-Directed Markov Decision Processes
Nevin Zhang, Weihong Zhang
Planning problems where effects of actions are non-deterministic can be modeled as Markov decision processes. Planning problems are usually goal-directed. This paper proposes several techniques for exploiting the goal-directedness to accelerate value iteration, a standard algorithm for solving Markov decision processes. Empirical studies have shown that the techniques can bring about significant speedups.
Keywords: Decision-theoretic planning, markov decision processes, value iteration, efficiency.
PS Link: file://ftp.cs.ust.hk/pub/lzhang/uai97zhang.ps.gz
PDF Link: /papers/97/p489-zhang.pdf
AUTHOR = "Nevin Zhang
and Weihong Zhang",
TITLE = "Fast Value Iteration for Goal-Directed Markov Decision Processes",
BOOKTITLE = "Proceedings of the Thirteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)",
PUBLISHER = "Morgan Kaufmann",
ADDRESS = "San Francisco, CA",
YEAR = "1997",
PAGES = "489--494"