Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
State space search
Summary
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 desired property.
Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.
State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.
In state space search, a state space is formally represented as a tuple , in which:
is the set of all possible states;
is the set of possible actions, not related to a particular state but regarding all the state space;
is the function that establish which action is possible to perform in a certain state;
is the function that returns the state reached performing action in state
is the cost of performing an action in state . In many state spaces a is a constant, but this is not always true.
According to Poole and Mackworth, the following are uninformed state-space search methods, meaning that they do not have any prior information about the goal's location.
Traditional depth-first search
Breadth-first search
Iterative deepening
Lowest-cost-first search / Uniform-cost search (UCS)
These methods take the goal's location in the form of a heuristic function.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related people (4)
Related concepts (2)
Search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with either discrete or continuous values. Although search engines use search algorithms, they belong to the study of information retrieval, not algorithmics. The appropriate search algorithm to use often depends on the data structure being searched, and may also include prior knowledge about the data.
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 desired property. Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.
Related courses (2)
CS-330: Artificial intelligence
Introduction aux techniques de l'Intelligence Artificielle, complémentée par des exercices de programmation qui montrent les algorithmes et des exemples de leur application à des problèmes pratiques.
CS-430: Intelligent agents
Software agents are widely used to control physical, economic and financial processes. The course presents practical methods for implementing software agents and multi-agent systems, supported by prog
Related lectures (5)
Deliberative Agents: Planning and Strategies
Covers planning with adversaries, heuristic search algorithms, and strategies for games with chance, emphasizing the significance of deliberative agents.
Controllability and Observability
Covers controllability and observability in linear systems, discussing necessary conditions and implications of unimodular matrices.
Optimization Methods: Theory Discussion
Explores optimization methods, including unconstrained problems, linear programming, and heuristic approaches.