A note on nomenclature in these notes. There is a clear distinction between the way the unofficial textbook and the lectures address formalisms of the content. For this reason, I will be providing my own mathematical interpretation.

A few notes on state spaces. A search problem’s encompassing, ambient environment is known as its world. There are two types of states: world states, which contain all information about a given state in the world, and search states, which only contain information about a given state relevant to planning. A state space is said to be complete if it contains all possible states a world can have and minimal if it contains no redundant or irrelevant information.

Search Problem

Given an initial state $x_0$, find a sequence of states $x_0, \space \dots, \space x_n$, known as a plan, that terminates with the goal state $x_n$ such that any two consecutive states are reachable by a legal action.

• State Space. A set $S$ of all possible states $x$ in the world.
• Action Set. A set $A$ of all possible actions in the world.
• Action Model. A function $a : S \rightarrow \mathcal{P}(A)$ which maps a state to a subset of actions available at that state.
• Cost. A function $c : S \times A \rightarrow \R$ which maps a state and an action to the cost incurred from taking that action at that state.
• Transition Model. A function $t : S \times A \rightarrow S$ which maps a state and an action to a reachable, successor state.
• Goal Test. A function $g : S \rightarrow \{0, 1\}$ which determines if a state is a goal state.

A search problem is entirely characterized by the above.

In lecture, the notion of a transition model, actions, and costs are encoded in a successor function.

State Space Graph

A search problem’s state space can be represented as a directed state space graph, where each node corresponds to a state and an arc from $x_i$ to $x_j$ exists if $x_j$ is reachable from $x_i$.

Each arc represents a legal action its tail can take.

Search Tree