Challenges for temporal planning with uncertain durations

Few temporal planners handle both concurrency and uncer-tain durations, but these features commonly co-occur in real-world domains. In this paper, we discuss the challenges caused by concurrent, durative actions whose durations are uncertain. We present five implemented algorithms, includ-ing ∆DURprun, a planner guaranteed to find the optimal pol-icy. An empirical comparison reveals that ∆DURexp, our fastest planner, obtains orders of magnitude speed-up com-pared to ∆DURprun — with little loss in solution quality. Im-portantly, our algorithms can handle probabilistic effects in addition to stochastic durations, and they are effective even when duration distributions are multi-modal. 1