Source-linked AI summary
Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs
Jiho Lee, Nisar Ahmed, Kyle Hollins Wray, Zachary Sunberg
TL;DR
High-dimensional POMDP planning is challenged by costly belief representation and high-variance Monte Carlo value estimation. The paper extends RB-POMDPs to hybrid continuous-discrete beliefs with arbitrary analytically tractable components, propagating their uncertainty during tree search. In search-and-rescue experiments with FastSLAM 2.0, the approach achieved higher cumulative rewards with fewer particles and simulations under equivalent computational budgets, while occupancy-grid SLAM remains a challenging scope boundary.
Problem
High-dimensional POMDPs make belief representation and online planning computationally difficult, while Monte Carlo estimation becomes high variance as belief dimensionality increases.
Method
The paper extends RB-POMDP planning to arbitrary analytically tractable components in hybrid continuous-discrete beliefs and propagates their uncertainty during tree-based planning.
Results
The proposed planner achieved higher cumulative rewards using significantly fewer particles and planning simulations than purely sampling-based methods under equivalent computational budgets.
Takeaways & Limitations
Structured high-dimensional robotic problems with tractable sufficient statistics can support computationally feasible online decision-making within the RB-POMDP framework.
Takeaways & Limitations
Occupancy-grid SLAM remains challenging because raycasting depends jointly on many cells, while independent cell sampling can produce spatially inconsistent maps.
Abstract
from arXiv · showhide
Online planning under uncertainty remains a fundamental challenge for robotic systems operating in partially observable environments with high-dimensional state spaces. While sampling-based POMDP solvers enable approximate decision-making in large or continuous domains, their performance degrades as belief dimensionality increases due to the high variance inherent in Monte Carlo-based estimation. In this work, we extend the Rao-Blackwellized online POMDP (RB-POMDP) framework to improve its generalizability in high-dimensional settings through hybrid continuous-discrete belief representations. By analytically propagating uncertainty associated with marginalized state components during tree-based planning, the proposed approach reduces sampling-induced variance in value estimation. We demonstrate the effectiveness of this framework in a robotic search-and-rescue task by integrating it with FastSLAM 2.0. Experimental results show that the proposed planner achieves higher cumulative rewards using significantly fewer particles and planning simulations than purely sampling-based methods under equivalent computational budgets. These results suggest that structured high-dimensional robotic problems admitting tractable sufficient statistics can be effectively leveraged within the RB-POMDP framework for computationally feasible online decision-making.
I. INTRODUCTION
High-dimensional POMDP planning is difficult because belief representation and online value estimation become computationally burdensome under uncertainty. The paper extends Rao-Blackwellized planning to hybrid, analytically tractable belief components and evaluates it in search-and-rescue.
- POMDPs support sequential decisions under uncertainty by maintaining beliefs over latent states and optimizing expected long-term reward.
- High-dimensional particle filtering can require many particles because probability mass concentrates and importance weights vary substantially across samples.
- Structured robotic states can contain variables with conditionally tractable posteriors and sufficient statistics that admit closed-form propagation.
- Earlier RB-POMDP planning improved efficiency but was limited to Kalman filter-based analytical components and relatively simple, low-dimensional settings.
- The proposed framework supports arbitrary analytically tractable belief components and targets computationally feasible online planning in high-dimensional problems.
- The search-and-rescue scenario combines robot pose, landmark geometry, and semantic victim presence within a hybrid belief representation.
B. Sampling-Based POMDP Online Planning
Sampling-based online POMDP planners approximate action values through Monte Carlo tree simulations, but high-dimensional beliefs increase simulation variance and computational requirements. Rao-Blackwellized planning addresses this by analytically propagating tractable uncertainty during belief updates and tree expansion.
- Online POMDP methods approximate intractable value functions by simulating future outcomes from the current belief state.
- POMCP and POMCPOW use particle beliefs and Monte Carlo tree search, with POMCPOW adding progressive widening for continuous observations.
- Monte Carlo sampling converges at O(1/sqrt(N)), so high-dimensional observation and reward uncertainty can produce substantial value-estimation variance.
- Reducing this variance requires significantly more tree simulations for consistent long-horizon planning, increasing computational overhead.
- Rao-Blackwellization reduces estimator variance by conditioning on sufficient statistics and analytically marginalizing tractable latent-state components.
- RB-POMDP associates each sampled particle with a conditional analytical distribution over marginalized state variables, changing how uncertainty is propagated during online planning.
A. Rao-Blackwell factorization of POMDPs
Rao-Blackwell factorization separates sampled state variables from components whose conditional posterior has a closed-form update. The resulting representation reduces particle dimensionality and uses analytically updated beliefs in importance-weight computation.
- The state is partitioned into non-tractable variables represented by particles and tractable variables with closed-form conditional posteriors.
- The factorization enables analytical marginalization of the tractable component rather than sampling it directly.
- Closed-form updates propagate tractable variables while sampling is required only for the non-tractable component, reducing particle dimensionality.
- In RBPFs, importance weights use the observation likelihood evaluated from the analytically updated belief over tractable state components.
- The RB-POMCPOW tree associates each particle with a Gaussian distribution, forming a weighted mixture of beliefs.
- Measurement-informed proposals such as FastSLAM 2.0 require additional care when computing importance weights.
C. Online Planning with Rao-Blackwellization
RB-POMDP planning replaces high-variance Monte Carlo evaluation of analytically tractable state components with deterministic expectation-based updates. Distribution-specific quadrature, including Smolyak sparse grids, balances integration accuracy and computational cost while reducing the tree iterations needed for planning.
- Monte Carlo sampling of analytically maintained components can produce high-variance value estimates and require substantially more tree simulations for convergence.Sampling many realizations removes Rao-Blackwellization’s computational benefit, while one realization inadequately captures uncertainty.
- Deterministic quadrature replaces random realizations with weighted evaluations over analytically tractable state components during tree expansion.The weighted evaluations approximate expectations of rewards and observations while preserving the Rao-Blackwellized belief structure.
- Quadrature choice depends on the analytically marginalized distribution, with Gaussian-Hermite rules applicable to Gaussian beliefs and other Askey-family methods available for different distributions.The integration method can therefore be matched to the belief model.
- Smolyak sparse grids reduce the number of quadrature points needed to mitigate the curse of dimensionality while maintaining approximation accuracy.Sparse-grid construction addresses the computational cost of higher-order quadrature.
- Higher sparse-grid levels improve expectation accuracy at increased computational cost, enabling a tunable trade-off between integration precision and planning time.The integration method or sparse-grid level can be adjusted independently for rollout and simulation functions.
- The framework supports exact expectations for marginalized variables with finite discrete support and more generally any component admitting a closed-form conditional update.This extends the approach beyond continuous distributions and Gaussian assumptions.
IV. PROBLEM FORMULATION
The search-and-rescue problem is formulated as a high-dimensional POMDP in which a robot must localize, map landmarks, infer victim-related semantics, and choose actions under partial observability. The planner combines motion and scanning actions with Rao-Blackwellized belief updates and tree-search procedures.
- IV. PROBLEM FORMULATION: The environment contains N static landmarks, each potentially associated with a victim, and the robot seeks to locate all victims.
- A. Problem Statement: The robot simultaneously estimates pose, landmark geometry, and latent semantic information while making sequential decisions under partial observability.
- A. Problem Statement: At each step, stochastic dynamics produce a new state and noisy observations combining geometric measurements z_t with semantic measurements y_t.
- A. Problem Statement: RB-POMCPOW searches by simulating sampled beliefs, progressively widening action and observation children, updating analytical beliefs, and backing up simulated returns.
- A. Problem Statement: Landmark geometry and semantic variables make belief dimensionality grow with the number of landmarks, challenging sampling-based online POMDP solvers.
- A. Problem Statement: The state decomposition includes robot pose, landmark locations, binary victim-presence variables, and visited indicators used for bookkeeping and reward evaluation.
- A. Problem Statement: Actions include discretized forward, backward, and turning motions plus a scanning action that observes a landmark’s latent semantic state without inducing motion.
- A. Problem Statement: Successful victim identification through scanning contributes to the detection reward, while the planning objective favors efficiently visiting landmarks with high semantic likelihood.
D. Transition Model T
The transition model combines stochastic robot motion with deterministic bookkeeping, while landmark geometry and semantic variables remain static. The observation and reward design supports search toward landmarks likely to contain victims.
- Transition dynamics: The robot pose follows a nonlinear unicycle model with zero-mean Gaussian process noise, while landmark and semantic states remain static.The broader framework does not require additive Gaussian transition or observation noise, although the experiments assume it.
- Bookkeeping updates: Visited indicators update deterministically after scanning: a landmark is marked visited when the robot is within a predefined radius.
- Observation structure: Observations combine geometric and semantic measurements for visible landmarks, under a known data-association assumption.Geometric measurements describe landmark positions relative to the robot, while semantic measurements provide evidence about latent landmark attributes.
- Reward design: The reward encourages efficient exploration toward likely victim locations while penalizing unnecessary motion and control effort.The heading-error term targets the nearest unvisited landmark with high semantic probability, and successful victim identification receives a positive detection reward.
V. METHODOLOGY
The methodology represents the belief with Rao-Blackwellized particles that sample robot trajectories while maintaining landmark geometry and semantics analytically. FastSLAM 2.0 supplies measurement-informed proposals for more efficient particle updates.
- Belief factorization: Conditioned on the robot trajectory, landmark states are independent, enabling a factorized posterior representation.The histories of robot trajectories, observations, and actions define the conditioning variables.
- Hybrid belief representation: Each Rao-Blackwellized particle samples a robot trajectory and bookkeeping variables while analytically maintaining landmark geometry and semantic attributes.Every particle carries N EKFs for geometric landmarks and N Bernoulli distributions for semantic landmark states.
- Per-landmark statistics: The geometric sufficient statistics are stored through EKFs, while each landmark’s semantic belief is represented by a Bernoulli parameter.
- Proposal distribution: FastSLAM 2.0 provides a measurement-informed proposal that uses control inputs and geometric landmark measurements to reduce particle depletion.Multiple landmark measurements are incorporated sequentially, and a first-order Taylor expansion yields a Gaussian proposal under an EKF-style approximation.
C. Importance Weight Computation
Importance weights incorporate geometric and semantic observation likelihoods while marginalizing analytically maintained uncertainty. A probit semantic model preserves closed-form computation under Gaussian range uncertainty.
- Weight construction: Semantic observations are excluded from the proposal but incorporated into importance weights by marginalizing geometry, robot pose, and semantic variables.Conditional independence across landmarks and sensing modalities makes the observation likelihood factorize.
- Geometric marginalization: FastSLAM 2.0 approximates the geometric integrals in closed form by linearizing the measurement model, producing a Gaussian likelihood evaluation.
- Semantic likelihood: The semantic likelihood is modeled so Gaussian marginalization over range uncertainty remains analytically tractable.The detection function must admit a closed-form integral under the Gaussian-distributed range.
- Probit model: A probit link provides an exact analytical solution for semantic detection probabilities, unlike commonly used logistic links.Expected detection and false-alarm probabilities can therefore be computed in closed form for importance weighting.
E. Belief update
Geometric landmark updates follow the FastSLAM EKF update, while semantic beliefs are updated analytically. Experiments show that RBPF achieves accurate estimation with far fewer particles despite higher per-particle update costs.
- Belief update: Geometric landmark beliefs use the standard EKF measurement update, while semantic landmark beliefs are updated analytically with Bayes’ rule.
- Estimation accuracy: Approximately 50 RBPF particles are sufficient for near-optimal RMSE, whereas SIRPF remains less accurate even with 10,000 particles.
- Computational cost: RBPF has higher per-update computation time at equal particle counts because each particle maintains analytical beliefs for every landmark.
- Efficiency trade-off: Analytically marginalizing continuous geometry and discrete semantics reduces sampled-state dimensionality and the particle count needed for accurate belief representation.Despite higher per-particle overhead, RBPF achieves lower overall computational cost for comparable belief quality.
B. Planning Performance and Computation
Under matched computational conditions, analytical integration in RB-POMCPOW produces more consistent planning and higher cumulative reward than sampling-based alternatives. The approach reduces both belief and planning variance, while its effectiveness depends on tractable expectations for marginalized state components.
- RB-POMCPOW uses deterministic expectations over analytically tractable state components, reducing predicted-outcome variance and producing more direct navigation toward high-belief rooms.RB-MC-POMCPOW instead samples stochastic realizations during tree expansion, introducing additional planning uncertainty.
- RB-POMCPOW consistently achieves higher cumulative reward than POMCPOW and RB-MC-POMCPOW under comparable computational budgets.The comparison varies sparse-grid levels for RB-POMCPOW and tree iterations for the two Monte Carlo planners.
- 1500 tree iterations for POMCPOW yield rewards comparable only to RB-POMCPOW with q = 1 and 100 tree iterations.RB-MC-POMCPOW with 500 tree iterations provides only marginal improvement over RB-POMCPOW with q = 1.
- RBPF analytically maintains conditionally independent landmark beliefs within each particle, increasing effective sample size relative to SIRPF.This is one of two variance-reduction mechanisms identified for the framework.
- RB-POMCPOW requires tractable reward and observation expectations over marginalized components; Gaussian landmark geometry and Bernoulli semantic attributes satisfy this condition.Occupancy-grid SLAM violates the convenient computational structure because raycasting couples many cells, requiring exponentially many joint realizations.
- Independent cell-wise occupancy sampling can create spatially inconsistent checkerboard maps, causing hallucinated behaviors during tree expansion.Generative range-sensing models are proposed as a direction for producing more realistic map realizations.
APPENDIX A. RB-POMCP
The RB-POMCP procedure follows standard recursive simulation while replacing generative sampling with quadrature and an analytical belief update. It initializes action nodes, rolls out unexplored histories, and backs up discounted returns.
- SIMULATE terminates when the discounted depth falls below ε and returns zero.
- For an unexplored history, the procedure initializes every action node before invoking ROLLOUT.
- RB-POMCP computes expected next state, observation, and reward using quadrature during simulation.
- After quadrature, ANALYTICALUPDATE produces the next belief, recursive simulation continues, and visit counts are incremented before returning the discounted return.
APPENDIX B. CLOSED-FORM MARGINALIZATION OF PROBIT DETECTION MODELS UNDER GAUSSIAN UNCERTAINTY
The appendix derives a closed-form marginalized detection probability for a probit observation model under Gaussian distance uncertainty. It introduces an independent standard normal variable to rewrite the expectation as a Gaussian probability.
- The distance variable d is modeled as Gaussian with mean μ and variance σ^2 in the probit detection model.
- The appendix seeks the marginalized detection probability by integrating Φ(α0 + α1d) against the Gaussian density of d.
- An independent standard normal variable u rewrites the probit expectation as the probability that u ≤ α0 + α1d.
- Because u and d are independent Gaussian variables, the transformed variable w is also Gaussian with derived mean and variance.