15th European Conference on Artificial Intelligence
|July 21-26 2002 Lyon France|
Recently, several authors have proposed serial decomposition techniques for solving approximately or exactly large Markov Decision Processes. Many of these techniques rely on a clever partitioning of the state space in roughly independent parts. The different parts only communicate through relatively few communicating states. The efficiency of these decomposition methods clearly depends on the size of the set of communicating states : the smaller, the better. However, the task of finding such a decomposition with few communicating states is often (if not always) left to the user. In this paper, we present automated decomposition techniques for MDPs. These techniques are based on methods which have been developed for graph partitioning problems.
Keywords: Reasoning Under Uncertainty, Markov Decision Processes
Citation: Regis Sabbadin: Graph partitioning techniques for Markov Decision Processes decomposition. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.670-674.