Designing the State Space

1A state is what the future needs

A state is a complete description of the situation for the purpose of choosing what happens next — no more, no less. The test of completeness is Markovian: given the state, the availability, outcome and cost of every remaining action must be predictable without knowing how the state was reached. History belongs in a state exactly when the future charges for it, and only then.

Keep the state distinct from the search node that wraps it. The node carries bookkeeping — the parent pointer, the g so far, sometimes a depth — that exists so a path can be reconstructed and priced. Two nodes holding the same state are candidates for merging; the bookkeeping around them never is. Conflating the two is how implementations end up hashing paths instead of situations and exploring the same situation thousands of times.

In a production planner this definition is a budget line: every field in the state multiplies the space the search can touch, and every field left out that the future actually needed makes the planner confidently wrong rather than slow. State design is choosing which of those two failures you can detect.

2The interchangeability test

Before coding any queue, put your encoding through one question: what must be true of two states for them to be interchangeable? If the same futures follow from them — every remaining action has the same availability, outcome and cost — they are one state, and an encoding that separates them is spending exponential space on a distinction no future action can see.

The warehouse robot makes it concrete. After aisles 1 and 2 are both finished, 'visited 1 then 2' and 'visited 2 then 1' present identical remaining problems; the order is history the future does not charge for, so the state is the set of finished aisles, not the sequence. Encode the set and two branches of the tree collapse into one node; encode the sequence and every permutation of the same progress is explored separately.

The test cuts the other way with equal force: if tomorrow's costs do depend on something — the robot's battery level, a one-way door that closed behind it — then that something belongs in the state, and abstracting it away produces fast, wrong plans. Interchangeability is a property of the problem's future, never of the author's convenience.

Figure. Two histories, one situation: after both aisles are finished, no remaining action can tell 'visited 1 then 2' from 'visited 2 then 1', so a set-valued state merges the two branches into one node. A sequence-valued state explores both.

Designing the encoding

1. Name what the future needsList what the availability, outcome or cost of any remaining action depends on.
2. Discard the restEverything else — visit order, the route taken, costs already paid — is node bookkeeping, not state.
3. Test interchangeabilityPick two candidates your encoding separates; if no future action can tell them apart, merge them.

3Count the space before you code

State design has an arithmetic check, and it costs five minutes against weeks of profiling: multiply out the encoding before implementing anything. Each independent field of the state contributes a factor, so the size of the space is a product you can estimate on paper — and the difference between two encodings of the same problem is almost never twenty per cent; it is ten orders of magnitude.

Take a delivery robot with 20 packages and 50 waypoints. A state of (set of delivered packages, current position) gives 2²⁰ × 50 ≈ 5 × 10⁷ states — large, but a laptop's problem. Let the delivery order leak into the state and the subset factor becomes 20!, and no machine on earth enumerates it. Same warehouse, same robot, same optimal routes: the encoding alone moved the problem across the line between feasible and hopeless.

The paper estimate also tells you which field to attack: the factor with the largest exponent is the design problem, and it is usually a history component pretending to be situation.

Figure. The same warehouse under two encodings, drawn on a log scale — each ladder rung is a factor of ten, and the encodings sit about eleven rungs apart.

4Abstraction: solve a smaller problem honestly

When the honest state space is still too large, the move is not a looser search but a smaller problem: map states through a homomorphism that forgets part of the situation, so that every real move has a counterpart among the abstract moves. Forgetting can only merge states and add moves, never remove them, so the abstract problem is easier — and its exact solution costs are a lower bound on the real ones.

That lower-bound property is why abstraction is the standard factory for admissible heuristics: solve the abstract problem exhaustively once, store the exact cost of every abstract state, and read the table during the real search. Stored this way the table is called a pattern database, and it is how optimal solvers for sliding-tile puzzles and many classical planning benchmarks are actually built.

The craft is in choosing what to forget: forget too little and the table will not fit; forget too much and the bound goes soft, steering the real search weakly. The count-before-you-code discipline is the tool — size the abstract space to the memory you have, then buy precision back by combining several abstractions.

5Duplicate detection is state design at run time

An encoding is only as good as the equality test that enforces it, because the explored set and the frontier both key on the state. The practical requirements: a canonical form — the same situation must serialise identically, so set-valued fields are sorted before hashing, costs are rounded to the lattice they live on, and node bookkeeping is gone — plus cheap hashing and immutability while queued.

Symmetry is the next rung of the same ladder. When the problem is invariant under some transformations — rotations of a board, relabelling of identical robots — canonicalise each state to a chosen representative of its orbit before hashing, and the search explores one member per orbit instead of all of them. In game search the same machinery appears as transposition tables: positions reached by different move orders hash to one entry.

None of this is optional bookkeeping. A duplicate that slips the net is expanded again, and everything downstream of it too — the cost of a missed merge is a subtree, not a node.

Picture two tic-tac-toe boards, one a quarter-turn of the other: different arrays, the same game. Canonicalisation maps both through all eight symmetries and keeps a single representative, so the explored set stores one entry for the pair.

Canonicalise before hashing

1. Normalise fieldsSort set-valued fields, round costs to their lattice, drop node bookkeeping.
2. Reduce by symmetryApply every symmetry transform and keep one fixed representative, such as the smallest serialisation.
3. Probe, then expandLook the canonical key up in the explored set before generating successors, never after.