Technical Summary: Think Fast and Far: Long-Horizon Online POMDP Planning via Rapid State Sampling

1. Problem Statement

Partially Observable Markov Decision Processes (POMDPs) provide a principled framework for motion planning under uncertainty by reasoning over belief states (probability distributions over states) rather than the state space itself. However, solving long-horizon POMDPs (requiring $\ge$15 lookahead steps) remains a significant challenge due to the exponential growth of the branching factor caused by actions and observations.

Existing online POMDP solvers face two primary bottlenecks:

1. Computational Cost of Sampling-Based Motion Planning (SBMP): Traditional SBMPs, while effective for deterministic planning, historically require hundreds of milliseconds to seconds to generate a single plan, making them too slow for online POMDP loops that require rapid macro-action generation.
2. Action Space Enumeration: Most online planners (e.g., POMCP, DESPOT) exhaustively enumerate all possible actions at each sampled belief to compute the optimal action. This limits the number of macro-actions that can be sampled at runtime, restricting the planner's ability to cover a diverse reachable belief space efficiently.

2. Methodology: ROP-RAS3

The authors propose ROP-RAS3 (Reference-Based Online POMDP Planning via Rapid State Space Sampling), an approximate online solver designed to address these bottlenecks. The methodology integrates three core components:

2.1 Rapid Macro-Action Generation via VAMP

ROP-RAS3 leverages Vector-Accelerated Motion Planning (VAMP), a hardware-accelerated SBMP framework. VAMP utilizes SIMD (Single Instruction, Multiple Data) vectorization to perform collision checks and kinematic validations in parallel. This allows the generation of probabilistically complete, collision-free trajectories for high-degree-of-freedom systems at kilohertz rates (tens of thousands of plans per second). These trajectories are converted into macro-actions (sequences of primitive actions) online.

2.2 Continuous Reference-Based POMDP Formulation

The paper introduces a modified Reference-Based POMDP formulation. Unlike previous work that defined references as belief-to-belief transitions, ROP-RAS3 defines the reference as a stochastic policy $\bar{\pi}(\cdot|b)$.

• Objective: The solver maximizes a reward function penalized by the Kullback-Leibler (KL) divergence from the reference policy:
  $$V(b) = \sup_{\pi} \left[ R(b, \pi) - \frac{1}{\eta} KL(\pi \parallel \bar{\pi}) + \gamma \int_{A,O} P(o|a,b)\pi(a|b)V(\tau(b,a,o)) da do \right]$$
• Partial Analytical Solution: The objective above can be partially solved analytically, yielding an expectation-only-form solution for the optimal policy:
  $$\pi^*(a|b) \propto \bar{\pi}(a|b) \exp(\eta Q(b, a))$$
  This replaces the computationally expensive numerical maximization (enumeration) over the action space with an expectation estimation, effectively removing the dependency on the total size of the action space $|A|$.

2.3 Tree Search and Convergence

ROP-RAS3 employs a tree search strategy that integrates the VAMP-generated macro-actions as a reference policy.

• Progressive Widening: The algorithm uses double progressive widening for both actions and observations to handle continuous spaces.
• Sampling Strategy: Instead of enumerating all actions, the planner samples macro-actions from the reference policy (induced by VAMP) based on informative states (e.g., goals, landmarks).
• Convergence: The authors prove that the convergence rate of ROP-RAS3 depends on $C_A$ (the number of actions sampled at each belief node) rather than $|A|$ (the total action space size). The convergence bound is $O(C_A(C_A C_S)^D \exp(-\min\{C_A, C_S\}t_{max}^2))$, where $C_S$ is the number of state samples and $D$ is the tree depth.

3. Key Contributions

1. ROP-RAS3 Algorithm: A novel online POMDP solver that combines rapid, hardware-accelerated SBMP (VAMP) with a reference-based POMDP formulation to handle long-horizon planning in continuous and hybrid spaces.
2. Theoretical Advancement: A modified reference-based Bellman backup that allows for continuous action spaces by replacing optimization with expectation estimation, leading to a convergence rate dependent on the number of sampled actions rather than the action space cardinality.
3. Scalability: The ability to solve POMDPs with up to 3000 lookahead steps and 35-dimensional state spaces, dimensions previously intractable for standard online solvers.
4. Empirical Validation: Extensive evaluation on 7 simulated scenarios (navigation and manipulation) and a physical robot demonstration (Hello-Robot Stretch 3).

4. Experimental Results

The paper evaluates ROP-RAS3 against state-of-the-art baselines including POMCP, DESPOT (with learned macro-actions MAGIC/RMAG), and a reference-based planner without VAMP (Ref-Basic).

• Performance: ROP-RAS3 outperforms all baselines in success rate across all tested scenarios, often by multiple folds.
  • Navigation: In the Maze2D (100-step horizon) and Random3D (high obstacle density) tasks, ROP-RAS3 achieved success rates of 80-90%, while baselines like POMCP and Ref-Basic failed or achieved near-zero success.
  • Manipulation: In high-dimensional manipulation tasks (Sphere-Search, Ray-Detect, Shelf-Move with 35D state space), ROP-RAS3 was the only method to achieve high success rates (e.g., 70% on Shelf-Move with 1500-step horizon). Learning-based methods (MAGIC, RMAG) failed to scale to these dimensions.
  • Multi-Agent: In the Multi-Drone Tag scenario, ROP-RAS3 achieved a 90% success rate, significantly outperforming R-POMCP (66.7%).
• Physical Robot: On a Hello-Robot Stretch 3 navigating around a moving pedestrian, ROP-RAS3 was the only method to successfully execute a smart detour to avoid collision while reaching the goal. Baselines either collided with the pedestrian or failed to navigate the environment efficiently.
• Ablation Studies:
  • Reference Policy Quality: Performance degrades as the reference policy becomes more uniform (less informative), but ROP-RAS3 remains robust, outperforming baselines even with purely explorative reference policies.
  • Tree Depth: An optimal tree depth exists (roughly equal to the deterministic solution steps); both shallower and deeper trees reduce performance under fixed time budgets.

5. Significance and Claims

The paper claims that ROP-RAS3 represents a significant step forward in making long-horizon POMDP planning practical for complex robotic systems.

• Overcoming the Enumeration Bottleneck: By utilizing reference-based POMDPs, the method bypasses the need for exhaustive action enumeration, allowing the integration of diverse, high-quality macro-actions generated by fast motion planners.
• Handling High Dimensions: The approach successfully scales to continuous, high-dimensional state and action spaces (up to 35 dimensions) where learning-based methods and traditional online solvers fail.
• Robustness: The integration of VAMP allows the planner to rapidly adapt to geometric constraints and uncertainties, generating robust policies that account for long-term consequences (e.g., navigating cluttered shelves or moving obstacles) that short-horizon planners miss.

The authors note that while the reference-based optimal solution may differ from the standard POMDP optimal solution, the empirical results demonstrate that this formulation enables the solution of challenging robotics tasks that were previously unsolvable online. The work extends their previous ISRR24 paper by handling continuous spaces, providing a neater backup formulation, and adding convergence analysis and physical robot demonstrations.