Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Search and Belief-Space Planning › Worked Example: Localizing and Acting in a Hidden-State Maze

Michael BrenndoerferJuly 9, 20265 min read

World Models HandbookAll chapters

Part 7 of 12Planning and Agency

Chapter 39Search and Belief-Space Planning › Worked Example: Localizing and Acting in a Hidden-State Maze

Reading section 7 of 13 · Worked Example: Localizing and Acting in a Hidden-State Maze · 5 minSection 7 of 13 · 5 min

Section 7 of 13 · 5 min read

Search and Belief-Space Planning › Worked Example: Localizing and Acting in a Hidden-State MazeOne section · Sections in this chapter7 / 13 ↓

Sections in this chapter13

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

We are now ready to put a belief-space agent into the maze. The agent starts at an unknown location, receives only its local wall signature, and must reach the goal. Its initial belief is uniform over the cells consistent with the first observation. Its planner is POMCP, re-planning at every step from the filtered belief. Its environment is exactly the model we built.

The dynamics and sensor are deterministic and match the planner's model; uncertainty about position comes from structural aliasing of the observation. The finite-simulation POMCP computation is still randomized, however, so one seeded successful episode is a worked example rather than an estimate of success probability.

In[24]:

Code

def run_pomcp_episode(
    true_start, n_sims=300, max_steps=30, max_depth=20, seed=0
):
    """Closed-loop POMCP control with an exact Bayesian belief filter."""
    rng = np.random.default_rng(seed + 12345)

    true_idx = S_IDX[true_start]
    belief = (O[SIG[true_idx]] > 0).astype(float)
    belief /= belief.sum()

    trace = {
        "belief": [belief.copy()],
        "true": [FREE[true_idx]],
        "entropy": [entropy(belief)],
        "actions": [],
    }
    total = 0.0

    for t in range(max_steps):
        if FREE[true_idx] == GOAL:
            break
        root = pomcp_plan(
            belief, n_sims=n_sims, max_depth=max_depth, seed=seed * 977 + t
        )
        a = int(np.argmax(root.Na))
        true_idx = int(rng.choice(N_CELLS, p=T[a, true_idx]))
        obs = int(rng.choice(16, p=O[:, true_idx]))
        belief = belief_update(belief, a, obs)
        total += GOAL_REWARD if FREE[true_idx] == GOAL else STEP_COST

        trace["actions"].append(a)
        trace["belief"].append(belief.copy())
        trace["true"].append(FREE[true_idx])
        trace["entropy"].append(entropy(belief))

    trace["solved"] = FREE[true_idx] == GOAL
    trace["steps"] = len(trace["actions"])
    trace["return"] = total
    return trace


TRACE = run_pomcp_episode((0, 2), n_sims=300, max_steps=30, seed=0)

Out[25]:

Console

Initial belief support: 8 cells
Initial entropy: 2.079 nats
Actions taken: ['right', 'down', 'down', 'left', 'down', 'up', 'left', 'right', 'right', 'right', 'right', 'down', 'down', 'down', 'down', 'down']
Goal reached: True  in 16 steps
Final entropy: 0.000 nats

In this seeded run, the agent reaches the goal in sixteen actions from an ambiguous start. Its exact filter begins with $\ln 8 \approx 2.08$ nats of uncertainty and reaches zero at control step 10. The shortest fully observed route from the true start takes ten actions, so this run uses six additional actions. We should not compare the trace's undiscounted accumulated reward directly with the discounted $V^*$ reported earlier, and this one trace does not establish that POMCP chose actions for their information value. It demonstrates the narrower point that history-based search can act while an external Bayes filter progressively localizes the state.

The two snapshots below show the first update of that localization process.

Out[26]:

Visualization

Heat map of belief concentrated over eight maze cells. — Belief distribution after the agent's first observation at step 0. Eight cells share the same wall signature across the top corridor and the bottom-left arm, so the belief is spread over a multimodal set of candidate positions and entropy is near ln 8.

Heat map of belief concentrated over a smaller set of maze cells. — Belief distribution after the first move at step 1. Folding in the new observation reduces the support from eight cells to five, while candidates remain in the top corridor, middle row, and bottom-left arm.

At step 0, the observation is consistent with eight cells. After the selected right action and next signature, exact filtering reduces the support to five cells. The panels visualize the belief used by the planner at consecutive control steps; they do not by themselves show why right was selected or prove a deliberate information-gathering choice.

The entropy trajectory shows when this particular action-observation sequence disambiguates the state. Entropy need not decrease on every step in a general POMDP, and a decreasing trace does not distinguish deliberate sensing from information obtained incidentally while pursuing reward.

Out[27]:

Visualization

Line chart of belief entropy falling to zero over the episode. — Belief entropy over the seeded sixteen-step episode. The support drops from eight to five cells after the first action, remains aliased for several steps, and becomes a point mass at step 10 when the action-observation history identifies the cell.

Here movement changes both position and the next observation. The trace shows that localization occurred along the executed route, but establishing active information gathering would require a counterfactual comparison against less informative actions with similar task reward. The episodic tiger calculation supplies that cleaner comparison: listening has an immediate cost and no physical progress, yet it is optimal over the middle belief band because it improves the later door decision.