Sensors & Information Spaces

Chapter 1: Observation Models

Before we can reason about uncertainty, we need to formalize how sensors work. A sensor takes the true hidden state x and produces an observation y. The crucial insight: sensors are not perfect measurement tools — they are probabilistic channels. The same state x can produce different observations on different trials.

LaValle models this with an observation space Y (the set of all possible sensor readings) and an observation mapping P(y | x) — a conditional probability distribution. For each state x, P(· | x) is a distribution over observations y ∈ Y. Some observations are more likely than others given a particular state.

Example: Binary hallway sensor

The robot is in a hallway with N cells. Three cells (positions 2, 4, 6) have doorways. The sensor returns y ∈ {door, open}. If the robot is at a doorway, the sensor returns "door" with probability 0.9 and "open" with 0.1 (missed detection). If the robot is at a non-doorway cell, it returns "open" with probability 0.8 and "door" with 0.2 (false alarm). Formally:

This matrix — one row per observation, one column per state — is the sensor model. It is the robot's model of how its hardware works. The robot uses this model to infer: "given that I saw y=door, how likely is it that I'm at each possible cell?" That inference is Bayesian — it's what drives belief updating.

Why the observation model is separate from the transition model

In Chapter 10, one model (the MDP transition P(x' | x, u)) governed everything. Chapter 11 splits this into two models: the motion model P(x_k+1 | x_k, u_k) governing how state evolves, and the sensor model P(y_k | x_k) governing what the sensor returns. This factorization lets us swap sensors without changing the environment model, and vice versa. It's also the structure that makes Bayes filtering tractable.

python
import numpy as np

class HallwaySensor:
    def __init__(self, n_cells=7, doorways=(1,3,5),
                 p_hit=0.9, p_false=0.2):
        self.n = n_cells
        self.doorways = set(doorways)
        self.p_hit   = p_hit    # P(door | at doorway)
        self.p_false = p_false  # P(door | not at doorway)

    def observe(self, x):
        """Sample an observation from P(y | x)."""
        at_door = x in self.doorways
        p_door = self.p_hit if at_door else self.p_false
        return 'door' if np.random.random() < p_door else 'open'

    def likelihood(self, y, x):
        """P(y | x) — the sensor likelihood."""
        at_door = x in self.doorways
        p_door = self.p_hit if at_door else self.p_false
        return p_door if y == 'door' else 1.0 - p_door

Chapter 2: Information States — The Master Concept

Here is the central question of Chapter 11: the robot can't condition its policy on x (hidden), so what does it condition on? The answer is the information state, or I-state η_k. Informally, the I-state is everything the robot knows at time k that is relevant for future decisions.

At time k, the robot has received observations y₀, y₁, ..., y_k and has applied actions u₀, u₁, ..., u_k-1. Define the history η_k = (y₀, u₀, y₁, u₁, ..., y_k). This history captures everything the robot has experienced. A policy π that maps each history to an action is called a history-based policy.

The I-space

The set of all possible I-states is the information space (I-space), written Ι. Just as X is the state space and U is the action space, Ι is the space of all possible information states. A policy is now a mapping π : Ι → U — from I-states to actions — instead of a mapping from states to actions.

This is a profound structural shift. In Chapter 10, the policy lived in X × U. In Chapter 11, the policy lives in Ι × U. The challenge: Ι can be enormous. If X has n states, the history-based I-space after k steps has |Y|^k×|U|^k-1 elements — exponential in k. This is the "curse of history."

I-state transitions

When the robot applies action u_k and receives observation y_k+1, its I-state updates. There is an I-state transition function:

This function τ is the "engine" that keeps the I-state current. For the raw history I-state, τ simply appends: τ(history, u, y) = (history, u, y). For the belief-state I-state (covered in Chapter 4), τ runs Bayesian filtering — a much more compact operation. The choice of I-state representation determines the form of τ.

Chapter 3: Derived I-Spaces — History, Belief, and Beyond

The raw history I-state is complete but impractical — it grows without bound. Chapter 11 introduces several derived I-spaces that are more compact while preserving the information needed for optimal planning. Each derived I-space trades off completeness for tractability in a different way.

The history I-space H_k

The most basic derived I-space is the history space. At stage k, η_k = (y₀, u₀, y₁, ..., u_k-1, y_k). This is the "keep everything" approach. It is complete — no information is lost — but the I-space H_k = Y × (U × Y)^k grows exponentially. It is practical only for very short horizons or tiny discrete problems.

The sufficient I-space and belief states

A sufficient I-state is one that captures all the information from the history that matters for future expected reward — and nothing more. For fully probabilistic problems, the belief state achieves this. The belief state b_k is a probability distribution over X: b_k(x) = P(x_k = x | y₀, u₀, ..., y_k). It is the posterior distribution over the hidden state given all observations.

The belief I-space

The belief I-space Β is the set of all probability distributions over X. For a discrete X with n states, this is the (n-1)-dimensional probability simplex: b ∈ Β ⇔ b(x) ≥ 0 for all x and ∑_x b(x) = 1. The I-state transition τ for belief states is Bayesian filtering:

where η is a normalizing constant. This two-step operation — predict then update — is the core of Bayes filtering. The predict step propagates the belief through the motion model; the update step incorporates the new observation via the sensor model.

The nondeterministic I-space (when probabilities are unavailable)

Sometimes we don't have probability models — we only know which transitions and observations are possible. The nondeterministic I-state l_k ⊆ X is the set of states the robot might currently occupy, given what it has observed. Update rule: l_k+1 = {x' : ∃ x ∈ l_k, P(x'|x,u_k) > 0, and P(y_k+1|x') > 0}. This is the "set-membership" or "worst-case" I-state — no probabilities, just possibility.

Chapter 4: Showcase — Robot in Hallway

This is the payoff chapter. You will run a robot through a 7-cell hallway, take sensor observations, and watch the belief histogram update in real time. The robot starts with a uniform prior — it thinks it might be anywhere. Each observation shrinks or reshapes the belief. Multiple observations pin it down.

Three cells (positions 1, 3, 5) are doorways. The sensor returns "door" with probability 0.85 at doorways and "door" with probability 0.1 at open cells. After each observation, Bayes' rule updates the belief. The motion model: when the robot moves right, it reaches the next cell with probability 0.8 or stays with probability 0.2 (wheels slip on the linoleum).

Tracing one update by hand

Say the robot observes y = "door." The prior is uniform: b(x) = 1/7 for each cell x ∈ {0,1,2,3,4,5,6}. The sensor model gives P(door|x=1) = 0.85 (doorway), P(door|x=0) = 0.10 (open). The Bayesian update is:

Numerator for x=1 (doorway): 0.85 × (1/7) = 0.1214. Numerator for x=0 (open): 0.10 × (1/7) = 0.0143. Normalizer η = 3 × 0.1214 + 4 × 0.0143 = 0.3643 + 0.0571 = 0.4214. After normalization: b'(1) = 0.1214/0.4214 = 0.288, b'(0) = 0.0143/0.4214 = 0.034. The three doorways together hold 3 × 0.288 = 0.864 of the probability mass — a single observation concentrated most of the belief onto doorway cells.

python
import numpy as np

def bayes_update(belief, obs, sensor_model):
    """Multiply belief by likelihood and renormalize."""
    likelihood = np.array([sensor_model[obs][x]
                           for x in range(len(belief))])
    posterior = likelihood * belief
    return posterior / posterior.sum()  # normalize

def motion_update(belief, transition_matrix):
    """Predict: convolve belief through motion model."""
    return transition_matrix.T @ belief   # P(x'|x) * b(x), summed over x

# Hallway: 7 cells, doorways at 1,3,5
doorways = {1, 3, 5}
sensor_model = {
    'door': [0.85 if x in doorways else 0.10 for x in range(7)],
    'open': [0.15 if x in doorways else 0.90 for x in range(7)],
}
belief = np.ones(7) / 7  # uniform prior

# After observing 'door':
belief = bayes_update(belief, 'door', sensor_model)
print(belief.round(3))  # [.034, .288, .034, .288, .034, .288, .034]

entropy = -np.sum(belief * np.log2(belief + 1e-10))
print(f"Entropy: {entropy:.2f} bits")  # 1.81 bits (down from 2.81)

Chapter 5: Continuous Information Spaces

So far we've worked with discrete state spaces — a finite number of cells, a finite belief vector. But most robots operate in continuous spaces: position x ∈ ℝ², orientation θ ∈ S¹, velocity v ∈ ℝ³. When X is continuous, the belief state b(x) is not a vector but a probability density function (PDF) over X.

The Bayesian update generalizes to continuous X by replacing sums with integrals. The predict step convolves the prior with the motion model:

The update step multiplies by the sensor likelihood and renormalizes:

The nondeterministic continuous I-space

When probabilistic models aren't available, the nondeterministic I-state generalizes from subsets of a discrete X to subsets of continuous X. L_k ⊆ X is a region in state space. If state dynamics are bounded — say, the robot's position can drift by at most ε per step — then L_k+1 is the ε-expansion of the motion-applied L_k, intersected with the observation-consistent set. This is called bounded-uncertainty planning and is useful in robust control applications.

Gaussian belief as a continuous I-state

For linear systems with Gaussian noise, the belief density at every step is a Gaussian: b_k(x) = 𝒩(x ; μ_k, Σ_k). This is remarkable: no matter how many steps occur, the belief is fully described by just the mean vector μ_k and the covariance matrix Σ_k. The I-space is ℝⁿ × 𝒮ⁿ (means × positive-definite matrices) — infinite-dimensional X, yet finite-dimensional I-space. This is the Kalman filter.

Chapter 6: Kalman Filter as I-State Computation

The Kalman filter is not a mystery — it is exactly the Bayesian belief update for linear Gaussian systems, executed in closed form. Chapter 11 presents it as a special case of the I-state framework. This grounds the Kalman filter in planning theory and clarifies what assumptions it makes.

The linear Gaussian model

State transition: x_k+1 = A · x_k + B · u_k + w_k, where w_k ~ 𝒩(0, Q). Observation: y_k = C · x_k + v_k, where v_k ~ 𝒩(0, R). Here A is the state transition matrix, B maps control input to state, C maps state to observation space, Q is process noise covariance, and R is measurement noise covariance. Both noise terms are zero-mean Gaussians — hence "linear Gaussian."

The two-step update — as I-state transitions

Predict step (τ_motion): Given I-state (μ_k, Σ_k) and action u_k, compute the predicted I-state after motion but before the new observation:

Update step (τ_sensor): Incorporate new observation y_k+1 to compute the posterior I-state:

Here K is the Kalman gain — a trust slider between what the motion model predicts and what the sensor measures. K near I (identity) means "trust the sensor"; K near 0 means "trust the prediction." K is determined automatically by the ratio of prediction uncertainty Σ⁻ to measurement uncertainty R.

python
import numpy as np

def kalman_predict(mu, Sigma, A, B, u, Q):
    mu_pred   = A @ mu + B @ u
    Sig_pred  = A @ Sigma @ A.T + Q
    return mu_pred, Sig_pred

def kalman_update(mu_pred, Sig_pred, y, C, R):
    S = C @ Sig_pred @ C.T + R          # innovation covariance
    K = Sig_pred @ C.T @ np.linalg.inv(S)  # Kalman gain
    innov = y - C @ mu_pred             # observation residual
    mu_post   = mu_pred + K @ innov
    Sig_post  = (np.eye(len(mu_pred)) - K @ C) @ Sig_pred
    return mu_post, Sig_post

# 1D example: tracking a robot moving at constant velocity
A = np.array([[1, 1], [0, 1]])  # position, velocity
B = np.zeros((2, 1))
C = np.array([[1, 0]])           # observe position only
Q = np.diag([0.1, 0.01])         # small process noise
R = np.array([[1.0]])              # measurement noise

mu = np.array([0.0, 1.0])         # initial: pos=0, vel=1
Sigma = np.eye(2) * 0.5

for k in range(10):
    mu, Sigma = kalman_predict(mu, Sigma, A, B, np.zeros(1), Q)
    y_obs = np.array([k + 1.0 + np.random.randn() * 1.0])
    mu, Sigma = kalman_update(mu, Sigma, y_obs, C, R)
    print(ff"k={k}: pos estimate={mu[0]:.2f} ± {np.sqrt(Sigma[0,0]):.2f}")

Chapter 7: Computing Probabilistic I-States

For most real systems — nonlinear dynamics, non-Gaussian noise, discrete mixtures — the Kalman filter doesn't apply. Chapter 11 surveys three families of algorithms for computing belief states in harder settings.

Grid-based belief approximation

Discretize the continuous state space X into a grid of cells. Each cell holds a probability mass value. The belief update runs exactly as in the discrete hallway: multiply by sensor likelihood, renormalize. This is simple and correct, but scales poorly: a 2D grid at 0.1m resolution covering a 10m×10m room needs 10,000 cells. A 3D space with heading needs millions. Grid methods are practical only for low-dimensional spaces (≤ 3D).

Particle filters — Monte Carlo belief

A particle filter represents the belief as a set of M weighted samples (particles): {(x⁽ⁱ⁾, w⁽ⁱ⁾)}_i=1..M. Each particle x⁽ⁱ⁾ is a hypothesis about the current state; its weight w⁽ⁱ⁾ is proportional to how well it explains the observations. The algorithm:

The set of particles approximates the belief: b_k(x) ≈ (1/M) ∑_i δ(x - x⁽ⁱ⁾_k) after resampling. As M → ∞, the approximation converges. In practice, M=500-2000 particles is sufficient for many problems. Particle filters handle nonlinear motion and sensor models effortlessly.

The POMDP value function is piecewise linear and convex over beliefs

When solving a Partially Observable MDP (POMDP) — choosing actions optimally given a belief state — the value function V(b) maps belief states to expected future reward. LaValle (pp. 599-607) establishes a key structural result: for finite-horizon POMDPs with finite X, U, Y, the value function at each time step is piecewise linear and convex (PWLC) over the belief simplex Β. This means V(b) = max_i (α_i · b) for a set of α-vectors, one per "policy tree." The complexity grows exponentially in horizon — solving POMDPs exactly is PSPACE-hard — but approximate methods (PBVI, SARSOP, POMCP) exploit this structure.

python
import numpy as np

class ParticleFilter:
    def __init__(self, n_particles, state_dim, motion_fn, sensor_fn):
        self.M = n_particles
        # Initialize particles uniformly in state space
        self.particles = np.random.uniform(0, 1, (n_particles, state_dim))
        self.weights   = np.ones(n_particles) / n_particles
        self.motion_fn = motion_fn   # samples x' ~ P(x'|x,u)
        self.sensor_fn = sensor_fn   # returns P(y|x)

    def update(self, u, y):
        # 1. Propagate through motion model
        self.particles = np.array([
            self.motion_fn(x, u) for x in self.particles
        ])
        # 2. Compute weights from sensor likelihood
        self.weights = np.array([
            self.sensor_fn(y, x) for x in self.particles
        ])
        self.weights += 1e-300         # avoid zero weights
        self.weights /= self.weights.sum()  # normalize
        # 3. Resample (systematic resampling)
        indices = np.random.choice(self.M, self.M, p=self.weights)
        self.particles = self.particles[indices]
        self.weights = np.ones(self.M) / self.M

    def mean(self):
        return self.particles.mean(axis=0)

Chapter 8: Game-Theoretic Information Spaces

Everything so far assumed one decision-maker (the robot) facing a stochastic but non-adversarial environment. Chapter 11 extends the I-state framework to multi-player games — situations where other rational agents are acting simultaneously and their actions affect you.

The two-player zero-sum case

Consider a pursuit-evasion game: a pursuer (robot) tries to catch an evader. Both move simultaneously. Neither can see the other's true state. The pursuer has a belief about where the evader is; the evader has a belief about where the pursuer is. Each player's I-state must model not just the environment but the other player's possible actions and beliefs.

For a two-player zero-sum game with partial observability, the I-state for player 1 is η_1,k = (y_1,0, u_1,0, ..., y_1,k) — player 1's own observation-action history. Player 2 has η_2,k separately. The minimax value function over belief states generalizes the POMDP value function, but now with an outer max (player 1 maximizes) and inner min (player 2 minimizes).

Nondeterministic game I-states

When probability models are unavailable, nondeterministic game I-states are sets. The pursuer maintains l_1,k ⊆ X — the set of states the evader might be in, given what the pursuer has observed. The evader maintains l_2,k ⊆ X for the pursuer. Planning becomes a minimax search over these sets: the pursuer picks an action to shrink its uncertainty about the evader, while the evader acts to maximize its uncertainty from the pursuer's perspective.

Visibility-based pursuit evasion

LaValle's canonical example (pp. 624-629) is pursuit-evasion in a polygonal environment. The pursuer (a robot with a limited field of view) tries to guarantee that the evader is visible. The I-state is the contamination region — the set of locations where an evader could be hiding without the pursuer having seen it. The pursuer's goal: shrink the contamination region to empty. This is equivalent to a coverage problem on the nondeterministic I-space.

Chapter 9: Connections — Where to Go Next

Chapter 11 establishes the theoretical framework for planning under partial observability. The I-state is the unifying concept. But the framework is deliberately general — it doesn't prescribe how to solve the resulting I-space planning problems. That is the subject of later chapters in LaValle and of a large research literature.

What Chapter 11 built

Known limitations of the Chapter 11 framework

The pure Bayesian approach requires a model: P(x'|x,u) and P(y|x). If the model is wrong — and it always is, to some degree — the belief can diverge from reality without any signal. This is the model mismatch problem. Robust methods (nondeterministic I-states, worst-case planning) guard against this, at the cost of being overly conservative. Active research is on data-driven models that learn P(x'|x,u) and P(y|x) from experience.

Computing the optimal policy in the POMDP I-space is PSPACE-hard in general. The exact algorithms (enumeration of α-vectors) are exponential in horizon. Approximation algorithms like PBVI, SARSOP, and Monte Carlo tree search (POMCP) make large-scale POMDPs tractable — but Chapter 11's exact framework is the foundation they build on.

Comparison of I-state representations

Related micro-lessons

The I-state framework connects directly to several estimation and planning lessons:

• Bayes Filter — the core Bayesian belief update algorithm that powers the discrete I-state transition τ.
• Kalman Filter — the exact Gaussian I-state computation for linear systems. Chapter 6 of this lesson is a preview.
• EKF / UKF — extensions of the Kalman filter I-state to nonlinear systems via linearization (EKF) or sigma-point propagation (UKF).
• POMDP — building a policy directly over the belief I-space using the value function structure hinted at in Chapter 7.
• Classical SLAM — simultaneous localization and mapping is a POMDP where the state includes the map; the belief is over (robot pose, map).

"The information space is not a computational convenience. It is the correct space in which to pose the problem."
— Steven M. LaValle, Planning Algorithms, §11.1