Is abstraction the same as removing data errors?

No. It intentionally merges distinctions, even when the original information is correct.

Must every abstract route be executable?

No. Some abstractions deliberately allow extra possibilities to produce useful lower bounds.

Can an abstraction be too detailed?

Yes. It can become expensive to construct or solve, reducing the benefit of simplification.

AI Glossary / Graphs and symbolic AI / Intermediate

State abstraction

Definition

State abstraction is the process of mapping detailed states of a problem into simpler states that retain selected information. Several different detailed states can share one abstract representation. In AI planning and search, a carefully constructed abstraction can make reasoning cheaper and provide an estimate of how much work remains before a goal is reached.

What it means

A state describes the aspects of a situation that a model treats as relevant. For a delivery robot, these might include its location, battery level, and which doors it can unlock. An abstraction might retain location while temporarily ignoring the other details.
That simplification has a purpose and a cost. It may make a large problem easier to inspect, but two situations represented as identical can still have different available actions. An abstract route therefore does not automatically constitute an executable plan. The intended use matters: estimating a lower bound requires different guarantees from replacing the original decision model entirely.

How it works

Choose the information to retain and define an explicit mapping from concrete states to abstract states. Construct abstract transitions that preserve the concrete possibilities needed for the intended guarantee. For an admissible planning heuristic, concrete solution paths must remain representable without becoming more expensive, and concrete goals must map to abstract goals.
Solve or analyze the smaller problem. Its cheapest remaining cost can then supply a lower bound under those conditions. A particularly simple abstraction projects a state onto a subset of its variables. More elaborate methods group states differently or refine an abstraction when it hides a distinction that matters. Arbitrarily deleting transitions or changing costs can invalidate the lower-bound argument.

Three practical examples

A puzzle solver can track selected pieces while ignoring others to estimate a minimum amount of remaining movement.
A robot-planning demonstration can reason about rooms before considering individual positions within each room.
A workflow planner can group detailed equipment configurations into broader availability states, provided it checks what that grouping preserves.

Think of it this way

Think of replacing a detailed building model with a diagram of connected rooms. The diagram helps explain possible movement at a glance. Its limitation is that it may omit a locked door, a narrow passage, or an access requirement. A useful overview is not necessarily a complete set of walking instructions.

Worked example

Consider an original planning example with rooms A, B, and C and a Boolean variable indicating whether a robot holds a key. There are six representational combinations of room and key status. The robot starts at A without the key and must reach C.
Moving between A and B costs one. Moving between B and C also costs one but requires the key. Picking up the key at B costs one. There is no dropping action, and all costs are nonnegative.
The concrete solution is A without key, B without key, B with key, then C with key. Its total cost is 1 + 1 + 1 = 3. A solution cannot cost less because the robot must move twice and acquire the key before entering C.
Now forget key status. Both concrete states at A map to abstract A, both at B to abstract B, and both at C to abstract C. The six representational combinations become three abstract states. Some concrete combinations may be unreachable from this particular start; the mapping need not pretend otherwise.
The abstract graph includes A - B and B - C because corresponding concrete transitions exist. The pickup action becomes a self-transition at B. The cheapest abstract route A - B - C costs two, so the abstract estimate is 2, below the concrete optimum of 3.
The two-step abstract route cannot be executed directly from the concrete start: the robot would reach B without the required key. This is exactly the distinction between a useful estimate and a valid concrete plan. At B, forgetting key status also merges two states with different remaining optimal costs: two without the key and one with it.

Illustrative case study

In a fictional warehouse-planning project, a team uses a room-level abstraction to prioritize detailed route searches. A suggested corridor route sometimes crosses an access-controlled door, so the concrete planner checks credentials and includes the necessary access action.
The team records which restrictions the abstraction omits and whether the resulting cost estimate remains a lower bound. It also compares the time spent constructing the abstraction with any search effort saved. This fictional case describes an evaluation approach, not a measured operational improvement.

Common misconceptions and mistakes

State abstraction does not mean that all omitted information is unimportant. It means the representation intentionally ignores it for a stated purpose. An abstract solution can be spurious when interpreted as a concrete action sequence.
Also, compression alone does not guarantee an admissible heuristic. The transition, goal, and cost relationships must support that guarantee. Conversely, an abstraction that gives a very weak estimate can be mathematically sound but operationally unhelpful. Smaller models and better search guidance are related design choices, not interchangeable outcomes.

Business use

The business value is making difficult planning models more manageable while keeping their limitations visible. Teams can discuss whether a simplified model supports early estimation, detailed scheduling, or actual execution.
Ask which distinctions are removed, which decisions still depend on them, and where the full model checks feasibility. Evaluate both computational effort and resulting plan quality. If a planner uses abstract distances to claim optimality, require a clear explanation of why those distances cannot overestimate the concrete remaining cost.

Check your understanding

In the worked example, does an abstract distance of two prove that the robot can reach C in two actions?

Answer: No. It supplies a lower bound under the stated construction. The concrete plan still requires the key pickup and costs three.

Related terms

State space
Admissible heuristic
Projection
Abstract state
Pattern database
Planning
Relaxation
Abstraction refinement

Learn next

Next, retain key status but forget the difference between rooms A and B. Draw the resulting abstract transitions and goal condition. Compare its remaining-cost estimate with the original room-only abstraction, explaining which necessary action each simplification hides.

Sources

Primary sources: Pozo and Seipp, Abstraction Heuristics for Classical Planning Tasks with Conditional Effects, especially its background definitions of transition systems and abstractions: https://www.ijcai.org/proceedings/2025/0957.pdf . Russell and Norvig's AIMA glossary source sentences provide the planning context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt . The room-and-key example is original.

Previous: State Next: State machine agent