# State space planning

In artificial intelligence and computer programming, **state space planning** is a process used in designing programs to search for data or solutions to problems. In a computer algorithm that searches a data structure for a piece of data, for example a program that looks up a word in a computer dictionary, the *state space* is a collective term for all the data to be searched. Similarly, artificial intelligence programs often employ a process of searching through a finite universe of possible procedures for reaching a goal, to find a procedure or the best procedure to achieve the goal. The universe of possible solutions to be searched is called the state space. *State space planning* is the process of deciding which parts of the state space the program will search, and in what order.

## Definition

The simplest classical planning (see Automated Planning) algorithms are state space search algorithms. These
are search algorithms in which the search space is a subset of the state space: Each
node corresponds to a state of the world, each arc corresponds to a state transition,
and the current plan corresponds to the current path in the search space.
Forward Search and Backward Search are two of main samples of **state space planning**.

## Forward search

Forward search is an algorithm that searches forward from the initial state of the world to try to find a state that satisfies the goal formula.

Forward-search(O, s_{0}, g)

s = s_{0}P = the empty plan loop if s satisfies g then return P applicable = {a | a is a ground instance of an operator in O,and precond(a) is true in s} if applicable = ∅ then return failure nondeterministically choose an action a from applicable s = γ(s, a) P = P.a

## Backward search

Backward-search is an algorithm that begins with goal state and back track to its initial state. This method is sometimes called "back propagation."

Backward-search(O, s_{0}, g)

s = s_{0}P = the empty plan loop if s satisfies g then return P relevant = {a | a is a ground instance of an operator in O that is relevant for g} if relevant = ∅ then return failure nondeterministically choose an action a from relevant P = a.P s = γ^{−1}(s, a)