Belief Space Planning

The mathematical framework underlying belief space planning. A POMDP models decision-making where the agent cannot directly observe the true state. Instead, it maintains a belief state—a probability distribution over possible states—and chooses actions based on this belief.

• States (S): The true, hidden world configuration
• Actions (A): Control inputs the agent can execute
• Observations (O): Noisy sensor readings received
• Transition Model: Probability of moving from one state to another given an action
• Observation Model: Probability of receiving a sensor reading given the true state

Solving a POMDP exactly is computationally intractable for most real-world problems, motivating approximate methods like point-based value iteration and Monte Carlo tree search variants.

The quintessential belief space problem in mobile robotics. A robot must build a map of an unknown environment while simultaneously estimating its own pose within that map. Both the trajectory and the landmark positions are uncertain and correlated.

• Filtering-based SLAM: Extended Kalman Filter (EKF) SLAM maintains a joint Gaussian over pose and landmarks
• Graph-based SLAM: Pose graph optimization solves a nonlinear least-squares problem over the entire trajectory
• Active SLAM: Closes the loop with belief space planning by selecting control actions that reduce map and pose uncertainty, trading off exploration and exploitation

Recursive Bayesian estimators that form the backbone of belief propagation. The Kalman Filter provides the optimal closed-form solution for linear Gaussian systems. The EKF linearizes nonlinear dynamics and observation models using first-order Taylor expansion.

• Prediction Step: Propagates the belief forward using the motion model, increasing covariance
• Update Step: Incorporates a sensor measurement, reducing covariance in observed dimensions
• Information Gain: The reduction in entropy achieved by a measurement, a core objective function in belief space planning

In belief space planning, the EKF predicts how future measurements will reshape the belief, enabling the planner to favor actions that localize the robot.

A nonparametric belief representation using a set of weighted particles. Unlike Gaussian filters, MCL can represent multimodal distributions, making it robust to the kidnapped robot problem and global localization.

• Particle Set: Hundreds to thousands of state hypotheses, each with an importance weight
• Motion Update: Particles are propagated through the probabilistic motion model
• Sensor Update: Weights are adjusted based on how well predicted observations match actual sensor data
• Resampling: Particles with low weights are replaced by copies of high-weight particles

Belief space planners using MCL must reason about the expected information gain of actions on the particle distribution, often approximated via entropy reduction or kernel density estimates.

A class of belief space planning methods that directly optimize information metrics rather than just distance or time. The robot actively seeks measurements that maximize knowledge about its state or the environment.

• Entropy Minimization: Select actions that minimize the expected entropy of the belief distribution
• Mutual Information: Maximize the reduction in uncertainty about the state given expected observations
• Fisher Information: Use the Fisher information matrix to quantify how much a trajectory informs parameter estimates
• Cauchy-Schwarz Quadratic Mutual Information (CSQMI): A computationally efficient approximation for non-Gaussian beliefs

These methods are critical for active perception tasks like inspection, surveillance, and scientific exploration where the primary goal is gathering information.

Originating from adaptive control, dual control explicitly balances the dual objectives of control: exploitation (driving the system toward a goal) and exploration (perturbing the system to reduce parameter uncertainty).

• Caution: The controller avoids aggressive actions that could destabilize the system given uncertain parameters
• Probing: The controller injects exploratory signals to improve future parameter estimates
• Certainty Equivalence: A suboptimal strategy that ignores uncertainty and uses point estimates as if they were true

Belief space planning is the modern generalization of dual control to robotics, where the uncertainty is over the robot's own state and the environment, not just system parameters.