Proceedings

Online Planning in MDPs with Stochastic Durative Actions

Tal Berman, Ronen I. Brafman, Erez Karpas

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8465-8473.

https://doi.org/10.24963/ijcai.2025/941

Keywords

  • Planning and Scheduling: PS: Markov decisions processes
  • Planning and Scheduling: PS: Planning algorithms
  • Planning and Scheduling: PS: Planning under uncertainty

Abstract

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.

Tal Berman, Ronen I. Brafman, and Erez Karpas. 2025. Online Planning in MDPs with Stochastic Durative Actions. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8465–8473. https://doi.org/10.24963/ijcai.2025/941
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards