Search problems

A search problem can be defined formally as follows:

• A set of possible states that the environment can be in. We call this the state space.
• The initial state that the agent starts in.
• A set of one or more goal states. Sometimes there is one goal state, sometimes there is a small set of alternative goal states, and sometimes the goal is defined by a property that applies to many states (potentially an infinite number).
• The actions available to the agent. Given a state $s$, $Actions(s)$ returns a finite set of actions that can be executed in $s$. We say that each of these actions is applicable in $s$.
• A transition model, which describes what each action does. $Result(s,a)$ returns the state that results from doing action $a$ in state $s$.
• An action cost function, denoted by $ActionCost(s,a,s')$ when we are programming or when we are doing math, that gives the numeric cost of applying action $a$ in state $s$ to reach state $s'$.

A sequence of actions forms a path, and a solution is a path from the initial state to a goal state. We assume that action costs are additive; that is, the total cost of a path is the sum of the individual action costs. An optimal solution has the lowest path cost among all solutions.

The state space can be represented as a graph in which the vertices are states and the directed edges between them are actions.