Partially Observable Markov Decision Processes (POMDPs) and Robotics

In plain words

A robot rarely knows exactly where it is or what is around it. Its sensors are noisy and its motors do not do exactly what it asks. A POMDP is a standard way to describe such a problem: the robot keeps a guess, in the form of probabilities over possible situations, and picks actions based on that guess rather than on a single assumed state.

Finding the perfect plan for this kind of problem is far too expensive for real robots. This review explains how a family of methods solves it approximately instead. These methods only consider a limited set of likely situations, and they are good enough to make a robot noticeably more robust.

The review walks through the main obstacles: large numbers of states, very long plans, complicated sensor readings, many possible actions, and slow physics. For each, it describes the ideas that have helped. It ends with notes on the software available and on practical lessons from running POMDPs on physical robots.

TL;DR

• A POMDP models decisions under action noise and partial observation; its exact solution is computationally intractable §1 §3.
• Sampling-based approximate solvers, which plan only over a sampled set of beliefs, made POMDPs practical for many robotics problems §1 §3.
• The review groups solver ideas by five difficulties: large state space, long horizon, large observation space, large action space and complex dynamics §3.
• Software exists for several solvers (e.g. SARSOP, HSVI, DESPOT, ABT), but licences were not checked here §4.1.
• The review has no experiments of its own; all numbers are quoted from cited work §3.1 §4.3.

Problem

The review asks how a robot should act when its actions have uncertain effects and its state is only partly observable §1. Such planning can be stated as a POMDP with a finite or continuous state, action and observation space; this review focuses on the discrete, finite case §2. Exact optimal policies are intractable (PSPACE-hard in general) §3, and motion planning under uncertainty is hard even without the POMDP framing §3. Most benchmarks before the sampling-based era had fewer than 30 states and took hours to solve §1.

Method

This is a survey, so there is no single method to implement. The core formal model is in §2, the common solver skeleton in §3 and alg. 1, and the individual solvers in §3.1 to §3.5.

Formal model (§2)

A POMDP is a 6-tuple of states S, actions A, observations O, transition function T, observation function Z and reward function R §2. Transitions can be written as a noisy dynamics function s' = f(s, a, η) with η drawn from a noise distribution, when states are real vectors §2.

The agent keeps a belief b, a probability distribution over states, and updates it after each action a and observation o §2:

1. Start from the current belief b.
2. Take action a; the hidden state moves according to T.
3. Receive observation o according to Z.
4. Update the belief with Bayes' rule eq. 2.
5. Receive reward R; repeat.

The optimal value is the best action value over beliefs, where each action value combines the expected immediate reward with the discounted expected value of the successor beliefs eq. 1 §2. The discount factor γ lies in (0, 1) §2. A finite-horizon variant with a horizon T is given in eq. 3. A Goal-POMDP, which minimises the cost to reach goal beliefs, is said to be equivalent to a discounted POMDP §2. The review concentrates on the discounted, infinite-horizon form §2.

The belief update is given as a single two-line equation with one number eq. 2. Its normaliser is the probability of the observation given the action and the current belief §2.

Common solver skeleton (§3)

Sampling-based approximate solvers restrict planning to a sampled set of beliefs, usually reachable from an initial belief b0 §3. The generic loop in alg. 1 is:

# Sampling-based approximate POMDP solver  [alg. 1] [§3]
# Input:  POMDP model, initial belief, planning budget
# Output: policy over the sampled beliefs

def sampling_pomdp_solver(model, initial_belief, budget):
    # Start with the initial belief in the sampled set  [alg. 1]
    policy = initial_policy()
    sampled_beliefs = [initial_belief]
    # Repeat until the stopping criterion holds  [alg. 1] [§3]
    while not stopping_criterion(budget):
        # Sample a belief; some methods sample histories instead  [alg. 1]
        new_belief = sample_belief(sampled_beliefs, model)
        sampled_beliefs.append(new_belief)
        # Estimate values with heuristics and backups  [alg. 1] [§3]
        values = estimate_values(sampled_beliefs, model)
        # The policy update is usually a by-product of the backup  [alg. 1]
        policy = update_policy(policy, values)
    return policy

Stopping is usually a time budget §3. Solvers that keep upper and lower bounds may instead stop when the gap at the initial belief is below a threshold, although in practice they often stop earlier §3. Offline solvers compute a policy before execution. Online solvers plan only from the current belief at each step and interleave planning with execution §3.

The review explicitly notes that a belief is a sufficient statistic of the whole history, so a belief-based policy is not restricted to the last observation §4.3.

Large state space (§3.1)

The belief space has dimension n − 1 for n states, which is the curse of dimensionality §3.1.

• PBVI §3.1 keeps one alpha-vector per sampled belief and performs point-based backups only. It expands the belief set by a one-step simulation for each belief and action, keeping the successor farthest from the set under the L1 metric §3.1.
• Perseus §3.1 separates belief sampling from backup and backs up only a subset of sampled beliefs, which reduces the number of vectors kept §3.1.
• HSVI2 §3.1 keeps lower and upper bounds. The upper bound starts from the fully observable (MDP) version and is stored as a set of points with sawtooth interpolation. Sampling is a forward simulation down a belief tree that chooses the action with the best upper bound and the observation with the largest excess gap §3.1.
• SARSOP §3.1 samples beliefs close to those reachable under an optimal policy. It predicts the value of new beliefs by binning sampled beliefs by features (initial upper bound and entropy), expands a belief when its predicted value exceeds a target from the lower bound, and prunes provably suboptimal branches and δ-dominated vectors §3.1.
• PBPI §3.1 applies point-based backup to policy iteration, with the policy stored as a finite state controller and alpha-vectors §3.1.
• Continuous-state extensions §3.1 include a point representation with k-nearest-belief averaging under KL divergence §3.1, alpha-functions with Gaussian mixtures §3.1, policy graphs (MCVI) §3.1, and guided cluster sampling (GCS) §3.1.
• Online methods §3.1 include RTDP-Bel, which runs a one-step lookahead with heuristics over a hash table of belief values §3.1; POMCP, which runs UCT-style Monte Carlo tree search over histories with a generative model and particle beliefs §3.1; ABT, which backs up values along the tree and reuses earlier trees §3.1; and DESPOT, which uses a fixed number K of sampled scenarios to build a sparse tree §3.1.

Long planning horizon (§3.2)

Look-ahead grows exponentially with depth, the curse of history §3.2. Methods alleviate this with macro-actions, temporally extended sub-policies that run until a termination condition §3.2. Hand-designed sub-goals are common §3.2. Automatic constructions include milestone-based open-loop sequences §3.2, LQG-based macro-actions over a probabilistic roadmap for Gaussian beliefs §3.2, and value-of-information based macro-actions with bounded regret §3.2.

Large observation space (§3.3)

Uniform discretisation of continuous observations is either too fine or too coarse §3.3. Offline remedies cluster observations using value-function features or extend policy graphs with classification §3.3. Online remedies are progressive widening (POMCPOW), which adds observations incrementally and needs an explicit observation function §3.3, and lazy belief extraction (LABECOP), which keeps episodes and assigns beliefs only at execution §3.3.

Large action space (§3.4)

Most solvers handle at most about 100 discrete actions and enumerate all of them §3.4. Remedies are sampled maxima over random action subsets (Perseus, GCS) §3.4, sampled actions for MDP trees §3.4, GPS-ABT, which uses generalised pattern search and converges in probability under stated smoothness conditions §3.4, Bayesian optimisation with Gaussian processes (usually below 4 dimensions) §3.4, LQG for linear-Gaussian cases §3.4, and a two-stage quantile-based sampler for very large discrete action sets §3.4.

Complex dynamics (§3.5)

Solvers assume a forward simulation is nearly free. When the dynamics require solving differential equations, this fails §3.5. Remedies are a switching (hybrid) dynamics model with an offline solver §3.5, linearised dynamics with LQR §3.5, and multilevel Monte Carlo that uses the expensive model rarely and cheaper models otherwise §3.5.

Software, tips and model notes (§4)

• Software §4.1: Symbolic Perseus (Java/Matlab), ZMDP (HSVI, HSVI2; C++), APPL toolkit (SARSOP; C++), APPL-online (DESPOT; C++), TAPIR (ABT; C++), OPPT (ROS interface, default ABT; C++) and pomdp_py (Python/Cython) §4.1.
• Parallelising §4.2: start the particle filter's proposal sampling as soon as an action is chosen, so only the importance weights remain after the observation. With ABT, sample extra episodes under the chosen action in advance §4.2.
• Distance §4.2: L1 and KL divergence are common; the earth mover's distance is suggested for robotics because it uses state-space distance §4.2.
• Model difficulty §4.3: state, action and observation spaces are usually easy to define, while transition, observation and reward functions are harder. Rough models can still give good policies, as reported for an ICRA 2018 demonstration §4.3.
• Robustness §4.3: the review argues that a POMDP policy balances information gathering and task progress, which matters in cluttered or tight spaces §4.3.
• Markov assumption §4.3: the policy accounts for the whole history, but the transition and observation functions are assumed first-order Markov §4.3.

Relations (§5)

Table 1 tab. 1 compares sampling-based POMDP solvers with sampling-based motion planning across five components: theory, primitives, combined methods, offline/multi-query, and online/single-query tab. 1 §5.1. Learning links are discussed in §5.2: POMDPs can model RL under unknown parameters, and recent work embeds POMDP structure in neural networks §5.2.

Hyperparameters

The review states no hyperparameter values for any solver and no implementation defaults. The table lists the parameters the text names.

Results

Author-reported. The review does not run experiments; the numbers below are cited from other papers and restated here. Setup as far as the review gives it.

The ICRA 2018 demonstration ran for 7 consecutive days and 7 hours per day §4. The success-rate comparison uses a rough, data-fitted model §4.3.

Paper vs code

No official code. The paper names no code repository. Its only link is the author's homepage, which lists no POMDP solver or repository. The paper is a survey, so it has no method implementation to compare. Searches on GitHub found several SARSOP implementations, including one under AdaCompNUS. That lab is not the authors' own, so it was not used. The solver software in §4.1 belongs to other groups and was not used either.

Pitfalls

• The review has no experiments. Every number is quoted from a cited paper, so check the original before using it. The review says some numbers are from a single demonstration §4.3.
• Hyperparameters are not stated for any solver. An implementer needs the original papers for ε, c, K, δ, bin counts and particle counts §3.1 §4.2.
• The printed observation-selection score for HSVI2 §3.1 uses a gap term with ε^(−t). It does not show the observation probability weight. Check the HSVI2 paper before implementing.
• The printed POMCP action rule §3.1 uses the square root of N(h)/N(ha) with no logarithm. This differs from the UCB1 rule that the same text cites. Check the POMCP paper.
• The belief-update notation in eq. 2 reuses the state symbol inside the sum. Read the sums carefully: the numerator sums over the predecessor state, and the denominator sums over the successor state eq. 2 §2.
• The finite-horizon recursion eq. 3 has no discount factor at horizon zero in the printed base case eq. 3. Confirm against the source paper before implementing.
• Two costs are hidden in the text: offline solvers may need tens of hours §3.1, and online solvers cannot be precomputed and must meet real-time limits §3.
• Sampling-based solvers' guarantees are approximate; the review explicitly says they do not produce optimal policies §1 §3.
• The software list §4.1 is descriptive only. Licences were not checked, so do not reuse licence claims from this card.
• Several claims are about other papers' convergence or scaling §3.4 §3.1. The review restates them without its own proof.

Lineage

• Builds on: the POMDP framework and its early value-function results, which the review cites §1 §2.
• Compared against: PBVI, Perseus, HSVI2, SARSOP, PBPI, POMCP, ABT, DESPOT, GCS, MCVI, RTDP-Bel and POMCPOW, as surveyed in §3.
• Superseded by: not stated.