  We describe an approach for exploiting structure in Markov Decision Processes
with continuous state variables. At each step of the dynamic programming, the
state space is dynamically partitioned into regions where the value function is
the same throughout the region. We first describe the algorithm for piecewise
constant representations. We then extend it to piecewise linear
representations, using techniques from POMDPs to represent and reason about
linear surfaces efficiently. We show that for complex, structured problems, our
approach exploits the natural structure so that optimal solutions can be
computed efficiently.
