A Framework for Planning in Continuous-time Stochastic Domains

Håkan L. S. Younes David J. Musliner Reid G. Simmons

Abstract
We propose a framework for policy generation in continuous-time stochastic domains with concurrent actions and events of uncertain duration. We make no assumptions regarding the complexity of the domain dynamics, and our planning algorithm can be used to generate policies for any discrete event system that can be simulated. We use the continuous stochastic logic (CSL) as a formalism for expressing temporally extended probabilistic goals and have developed a probabilistic anytime algorithm for verifying plans in our framework. We present an efficient procedure for comparing two plans that can be used in a hill-climbing search for a goal-satisfying plan. Our planning framework falls into the Generate, Test and Debug paradigm, and we propose a transformational approach to plan generation. This relies on effective analysis and debugging of unsatisfactory plans. Discrete event systems are naturally modeled as generalized semi-Markov processes (GSMPs). We adopt the GSMP as the basis for our planning framework, and present preliminary work on a domain independent approach to plan debugging that utilizes information from the verification phase.

Full paper: PDF (10 pages, 39 references)
Copyright © 2003, American Association for Artificial Intelligence. All rights reserved.

Presentation: PPT, PDF (34 slides)

Citings

  1. Douglas Aberdeen, Sylvie Thiébaux, and Lin Zhang. 2004. Decision-theoretic military operations planning. In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling, 402–411. AAAI Press.


Håkan L. S. Younes Valid CSS! Valid XHTML 1.0!
Last modified: Thu May 11 14:56:17 EDT 2006