Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
State space (computer science)
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (1)
Stochastic Control and Free Boundary Problems for Sailboat Trajectory Optimization
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
EPFL2012Personnes associées (5)
Concepts associés (10)
Théorie des systèmes dynamiques
La théorie des systèmes dynamiques désigne couramment la branche des mathématiques qui s'efforce d'étudier les propriétés d'un système dynamique. Cette recherche active se développe à la frontière de la topologie, de l'analyse, de la géométrie, de la théorie de la mesure et des probabilités. La nature de cette étude est conditionnée par le système dynamique étudié et elle dépend des outils utilisés (analytiques, géométriques ou probabilistes).
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)
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.
Cours associés (7)
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
Séances de cours associées (48)
Représentation de l'État et dynamique des systèmes
Couvre la représentation des modèles état-espace et la dynamique des systèmes.
Réponse dynamique de l'État et de l'espace
Couvre le calcul des fonctions de transfert, des pôles système et des zéros.
Méthode de linéarisation: Exemples
Couvre la méthode de linéarisation à travers deux exemples de contrôle de processus.
MOOCs associés (4)
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.