Sequential Monte Carlo in reachability heuristics for probabilistic planning

Daniel Bryce, Subbarao Kambhampati, David E. Smith

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Some of the current best conformant probabilistic planners focus on finding a fixed length plan with maximal probability. While these approaches can find optimal solutions, they often do not scale for large problems or plan lengths. As has been shown in classical planning, heuristic search outperforms bounded length search (especially when an appropriate plan length is not given a priori). The problem with applying heuristic search in probabilistic planning is that effective heuristics are as yet lacking. In this work, we apply heuristic search to conformant probabilistic planning by adapting planning graph heuristics developed for non-deterministic planning. We evaluate a straight-forward application of these planning graph techniques, which amounts to exactly computing a distribution over many relaxed planning graphs (one planning graph for each joint outcome of uncertain actions at each time step). Computing this distribution is costly, so we apply Sequential Monte Carlo (SMC) to approximate it. One important issue that we explore in this work is how to automatically determine the number of samples required for effective heuristic computation. We empirically demonstrate on several domains how our efficient, but sometimes suboptimal, approach enables our planner to solve much larger problems than an existing optimal bounded length probabilistic planner and still find reasonable quality solutions.

Original languageEnglish (US)
Pages (from-to)685-715
Number of pages31
JournalArtificial Intelligence
Issue number6-7
StatePublished - Apr 2008


  • Heuristics
  • Planning

ASJC Scopus subject areas

  • Language and Linguistics
  • Linguistics and Language
  • Artificial Intelligence


Dive into the research topics of 'Sequential Monte Carlo in reachability heuristics for probabilistic planning'. Together they form a unique fingerprint.

Cite this