  Although many real-world stochastic planning problems are more naturally
formulated by hybrid models with both discrete and continuous variables,
current state-of-the-art methods cannot adequately address these problems. We
present the first framework that can exploit problem structure for modeling and
solving hybrid problems efficiently. We formulate these problems as hybrid
Markov decision processes (MDPs with continuous and discrete state and action
variables), which we assume can be represented in a factored way using a hybrid
dynamic Bayesian network (hybrid DBN). This formulation also allows us to apply
our methods to collaborative multiagent settings. We present a new linear
program approximation method that exploits the structure of the hybrid MDP and
lets us compute approximate value functions more efficiently. In particular, we
describe a new factored discretization of continuous variables that avoids the
exponential blow-up of traditional approaches. We provide theoretical bounds on
the quality of such an approximation and on its scale-up potential. We support
our theoretical arguments with experiments on a set of control problems with up
to 28-dimensional continuous state space and 22-dimensional action space.
