Planning When You Can't See the Whole World

Classical planning assumes you know everything. Real agents almost never do. Belief states give us a principled way to plan under uncertainty — and an extraordinary computational cost in the bargain.

Where the assumption breaks

The sibling series — Learning for Planning — opened with the same warehouse we'll use here: zones A, B, C, D, a robot, a package. There, the robot knew exactly where every package was. The hard part was the search space, not the perception.

Now change one thing. The robot can only see what's in its current zone. It can't see into the other three. If it walks into Zone C and the package is sitting on the shelf, it perceives that. If the package isn't there, it just sees an empty shelf — and learns one fact about the world, but not where the package actually is.

This is partial observability. The state of the world is what it is — the package has some real position. But the agent doesn't know it. It only has a probability distribution over possible positions, updated each time it observes something. That distribution is the agent's belief, and it's the only handle on the world the agent can plan against.

From state to belief, formally

The right card above isn't just visual flourish — that counter is real. Each action the robot takes produces an observation (what it sees in its new zone), and each observation could be any of several possibilities, each updating the belief differently. The agent has to plan against all of them. Branching factors compound.

A POMDP — partially observable Markov decision process — formalizes this with a seven-tuple 〈S, A, T, R, Z, O, γ〉: states, actions, transition function, reward, observations, observation function, discount. The agent never gets to see s; it only gets observations z drawn from O(s', a, z) after acting.

The agent's belief b(s) — its probability distribution over the true state — updates by Bayes' rule:

b'(s') = η · O(s', a, z) · Σ_s T(s, a, s') · b(s)

That is: take the prior belief, push it forward through the transition model, weight by how likely each successor would have produced the observation we got, then normalize. Mechanically simple, computationally brutal. The Bellman equation now ranges over belief states — an uncountable, infinite-dimensional space — rather than the finite state space we had in classical planning.

Two strategies for getting past the wall

The rest of this series mirrors the LFP series structure, but for the partially observable case. Same two strategies:

• Make the problem smaller. If the agent abstracts away most of the state — objects, zones, package identities that don't matter for the current decision — a principled POMDP solver can handle the abstraction. That's Part 3, HOO-POMDP.
• Learn to plan in belief space. Frame the belief as a graph; train a GNN to score actions over that graph; transfer to larger instances. That's Part 4, GammaZero — the partially observable cousin of GABAR from the LFP series.

Part 2 covers what the community built in between — online tree search methods like POMCP and DESPOT, which made POMDPs tractable in practice but pushed the difficulty into heuristic ingredients (rollout policies, value estimates). That heuristic gap is exactly what Parts 3 and 4 close, from two different angles.

If PDDL and classical planning are new to you, the Planning in the Era of LLMs series covers that background. This series picks up where classical planning ends — when the assumption of a known state no longer holds.