From Surf Wiki (app.surf) — the open knowledge base
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 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.
In the algorithms that follow, by "non-deterministic", we mean that the chosen graph search algorithm for picking a next branch is arbitrary. One can brute-force (BFS, DFS, IDS, etc.), use heuristics (A*, IDA*, etc.), etc. This is a choice which generally depends on the nature of the problem.
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.
We say an action is applicable in a state s if the preconditions of this action are true in s.
With O the set of actions, s0 the initial state, and g the goal state:
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 a is applicable 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".
We say an action is relevant if its add-effects (literals of the state turned true) are in G, and none of its del-effects (literals of the state turned false) are in G.
With O the set of actions, s0 the initial state, and g the goal state:
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)
References
This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.
Ask Mako anything about State-space planning — get instant answers, deeper analysis, and related topics.
Research with MakoFree with your Surf account
Create a free account to save articles, ask Mako questions, and organize your research.
Sign up freeThis content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.
Report