======================================================================
= State space planning =
======================================================================
Introduction
======================================================================
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, s0, g)
s = s0
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, s0, g)
s = s0
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)
See also
======================================================================
* State space
* State space search
License
=========
All content on Gopherpedia comes from Wikipedia, and is licensed under CC-BY-SA
License URL:
http://creativecommons.org/licenses/by-sa/3.0/
Original Article:
http://en.wikipedia.org/wiki/State_space_planning
