Solving Generalized Semi-Markov Processes using Continuous Phase-Type Distributions

Håkan L. S. Younes Reid G. Simmons

We introduce the generalized semi-Markov decision process (GSMDP) as an extension of continuous-time MDPs and semi-Markov decision processes (SMDPs) for modeling stochastic decision processes with asynchronous events and actions. Using phase-type distributions and uniformization, we show how an arbitrary GSMDP can be approximated by a discrete-time MDP, which can then be solved using existing MDP techniques. The techniques we present can also be seen as an alternative approach for solving SMDPs, and we demonstrate that the introduction of phases allows us to generate higher quality policies than those obtained by standard SMDP solution techniques.

Full paper: PDF (6 pages, 15 references)
Copyright © 2004, American Association for Artificial Intelligence. All rights reserved.

Presentation: PPT, PDF (34 slides)


  1. Mausam and Daniel S. Weld. 2006. Challenges for temporal planning with uncertain durations. In Proceedings of the Sixteenth International Conference on Planning and Scheduling, 414–417. AAAI Press.

  2. Mausam, Emmanuel Benazera, Ronen Brafman, Nicolas Meuleau, and Eric A. Hansen. 2005. Planning with continous resources in stochastic domains. In Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, 1244–1251.

Håkan L. S. Younes Valid CSS! Valid XHTML 1.0!
Last modified: Fri Sep 28 15:37:32 EDT 2007