Does every vertex need a human-readable name?

No. A state can be stored as a tuple, bit pattern, or other structured representation.

Can several actions connect the same pair of states?

Yes. They may have different labels or costs, so the model should preserve distinctions that matter.

Is the graph the same as the search frontier?

No. The frontier is the current collection of candidates maintained by a particular search run.

AI Glossary / Graphs and symbolic AI / Intermediate

State space graph

Definition

A state space graph represents the possible states of a problem and the actions that connect them. Each vertex represents a state, and an edge represents an allowed transition. A search algorithm can use this representation to find a sequence of actions from a starting state to a state that satisfies a goal.

What it means

The graph describes the problem rather than a particular search procedure. Two algorithms can examine the same state space graph in different orders and use very different amounts of memory.
A state must contain the information needed to determine relevant future possibilities. For example, a robot's location may be insufficient if its available moves also depend on whether it holds a key. A search node, by contrast, can contain a state together with a parent, an action, and the cost of the path used to reach it. Several search nodes can refer to the same underlying state.

How it works

Specify a state representation, a starting state, available actions, a transition model, action costs, and a goal test. The transitions define the graph's edges. Depending on the problem, edges may be directed, weighted, or labeled with actions.
The entire graph does not have to be stored in advance. A successor function can generate outgoing transitions when a search algorithm examines a state. The search then maintains a frontier of candidates and, where appropriate, records previously encountered states. Correct state comparison is essential: it determines whether two paths have reached the same situation or merely situations that look similar.

Three practical examples

A puzzle solver represents board configurations as states and legal moves as edges.
A workflow planner represents task-completion configurations as states and permitted next tasks as transitions.
A routing model can represent locations as states when location alone captures the relevant choices; additional variables are needed when access or resources affect movement.

Think of it this way

Think of a subway map showing stations and direct connections. The graph tells you what can follow what, while your chosen itinerary is only one path through it. The analogy is limited because AI states can be entire configurations rather than physical places, and a transition may change several variables simultaneously.

Worked example

Consider an original device with two independent lights. A state is a two-bit string: the first bit records the left light, and the second records the right. Zero means off and one means on. An action toggles exactly one light and costs one.
The state space graph has four vertices: 00, 10, 01, and 11. From 00, toggling the left light reaches 10 and toggling the right reaches 01. From 10, toggling the right reaches 11 and toggling the left returns to 00. From 01, transitions reach 00 and 11.
Because every toggle can be reversed, this graph can be drawn as an undirected square with four edges. Alternatively, explicitly drawing each directional action gives eight directed transitions. These are two representations of the same reversible behavior, not contradictory edge counts.
Starting from 00 with the goal 11, there are two shortest solutions: 00-10-11 and 00-01-11. Each costs two. No one-action solution exists because a single action changes only one bit, while both bits must change.
Now unfold the graph into a search tree. The root is 00, its children are 10 and 01, and 11 appears beneath both branches. The state 00 also reappears after toggling the same light twice. Without cycle handling or another stopping restriction, arbitrarily long action sequences can be generated even though the graph contains only four distinct states.
This distinction explains why counting search-tree nodes is different from counting unique states. It also shows why recording visited states can prevent repeated work. In a weighted problem, however, discovering a state again through a cheaper path may require updating its recorded cost rather than rejecting every repeat automatically.

Illustrative case study

In a fictional equipment-configuration project, engineers model each enabled feature as a Boolean variable. They initially assume that any feature can be toggled independently, then discover a dependency requiring one feature to remain enabled while another operates.
They revise the allowed transitions and test the model against documented operating rules before running search. The exercise separates a mistake in the graph from a mistake in the search algorithm. It does not claim that a successfully found path is safe for real equipment without that validation.

Common misconceptions and mistakes

A state space graph is not necessarily a tree. Cycles and multiple paths to the same state are common. It also need not be explicitly enumerated: a compact transition rule can describe a graph far too large to store.
Do not assume that two identical locations are the same state when their resources or permissions differ. Finally, shortest in number of edges means cheapest only when the edge costs make that comparison appropriate. A route with fewer actions may have a larger total cost.

Business use

The concept helps business teams evaluate whether a planning system represents the actual decision problem. Before comparing algorithms, examine the state variables, legal transitions, goal conditions, and cost units.
A scheduling model might need to include completed tasks, available resources, and time-related constraints. Omitting a relevant variable can create impossible plans or hide feasible ones. Keeping unnecessary detail can also make search harder. A useful review therefore asks both whether the model preserves required distinctions and whether its size remains practical for the intended task.

Check your understanding

In the two-light example, does seeing 11 twice in a search tree mean the state space graph has two different goal vertices?

Answer: No. The two tree nodes represent different paths to the same state 11.

Related terms

State
Transition model
Search tree
Graph search
Frontier
Goal test
Search node
Successor function
Path cost

Learn next

Next, give left-light toggles cost three and right-light toggles cost one. The two shortest goal paths still use two actions, but each now costs four. Add a special action that turns both lights on for cost five and explain why the fewest-action solution becomes more expensive than the cheapest solution.

Sources

Primary sources: University of California, Berkeley, CS188, State Spaces and Search Problems: https://inst.eecs.berkeley.edu/~cs188/textbook/search/state.html . Russell and Norvig's AIMA source sentences discuss state space graphs and their relationship to search trees: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt . The light-switch graph and cost variation are original teaching examples.

Previous: State space Next: State-space landscape