In previous lessons on belief-space and chance-constrained planning, we assumed that belief dynamics were available but did not fully formalize the decision-making problem. POMDPs provide such a formalism when the robot's state \( s_t \in \mathcal{S} \) is not directly observable, but the robot receives observations \( o_t \in \mathcal{O} \) through noisy sensors and executes actions \( a_t \in \mathcal{A} \) that are themselves subject to uncertainty.

Intuitively, a POMDP planner maintains a belief distribution \( b_t \) over possible states and chooses actions that trade off information gathering (reducing uncertainty) and task performance (e.g., reaching a goal, avoiding collision). This is crucial for tasks like:

• Mobile robot navigation with imperfect localization.
• Manipulation in clutter with occlusions and partial object poses.
• Search tasks (e.g., locating an object in a shelf) under sensor noise.

flowchart TD
  S["Hidden state s_t (world, robot)"]
  O["Noisy observation o_t"]
  B["Belief b_t (distribution over states)"]
  P["Planner on beliefs"]
  A["Action a_t"]
  W["Physical robot + environment"]

  S --> O
  B --> P
  O --> B
  P --> A
  A --> W
  W --> S
  W --> O

  classDef belief fill:#eef,stroke:#333,stroke-width:1px;
  class B belief;
        

The core idea is that the planner never sees \( s_t \) directly; it reasons only through the belief \( b_t \) and the known probabilistic models of actions and observations.

A discounted POMDP is a tuple \( \mathcal{M} = (\mathcal{S}, \mathcal{A}, \mathcal{O}, T, Z, R, \gamma) \) where:

• \( \mathcal{S} \): finite or continuous state space (e.g., robot pose, object poses).
• \( \mathcal{A} \): action space (motion commands, grasp attempts, etc.).
• \( \mathcal{O} \): observation space (sensor outputs).
• \( T(s' \mid s, a) \): state transition kernel \( \mathbb{P}(s_{t+1} = s' \mid s_t = s, a_t = a) \).
• \( Z(o \mid s', a) \): observation kernel \( \mathbb{P}(o_{t+1} = o \mid s_{t+1} = s', a_t = a) \).
• \( R(s, a) \): immediate reward (e.g., goal proximity, collision penalty).
• \( \gamma \): discount factor with \( 0 \le \gamma < 1 \).

A (history-dependent) policy selects actions based on the history \( h_t = (o_0, a_0, \dots, o_{t-1}, a_{t-1}, o_t) \). The return of a policy \( \pi \) starting from an initial belief \( b_0 \) is

\[ J^{\pi}(b_0) = \mathbb{E}^{\pi}\!\left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \;\middle|\; b_0 \right]. \]

The objective is to find an optimal policy \( \pi^* \) that maximizes \( J^{\pi}(b_0) \) for all initial beliefs of interest. Because the state is hidden, naively optimizing over all histories is intractable. The crucial insight is that we can compress the history into a belief state.

A belief is a probability distribution over states: \( b_t(s) = \mathbb{P}(s_t = s \mid h_t) \). For discrete \( \mathcal{S} \), we view \( b_t \in \Delta(\mathcal{S}) \), the probability simplex. After executing action \( a_t \) and receiving observation \( o_{t+1} \), the belief is updated via the Bayes filter:

\[ \begin{aligned} \tilde{b}_{t+1}(s') &= \sum_{s \in \mathcal{S}} T(s' \mid s, a_t)\, b_t(s), \\ b_{t+1}(s') &= \eta\, Z(o_{t+1} \mid s', a_t)\, \tilde{b}_{t+1}(s') \end{aligned} \]

where \( \eta \) is a normalizing constant chosen so that \( \sum_{s'} b_{t+1}(s') = 1 \). In compact notation:

\[ b_{t+1} = \tau(b_t, a_t, o_{t+1}), \]

where \( \tau \) is the belief update operator determined by \( T \) and \( Z \).

Belief-state MDP. Define:

• State space: beliefs \( \mathcal{B} = \Delta(\mathcal{S}) \).
• Actions: same \( \mathcal{A} \).
• Reward: \( r(b, a) = \sum_{s \in \mathcal{S}} b(s)\, R(s, a) \).
• Stochastic transition: \( b' = \tau(b, a, o) \) with probability \( \mathbb{P}(o \mid b, a) \).

Then the POMDP is equivalent to a fully observable MDP on beliefs. The next theorem formalizes this.

Theorem (Belief is a sufficient statistic). For any policy and any time \( t \), \( \mathbb{P}(s_{t+1}, o_{t+1} \mid h_t, a_t) = \mathbb{P}(s_{t+1}, o_{t+1} \mid b_t, a_t) \). Consequently, the process \( (b_t)_{t \ge 0} \) is Markov.

Sketch of proof. Using the definition of the belief, for any state \( s' \) and observation \( o' \):

\[ \begin{aligned} \mathbb{P}(s_{t+1} = s', o_{t+1} = o' \mid h_t, a_t) &= \sum_{s \in \mathcal{S}} \mathbb{P}(s_{t+1} = s', o_{t+1} = o' \mid s_t = s, h_t, a_t) \,\mathbb{P}(s_t = s \mid h_t) \\ &= \sum_{s \in \mathcal{S}} T(s' \mid s, a_t)\, Z(o' \mid s', a_t)\, b_t(s), \end{aligned} \]

which depends on the history only through \( b_t \). Thus belief is a sufficient statistic for control.

flowchart TD
  H["History h_t"] --> B["Belief b_t"]
  B --> A["Choose action a_t"]
  A --> PRED["Predictive belief (prediction step)"]
  PRED --> O["Observe o_(t+1)"]
  O --> UPD["Update belief b_(t+1) = tau(b_t, a_t, o_(t+1))"]
  UPD --> LOOP["Next decision step"]

  classDef bel fill:#eef,stroke:#333,stroke-width:1px;
  class B,UPD,PRED bel;
        

For a fixed policy \( \pi \), the value function on beliefs is

\[ V^{\pi}(b) = \mathbb{E}^{\pi}\!\left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \;\middle|\; b_0 = b \right]. \]

The optimal value function satisfies the Bellman equation

\[ V^*(b) = \max_{a \in \mathcal{A}} \left( r(b, a) + \gamma \sum_{o \in \mathcal{O}} \mathbb{P}(o \mid b, a)\, V^*\big(\tau(b, a, o)\big) \right). \]

For finite \( \mathcal{S} \), \( \mathcal{A} \), and \( \mathcal{O} \), a classical result (Sondik, Smallwood) states that \( V^* \) is piecewise linear and convex over beliefs:

\[ V^*(b) = \max_{\alpha \in \Gamma} \alpha^{\top} b, \]

where \( \Gamma \subset \mathbb{R}^{|\mathcal{S}|} \) is a finite set of so-called alpha-vectors. Each alpha-vector corresponds to a conditional plan (a policy tree) of finite depth, and POMDP value iteration repeatedly applies a backup operator that produces improved alpha-vectors from the previous set.

Exact solutions are computationally expensive in general, and robotics applications tend to rely on approximations (e.g., point-based value iteration, QMDP, finite horizon with receding horizon control), but the alpha-vector structure underlies many of these approximations.

Consider a robot moving along a short corridor with two possible discrete positions: \( \mathcal{S} = \{0, 1\} \) (near the door, far from the door). The robot does not know exactly where it is but has a binary range sensor that returns observation \( o \in \{\text{"door"}, \text{"no-door"}\} \).

Actions. The robot has two actions:

• \( a = \text{"stay"} \): do not move.
• \( a = \text{"step"} \): move one cell towards larger index.

Transition model. Suppose motion is noisy:

\[ T(s' \mid s, \text{"step"}) = \begin{bmatrix} T(0 \mid 0, \text{"step"}) & T(0 \mid 1, \text{"step"}) \\ T(1 \mid 0, \text{"step"}) & T(1 \mid 1, \text{"step"}) \end{bmatrix} = \begin{bmatrix} 0.1 & 0 \\ 0.9 & 1 \end{bmatrix}. \]

That is, from position 0, stepping moves to 1 with probability 0.9 (and fails with probability 0.1); from position 1, stepping leaves the robot at 1. For the "stay" action, let

\[ T(s' \mid s, \text{"stay"}) = \begin{bmatrix} 0.9 & 0 \\ 0.1 & 1 \end{bmatrix}, \]

representing a small drift from 0 to 1 due to slippage.

Observation model. Assume the door is at position 1:

\[ Z(\text{"door"} \mid 1, a) = 0.9, \quad Z(\text{"door"} \mid 0, a) = 0.2 \]

for both actions. Thus the sensor is informative but noisy: it occasionally detects a door when there is none and misses the door some of the time.

Belief update example. Suppose the prior belief is uniform:

\[ b_0(0) = 0.5, \quad b_0(1) = 0.5. \]

The robot takes action \( a_0 = \text{"step"} \) and then observes \( o_1 = \text{"door"} \).

1. Prediction:

   \[ \begin{aligned} \tilde{b}_1(0) &= T(0 \mid 0, \text{"step"})\,b_0(0) + T(0 \mid 1, \text{"step"})\,b_0(1) = 0.1 \cdot 0.5 + 0 \cdot 0.5 = 0.05, \\ \tilde{b}_1(1) &= T(1 \mid 0, \text{"step"})\,b_0(0) + T(1 \mid 1, \text{"step"})\,b_0(1) = 0.9 \cdot 0.5 + 1 \cdot 0.5 = 0.95. \end{aligned} \]

2. Update using observation "door":

   \[ \begin{aligned} b_1(0) &\propto Z(\text{"door"} \mid 0, \text{"step"})\,\tilde{b}_1(0) = 0.2 \cdot 0.05 = 0.01, \\ b_1(1) &\propto Z(\text{"door"} \mid 1, \text{"step"})\,\tilde{b}_1(1) = 0.9 \cdot 0.95 = 0.855. \end{aligned} \]

   Normalizing gives \( b_1(0) \approx 0.0115 \) and \( b_1(1) \approx 0.9885 \), so the robot becomes highly confident that it is at position 1 (at the door).

A POMDP planner on this toy problem would balance taking informative actions to reduce uncertainty with moving towards the goal region.

As another small example, consider a manipulator searching for an object on a three-cell shelf. Let \( \mathcal{S} = \{1, 2, 3, \text{absent}\} \) encode the object's true location, and let the robot's configuration be controlled so that it can direct its camera or end-effector to any cell.

Actions.

• \( a_i = \text{"look at cell } i\text{"} \), \( i \in \{1,2,3\} \).
• \( a_{\text{grasp}, i} = \text{"grasp at cell } i\text{"} \).

Observations.

• \( o \in \{\text{"see"}, \text{"no-see"}, \text{"grasp-success"}, \text{"grasp-fail"}\} \).

Observation model for look actions. For \( a_i \):

\[ Z(\text{"see"} \mid s = i, a_i) = p_{\text{det}}, \quad Z(\text{"see"} \mid s \neq i, a_i) = p_{\text{fp}}. \]

Typically \( p_{\text{det}} \) is high and \( p_{\text{fp}} \) is small. For grasp actions, \( Z(\text{"grasp-success"} \mid s = i, a_{\text{grasp}, i}) \) is high and nearly zero otherwise.

A reasonable reward structure penalizes time and failures but gives a large positive reward for a successful grasp. The POMDP then encodes a closed-loop search strategy that might, for example, look at the most likely cell, then either grasp or continue searching depending on the observations.

We now implement the 1D localization POMDP in Python. The following code focuses on the belief update and a small finite-horizon planner. In a robotics system, this logic would be integrated with rospy (ROS Python client) to obtain observations (e.g., from a range sensor) and to send velocity or position commands.

import numpy as np

# Discrete states: 0 = near door, 1 = far from door
S = [0, 1]

# Actions and observations
A = ["stay", "step"]
O = ["door", "no-door"]

# Transition matrices T[a][s, s_prime]
T = {
    "stay": np.array([
        [0.9, 0.0],
        [0.1, 1.0]
    ]),
    "step": np.array([
        [0.1, 0.0],
        [0.9, 1.0]
    ])
}

# Observation model as vectors Z[o][s_prime]
Z = {
    "door": np.array([0.2, 0.9]),
    "no-door": np.array([0.8, 0.1])
}

# Reward R[s, a]
R = {
    "stay": np.array([-0.05, -0.05]),   # small time penalty
    "step": np.array([-0.5,  +1.0])     # costly motion, reward for being at door
}

gamma = 0.95

def normalize(p):
    total = float(np.sum(p))
    if total == 0.0:
        return np.ones_like(p) / float(len(p))
    return p / total

def predict_belief(b, a):
    # b is a length-2 numpy array
    # T[a] has shape (2, 2) with rows indexed by s and columns by s_prime
    # We want p(s_prime) = sum_s T[s, s_prime] * b[s]
    return T[a].T @ b

def belief_update(b, a, o):
    b_pred = predict_belief(b, a)
    b_post = Z[o] * b_pred
    return normalize(b_post)

def expected_reward(b, a):
    return float(np.dot(b, R[a]))

def observation_prob(b, a, o):
    b_pred = predict_belief(b, a)
    return float(np.dot(b_pred, Z[o]))

def value(b, depth):
    """
    Simple finite-horizon value function via recursion.
    depth = remaining planning steps.
    """
    if depth == 0:
        return 0.0
    q_values = []
    for a in A:
        r = expected_reward(b, a)
        future = 0.0
        b_pred = predict_belief(b, a)
        for o in O:
            # probability of observation o
            p_o = float(np.dot(b_pred, Z[o]))
            if p_o == 0.0:
                continue
            # posterior given o
            b_post = normalize(Z[o] * b_pred)
            future += p_o * value(b_post, depth - 1)
        q_values.append(r + gamma * future)
    return float(np.max(q_values))

def greedy_action(b, depth):
    """
    One-step lookahead using value() for depth - 1 steps in the future.
    """
    best_a = None
    best_q = None
    for a in A:
        r = expected_reward(b, a)
        future = 0.0
        b_pred = predict_belief(b, a)
        for o in O:
            p_o = float(np.dot(b_pred, Z[o]))
            if p_o == 0.0:
                continue
            b_post = normalize(Z[o] * b_pred)
            future += p_o * value(b_post, depth - 1)
        q = r + gamma * future
        if best_q is None:
            best_q = q
            best_a = a
        else:
            best_q = max(best_q, q)
            if best_q == q:
                best_a = a
    return best_a

if __name__ == "__main__":
    # Start from uniform belief
    b = np.array([0.5, 0.5])
    horizon = 3
    a_star = greedy_action(b, horizon)
    print("Greedy action at initial belief:", a_star)
      

This is a minimal pedagogical implementation. For more complex robotic systems, POMDP algorithms (e.g., point-based solvers) are typically written in Python and connected via ROS to real or simulated robots (Gazebo, Isaac Sim, etc.).

In C++, POMDP reasoning often appears in higher-level planners built on top of libraries like OMPL (Open Motion Planning Library) and robot middleware such as ROS2. Below is a lightweight belief-update class for the 1D example. The code can be called from a ROS node that subscribes to sensor topics and publishes motion commands.

#include <array>
#include <string>
#include <unordered_map>
#include <iostream>

class OneDPOMDP {
public:
    using Vec2 = std::array<double, 2>;

    OneDPOMDP() {
        // Transition matrices (row: s, column: s_prime)
        T_["stay"] = { { {0.9, 0.0},
                       {0.1, 1.0} } };
        T_["step"] = { { {0.1, 0.0},
                       {0.9, 1.0} } };

        // Observation likelihoods Z[o][s_prime]
        Z_["door"]    = { {0.2, 0.9} };
        Z_["no-door"] = { {0.8, 0.1} };

        // Start with uniform belief
        belief_ = { {0.5, 0.5} };
    }

    void applyActionAndObservation(const std::string& a,
                                   const std::string& o) {
        Vec2 b_pred = predict(belief_, a);
        Vec2 b_post = { {
            Z_[o][0] * b_pred[0],
            Z_[o][1] * b_pred[1]
        } };
        normalize(b_post);
        belief_ = b_post;
    }

    const Vec2& belief() const {
        return belief_;
    }

private:
    // T_[a][s][s_prime]
    std::unordered_map<std::string, std::array<std::array<double, 2>, 2>> T_;
    // Z_[o][s_prime]
    std::unordered_map<std::string, Vec2> Z_;
    Vec2 belief_;

    static Vec2 predict(const Vec2& b, const std::string& a) {
        Vec2 out = ;
        // out[s_prime] = sum_s T[a][s][s_prime] * b[s]
        for (int s = 0; s < 2; ++s) {
            for (int sp = 0; sp < 2; ++sp) {
                out[sp] += T_[a][s][sp] * b[s];
            }
        }
        return out;
    }

    static void normalize(Vec2& v) {
        double sum = v[0] + v[1];
        if (sum == 0.0) {
            v[0] = 0.5;
            v[1] = 0.5;
        } else {
            v[0] /= sum;
            v[1] /= sum;
        }
    }
};

int main() {
    OneDPOMDP pomdp;
    pomdp.applyActionAndObservation("step", "door");
    auto b = pomdp.belief();
    std::cout << "Belief after step+door: "
              << b[0] << ", " << b[1] << std::endl;
    return 0;
}
      

In a ROS2 setup, this class could be embedded inside a node that interacts with nav2 or OMPL-based planners, where the high-level POMDP logic chooses waypoints or high-level maneuvers, while lower-level controllers handle continuous dynamics.

Java is less common in robotics planning than C++ and Python, but it can be used in conjunction with rosjava to build higher-level decision-making components. Below is a small Java class implementing belief updates for the same 1D POMDP.

public class OneDPOMDP {
    // belief[0] = P(state 0), belief[1] = P(state 1)
    private double[] belief = new double[]{0.5, 0.5};

    // Transition matrices T[action][s][s_prime]
    private final double[][][] T = new double[][][]{
        {   // "stay"
            {0.9, 0.0},
            {0.1, 1.0}
        },
        {   // "step"
            {0.1, 0.0},
            {0.9, 1.0}
        }
    };

    // Observation model Z[o_index][s_prime]
    private final double[][] Z = new double[][]{
        {0.2, 0.9},  // "door"
        {0.8, 0.1}   // "no-door"
    };

    private int actionIndex(String a) {
        if (a.equals("stay")) return 0;
        if (a.equals("step")) return 1;
        throw new IllegalArgumentException("Unknown action");
    }

    private int obsIndex(String o) {
        if (o.equals("door")) return 0;
        if (o.equals("no-door")) return 1;
        throw new IllegalArgumentException("Unknown observation");
    }

    private double[] predict(double[] b, int aIdx) {
        double[] out = new double[]{0.0, 0.0};
        for (int s = 0; s < 2; ++s) {
            for (int sp = 0; sp < 2; ++sp) {
                out[sp] += T[aIdx][s][sp] * b[s];
            }
        }
        return out;
    }

    private void normalize(double[] v) {
        double sum = v[0] + v[1];
        if (sum == 0.0) {
            v[0] = 0.5;
            v[1] = 0.5;
        } else {
            v[0] /= sum;
            v[1] /= sum;
        }
    }

    public void applyActionAndObservation(String a, String o) {
        int aIdx = actionIndex(a);
        int oIdx = obsIndex(o);
        double[] bPred = predict(belief, aIdx);
        double[] bPost = new double[2];
        bPost[0] = Z[oIdx][0] * bPred[0];
        bPost[1] = Z[oIdx][1] * bPred[1];
        normalize(bPost);
        belief = bPost;
    }

    public double[] getBelief() {
        return belief;
    }

    public static void main(String[] args) {
        OneDPOMDP pomdp = new OneDPOMDP();
        pomdp.applyActionAndObservation("step", "door");
        double[] b = pomdp.getBelief();
        System.out.println("Belief: " + b[0] + ", " + b[1]);
    }
}
      

In a practical system, this Java component could subscribe (via rosjava) to topics encoding observations and publish high-level actions to other nodes implementing motion primitives.

Matlab is widely used in control and robotics (e.g., via the Robotics System Toolbox). Below is a simple script implementing belief updates and a short finite-horizon evaluation. This code can be wrapped in a MATLAB Function block inside Simulink to form part of a decision-making subsystem.

function pomdp_demo()
    % States: 0 (near door), 1 (far)
    % Belief vector b
    b = [0.5; 0.5];

    % Transition matrices T{a}
    T_stay = [0.9, 0.0;
              0.1, 1.0];
    T_step = [0.1, 0.0;
              0.9, 1.0];

    % Observation vectors Z{o}
    Z_door    = [0.2; 0.9];
    Z_nodoor  = [0.8; 0.1];

    gamma = 0.95;
    horizon = 3;

    % Example: take action "step" and observe "door"
    b = belief_update(b, T_step, Z_door);

    fprintf('Belief after step + door: [%f, %f]\n', b(1), b(2));

    % Evaluate a trivial one-step policy for illustration
    V = value_horizon(b, horizon, T_stay, T_step, Z_door, Z_nodoor, gamma);
    fprintf('Approximate value at belief: %f\n', V);
end

function b_new = belief_update(b, T, Z)
    % Prediction
    b_pred = T' * b;
    % Update
    b_post = Z .* b_pred;
    s = sum(b_post);
    if s == 0
        b_new = [0.5; 0.5];
    else
        b_new = b_post / s;
    end
end

function V = value_horizon(b, depth, T_stay, T_step, Z_door, Z_nodoor, gamma)
    if depth == 0
        V = 0.0;
        return;
    end
    % Rewards
    R_stay = [-0.05; -0.05];
    R_step = [-0.5; +1.0];

    % Actions: 1 = stay, 2 = step
    V_actions = zeros(2, 1);

    % "stay"
    a = 1;
    T = T_stay;
    r = b' * R_stay;
    V_actions(a) = r + gamma * expected_future(b, T, Z_door, Z_nodoor, depth - 1, ...
                                               T_stay, T_step, gamma);

    % "step"
    a = 2;
    T = T_step;
    r = b' * R_step;
    V_actions(a) = r + gamma * expected_future(b, T, Z_door, Z_nodoor, depth - 1, ...
                                               T_stay, T_step, gamma);

    V = max(V_actions);
end

function fut = expected_future(b, T, Z_door, Z_nodoor, depth, T_stay, T_step, gamma)
    % Compute predictive belief
    b_pred = T' * b;

    % Probabilities of each observation
    p_door   = (b_pred' * Z_door);
    p_nodoor = (b_pred' * Z_nodoor);

    fut = 0.0;
    if p_door > 0
        b_post = belief_update(b, T, Z_door);
        fut = fut + p_door * value_horizon(b_post, depth, T_stay, T_step, ...
                                           Z_door, Z_nodoor, gamma);
    end
    if p_nodoor > 0
        b_post = belief_update(b, T, Z_nodoor);
        fut = fut + p_nodoor * value_horizon(b_post, depth, T_stay, T_step, ...
                                             Z_door, Z_nodoor, gamma);
    end
end
      

In Simulink, belief_update and value_horizon can be called from a MATLAB Function block that receives inputs (current belief, action, and observation) and outputs the updated belief and recommended action.

Mathematica can be used for symbolic and numerical analysis of small POMDPs, which is useful for verifying theoretical properties (e.g., convexity of the value function) on toy robotics problems.

(* States s = 0, 1 *)
states = {0, 1};

(* Transition matrices T[a][[s_index, sprime_index]] *)
T["stay"] = { {0.9, 0.0},
             {0.1, 1.0} };
T["step"] = { {0.1, 0.0},
             {0.9, 1.0} };

(* Observation models Z[o][[sprime_index]] *)
Z["door"]    = {0.2, 0.9};
Z["no-door"] = {0.8, 0.1};

R["stay"] = {-0.05, -0.05};
R["step"] = {-0.5, 1.0};

gamma = 0.95;

normalize[v_List] := Module[{s = Total[v]},
  If[s == 0, {1/2, 1/2}, v/s]
];

predict[b_List, a_String] :=
  Transpose[T[a]].b;

beliefUpdate[b_List, a_String, o_String] :=
 Module[{bPred, bPost},
  bPred = predict[b, a];
  bPost = Z[o]*bPred;
  normalize[bPost]
 ];

expectedReward[b_List, a_String] :=
  b.R[a];

obsProb[b_List, a_String, o_String] :=
 Module[{bPred},
  bPred = predict[b, a];
  bPred.Z[o]
 ];

Clear[value];
value[b_List, depth_Integer] /; depth == 0 := 0.0;
value[b_List, depth_Integer] :=
 Module[{qs},
  qs = Table[
    Module[{a = act, r, fut, bPred, pDoor, pNo, bDoor, bNo},
      r = expectedReward[b, a];
      bPred = predict[b, a];
      pDoor = bPred.Z["door"];
      pNo   = bPred.Z["no-door"];
      fut = 0.0;
      If[pDoor > 0,
        bDoor = normalize[Z["door"]*bPred];
        fut += pDoor*value[bDoor, depth - 1];
      ];
      If[pNo > 0,
        bNo = normalize[Z["no-door"]*bPred];
        fut += pNo*value[bNo, depth - 1];
      ];
      r + gamma*fut
    ],
    {act, {"stay", "step"}}
  ];
  Max[qs]
 ];

(* Example: value of uniform belief at horizon 3 *)
b0 = {1/2, 1/2};
value[b0, 3]
      

For didactic purposes, one can discretize the belief interval \( b(0) \in [0, 1] \) and numerically verify that the resulting value function over that grid is convex and equal to the upper envelope of finitely many linear segments.

Problem 1 (Normalization of Belief Update). Show that the Bayes filter update \( b_{t+1}(s') = \eta\, Z(o_{t+1} \mid s', a_t) \sum_{s} T(s' \mid s, a_t) b_t(s) \) defines a valid probability distribution, that is \( \sum_{s'} b_{t+1}(s') = 1 \).

Solution. Let \( \tilde{b}_{t+1}(s') = Z(o_{t+1} \mid s', a_t) \sum_{s} T(s' \mid s, a_t) b_t(s) \). Define \( \eta = \left( \sum_{s'} \tilde{b}_{t+1}(s') \right)^{-1} \) when the denominator is nonzero. Then

\[ \sum_{s'} b_{t+1}(s') = \sum_{s'} \eta\, \tilde{b}_{t+1}(s') = \eta \sum_{s'} \tilde{b}_{t+1}(s') = \eta \left( \sum_{s'} \tilde{b}_{t+1}(s') \right) = 1. \]

Nonnegativity follows from nonnegativity of \( T \) and \( Z \), so \( b_{t+1} \) is a valid probability distribution.

Problem 2 (Belief-State Markov Property). Starting from the definition of the belief, derive explicitly that \( \mathbb{P}(b_{t+1} \mid h_t, a_t) = \mathbb{P}(b_{t+1} \mid b_t, a_t) \).

Solution. The belief \( b_{t+1} \) is a deterministic function \( \tau(b_t, a_t, o_{t+1}) \) of the previous belief, current action, and new observation. Hence

\[ \mathbb{P}(b_{t+1} \mid h_t, a_t) = \sum_{o_{t+1}} \mathbb{P}\big(b_{t+1} \mid h_t, a_t, o_{t+1}\big)\, \mathbb{P}(o_{t+1} \mid h_t, a_t). \]

The first factor is one when \( b_{t+1} = \tau(b_t, a_t, o_{t+1}) \) and zero otherwise, because the update is deterministic. The second factor depends on the history only through \( b_t \), as shown in Section 3. Therefore,

\[ \mathbb{P}(b_{t+1} \mid h_t, a_t) = \sum_{o_{t+1}} \mathbb{P}\big(b_{t+1} \mid b_t, a_t, o_{t+1}\big)\, \mathbb{P}(o_{t+1} \mid b_t, a_t) = \mathbb{P}(b_{t+1} \mid b_t, a_t), \]

confirming the Markov property at the belief level.

Problem 3 (Reduction to MDP under Full Observability). Suppose the observation kernel is \( Z(o \mid s, a) = \mathbb{I}[o = s] \), i.e., the robot observes the exact state at each step. Show that the POMDP reduces to an MDP in the usual sense.

Solution. With perfect observations, after the first observation the belief is a Dirac distribution on the current state: \( b_t(s) = \mathbb{I}[s = s_t] \). The Bayes filter always maps a Dirac belief to another Dirac belief because the observation deterministically identifies the next state. Consequently the belief process and the state process are isomorphic, and the value function over beliefs is equal to the standard MDP value function \( V(s) = \max_{a} \mathbb{E}[\sum_{t} \gamma^t R(s_t, a_t) \mid s_0 = s] \). The POMDP Bellman equation specializes to the usual MDP Bellman equation.

Problem 4 (One-Step Lookahead in the 1D Example). For the 1D localization POMDP, consider the initial belief \( b_0(0) = b_0(1) = 0.5 \). Assume the rewards defined earlier. Compute the one-step expected return of actions \( \text{"stay"} \) and \( \text{"step"} \) under horizon one (i.e., immediate reward only), and determine which action is preferred.

Solution. The one-step value at horizon one is simply \( V_1(b) = \max_a r(b, a) \) with \( r(b, a) = \sum_s b(s) R(s, a) \).

\[ \begin{aligned} r(b_0, \text{"stay"}) &= 0.5 \cdot (-0.05) + 0.5 \cdot (-0.05) = -0.05, \\ r(b_0, \text{"step"}) &= 0.5 \cdot (-0.5) + 0.5 \cdot 1.0 = 0.25. \end{aligned} \]

Hence at horizon one, \( \text{"step"} \) is preferred. For longer horizons, this may change because repeated stepping could incur larger cumulative penalties, illustrating the role of discounting and planning depth.

Problem 5 (Piecewise Linearity of Finite-Horizon Value). Show that the finite-horizon optimal value function \( V_H(b) \) of a POMDP with finite state and action spaces is piecewise linear and convex by induction on the horizon length \( H \).

Solution (sketch). For \( H = 0 \), \( V_0(b) \equiv 0 \) is linear and convex. Suppose \( V_H \) is piecewise linear and convex, so \( V_H(b) = \max_{\alpha \in \Gamma_H} \alpha^{\top} b \). For horizon \( H+1 \), we have

\[ V_{H+1}(b) = \max_{a} \left( r(b, a) + \gamma \sum_{o} \mathbb{P}(o \mid b, a)\, V_H\big(\tau(b, a, o)\big) \right). \]

Since \( V_H \) is a maximum of linear functions and beliefs map linearly (up to normalization) under \( \tau \), one can show (Smallwood & Sondik) that for each action and observation the contribution to the backup is again a maximum of linear functions in \( b \). The maximum over finitely many actions of finitely many linear functions is still a maximum of finitely many linear functions, hence \( V_{H+1} \) is piecewise linear and convex. By induction, this property holds for all horizons.

In this lesson we introduced POMDPs as a principled framework for planning under observation and motion uncertainty in robotics. We defined the POMDP tuple, derived the Bayes-filter belief update, and established that the belief is a sufficient statistic yielding a fully observable MDP on the belief space. We then discussed the Bellman equation, the piecewise-linear and convex structure of the value function, and studied two small robotic examples (1D localization and object search).

Finally, we implemented core belief update and finite-horizon planning routines in Python, C++, Java, Matlab/Simulink, and Wolfram Mathematica, highlighting how these abstractions can be embedded in robotics software stacks (ROS, OMPL, Simulink). In the next lesson, we will contrast POMDP-style planning with robust and risk-sensitive formulations that treat uncertainty in a different, more conservative way.