Markov Decision Processes (MDPs) are a classical framework for
stochastic sequential decision problems, based on an enumerated state
space representation. More compact and structured representations have
been proposed: factorization techniques use state variables
representations, while decomposition techniques are based on a
partition of the state space into sub-regions and take advantage of
the resulting structure of the state transition graph. We use a family
of probabilistic exploration-like planning problems in order to study
the influence of the modeling structure on the MDP solution. We first
discuss the advantages and drawbacks of a graph based representation
of the state space, then present our comparisons of two decomposition
techniques, and propose to use a global approach combining both state
space factorization and decomposition techniques. On the exploration
problem instance, it is proposed to take advantage of the natural
topological structure of the navigation space, which is partitioned
into regions. A number of local policies are optimized within each
region, that become the macro-actions of the global abstract MDP
resulting from the decomposition. The regions are the corresponding
macro-states in the abstract MDP. The global abstract MDP is obtained
in a factored form, combining all the initial MDP state variables and
one macro-state “region” variable standing for the different possible
macro-states corresponding to the regions. Further research is
presently conducted on efficient solution algorithms implementing the
same hybrid approach for tackling large size MDPs.