Online Planning in MDPs with Stochastic Durative Actions

Online Planning in MDPs with Stochastic Durative Actions

Tal Berman, Ronen I. Brafman, Erez Karpas

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence
Main Track. Pages 8465-8473. https://doi.org/10.24963/ijcai.2025/941

Stochastic planning problems are typically modeled as Markov Decision Processes, in which actions are assumed to be instantaneous and applied sequentially. Yet, real-world actions often have durations and are applied concurrently. This paper presents an online planning approach that can deal with durative actions with stochastic outcomes. Our approach relies on Monte Carlo Tree Search with a new backpropagation procedure and temporal reasoning techniques that address the need to not only choose which action to execute, but also when to execute it. We also introduce a novel heuristic that combines reasoning about time and probabilities. Overall, we present the first online planner for stochastic temporal planning, solving a richer problem representation than previous work while achieving state-of-the-art empirical results.
Keywords:
Planning and Scheduling: PS: Planning algorithms
Planning and Scheduling: PS: Markov decisions processes
Planning and Scheduling: PS: Planning under uncertainty