State space search

In state space search, a state space is formally represented as a tuple ${\displaystyle S:\langle S,A,Action(s),Result(s,a),Cost(s,a)\rangle }$, in which:

• ${\displaystyle S}$ is the set of all possible states;
• ${\displaystyle A}$ is the set of possible actions, not related to a particular state but regarding all the state space;
• ${\displaystyle Action(s)}$ is the function that establish which action is possible to perform in a certain state;
• ${\displaystyle Result(s,a)}$ is the function that returns the state reached performing action ${\displaystyle a}$ in state ${\displaystyle s}$
• ${\displaystyle Cost(s,a)}$ is the cost of performing an action ${\displaystyle a}$ in state ${\displaystyle s}$. In many state spaces a is a constant, but this is not always true.

• State space
• State space planning
• Branch and bound - a method for making state-space search more efficient by pruning subsets of it.

• Stuart J. Russell and Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall.