state space search
In plain wordsSolving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
The formulation of problem solving as finding a path through a graph whose nodes are states and whose edges are actions, from an initial state to any state that passes a goal test, often minimizing total path cost. A search algorithm maintains a frontier of generated but unexpanded states, repeatedly selects one and expands it by applying every applicable action; graph search also records visited states to avoid repeating work. Algorithms differ chiefly in the order of expansion: uninformed methods such as breadth-firstbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first., depth-firstdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch. and iterative deepeningiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest answer. use only the problem definition, while informed methods such as best-firstbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next. and A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first. use a heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.. The central obstacle is combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.: the state spaces of puzzles, games and plans grow exponentially with depth.
Once the puzzle is framed as state space search, any off-the-shelf A* implementation can solve it.
Origin
Newell, Shaw and Simon's programs of the late 1950s treated problem solving as search through a space of possibilities. Saul Amarel (1968) showed how the choice of representation shapes the space, Nils Nilsson's Problem-Solving Methods in Artificial Intelligence (1971) systematized the algorithms, and Newell and Simon's Human Problem Solving (1972) made the 'problem space' a psychological theory.
Usage note
Search remains central in modern AI in new forms: Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average. in game playing, beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility. in text generation, and search over reasoning steps in tree of thoughtstree of thoughts, n.: A method in which an AI explores several possible next steps of a problem, judges which look promising and backs out of dead ends, like a chess player weighing moves, instead of reasoning in one straight line. and other test-time methods.
Related
- breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first.
- depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch.
- A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first.
- heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer.
- best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next.
- combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- game treegame tree, n.: A branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
Sources
- Nilsson, N. J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.
- Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach, 4th ed. Pearson.
Mentioned in
symbolic AIsymbolic AI, n.: An approach to AI that writes knowledge down as human-readable symbols and rules, such as 'every bird has wings', and reasons by manipulating them step by step instead of learning patterns from data., A* searchA* search, n.: A method for finding the shortest route on a map or network that weighs both how far you have already come and a smart guess of how far is left, so it tries the most promising paths first., automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., beam searchbeam search, n.: A search method that keeps several of the best partial answers at each step, rather than only the single best, to find a better overall result without trying every possibility., breadth-first searchbreadth-first search, n.: A way of exploring a maze or network level by level — first every place one step away, then every place two steps away, and so on — so that the shortest route is found first., combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers., depth-first searchdepth-first search, n.: A way of exploring a maze or network by following one path as far as it goes, then backing up to the most recent fork and trying the next branch., Dijkstra's algorithmDijkstra's algorithm, n.: A classic method for finding the shortest routes from one starting point to every other point on a map or network, by always settling the nearest not-yet-settled point next., heuristicheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer., admissible heuristicadmissible heuristic, n.: An estimate of the remaining distance to a goal that is never more than the real distance — an optimistic guess — which lets some search methods guarantee that they find the best route., best-first searchbest-first search, n.: A family of search methods that rank every option waiting to be explored by a score, such as an estimate of the distance still to go, and always take the top-ranked one next., iterative deepening searchiterative deepening search, n.: A search strategy that explores one step deep, then starts over and explores two steps deep, then three, and so on. It repeats some work but needs very little memory and still finds the shortest answer., local searchlocal search, n.: A family of problem-solving methods that start with some complete answer, however poor, and keep improving it by small changes, instead of building an answer piece by piece from scratch., means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken., Nils NilssonNils Nilsson, prop. n.: An American computer scientist who co-created the A* search algorithm and the STRIPS planner for Shakey, the first robot to plan its own moves by reasoning, and wrote standard AI textbooks., Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them., STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true., tree of thoughtstree of thoughts, n.: A method in which an AI explores several possible next steps of a problem, judges which look promising and backs out of dead ends, like a chess player weighing moves, instead of reasoning in one straight line.