This work addresses the computational complexity of solving large
Markov decision processes by partitioning their state spaces into
nearly-independent regions.  We propose a method for developing
partial plans, or macros, over such regions that yields a polynomial
number of macros for each region.  Each macro represents knowledge
about how to achieve one particular sub-goal within its region of
interest, and we demonstrate a simple, linear-time rule for combining
these macros into a single full policy over the region and for
propagating value information between regions.  We empirically
demonstrate the efficacy of our approach on small MDPs, for which
exact solution is feasible, and give asymptotic analyses of its
scalability.