15th European Conference on Artificial Intelligence
  July 21-26 2002     Lyon     France  

ECAI-2002 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

Graph partitioning techniques for Markov Decision Processes decomposition

Regis Sabbadin

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.

[prev] [tofc] [next]

ECAI-2002 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the UniversitÚ Claude Bernard and INSA, Lyon, on behalf of Association Franšaise pour l'Intelligence Artificielle.