期刊名称：Journal of Automation, Mobile Robotics & Intelligent Systems (JAMRIS)
印刷版ISSN：1897-8649
电子版ISSN：2080-2145
出版年度：2008
卷号：31
页码：33-82
出版社：Industrial Research Inst. for Automation and Measurements, Warsaw
摘要：Probabilistic planning problems are typically modeled as a Markov Decision
Process (MDP). MDPs, while an otherwise expressive model, allow only for
sequential, non-durative actions. This poses severe restrictions in modeling and
solving a real world planning problem. We extend the MDP model to incorporate 1)
simultaneous action execution, 2) durative actions, and 3) stochastic durations.
We develop several algorithms to combat the computational explosion introduced
by these features. The key theoretical ideas used in building these algorithms
are -- modeling a complex problem as an MDP in extended state/action space,
pruning of irrelevant actions, sampling of relevant actions, using informed
heuristics to guide the search, hybridizing different planners to achieve
benefits of both, approximating the problem and replanning. Our empirical
evaluation illuminates the different merits in using various algorithms, viz.,
optimality, empirical closeness to optimality, theoretical error bounds, and
speed
