# Rollout Heuristics for Online Stochastic Contingent Planning

arXiv: https://arxiv.org/abs/2310.02345 · HTML: https://mlsanity.com/paper/2310.02345/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 31 references that are in the map.
- First posted on arXiv 3 Oct 2023.

## Builds on (most cited first, 5 of 5)

- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Online algorithms for POMDPs with continuous state, action, and observation spaces](https://mlsanity.com/paper/1709.06196/) (2017)
- [Partially Observable Markov Decision Processes (POMDPs) and Robotics](https://mlsanity.com/paper/2107.07599/) (2021)
- [Online Planning Algorithms for POMDPs](https://mlsanity.com/paper/1401.3436/) (2014)
- [Replanning in Domains with Partial Information and Sensing Actions](https://mlsanity.com/paper/1401.6048/) (2014)

## Built on by (most cited first, 2 of 2)

- [Heuristics for Partially Observable Stochastic Contingent Planning](https://mlsanity.com/paper/2410.05870/) (2024)
- [Stochastic Path Planning in Correlated Obstacle Fields](https://mlsanity.com/paper/2509.19559/) (2025)

## Abstract (arXiv)

Partially observable Markov decision processes (POMDP) are a useful model for decision-making under partial observability and stochastic actions. Partially Observable Monte-Carlo Planning is an online algorithm for deciding on the next action to perform, using a Monte-Carlo tree search approach, based on the UCT (UCB applied to trees) algorithm for fully observable Markov-decision processes. POMCP develops an action-observation tree, and at the leaves, uses a rollout policy to provide a value estimate for the leaf. As such, POMCP is highly dependent on the rollout policy to compute good estimates, and hence identify good actions. Thus, many practitioners who use POMCP are required to create strong, domain-specific heuristics. In this paper, we model POMDPs as stochastic contingent planning problems. This allows us to leverage domain-independent heuristics that were developed in the planning community. We suggest two heuristics, the first is based on the well-known h_add heuristic from classical planning, and the second is computed in belief space, taking the value of information into account.