State space (computer science)

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.

In computer science, a state space is a discrete space representing 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 toy problem Vacuum World has a discrete finite state space in which there are a limited set of configurations that the vacuum and dirt can be in. A "counter" system, where states are the natural numbers starting at 1 and are incremented over time has an infinite discrete state space. The angular position of an undamped pendulum is a continuous (and therefore infinite) state space. State spaces are useful in computer science as a simple model of machines. Formally, a state space can be defined as a tuple [N, A, S, G] where: N is a set of states A is a set of arcs connecting the states S is a nonempty subset of N that contains start states G is a nonempty subset of N that contains the goal states. A state space has some common properties: complexity, where branching factor is important structure of the space, see also graph theory: directionality of arcs tree rooted graph For example, the Vacuum World has a branching factor of 4, as the vacuum cleaner can end up in 1 of 4 adjacent squares after moving (assuming it cannot stay in the same square nor move diagonally). The arcs of Vacuum World are bidirectional, since any square can be reached from any adjacent square, and the state space is not a tree since it is possible to enter a loop by moving between any 4 adjacent squares. State spaces can be either infinite or finite, and discrete or continuous. The size of the state space for a given system is the number of possible configurations of the space. If the size of the state space is finite, calculating the size of the state space is a combinatorial problem. For example, in the Eight queens puzzle, the state space can be calculated by counting all possible ways to place 8 pieces on an 8x8 chessboard.

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 publications (1)

Related people (5)

Related concepts (10)

Related courses (7)

Related lectures (48)

Related MOOCs (4)

Dynamical systems theory

Dynamical systems theory is an area of mathematics used to describe the behavior of complex dynamical systems, usually by employing differential equations or difference equations. When differential equations are employed, the theory is called continuous dynamical systems. From a physical point of view, continuous dynamical systems is a generalization of classical mechanics, a generalization where the equations of motion are postulated directly and are not constrained to be Euler–Lagrange equations of a least action principle.

Game complexity

Combinatorial game theory measures game complexity in several ways: State-space complexity (the number of legal game positions from the initial position), Game tree size (total number of possible games), Decision complexity (number of leaf nodes in the smallest decision tree for initial position), Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large).

State space (computer science)

Stochastic Control and Free Boundary Problems for Sailboat Trajectory Optimization

Laura Vinckenbosch

The topic of this thesis is the study of several stochastic control problems motivated by sailing races. The goal is to minimize the travel time between two locations, by selecting the fastest route i

EPFL2012

ENG-639: Dynamic programming and optimal control

This course provides an introduction to stochastic optimal control and dynamic programming (DP), with a variety of engineering applications. The course focuses on the DP principle of optimality, and i

ME-326: Control systems and discrete-time control

Ce cours inclut la modélisation et l'analyse de systèmes dynamiques, l'introduction des principes de base et l'analyse de systèmes en rétroaction, la synthèse de régulateurs dans le domain fréquentiel

CIVIL-467: Advanced Structural Dynamics

This course covers theoretical and practical aspects of the dynamic response of linear and nonlinear structural systems in continuous and discrete time. First and second order system dynamics are used

Neuronal Dynamics - Computational Neuroscience of Single Neurons

The activity of neurons in the brain and the code used by these neurons is described by mathematical neuron models at different levels of detail.

Neuronal Dynamics 2- Computational Neuroscience: Neuronal Dynamics of Cognition

This course explains the mathematical and computational models that are used in the field of theoretical neuroscience to analyze the collective dynamics of thousands of interacting neurons.

Neuronal Dynamics 2- Computational Neuroscience: Neuronal Dynamics of Cognition

This course explains the mathematical and computational models that are used in the field of theoretical neuroscience to analyze the collective dynamics of thousands of interacting neurons.

State Representation and System Dynamics ME-523: Nonlinear Control Systems

Covers the representation of state-space models and system dynamics.

State-Space Dynamic Response ME-321: Control systems + TP

Covers the computation of transfer functions and system poles and zeros.

Linearization Method: Examples ME-323: Chemical process control

Covers the linearization method through two examples in process control.