**Ê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.
Definition
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

Source officielle

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

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Publications associées (39)

Chargement

Chargement

Chargement

Personnes associées (5)

Concepts associés (13)

Système dynamique

En mathématiques, en chimie ou en physique, un système dynamique est la donnée d’un système et d’une loi décrivant l'évolution de ce système. Ce peut être l'évolution d'une réaction chimique au cour

Théorie du contrôle

En mathématiques et en sciences de l'ingénieur, la théorie du contrôle a comme objet l'étude du comportement de systèmes dynamiques paramétrés en fonction des trajectoires de leurs paramètres.

Chaîne de Markov

vignette|Exemple élémentaire de chaîne de Markov, à deux états A et E. Les flèches indiquent les probabilités de transition d'un état à un autre.
En mathématiques, une chaîne de Markov est un process

Cours associés (8)

MGT-484: Applied probability & stochastic processes

This course focuses on dynamic models of random phenomena, and in particular, the most popular classes of such models: Markov chains and Markov decision processes. We will also study applications in queuing theory, finance, project management, etc.

PHYS-216: Mathematical methods for physicists

This course complements the Analysis and Linear Algebra courses by providing further mathematical background and practice required for 3rd year physics courses, in particular electrodynamics and quantum mechanics.

BIOENG-450: In silico neuroscience

"In silico Neuroscience" introduces students to a synthesis of modern neuroscience and state-of-the-art data management, modelling and computing technologies.

Séances de cours associées (37)

Unités associées (4)

Multi-Object tracking (MOT) is an important problem in a number of vision applications. For particle filter (PF) tracking, as the number of objects tracked increases, the search space for random sampling explodes in dimension. Partitioned sampling (PS) solves this problem by partitioning the search space, then searching each partition sequentially. However, sequential weighted resampling steps cause an impoverishment effect that increases with the number of objects. This effect depends on the specific order in which the partitions are explored, creating an erratic and undesirable performance. We propose a method to search the state space that fairly distributes these impoverishment effects between the objects by defining a set of mixture components and performing PS in each of these components using one of a small set of representative object orderings. Using synthetic and real data, we show that our method retains the overall performance and reduced computational cost of PS, while improving performance in scenes where the impoverishment effect is significant.

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 in face of randomly changing weather conditions, such as wind direction. When a sailboat is travelling upwind, the key is to decide when to tack. Since this maneuver slows down the yacht, it is natural to model this time lost by a "tacking penalty" which places the problem in the context of optimal stochastic control problems with switching costs. An objective of this work is to propose and to study mathematical models that capture some of the features of a sailing race, but which remain amenable to an explicit rigorous solution that can be proved to be optimal. We consider three different models in which the wind direction is described by a stochastic process. In the first model, we consider a wind that changes randomly only once. In the second model, the wind oscillates between two possible directions according to a continuous-time Markov chain. We exhibit a free boundary problem for the value function involving hyperbolic partial differential equations of Klein-Gordon type. The last model considers the wind direction as a Brownian motion. We prove the existence of a finite value function and exhibit a free boundary problem involving parabolic partial differential equations with non-constant coefficients. In these three models, the optimal solution consists of a partition of the state space into a region where it is optimal to tack immediately and a region where it is optimal to continue on the current tack. The boundaries between these regions are given by one or more "switching curves" and in the cases where we have been able to exhibit them, the optimality of the solution is established by a verification theorem based on the martingale method. We also solve two other control problems in which a player tries to minimize or maximize the exit time from an interval of a Brownian particle by controlling its drift and subject to a switching penalty. In each problem, the value function is written as the solution of a second order ordinary differential equations problem whose unknown boundaries are found by applying the principle of smooth fit. For both problems, we exhibit a candidate strategy as a function of the switching cost and we prove its optimality as well as its generic uniqueness.

Multi-Object tracking (MOT) is an important problem in a number of vision applications. For particle filter (PF) tracking, as the number of objects tracked increases, the search space for random sampling explodes in dimension. Partitioned sampling (PS) solves this problem by partitioning the search space, then searching each partition sequentially. However, sequential weighted resampling steps cause an impoverishment effect that increases with the number of objects. This effect depends on the specific order in which the partitions are explored, creating an erratic and undesirable performance. We propose a method to search the state space that fairly distributes these impoverishment effects between the objects by defining a set of mixture components and performing PS in each of these components using one of a small set of representative object orderings. Using synthetic and real data, we show that our method retains the overall performance and reduced computational cost of PS, while improving performance in scenes where the impoverishment effect is significant.

2004