Online Planning in MDPs with Stochastic Durative Actions

Tal Berman, Ronen I. Brafman, Erez KarpasIJCAI 2025 · DOI

TL;DR

This paper introduces TP-MCTS, the first online planning algorithm capable of handling stochastic, durative actions that can execute concurrently. It extends traditional planning by allowing actions to have durations and uncertain outcomes, while still respecting temporal constraints like deadlines, and achieves state-of-the-art results on complex temporal planning problems.

What Problem Does This Paper Address?

Traditional planning methods often model actions as instantaneous events. However, in many real-world scenarios, actions take time to complete (durative actions) and can occur simultaneously (concurrent actions). Furthermore, these actions often have uncertain outcomes (stochastic effects), meaning they might succeed, fail, or have unintended side effects. While Markov Decision Processes (MDPs) handle stochastic actions, they typically assume sequential, instantaneous execution. Temporal planning (TP) deals with action durations and concurrency but usually assumes deterministic outcomes. This paper bridges this gap by addressing the challenging problem of planning with stochastic, durative, and concurrent actions while respecting temporal constraints like deadlines. This is crucial for applications like robotics, multi-agent systems, and smart homes where precise timing and uncertainty are paramount.

Methods

The core of the paper is the TP-MCTS (Temporal Planning Monte Carlo Tree Search) algorithm. It combines the strengths of Monte Carlo Tree Search (MCTS), a popular online planning technique, with classical temporal planning concepts.

Here's a breakdown of the key innovations:

  • CoMDP+ Model: They define a richer planning model that extends MDPs to include deterministic action durations, concurrency, temporal constraints (like deadlines), and stochastic effects.
  • Offline Preprocessing: Durative actions are split into two "snap actions" (start and end) with associated start and end effects. This allows the planner to reason about actions as if they were instantaneous, while maintaining temporal constraints using Simple Temporal Networks (STNs).
  • TP-MCTS Algorithm:
    • Temporal Tree Structure: The search tree in MCTS is augmented to store not just states but also STNs, representing the temporal relationships between actions.
  • PTRPG Heuristic: Instead of standard MCTS rollouts, they introduce a novel heuristic called Probabilistic Temporal Relaxed Planning Graph (PTRPG). This heuristic estimates the probability of achieving the goal within the deadline, considering temporal information.
  • Novel Backpropagation: A new backpropagation method is used to propagate temporal information (represented as functions over time intervals) up the search tree, rather than just scalar values.
  • Scheduling: TP-MCTS not only decides which action to execute but also when to dispatch it, considering temporal constraints and the overall plan.
  • Two Variants: They propose two versions of TP-MCTS: "Earliest" (simpler, faster in less complex domains) and "Root-Interval" (more sophisticated, better for complex temporal dependencies).

Datasets

The paper evaluates their approach on a variety of domains:

  • Structured Domains: NASA Rover and Machine Shop (adapted from previous work to include durations and stochastic effects).
  • New Domains: Stuck-Car (new domain with stochastic effects and concurrency), Hosting (new domain with required concurrency and deadlines), and Probabilistic Match-Cellar (probabilistic variant of a known domain with required concurrency).
  • Synthetic Domains: Simple-x and Conc (designed to study specific algorithmic properties like scalability and concurrency).

The authors note that their implementation supports domain representations written in the Unified Planning Framework.

Key Insights and Ideas

  • Bridging the Gap: The most significant insight is the successful integration of stochasticity, action durations, and concurrency into an online planning framework. This tackles a problem previously addressed only by computationally expensive offline methods.
  • Temporal Reasoning is Crucial: The paper highlights that simply treating actions as instantaneous or sequential is insufficient for many real-world problems. Explicitly modeling and reasoning about time, deadlines, and action overlaps is essential for achieving goals.
  • Heuristics Matter: The development of PTRPG demonstrates that domain-specific, temporally-aware heuristics can significantly improve the performance of MCTS in complex planning scenarios, outperforming standard rollout-based approaches.
  • Scalability through Representation: By transforming the problem into a factored MDP with snap actions and using STNs, TP-MCTS achieves better scalability than methods that might resort to exponential state-space expansions.
  • Online Planning Advantage: The online nature of TP-MCTS allows it to adapt to uncertainty and make decisions incrementally, making it more practical for dynamic environments compared to offline planners.

Key Results

  • State-of-the-Art Performance: TP-MCTS (particularly the root-interval variant) consistently outperforms the closest relevant algorithm (MW-RTDP and MW-MCTS) across a wide range of domains, achieving significantly higher success rates.
  • Handling Required Concurrency: TP-MCTS is the first online algorithm shown to effectively handle problems with required concurrency, which are unsolvable by MW's method.
  • Scalability: The algorithm demonstrates better scalability than previous methods, especially in domains with a large number of actions and propositions.
  • Efficiency: Offline compilation times are very fast (often less than 0.01 seconds), making it practical for online use.
  • Root-Interval Superiority: While the "Earliest" variant performs well in simpler domains, the "Root-Interval" variant is crucial for solving problems with complex temporal dependencies and deadlines.

Limitations and Future Work

  • Heuristic Tuning: The authors acknowledge that the PTRPG heuristic uses simple, fixed parameters. Optimizing these parameters, potentially per domain, could lead to further improvements.
  • Soft Mutex Definition: The current implementation uses a simplified global definition of mutex actions. More nuanced, state-dependent mutex definitions could be incorporated.
  • Reward Functions: The current focus is on goal-oriented problems. Extending the framework to handle reward functions (beyond just goal achievement probability) would be a natural next step.
  • Partial Observability: The current work assumes full observability. Incorporating partial observability would significantly increase the complexity but is a relevant extension for real-world applications.
  • Action Interruptions: The current model assumes actions cannot be stopped once started. Allowing for interruptions could add flexibility.

Summary updated

BibTeX
@inproceedings{berman2025online,
  author = {Tal Berman and Ronen I. Brafman and Erez Karpas},
  title = {{Online Planning in MDPs with Stochastic Durative Actions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/941},
}
Figure