In
artificial intelligence
Artificial intelligence (AI) is intelligence—perceiving, synthesizing, and inferring information—demonstrated by machines, as opposed to intelligence displayed by animals and humans. Example tasks in which this is done include speech r ...
and
computer programming
Computer programming is the process of performing a particular computation (or more generally, accomplishing a specific computing result), usually by designing and building an executable computer program. Programming involves tasks such as anal ...
, 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
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.
For instance, the to ...
'' 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
Automation describes a wide range of technologies that reduce human intervention in processes, namely by predetermining decision criteria, subprocess relationships, and related actions, as well as embodying those predeterminations in machines ...
) 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 =
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 =
if relevant = ∅ then return failure
nondeterministically choose an action a from relevant
P = a.P
s = γ
−1(s, a)
See also
*
State space
A state space is the set of all possible configurations of a system. It is a useful abstraction for reasoning about the behavior of a given system and is widely used in the fields of artificial intelligence and game theory.
For instance, the to ...
*
State space search
State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or ''states'' of an instance are considered, with the intention of finding a ''goal state'' with the ...
References
* {{Citation , last1=Ghallab , first=Malik , last2=Nau , first2=Dana S. , last3=Traverso , first3=Paolo , title=Automated Planning: Theory and Practice , publisher=
Morgan Kaufmann , year=2004 , url=https://books.google.com/books?id=eCj3cKC_3ikC&printsec=frontcover&dq=isbn:1558608567&hl=en&sa=X&ved=0ahUKEwjVtpXc-snjAhVOAqwKHRmGArQQ6AEIKjAA#v=onepage&q=%22state%20space%22&f=false , isbn=1-55860-856-7