Integrating Planning and Execution in Stochastic Domains

Richard Dearden, Craig BoutilierUAI 1994 · OpenReview

TL;DR

This paper introduces a novel approach to planning in time-critical, stochastic environments by interleaving action execution with search. By executing actions as plans are built, the system dynamically prunes the search space, leading to near-optimal policies with significantly reduced computational cost compared to traditional methods.

What Problem Does This Paper Address?

Planning in domains where actions have uncertain outcomes (stochastic domains) is a fundamental challenge in AI. Traditional methods like dynamic programming (e.g., value or policy iteration) can compute optimal policies, but they are computationally expensive, especially for large state spaces. This makes them impractical for real-time applications where decisions must be made quickly. Dean et al. (1993a; 1993b) proposed an "envelope" approach to relax optimality for anytime planning, but this paper tackles the problem from a different angle: by viewing MDPs as search problems and integrating execution directly into the planning loop. The core challenge is to find good, near-optimal plans quickly in domains where time is a critical resource.

Methods

The paper proposes an algorithm that interleaves planning and execution. Instead of building a complete plan before acting, the agent:

  1. Builds a partial decision tree: For the current state, it constructs a search tree to a limited depth, using a heuristic function to estimate state values.
  2. Selects and executes the best action: Based on the partial tree and heuristic, it chooses the action with the highest estimated utility and executes it.
  3. Observes the outcome: The agent observes the actual resulting state, which is known with certainty.
  4. Repeats: The process restarts from the new, observed state.

This "search-execution" loop dynamically prunes the search space. By observing the actual outcome, the agent avoids exploring branches of the search tree corresponding to unrealized outcomes. The algorithm also incorporates:

  • Heuristic functions: These estimate state values, guiding the search and preventing purely greedy choices. The paper discusses methods for generating these, including abstraction by ignoring propositions.
  • Pruning techniques: Similar to minimax search, "utility pruning" and "expectation pruning" are used to cut off branches of the search tree that cannot lead to better solutions, further reducing computation.
  • Caching: Best actions for visited states are cached to avoid recomputation if the agent revisits a state.

Datasets

Not discussed in the paper. The authors use a custom domain based on a robot delivering coffee and snacks, with 256 states and six actions, for experimental evaluation.

Key Insights and Ideas

  • Execution as a powerful pruning mechanism: The most significant insight is that interleaving execution with search dramatically reduces the effective search space. By committing to an action and observing its outcome, the agent eliminates the need to consider alternative, unrealized outcomes, which is a major computational burden in standard stochastic planning.
  • Heuristics bridge the gap between reactive and deliberative planning: The heuristic function acts as a reactive policy, providing a default action. The search process then uses deliberation to refine this reactive strategy, leading to better performance than purely reactive or purely deliberative (but slow) approaches.
  • Abstraction for heuristic generation: Generating effective heuristics is crucial. The paper highlights abstraction by ignoring propositions as a viable method, allowing for efficient computation of heuristic values and bounds useful for pruning.
  • Trade-offs are inherent: The paper emphasizes the need to balance search depth, heuristic detail, and available time. Deeper search generally yields better policies but at a higher computational cost.

Key Results

  • Significant speedup: The search-execution framework performs better than straight search, especially for deeper search. Figure 7 shows that search with execution is significantly faster than search without execution, particularly for longer sequences of actions. For example, at depth 5, search with execution takes 55.4 seconds, while search without execution takes 102 seconds.
  • Near-optimal policies: The algorithm can find policies that are very close to optimal. Figure 5a shows that for a specific state, a near-optimal reward is achieved with a search depth of 4, requiring less than 5 seconds per state. Figure 6 indicates that policies found with search depths of 4 and 5 have very few errors compared to the optimal policy.
  • Pruning effectiveness: Utility pruning and expectation pruning demonstrably reduce the number of states searched and the time required. Utility pruning, in particular, removes about 20% of states at depth 5.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that expectation pruning can be slower than no pruning at all, though it might be worthwhile for deep searches.
  • The effectiveness of the approach is tied to the quality of the heuristic function.
  • The current model assumes complete observability of states after action execution.
  • Future Work:
    • Investigate variable-depth search and methods for improving heuristic functions by recording state values (not just actions).
  • Explore the framework in other domains like high-level robot navigation and scheduling.
  • Extend the model to handle semi-Markov processes and partially observable processes.
  • Investigate how the restricted envelope approach can be integrated.
  • Further theoretical analysis of the algorithm's properties, especially regarding the value of deeper searching.

Summary updated

Abstract

We investigate planning in time-critical domains represented as Markov Decision Processes, showing that search based techniques can be a very powerful method for finding close to optimal plans. To reduce the computational cost of planning in these domains, we execute actions as we construct the plan, and sacrifice optimality by searching to a fixed depth and using a heuristic function to estimate the value of states. Although this paper concentrates on the search algorithm, we also discuss ways of constructing heuristic functions suitable for this approach. Our results show that by interleaving search and execution, close to optimal policies can be found without the computational requirements of other approaches.
BibTeX
@inproceedings{dearden1994integrating,
  author = {Richard Dearden and Craig Boutilier},
  title = {{Integrating Planning and Execution in Stochastic Domains}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1994},
  url = {https://openreview.net/forum?id=oexPE9ni2A_},
}
Figure