Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs

1

Scalable Rao-Blackwellized Online Planning for High-Dimensional POMDPs

arXiv:2609.01351v1 [cs.RO] 1 Sep 2026

Jiho Lee1 , Nisar Ahmed1 , Kyle Hollins Wray2 , Zachary Sunberg1

Abstract—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 decisionmaking 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.

Fig. 1. Motivating scenario for search-and-rescue under partial observability. A robot navigates an indoor environment consisting of multiple rooms while constructing a map and localizing itself. Victim presence behind each door is unknown and can only be inferred through limited sensing of both spatial and victim-related semantic cues. To accomplish the task, the agent maintains a belief over the joint robot and environment state and considers multiple possible future outcomes under different action-observation histories, represented by the planning tree on the right, to select actions that locate victims efficiently.

Index Terms—POMDPs, FastSLAM, Rao-Blackwellization

I. I NTRODUCTION OBOTIC decision-making tasks such as search-andrescue, autonomous navigation, and exploration often require reasoning under significant uncertainty arising from limited sensing and incomplete knowledge of the environment [1] [2] [3] [4] [5]. Partially Observable Markov Decision Processes (POMDPs) provide a powerful mathematical framework for sequential decision-making under uncertainty by enabling agents to maintain beliefs over latent system states while planning actions that maximize expected long-term reward [6]. While POMDPs have been widely applied to various domains [7] [8] [9], their practical deployment still remains challenging due to the computational burden associated with belief representation and online planning in large-scale environments. Sampling-based online POMDP solvers such as partially observable Monte Carlo planning (POMCP) [10] and its variant partially observable Monte Carlo planning with observation widening (POMCPOW) [11] maintain particle-based belief representations and rely on Monte Carlo simulation to approximate value estimates during online tree search. Recent theoretical results show that these planners can achieve convergence

R

1 Ann And H.J. Smead Aerospace Engineering Sciences Department, University of Colorado Boulder, Boulder, CO, USA. Email: {Jiho.Lee,

Nisar.Ahmed, Zachary.Sunberg}@colorado.edu 2 Manning College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA. Email:

kwray@umass.edu

guarantees that depend only on the number of samples and are independent of state or observation space dimensionality, provided that the importance weight is bounded [12]. In practice, however, maintaining bounded importance weights become extremely challenging in high-dimensional settings, where probability mass concentrates in a small typical set of the state space and importance weights may vary significantly across samples [13]. As a result, particle filters often require a substantial increase in the number of particles to maintain reliable belief representation due to likelihood concentration and importance weight degeneracy [14] [15] [16]. In such settings, the effective sample size of the particles decreases, increasing the variance of estimators computed using the particles [17]. Since value estimates are computed via Monte Carlo runs under the particle belief, a low effective sample size increases the variance in value estimates in tree search. Consequently, consistent long-horizon planning requires a substantial increase in both the number of particles used for belief representation and the number of tree simulations needed for reliable planning. This leads to significant computational overhead and often renders these purely sampling-based approaches impractical for realistic robotic decision-making scenarios. Many robotic systems, however, exhibit structured latent state spaces in which subsets of variables admit conditionally tractable posterior updates. For example, problems such

2

as simultaneous localization and mapping (SLAM) involve latent geometric variables (e.g., landmark positions) whose uncertainty can be represented analytically given a sampled robot trajectory [18]. Such conditional structure implies that portions of the state admit sufficient statistics that can be propagated in closed form, rather than requiring full Monte Carlo approximation. Rao-Blackwellized Particle Filtering (RBPF) exploits this structure by analytically marginalizing subsets of the latent state conditioned on sampled variables, reducing the dimensionality that must be explored via particles [19] [20]. RBPF has been successfully applied to various estimation problems such as SLAM and target tracking [21] [22] [23]. Within the context of POMDPs, a recent work [24] introduced a Rao-Blackwellized POMDP (RB-POMDP) online planning framework that leverages analytical belief updates within the POMCPOW planner. While this approach demonstrated improved efficiency in continuous state and observation planning tasks, it remained limited to Kalman filter-based analytical components and relatively simple, low-dimensional experimental settings. Therefore, it is of significant interest to explore how this framework can provide a general mechanism to enable scalable decision-making in realistic robotic problems with much larger latent state spaces and non-Gaussian distributions. This paper addresses this gap by extending the RB-POMDP framework to support arbitrary analytically tractable belief components and demonstrating the feasibility of online planning in high-dimensional problems. By analytically propagating uncertainty associated with marginalized state variables during tree-based planning, the new framework reduces sampling-induced variance in reward estimates, enabling consistent long-horizon reasoning with substantially fewer particles and tree iterations. In summary, this work makes the following three contributions: 1) We demonstrate that Rao-Blackwellized online planning is not merely beneficial but essential for computationally feasible decision-making in high-dimensional POMDPs with analytically tractable structure. Scalable planning becomes possible where purely sampling-based methods are infeasible under practical computational budgets. 2) We generalize the RB-POMDP framework beyond Gaussian assumptions by allowing the analytically maintained component to be instantiated with arbitrary closed-form belief update models. This enables planning over hybrid continuous-discrete latent state spaces in which marginalized variables may follow non-Gaussian distributions. 3) We validate the proposed framework in a realistic searchand-rescue scenario involving both geometric and semantic observations by integrating it with the FastSLAM 2.0 algorithm, as illustrated in Figure 1. This scenario induces a hybrid belief over robot pose, landmark geometry, and semantic victim presence, represented by particles, Gaussian, and Bernoulli distributions, respectively. This demonstrates that any structured high-dimensional estimation problems, if admitting tractable sufficient statistics, can be leveraged within the RB-POMDP framework. The remainder of this article is organized as follows.

Section II reviews POMDPs, sampling-based POMDP planning methods, and RBPFs. Section III introduces the RaoBalckwellized factorization of POMDPs, RBPF-based belief updates, and Rao-Blackwellized online planning. Section IV presents the search-and-rescue problem application, followed by Section V, which details the proposed Rao-Blackwellized belief representation and associated planning components. Experimental results are provided in Section VI. Finally, Section VII discusses the results and outlines directions for future work. II. BACKGROUND A. Partially Observable Markov Decision Process (POMDP) In Markov Decision Processes (MDPs), agents operate with full knowledge of the current system state. At any given time, the agent fully understands where it is or what the situation is. In POMDPs, however, agents do not have perfect knowledge of the current state. They must make decisions under uncertainty about the current as well as future states; thus, POMDPs are more suitable for real-world robotics scenarios where the true state of the environment cannot be directly observed due to sensing limitations or environmental uncertainty [25]. A POMDP is formally defined by the tuple (S, A, T , O, R, Z, γ) where S is the state space, A is the action space, T is the state transition function, O is the observation space, Z is the observation function, R is the reward function, and γ ∈ (0, 1) is the discount factor. Because the agent cannot directly observe the system state, it instead maintains a probabilistic belief distribution over possible states. This belief is recursively updated using Bayes’ rule: X b′ (s′ ) ∝ P (o | s′ , a) P (s′ | s, a)b(s), (1) s∈S ′

′

where b(s) and b (s ) denote the prior and posterior beliefs before and after executing action a and receiving observation o, respectively. Solving POMDPs is therefore performed over belief states rather than fully observed states. The optimal value function, which guides the selection of the best action based on the current belief, is given by " # X ∗ ∗ ′ V (b) = max R(b, a) + γ P (o | b, a)V (b ) , (2) a∈A

o∈O

where R(b, a) is the expected immediate reward for taking action a and P (o|b, a) is the probability of receiving observation o after taking action a. Consequently, the dimensionality and structure of the belief representation can directly influence the computational complexity of evaluating the value function during planning. B. Sampling-Based POMDP Online Planning Evaluating the optimal value function in (2) is computationally intractable for most real-world problems due to the high-dimensional nature of belief spaces and observations. Consequently, a large body of work has focused on online planning methods that compute approximate action values

3

during execution by simulating future outcomes from the current belief state. The well-known sampling-based solver POMCP [10] employs particle-filter-based belief representations with Monte Carlo tree search (MCTS) and relies on a black-box generative model to sample future states, observations, and rewards during tree expansion. Extensions such as POMCPOW incorporate progressive widening techniques to regulate tree growth and improve planning performance in continuous observation spaces [11]. These sampling-based methods approximate value functions by averaging simulated rewards obtained from running N tree search simulations to a depth D. Specifically, the value at an observation-action history h at depth τ is estimated using the set of simulations consistent with that history, I(h), as

Algorithm 1 Belief Updates for Rao-Blackwellized Particle Filter adapted from [24] α|π,i

i s Require: (sπ,i )N i=1 , ok+1 , ak+1 k , wk , Θk α|π,i π,i i s Ensure: (sk+1 , wk+1 , Θk+1 )N i=1 1: for i = 1 to Ns do π,i π,i 2: Draw sπ,i k+1 ∼ p(sk+1 |sk , ak+1  ) α|π,i

α|π,i

α|π,i

Θk+1 , Λk+1 ← AnalytUpd Θk , sπ,i k+1 , ok+1 , ak+1   α|π,i α|π,i i 4: w̃k+1 ← Reweight Θk+1 , Λk+1 , sπ,i , o k+1 k+1 5:  end for   Ns Ns i i 6: wk+1 = Normalize w̃k+1 i=1 i=1 7: Compute Ness = PNs 1 i )2 (w 3:

s=1

8: if Ness < τ then 9:

k+1

n oNs  n oNs π,i π,i i i ← Resample sk+1 , wk+1 sk+1 , wk+1 i=1

i=1

V (h) ≈

1 |I(h)|

X

D X

γ d−τ R(si,d , ai,d ).



10: end if

(3)

i∈I(h) d=τ

However, √ Monte Carlo sampling exhibits a convergence rate of O(1/ N ), which can require a large number of simulations to achieve consistent estimates. Especially when operating over high-dimensional belief spaces, uncertainty in predicted observations and rewards during simulation can introduce substantial variance in estimated values within the planning tree. As a result, significant increase in the number of tree simulations is needed to achieve consistent, reliable longhorizon planning, inevitably leading to considerable computational overhead. C. Rao-Blackwellized Particle Filter (RBPF) One approach to reducing the variance of purely samplingbased Monte Carlo estimators is to exploit analytically tractable structure in the latent state using the Rao-Blackwell theorem. This theorem states that conditioning an estimator on sufficient statistics cannot increase its variance [26], as expressed by var[δ(s)] ≥ var[δ(s | Θ)], (4) where δ(s) is any kind of estimator of the random variable s, and Θ denotes sufficient statistics for s. In the context of sequential Monte Carlo estimation, i.e., particle filtering via sequential importance sampling, RBPF leverages this principle by analytically marginalizing subsets of the latent state that admit closed-form conditional updates. By maintaining sufficient statistics for these tractable components within each particle, RBPF reduces the dimensionality of the belief representation that must be approximated through sampling. This enables more efficient belief updates by reducing the variance of the resulting particle importance weights [17] [20]. As a result, this leads to using fewer particles compared to purely sampling-based approaches which sample all variables whether they possess analytically tractable conditional posterior sufficient statistics or not. III. T ECHNICAL A PPROACH Incorporating analytically tractable belief components within sampling-based approximate POMDP solvers requires

not only modifying how belief is represented but also altering how its conditional uncertainty is propagated during online planning. A recent work [24] introduced such an approach, referred to as the RB-POMDP framework, in which each particle is associated with a conditional analytical distribution over marginalized state variables as shown in Fig. 2. This section describes the proposed method for addressing these challenges. A. Rao-Blackwell factorization of POMDPs The key idea underlying Rao-Blackwellization is to exploit conditional structure in the latent state by decomposing it into analytically tractable and non-tractable components. Let the α|π state be partitioned as st = (sπt , st ), where sπt denotes the subset of variables that must be represented through randomly α|π sampled particles and st denotes variables whose conditional posterior admits a closed-form update. Using the chain rule, the joint posterior distribution over these components can be factorized as α|π

α|π

p(st+1 , sπt+1 | o1:t ) = p(st+1 | sπt+1 , o1:t ) p(sπt+1 | o1:t ). (5) This factorization enables analytical marginalization of the α|π tractable component st+1 conditioned on sampled realizations α|π π of st+1 . In other words, the conditional belief p(st+1 | π st+1 , o1:t ) can be propagated using closed-form updates (e.g., Kalman filtering). When such a decomposition exists, sampling is required only over the non-tractable component sπt+1 , effectively reducing the dimensionality of the particles. B. RBPF Belief Updates In the most commonly used particle filtering variant, Sequential Importance Resampling particle filters (SIRPF) (also known as Bootstrap particle filters), a common choice for the proposal distribution is the transition function p(s′ | s, a), which leads to importance weights that are proportional to the observation likelihood [27]. In RBPFs, this likelihood is evaluated using the analytically updated belief over the tractable state components [28], as indicated by Λ in line 3

4

Fig. 2. Tree structure comparison adapted from [24]. Each square and larger circle represents an action node and an observation node, respectively. In the POMCPOW tree, particles are shown as black dots while each particle in the RB-POMCPOW tree is associated with a Gaussian distribution. Due to the nature of POMCPOW, these particles form a weighted mixture of beliefs.

of Algorithm 1. When using Kalman filters, for instance, this corresponds to the filter innovation likelihood function for a received observation and involves the innovation covariance matrix computed from the measurement update step. When alternative proposal distributions are employed, such as the measurement-informed proposal used in FastSLAM 2.0, the importance weights must be computed with additional care. The corresponding computation for this likelihood is described in detail in Section V for our application problem. Unlike standard SIRPF approaches, where the weights are based solely on sampled observation likelihoods, the RBPF formulation leverages sufficient statistics (Θ) maintained within each particle. This conditioning mechanism reduces the variance of importance weights [17] and thereby enables lower variance belief updates in accordance with the Rao-Blackwell theorem. The overall Rao-Blackwellized belief update procedure is summarized in Algorithm 1. C. Online Planning with Rao-Blackwellization The key modification required to incorporate RaoBlackwellized belief representations into sampling-based online POMDP solvers arises during generative evaluation inside the planning tree. In standard POMCP and POMCPOW, rewards and observations are simulated by drawing a fully instantiated state realization from the particle-based belief at each tree expansion step. However, when analytically tractable components of the state are maintained as conditional distributions within each Rao-Blackwellized particle, randomly sampling these variables from their distributions during simulation introduces additional uncertainty into predicted observations and rewards. Instead, planning can be performed by computing the expected values with respect to the analytically maintained conditional distribution. For states consistent with a given history h, the immediate reward can be approximated as h i X 1 α|π R(h) ≈ Esα|π R(sπi , si , ai ) . (6) i |I(h)| i∈I(h)

A straightforward approach is to approximate this expectation via Monte Carlo sampling by drawing multiple realizations from the analytical distribution. However, drawing a

large number of samples negates the computational benefits of Rao-Blackwellization, while again, using a single sample fails to adequately capture the underlying uncertainty and leads to high-variance value estimates. This increased variance degrades the accuracy of value estimates within the planning tree and typically requires substantially more tree simulations for convergence. To address this issue, we instead approximate these expectations using deterministic quadrature methods. Quadrature techniques explicitly account for uncertainty in analytically tractable state components by replacing the expectation with α|π a weighted sum over M quadrature points si,d,k and corresponding weights wi,d,k . The resulting value estimate is given by the following: V (h) ≈

D M X X X 1 α|π γ d−τ wi,d,k R(sπi,d , si,d,k , ai,d ). |I(h)| i∈I(h) d=τ

k=1

(7) This comparison between quadrature and Monte Carlo methods is illustrated in Fig. 3 which corresponds to lines 17 and 18 in ROLLOUT and lines 27 and 34 in S IMULATE functions in Algorithm 2. When using quadrature techniques, the choice of method depends on the distribution used for the analytically marginalized states. For example, we can employ Gaussian-Hermite quadrature to interpolate and perform the necessary integration when using Gaussian beliefs for the linear states [29]. If different distributions were considered, other methods from the Askey family of orthogonal polynomials could be utilized [30] [31]. To mitigate the curse of dimensionality associated with high-order quadrature, we employ Smolyak sparse grids, which reduce the number of quadrature points required while maintaining approximation accuracy [32] [33]. The Smolyak formula for constructing the sparse grid is: A(q, d) =

X q−d+1≤|i|≤q

q−|i|

(−1)



 d d−1 O Qi , q − |i| j=1 j

(8)

where A(q, d) is the set of Smolyak quadrature points and their corresponding weights for a given sparse grid level q and dimensionality d, i is a multi-index with ij representing Nd the level of the univariate quadrature rules, and j=1 Qij denotes the tensor product of the univariate quadrature rules Qij at levels ij for each dimension j. Higher sparse grid levels yield more accurate expectation estimates at the cost of increased computational time. Hence, by choosing different levels of sparse grid, we can fine-tune the trade off between computational cost and integration accuracy in the planner. Overall, this approach reduces the reliance on Monte Carlo sampling for all states by capturing the marginalized states using deterministic quadrature techniques and ultimately reduces the total number of tree iterations needed in POMCP and POMCPOW. The RB-POMCPOW pseudocode, adapted from [24], is presented in Algorithm 2 with the modified code written in blue. Quadrature techniques are used in lines 17 and

5

Quadrature Method Selection

Generative Evaluation

Integration & Analytical Update

Deterministic Sampling

Monte Carlo Method Selection

Generative Evaluation

Analytical Update

Random Sampling

Fig. 3. Illustration of the Rao-Blackwellized particle generative evaluation and analytical update during online planning. Top: Quadrature-based integration. A selected Rao-Blackwellized particle consists of sampled (particle-based) state components and analytically maintained conditional distributions. During generative evaluation, deterministic quadrature nodes are combined with the particle state to produce multiple fully instantiated and weighted next states, rewards, and observations. Although each realization yields a complete next state, only the sampled state components are used for the analytical belief update. The analytical state components are not averaged across these realizations; instead, they are updated using the expected observation and the expected next sampled component computed via their corresponding quadrature weights, yielding an updated analytical distribution. This results in a new Rao-Blackwellized particle stored at the corresponding tree node. Bottom: Monte Carlo evaluation. Analytically tractable components are randomly sampled to generate a single next-state realization. Integration is no longer needed, and the realized observation and next sampled state component is directly used for belief update. This introduces additional sampling-induced variance into predicted rewards, leading to slower convergence of value estimates and requiring substantially more tree simulations, as validated in Section VI-B.

27. Note that the sparse grid level or the integration methods can be adjusted independently for the ROLLOUT and S IMULATE functions to compute the expectations. While this study primarily focuses on the RB-POMCPOW algorithm, the underlying principles for handling uncertainty in the analytical distributions of tractable states remain the same for POMCP (refer to Appendix for the pseudocode). While quadrature techniques are used to approximate expectations for continuous analytically maintained belief components, the RB-POMDP framework is not restricted to such distributions. In particular, when marginalized variables have finite discrete support, expectations can be computed exactly. For example, if X ∼ Bern(p), then E[R(X)] = (1 − p)R(0) + pR(1).

(9)

This again helps avoid randomly sampling stochastic realizations when evaluating expected rewards and observations during tree expansion. In general, any marginalized state component admitting a closed-form conditional update can be incorporated within the proposed RB-POMDP framework. IV. P ROBLEM F ORMULATION We consider a robotic search-and-rescue task in an initially unknown indoor environment populated with a set of N ∈ N

static landmarks, each of which may or may not be associated with a victim. The robot must operate under partial observability, simultaneously localizing itself, estimating landmark geometry, and reasoning about latent semantic information associated with each landmark in order to make sequential decisions that maximize a task-specific objective (i.e., locating all victims in the environment). An overview of the experimental setup is shown in Fig. 5.

A. Problem Statement At each discrete time step t, the robot executes an action at ∈ A, transitions to a new state st ∈ S according to stochastic dynamics, and receives a noisy observation ot ∈ O. Observations are composed of both geometric measurements zt and semantic measurements yt , such that ot = (zt , yt ). Geometric observations provide information about landmark locations relative to the robot, while semantic observations provide probabilistic evidence regarding latent semantic attributes associated with each landmark. Therefore, the underlying state space contains both continuous geometric variables and discrete semantic variables that must be inferred from noisy observations over time. The robot’s objective is to select

6

Algorithm 2 RB-POMCPOW adapted from [24] 1: procedure S EARCH(h) 2: for i ← 1 to N do 3: S IMULATE(p ∼ b(h), h, dmax ) 4: return arg maxa Q(ha); 5: 6: procedure ACTION P ROG W IDEN(h) 7: if |C(h)| ≤ ka N (h)αa then 8: a ← N EXTACTION(h) 9: C(h) ← C(h) ∪ {a} h q

log N (h)

26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41:

i

a ← ACTION P ROG W IDEN(h) (sˆ′ , ô, r̂) ← E[G(p, a)] ▷ Quadrature Techniques if |C(ha)| ≤ ko N (ha)αo then o ← ô M (hao) ← M (hao) + 1 else (hao) o ← select o ∈ C(ha) w.p. PMM (hao) o end if p′ ←A NALYTICAL U PDATE(p, sˆ′ , o, a) append (p′ , r̂) to B(hao) append Z(o | p, a, p′ ) to W (hao) if o ∈ / C(ha) then ▷ new node C(ha) ← C(ha) ∪ {o} total ← r̂ + γ * ROLLOUT(p′ , hao, d − 1) else (p′ , r) ← select B(hao)[i] w.p. PmW (hao)[i] W (hao)[j]

10: return arg maxa∈C(h) Q(ha) + c N (ha) 11: 12: procedure ROLLOUT(p, h, d) 13: if γ depth < ϵ then 14: return 0 15: end if 16: a ∼ πrollout (h, ·) j=1 17: (sˆ′ , ô, r̂) ← E[G(p, a)] ▷ Quadrature Techniques 42: total ← r + γS IMULATE(p′ , hao, d − 1) ′ ′ 43: end if 18: p ← A NALYTICAL U PDATE(p, sˆ , ô, a) 44: N (h) ← N (h) + 1 19: return r̂ + γ · ROLLOUT(p′ , haô, d − 1) 45: N (ha) ← N (ha) + 1 20: end procedure 21: 46: Q(ha) ← Q(ha) + total−Q(ha) N (ha) 22: procedure S IMULATE(p, h, d) 47: return total 23: if d = 0 then 48: end procedure 24: return 0 25: end if

actions that maximizes the expected cumulative reward by efficiently visiting landmarks with high semantic likelihood. This decision-making problem can be naturally formulated as a POMDP as detailed below. Importantly, because the state includes not only robot pose but also landmark geometry and latent semantic variable whose dimensionality grows with the number of landmarks, this results in a high-dimensional belief representation that poses significant challenges for samplingbased online POMDP solvers. B. State Space S The agent’s state at time t is defined as

robot is within the sensing range. Successful identification of a victim through this action contributes to the detection reward defined in IV-F. D. Transition Model T The agent dynamics are governed by the robot motion model and deterministic bookkeeping updates while landmark location and latent semantic variables are assumed to remain static. Given state st and action at , the robot pose evolves according to xt+1 = h(xt , at ) + δt , (11)

where xt ∈ Rdx denotes the robot pose (i.e., position and orientation), θn,t ∈ Rdθ denotes the geometric location of the n-th landmark, en,t ∈ {0, 1} denotes a latent semantic variable indicating the presence or absence of a victim associated with the n-th landmark, and vn,t ∈ {0, 1} denotes a visited indicator used for bookkeeping and reward evaluation. This structured decomposition will later be exploited in section V-A to analytically marginalize subsets of the state within the proposed Rao-Blackwellized belief representation.

where h denotes a nonlinear unicycle motion model and δt ∼ N (0, Qt ) represents zero-mean Gaussian process noise. While additive Gaussian noise is assumed here for our experimental setup, both the transition and observation models are not required to follow additive noise assumptions. We adopt the notation convention used in [18] in accordancce to the SLAM literature. The visited indicators {vn,t }N n=1 are updated deterministically when the robot executes a scan action. If the robot is within a predefined radius of landmark n, then the corresponding visited flag is set to one. Otherwise, it remains unchanged.

C. Action Space A

E. Observations and Observation Model O, Z

At each time step, the robot selects an action at = (vt , ωt ) where vt denotes the linear velocity and ωt denotes the angular velocity. The action space is discretized to include forward, backward, and left and right turning motions. In addition to motion actions, the robot is equipped with a scanning action that does not induce motion but allows the robot to directly observe the latent semantic state of a landmark when the

At each time step, the robot receives observations ot = (zt , yt ) = {(zn,t , yn,t )}n∈Nt consisting of geomeric and semantic measurements associated with a set of visible landmarks Nt ⊆ {1, . . . , N }. We assume that data association is known (i.e., each observation is associated with a unique landmark index). While FastSLAM has been extended to handle unknown data association [18], this assumption allows

N N st = xt , {θn,t }N n=1 , {en,t }n=1 , {vn,t }n=1 ,

(10)

7

us to focus on belief representation and its integration within the POMDP framework. Geometric observations provide noisy landmark positions relative to the robot and are received whenever landmarks are within the sensing range. Specifically, the geometric observation associated with landmark n ∈ Nt is modeled as zn,t = g(xt , θn,t ) + ϵn,t ,

(12)

where g denotes a nonlinear range-and-bearing measurement function and ϵn,t ∼ N (0, Rt ) is zero-mean Gaussian noise. Again, additive Gaussian observation noise assumption is not required. Semantic observations provide information about the latent semantic variable en,t associated with each landmark. Such observations are also assumed to be available once the robot executes a sensing action within the sensing range. We assume conditional independence across landmarks and sensing modalities. Details of the semantic measurement model and its role in the importance weight computation are provided in Section V-D. F. Reward R The reward function is designed to encourage efficient exploration toward potential victim locations while penalizing unnecessary motion and control effort:

robot trajectory and deterministic bookkeeping variables, combined with an associated map in which landmark geometry and semantic attributes are maintained analytically. In particular, each particle carries N EKFs for geometric landmark states and N Bernoulli distributions for semantic landmark states. Formally, the m-th particle at time t is given by ! oN n [m] [m]
[m] [m] [m] t,[m] , (16) St = x , µn,t , Σn,t , πn,t , vn,t n=1 | {z } |{z} EKF

sian estimate of landmark geometry maintained by each EKF [m] and πn,t denotes the Bernoulli parameter associated with the semantic variable en,t . B. Proposal Distribution The efficiency of particle-based belief updates depends on the proposal distribution used for sampling. We adopt the measurement-informed proposal distribution from FastSLAM 2.0. The key idea is to sample robot poses by incorporating both the control input and the geometric landmakr measurements to reduce particle depletion compared to sampling from the motion model alone [21]. Specifically, the proposal distribution for the robot state at time t is given by   [m] q xt | xt−1 , at , z t ∝

R(st , at , st+1 ) = Rfound (st , at , st+1 ) + kp vt cos(eψt ) {z } | {z } | detection reward

radial motion reward

lateral motion penalty

Z

heading penalty

(13)

where eψt denotes the heading error between the robot orientation and the direction toward the nearest, unvisited target landmark with high semantic probability, and kp , kv , kω , klat , and kh are positive weighting coefficients. The detection reward is defined as Rfound (st , at , st+1 ) =

N X

I [at = ascan ∧ vn,t+1 = 1 ∧ vn,t = 0 ∧ en,t = 1] R0 ,

n=1

(14)

where R0 is a constant positive reward associated with successfully identifying a victim.. V. M ETHODOLOGY

  t t p xt , {θn,t , en,t , vn,t }N n=1 | o , a N Y n=1

  p (zn,t | θn,t , xt ) p θn,t | xt−1,[m] , z t−1 dθn,t | {z } | {z }   ∼N(zn,t ; g(θn,t ,xt ),Rt ) [m] [m] ∼N θ ;µ ,Σ n,t

p(θn,t , en,t | xt , ot , at ) (15)

where xt , ot , and at denote the histories of robot trajectory, observations, and actions up to time step t, respectively. The belief is approximated using a set of M RaoBlackwellized particles. Each particle represents a sampled

n,t−1

n,t−1

(17)

Although multiple landmark measurements may be available at time t, the proposal is constructed by incorporating landmark measurements sequentially. For notational clarity, this is illustrated here for a single measurement zn,t following [21]. The above proposal does not admit a closed form solution in general. However, we can approximate the measurement function using a first-order Taylor expansion, yielding a Gaussian proposal distribution. Under this EKF-style approximation, the proposal distribution becomes   [m] [m] q(xt | xt−1 , at , z t ) = N xt ; µ[m] , Σ , (18) xt xt [m]

A. Rao-Blackwellized Belief Representation Conditioned on the robot trajectory, landmark states are assumed to be independent, as is standard in FastSLAMbased formulations. The posterior then admits the following factorization

t t = p(xt , {vn,t }N n=1 | o , a )

  [m] p xt | xt−1 , at {z } |

  [m] ∼N xt ; h(xt−1 ,at ),Qt

− (kv vt2 + kω ωt2 ) − klat |vt | sin2 (eψt ) − kh (1 − cos(eψt )), {z } | {z } | {z } | control penalty

Bernoulli

[m] [m] where (µn,t , Σn,t ) denote the sufficient statistics of the Gaus-

[m]

where µxt and Σxt are computed as described in [21]. C. Importance Weight Computation Note that semantic observations are not used in the proposal distribution. However, they still must be incorporated in the importance weights computation by marginalizing the continuous landmark geometry, robot’s pose, and the discrete semantic variables. Under the assumption of conditional independence across landmarks and sensing modalities, the overall observation likelihood factorizes as Y p(ot | st ) = p(zn,t | xt , θn,t , en,t ) p(yn,t | xt , θn,t , en,t ). n∈Nt

(19)

8

Therefore, for an observation associated with landmark n, the weight update for particle m can be written as   [m] wn,t ∝ p zn,t , yn,t | xt−1,[m] , at , ot−1   X = p en,t = e | xt−1,[m] , at , ot−1

this closed-form expression is provided in Appendix VII. Under this formulation, the expected detection and similarly [m] expected false-alarm probabilities (i.e. P̄F A with different model parameters β0 and β1 ) can be computed in closed form. This enables the importance weight computation in (20) to be performed analytically:

e∈{0,1}

ZZ p(yn,t | xt , θn,t , e)

p(zn,t | xt , θn,t ) | {z } ∼N(zn,t ; g(θn,t ,xt ),Rt )   [m] p θn,t | xt−1,[m] , at−1 , z t−1 dθn,t p(xt | xt−1 , at ) dxt . | {z } | {z }     [m] [m] ∼N θn,t ; µn,t−1 ,Σn,t−1

h [m]
1−yn,t [m] [m]
yn,t [m] [m] [m]
1 − P̄D wn,t ≈ N zn,t ; ẑn,t , Λn,t πn,t P̄D i [m]
[m]
y [m]
1−yn,t + 1 − πn,t P̄F A n,t 1 − P̄F A , (25)   [m]

[m]

∼N xt ; h(xt−1 ,at ),Qt

D. Semantic Observation Modeling One way to ensure that (20) remains analytically tractable is to model the semantic likelihood such that it admits a closed-form expression when marginalized under the Gaussian uncertainty induced by the robot pose and landmark geometry. Specifically, we model semantic detection as a Bernoulli random variable whose success probability is defined as a function of the range defined as d:
p(yn,t = 1 | θn,t , xt , en,t = 1) = PD d(xt , θn,t ) . (21) To preserve analytical tractability, the detection function PD (d) must be chosen such that marginalization over a Gaussian-distributed range,   2 [m] d ∼ N dˆ[m] , (22) n , σn,d

[m]

[m]

[m]

⊤ Λn,t = Gx Qt G⊤ x + Gθ Σn,t−1 Gθ + Rt .

(20)

Following FastSLAM 2.0, the integrals over the robot pose and landmark geometry are again approximated in closed form by linearizing the measurement model g, yielding a Gaussian likelihood evaluation. To preserve a fully closed-form importance weight computation, the semantic observation model must be carefully designed, as detailed in the next section V-D.

[m]

where ẑn,t = g x̂t , θ̂n,t is the predicted measurement and the innovation covariance is (26)

Here, the matrices Gx and Gθ are the Jacobians of g with respect to xt and θn,t , respectively [18]. E. Belief update The update step for geometric landmark states remains the same as in FastSLAM, which is equivalent to the standard EKF measurement update [18] [34]. We therefore focus on the update of the semantic belief associated with each landmark. The latent semantic state is modeled as a Bernoulli random [m] variable with particle-specific belief πn,t for landmark n. Hence, given a binary semantic observation yn,t , the semantic belief is updated analytically via Bayes’ rule as " [m] πn,t =

1+

[m]

[m]

1 − πn,t−1

P̄F A

[m]

P̄D

πn,t−1

!yn,t

[m]

[m]

1 − P̄F A

[m]

1 − P̄D

!1−yn,t #−1 . (27)

VI. E XPERIMENTAL R ESULTS A. Belief Quality and Computation

We first compare the accuracy of RBPF and SIRPF by evaluating their root-mean-square error (RMSE). As shown in the top plot of Figure 4, RBPF achieves low RMSE with a relatively small number of particles, after which further admits a closed-form solution. The mean and variance of increases in particle count yield only marginal improvements. the range distribution are again approximated via first-order In particular, approximately 50 particles are sufficient for linearization as RBPF to near-optimal accuracy. In contrast, SIRPF requires   [m] [m] 2 [m] [m] ⊤ ⊤ [m] dˆn = f x̂t , θ̂n,t , σn,d = Jx Qt Jx + Jθn Σn,t−1 Jθn , substantially more number of particles to approach comparable accuracy. Even with 10,000 particles, the RMSE of SIRPF (23) remains higher than that of RBPF using as few as 10 particles. [m] [m] [m] [m] where x̂t = h(xt−1 , at ) and θ̂n,t = µn,t−1 denote the This behavior is consistent with prior results in FastSLAM predicted robot pose and predicted landmark location, respecworks, where Rao-Blackwellization substantially improves estively, and Jx and Jθn are the Jacobians of f with respect to timation efficiency and accuracy by analytically marginalizing xt and θn,t . While commonly used link functions such as the logistic conditionally tractable state subcomponents [18] [21]. We next analyze the computational costs of belief updates function do not yield closed-form expressions when marginalized under Gaussian uncertainty, the probit link yields an exact shown in the bottom plot of Figure 4. For an equal numanalytical solution. Using the probit model, we therefore define ber of particles, RBPF incurs higher per-update computation the detection probabilities as time than SIRPF due to the additional analytical updates [m] required for each landmark belief. This increase is expected as P̄D = Ed∼N (dˆ[m] ,σ2 [m] ) [PD (d)] n n,d   each Rao-Blackwellized particle maintains an EKF for every Z [m]   α0 + α1 dˆn  landmark geometry as well as a Bernoulli belief for each 2 [m] = Φ(α0 + α1 d) N d; dˆ[m] dd = Φ q , n , σn,d latent semantic variable. Inevitably, updating these analytical 2 [m] 1 + α12 σn,d (24) belief components incurs additional per-particle computational where Φ denotes the standard normal cumulative distribution overhead compared to SIRPF, which samples all state variables function and α0 , α1 are model parameters. A derivation of directly. However, because RBPF analytically marginalizes

9

Accuracy Comparison Between SIRPF and RBPF SIRPF RBPF

5.0

RMSE (m)

4.5 4.0 3.5 3.0 2.5 101

102

Particle Count

103

104

Computational Cost Comparison Between SIRPF and RBPF

Belief Update Time (ms)

600

SIRPF RBPF

500 400 300 200 100 0 101

102

Particle Count

103

104

Fig. 4. Comparison of estimation accuracy and computational cost between SIRPF and RBPF. RMSE is computed by combining the squared estimation errors of both the robot pose and all observed landmark positions. Computational cost is computed per belief update at each time step.

both continuous landmark geometry and discrete semantic variables, it decreases the dimensionality of the sampled state space. As a result, RBPF achieves improved estimation accuracy with significantly fewer particles, reducing the overall computational cost required to maintain a belief of similar quality. Thus, despite higher per-particle costs, RBPF still offers superior efficiency in practice by significantly reducing the number of particles required for accurate belief representation. B. Planning Performance and Computation We next evaluate how belief representation and generative evaluation influence planning performance under a fixed planning computational budget. Representative trajectories generated by each planner are shown in Fig. 5. In Fig. 5 (a), POMCPOW with a standard SIRPF belief exhibits large trajectory deviations and fails to reach the high-probability victim in Room 4. In Fig. 5 (b), we replace the belief representation with RBPF while retaining Monte Carlo–based generative evaluation during tree expansion. In this setting, analytically maintained landmark geometry and semantic states are randomly sampled to produce a single realization when simulating predicted observations and rewards, as illustrated by the Monte Carlo scheme in Fig. 3. We denote this planner as RB-MCPOMCPOW. Although RB-MC-POMCPOW benefits from re-

duced belief estimation variance due to Rao-Blackwellization, the use of stochastic realizations of analytically tractable state components during planning introduces additional planning uncertainty. As a result, the planner eventually locates all victim rooms but exhibits unnecessary detours when approaching Room 5 from Room 7. While both sampling-based planners can occasionally generate near-optimal trajectories given sufficient simulations with increased planning computational budget, their performance remains inconsistent due to samplinginduced variance in predicted rewards and observations during tree expansion. In contrast, RB-POMCPOW replaces these stochastic realizations with deterministic expectation over analytically tractable state components during generative evaluation. This corresponds to the quadrature scheme in Fig. 3. This reduces the variance of predicted outcomes within the planning tree and results in more consistent value estimation, yielding more direct navigation toward rooms with high victim belief, as shown in Fig. 5 (c). To quantify this effect, Figure 6 shows cumulative reward as a function of per-step planning computation time for the baseline POMCPOW, RB-MC-POMCPOW, and RB-POMCPOW planners. To ensure comparable belief estimation accuracy, we use 50 and 10,000 particles for RBPF and SIRPF, respectively, as established in the previous section. For RB-POMCPOW, performance is evaluated across varying sparse grid levels with fixed tree iteration counts. For POMCPOW and RB-MCPOMCPOW, we only vary the tree iterations because both rely on Monte Carlo generative evaluation. As expected, increasing either the sparse grid level or the number of tree iterations generally improves cumulative reward by producing more accurate value function estimates. However, computational cost grows proportionally with the sparse grid level for RB-POMCPOW, which limits the number of tree iterations that can be performed within a fixed computational budget. Despite this trade-off, RB-POMCPOW consistently outperforms both POMCPOW and RB-MC-POMCPOW under similar computational budgets. For example, even with 1500 tree iterations, POMCPOW achieves cumulative rewards comparable only to RB-POMCPOW using a sparse grid level of q = 1 with just 100 tree iterations. Similarly, RB-MCPOMCPOW with 500 tree iterations provides only marginal improvement over RB-POMCPOW with q = 1, indicating that improved belief representation alone is insufficient to achieve comparable planning performance. These results can be explained by two complementary variance-reduction mechanisms. First, RBPF maintains conditionally independent landmark beliefs analytically within each particle, resulting in higher effective sample size compared to SIRPF. This aligns with the Rao-Blackwell theorem, ensuring that each selected Rao-Blackwellized particle provides a highquality representation of the belief state with reduced variance in belief representation. Second, RB-POMCPOW computes expected observations and rewards during generative evaluation by integrating over analytically tractable state components, further reducing uncertainty in predicted outcomes during tree expansion. Together, these effects reduce both belief and planning variance, allowing value function estimates to

10

(a) POMCPOW (SIRPF)

(b) RB-MC-POMCPOW (RBPF)

(c) RB-POMCPOW (RBPF)

Fig. 5. Effect of planner and belief representation on robot behavior. Representative robot trajectories generated using (a) POMCPOW with a standard SIRPF, (b) RB-MC-POMCPOW with RBPF but performs Monte Carlo–based generative evaluation by drawing a single realization (cf. Monte Carlo scheme in Fig. 3), and (c) RB-POMCPOW which instead evaluates expected rewards and observations via analytical integration (cf. Quadrature scheme in Fig. 3). Victims are located at the centers of rooms, and the blue bars indicate the corresponding victim-evidence belief which converges toward the true value over time. Red and blue curves denote the estimated and ground-truth robot trajectories, respectively, while green crosses indicate particle or EKF-based estimates of victim locations. All planners are executed with the same maximum time horizon, computational budget, and hyperparameters. In the representative run shown, POMCPOW with SIRPF (a) fails to reach the high-probability victim in Room 4. RB-MC-POMCPOW (b) eventually reaches all of the victim rooms, but the trajectory exhibits unnecessary detours when approaching Room 5. Although these purely sampling-based planners can occasionally produce optimal trajectories, they exhibit higher variability, reflecting sampling-induced variance in value estimation. In contrast, RB-POMCPOW (c) better accounts for uncertainty with analytical integration at each tree node and results in more direct navigation toward rooms with high victim belief.

Cumulative Reward Comparison

Cumulative Reward

100

RB-POMCPOW (Tree Iter=100) POMCPOW with SIRPF RB-MC-POMCPOW Theoretical Upper Bound

95 90 85

q=1

q=2

q=6

q=5

q=3 q=4

Iter=500

80 75 70

Iter=100 Iter=200 Iter=200 Iter=100

50

100

Iter=1000 Iter=500

150

200

250

Planning Computational Time per Step (ms)

Fig. 6. Planning performance versus computational cost. Cumulative reward as a function of per-step planning time for POMCPOW, RB-MC-POMCPOW and RB-POMCPOW. For RB-POMCPOW, results are shown for different sparse grid levels (denoted as q) with fixed tree iterations. The dashed red line indicates a theoretical upper bound on cumulative reward obtained by assuming perfect semantic information and optimal trajectory path; therefore, it represents a loose performance reference that cannot be achieved. RBPOMCPOW consistently achieves higher reward than both POMCPOW and RB-MC-POMCPOW under comparable computational budgets.

converge with much fewer tree iterations than purely samplingbased planners. VII. C ONCLUSION AND F UTURE W ORK This work presented a Rao-Blackwellized online planning framework for high-dimensional POMDPs and validated its effectiveness in an indoor robotic search-and-rescue task by integrating it with the FastSLAM 2.0 algorithm. The results highlight an important relationship between belief quality and planning quality in POMDPs. While RBPFs have long

been shown to improve estimation accuracy and efficiency in robotic systems, improving belief performance alone is not the only benefit of Rao-Blackwellization in online planning settings. By analytically marginalizing tractable state components and propagating their uncertainty through deterministic integration, the RB-POMDP framework reduces variance not only in belief estimation but also in value estimation during planning. This reduction in planning variance translates directly into improved computational efficiency, suggesting that Rao-Blackwellized online planning is not merely beneficial but becomes essential for computationally tractable decisionmaking in high-dimensional problems. However, the effectiveness of Rao–Blackwellized planning depends fundamentally on whether expectations of rewards and observations can be computed tractably with respect to the marginalized state components during generative evaluation. In this work, landmark geometry and semantic attributes are represented using Gaussian and Bernoulli distributions, respectively, both of which admit closed-form belief updates and efficient expectation computation during planning. In contrast, extending the RB-POMDP framework to occupancy grid-based SLAM such as GMapping [35] [36] presents additional challenges. Occupancy grid maps represent each cell using independent Bernoulli random variables, resulting in a very high-dimensional discrete belief space. Although these cell-wise beliefs are analytically tractable, the raycasting observation model depends jointly on multiple cells along each sensing beam. Therefore, computing the expected rewards and observations during generative evaluation requires marginalization over the joint occupancy configuration of all cells intersecting the ray, resulting in an exponential number of realizations. While naive Monte Carlo sampling from independent cell-

11

wise occupancy distributions is computationally feasible, it fails to enforce spatial coherence in the instantiated map realizations and can produce spatially inconsistent checkerboardlike occupancy patterns. Planning over such sampled map can cause the agent to exhibit hallucinated behaviors during tree expansion. Recent work on generative observation models for range sensing, including learned LiDAR simulators, offers a promising direction for addressing this limitation by producing realistic map realizations [37] [38] [39] [40]. Integrating such generative sensing models (e.g. [41]) into the Rao-Blackwellized online planning represents an important avenue for future work to enable integrating POMDPs in richer SLAM settings beyond feature-based representations.

We seek the marginalized detection probability: Z P̄D ≜ E[Φ(α0 + α1 d)] = Φ(α0 + α1 d) N (d; µ, σ 2 ) dd.

A PPENDIX A. RB-POMCP

Since u and d are Gaussian and independent, w is also Gaussian with mean and variance

The following pseudocode outlines the RB-POMCP algorithm. The code is adapted from [10] with the modified code written in blue. The ROLLOUT function is the same as the one defined in Algorithm 2.

P̄D = Ed [P(u ≤ α0 + α1 d | d)] = P(u ≤ α0 + α1 d) . (31) Equivalently, P̄D = P(u − α1 d ≤ α0 ) .

(32)

Now define the random variable w ≜ u − α1 d.

E[w] = E[u] − α1 E[d] = 0 − α1 µ = −α1 µ, Var(w) = Var(u) + α12 Var(d) = 1 + α12 σ 2 .

(33)

(34) (35)

Therefore,
w ∼ N −α1 µ, 1 + α12 σ 2 .

Algorithm 3 RB-POMCP 1: procedure S IMULATE(p,h, depth) 2: if γ depth < ϵ then 3: return 0 4: end if 5: if hao ∈ / T then 6: for all a ∈ A do 7: T (ha) ← (Ninit (ha), Vinit (ha), ∅) 8: end for 9: return ROLLOUT(p, h, depth) 10: end if q h i N (h) 11: a ← arg maxb V (hb) + c log N (hb)

(36)

Hence, ! α0 − E[w] P̄D = P(w ≤ α0 ) = Φ p Var(w) ! ! α0 − (−α1 µ) α0 + α1 µ =Φ p =Φ p , 1 + α12 σ 2 1 + α12 σ 2

(37) (38)

which proves (28). R EFERENCES

(ŝ′ , ô, r̂) ← E[G(p, a)] ▷ Quadrature Techniques p′ ← A NALYTICAL U PDATE(p, ŝ′ , ô, a) R ← r̂ + γ * S IMULATE(p′ , haô, depth + 1) N (h) ← N (h) + 1 N (ha) ← N (ha) + 1 (ha) 17: V (ha) ← V (ha) + R−V N (ha) 18: return R 19: end procedure 12: 13: 14: 15: 16:

A PPENDIX B. C LOSED -F ORM M ARGINALIZATION OF P ROBIT D ETECTION M ODELS UNDER G AUSSIAN U NCERTAINTY This appendix derives the closed-form expression ! Z α0 + α1 µ 2 Φ(α0 + α1 d) N (d; µ, σ ) dd = Φ p , (28) 1 + α12 σ 2 [m]

(30) We introduce an independent standard normal random variable u ∼ N (0, 1) with u ⊥ d. Using the identity Φ(x) = P(u ≤ x), we can rewrite

2 [m]

which is used in the main text with µ = dˆn and σ 2 = σn,d in (24). Let d ∼ N (µ, σ 2 ) and define the probit detection model PD (d) = Φ(α0 + α1 d). (29)

[1] A.-a. Agha-mohammadi, S. Agarwal, S.-K. Kim, S. Chakravorty, and N. M. Amato, “SLAP: Simultaneous Localization and Planning Under Uncertainty via Dynamic Replanning in Belief Space,” IEEE Transactions on Robotics, vol. 34, no. 5, pp. 1195–1214, Oct. 2018. [Online]. Available: https://ieeexplore.ieee.org/document/8479330/ [2] A. A. Meera, M. Popovic, A. Millane, and R. Siegwart, “Obstacle-aware Adaptive Informative Path Planning for UAV-based Target Search,” in 2019 International Conference on Robotics and Automation (ICRA). Montreal, QC, Canada: IEEE, May 2019, pp. 718–724. [Online]. Available: https://ieeexplore.ieee.org/document/8794345/ [3] G. Flaspohler, V. Preston, A. P. M. Michel, Y. Girdhar, and N. Roy, “Information-Guided Robotic Maximum Seek-and-Sample in Partially Observable Continuous Environments,” IEEE Robotics and Automation Letters, vol. 4, no. 4, pp. 3782–3789, Oct. 2019. [Online]. Available: https://ieeexplore.ieee.org/document/8767964/ [4] J. A. Placed, J. Strader, H. Carrillo, N. Atanasov, V. Indelman, L. Carlone, and J. A. Castellanos, “A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers,” IEEE Transactions on Robotics, vol. 39, no. 3, pp. 1686–1705, Jun. 2023. [Online]. Available: https://ieeexplore.ieee.org/document/10075065/ [5] A. Zhitnikov and V. Indelman, “Simplified Continuous HighDimensional Belief Space Planning With Adaptive Probabilistic Belief-Dependent Constraints,” IEEE Transactions on Robotics, vol. 40, pp. 1684–1705, 2024. [Online]. Available: https://ieeexplore.ieee.org/ document/10354386/ [6] M. J. Kochenderfer, T. A. Wheeler, and K. H. Wray, Algorithms for decision making. Cambridge, Massachusetts: The MIT Press, 2022. [7] Z. N. Sunberg, C. J. Ho, and M. J. Kochenderfer, “The value of inferring the internal state of traffic participants for autonomous freeway driving,” in 2017 American Control Conference (ACC). Seattle, WA, USA: IEEE, May 2017, pp. 3004–3010. [Online]. Available: https://ieeexplore.ieee.org/document/7963408/

12

[8] H. Durrant-Whyte, N. Roy, and P. Abbeel, “Unmanned Aircraft Collision Avoidance Using Continuous-State POMDPs,” in Robotics: Science and Systems VII, 2012, pp. 1–8. [9] K. H. Wray, S. J. Witwicki, and S. Zilberstein, “Online DecisionMaking for Scalable Autonomous Systems,” in Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. Melbourne, Australia: International Joint Conferences on Artificial Intelligence Organization, Aug. 2017, pp. 4768–4774. [Online]. Available: https://www.ijcai.org/proceedings/2017/664 [10] D. Silver and J. Veness, “Monte-Carlo Planning in Large POMDPs,” in Advances in Neural Information Processing Systems, J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, Eds., vol. 23. Curran Associates, Inc., 2010. [Online]. Available: https://proceedings.neurips.cc/paper_files/paper/ 2010/file/edfbe1afcf9246bb0d40eb4d8027d90f-Paper.pdf [11] Z. Sunberg and M. Kochenderfer, “Online Algorithms for POMDPs with Continuous State, Action, and Observation Spaces,” Proceedings of the International Conference on Automated Planning and Scheduling, vol. 28, pp. 259–263, Jun. 2018. [Online]. Available: https://ojs.aaai. org/index.php/ICAPS/article/view/13882 [12] M. H. Lim, T. J. Becker, M. J. Kochenderfer, C. J. Tomlin, and Z. N. Sunberg, “Optimality Guarantees for Particle Belief Approximation of POMDPs,” Journal of Artificial Intelligence Research, vol. 77, pp. 1591–1636, Aug. 2023. [Online]. Available: https://jair.org/index.php/jair/article/view/14525 [13] D. J. C. Mackay, “Introduction to Monte Carlo Methods,” in Learning in Graphical Models, M. I. Jordan, Ed. Dordrecht: Springer Netherlands, 1998, pp. 175–204. [Online]. Available: http: //link.springer.com/10.1007/978-94-011-5014-9_7 [14] C. Snyder, T. Bengtsson, P. Bickel, and J. Anderson, “Obstacles to High-Dimensional Particle Filtering,” Monthly Weather Review, vol. 136, no. 12, pp. 4629–4640, Dec. 2008. [Online]. Available: http://journals.ametsoc.org/doi/10.1175/2008MWR2529.1 [15] S. C. Surace, A. Kutschireiter, and J.-P. Pfister, “How to Avoid the Curse of Dimensionality: Scalability of Particle Filters with and without Importance Weights,” SIAM Review, vol. 61, no. 1, pp. 79–91, Jan. 2019. [Online]. Available: https://epubs.siam.org/doi/10.1137/17M1125340 [16] P. Bickel, B. Li, and T. Bengtsson, “Sharp failure rates for the bootstrap particle filter in high dimensions,” in Institute of Mathematical Statistics Collections. Beachwood, Ohio, USA: Institute of Mathematical Statistics, 2008, pp. 318–329. [Online]. Available: http://projecteuclid.org/euclid.imsc/1209398477 [17] J. S. Liu, Monte Carlo Strategies in Scientific Computing, ser. Springer Series in Statistics Ser. New York, NY: Springer New York, 2008. [18] M. Montemerlo, S. Thrun, D. Roller, and B. Wegbreit, “FastSLAM 2.0: an improved particle filtering algorithm for simultaneous localization and mapping that provably converges,” in Proceedings of the 18th International Joint Conference on Artificial Intelligence, ser. IJCAI’03. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2003, pp. 1151–1156. [19] A. Doucet, S. Godsill, and C. Andrieu, “On Sequential Monte Carlo Sampling Methods for Bayesian Filtering,” in Readings In Unobserved Components Models, A. C. Harvey and T. Proietti, Eds. Oxford University PressOxford, May 2005, pp. 418–441. [Online]. Available: https://academic.oup.com/book/52077/chapter/421060565 [20] K. Murphy and S. Russell, “Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks,” in Sequential Monte Carlo Methods in Practice, A. Doucet, N. Freitas, and N. Gordon, Eds. New York, NY: Springer New York, 2001, pp. 499–515. [Online]. Available: http://link.springer.com/10.1007/978-1-4757-3437-9_24 [21] M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, “FastSLAM: a factored solution to the simultaneous localization and mapping problem,” in Eighteenth National Conference on Artificial Intelligence. USA: American Association for Artificial Intelligence, 2002, pp. 593–598. [22] S. Särkkä, A. Vehtari, and J. Lampinen, “Rao-Blackwellized particle filter for multiple target tracking,” Information Fusion, vol. 8, no. 1, pp. 2–15, 2007. [Online]. Available: https://www.sciencedirect.com/ science/article/pii/S1566253505000874 [23] C. Stachniss, G. Grisetti, and W. Burgard, “Information Gain-based Exploration Using Rao-Blackwellized Particle Filters,” in Robotics: Science and Systems I. Robotics: Science and Systems Foundation, Jun. 2005. [Online]. Available: http://www.roboticsproceedings.org/ rss01/p09.pdf [24] J. Lee, N. Ahmed, K. H. Wray, and Z. Sunberg, “Rao-Blackwellized POMDP Planning,” in 2025 IEEE International Conference on Robotics and Automation (ICRA). Atlanta, GA, USA: IEEE, May

2025, pp. 14 133–14 139. [Online]. Available: https://ieeexplore.ieee. org/document/11128426/ [25] S. Thrun, W. Burgard, and D. Fox, Probabilistic robotics, ser. Intelligent robotics and autonomous agents. Cambridge, Mass: MIT Press, 2005. [26] B. Ristic, S. Arulampalam, and N. Gordon, Beyond the Kalman filter: particle filters for tracking applications, ser. Artech House radar library. Boston, MA: Artech House, 2004. [27] A. Doucet, N. Freitas, and N. Gordon, “An Introduction to Sequential Monte Carlo Methods,” in Sequential Monte Carlo Methods in Practice, A. Doucet, N. Freitas, and N. Gordon, Eds. New York, NY: Springer New York, 2001, pp. 3–14. [Online]. Available: http://link.springer.com/10.1007/978-1-4757-3437-9_1 [28] C. Andrieu, A. Doucet, and E. Punskaya, “Sequential Monte Carlo Methods for Optimal Filtering,” in Sequential Monte Carlo Methods in Practice, A. Doucet, N. Freitas, and N. Gordon, Eds. New York, NY: Springer New York, 2001, pp. 79–95. [Online]. Available: http://link.springer.com/10.1007/978-1-4757-3437-9_4 [29] Q. Liu and D. A. Pierce, “A Note on Gauss-Hermite Quadrature,” Biometrika, vol. 81, no. 3, p. 624, Aug. 1994. [Online]. Available: https://www.jstor.org/stable/2337136?origin=crossref [30] G. Szegő, Orthogonal polynomials, 4th ed., ser. Colloquium publications - American Mathematical Society. Providence: American Mathematical Society, 1939, no. v. 23. [31] W. Schoutens, Stochastic processes and orthogonal polynomials, ser. Lecture notes in statistics. New York: Springer, 2000, no. 146. [32] V. Barthelmann, E. Novak, and K. Ritter, “High dimensional polynomial interpolation on sparse grids,” Advances in Computational Mathematics, vol. 12, no. 4, pp. 273–288, Mar. 2000. [Online]. Available: https://link.springer.com/10.1023/A:1018977404843 [33] F. Heiss and V. Winschel, “Likelihood approximation by numerical integration on sparse grids,” Journal of Econometrics, vol. 144, no. 1, pp. 62–80, May 2008. [Online]. Available: https://linkinghub.elsevier. com/retrieve/pii/S0304407607002552 [34] P. S. Maybeck, Stochastic models, estimation and control, ser. Mathematics in science and engineering. New York: Academic Press, 1979, no. v. 141. [35] G. Grisetti, C. Stachniss, and W. Burgard, “Improving Grid-based SLAM with Rao-Blackwellized Particle Filters by Adaptive Proposals and Selective Resampling,” in Proceedings of the 2005 IEEE International Conference on Robotics and Automation. Barcelona, Spain: IEEE, 2005, pp. 2432–2437. [Online]. Available: https: //ieeexplore.ieee.org/document/1570477/ [36] ——, “Improved Techniques for Grid Mapping With Rao-Blackwellized Particle Filters,” IEEE Transactions on Robotics, vol. 23, no. 1, pp. 34– 46, 2007. [37] V. Zyrianov, X. Zhu, and S. Wang, “Learning to Generate Realistic LiDAR Point Clouds,” in Computer Vision – ECCV 2022, S. Avidan, G. Brostow, M. Cissé, G. M. Farinella, and T. Hassner, Eds. Cham: Springer Nature Switzerland, 2022, vol. 13683, pp. 17–35, series Title: Lecture Notes in Computer Science. [Online]. Available: https://link.springer.com/10.1007/978-3-031-20050-2_2 [38] V. Zyrianov, H. Che, Z. Liu, and S. Wang, “LidarDM: Generative LiDAR Simulation in a Generated World,” in 2025 IEEE International Conference on Robotics and Automation (ICRA). Atlanta, GA, USA: IEEE, May 2025, pp. 6055–6062. [Online]. Available: https: //ieeexplore.ieee.org/document/11128001/ [39] L. Caccia, H. V. Hoof, A. Courville, and J. Pineau, “Deep Generative Modeling of LiDAR Data,” in 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Macau, China: IEEE, Nov. 2019, pp. 5034–5040. [Online]. Available: https://ieeexplore.ieee.org/document/8968535/ [40] Y. Xiong, W.-C. Ma, J. Wang, and R. Urtasun, “Learning Compact Representations for LiDAR Completion and Generation,” in 2023 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). Vancouver, BC, Canada: IEEE, Jun. 2023, pp. 1074–1083. [Online]. Available: https://ieeexplore.ieee.org/document/10204732/ [41] S. Deglurkar, M. H. Lim, J. Tucker, Z. Sunberg, A. Faust, and C. J. Tomlin, “Compositional Learning-based Planning for Vision POMDPs,” in Conference on Learning for Dynamics & Control, 2021. [Online]. Available: https://api.semanticscholar.org/CorpusID:254247358

Related documents

• Closed-Loop Motion Planning for Differentially Flat Systems: A Time-Varying Optimization Framework#1014448
• Markovian Dynamics Enforcer: Feasibility Preserving Correction on Learned Dynamics Manifolds#1145055
• Seeing the Bigger Picture: 3D Latent Mapping for Mobile Manipulation Policy Learning#612843
• Seeing the Bigger Picture: 3D Latent Mapping for Mobile Manipulation Policy Learning#611366
• Continual Learning for 6-DoF Grasp Synthesis via Experience and Demonstrations#1156573