State space

state space is the set of all possible configurations of a system.[1] 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[2] has an infinite discrete state space. The angular position of an undamped pendulum[3] is a continuous (and therefore infinite) state space.

Definition

In the theory of dynamical systems, a discrete system defined by a function ƒ, the state space of the system can be modeled as a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ(a) = b.[4] This is known as a state diagram.

For a continuous dynamical system defined by a function ƒ, the state space of the system is the image of ƒ.

State spaces are useful in computer science as a simple model of machines. Formally, a state space can be defined as a tuple [NASG] where:

  • Nis a set of states
  • Ais a set of arcs connecting the states
  • Sis a nonempty subset of N that contains start states
  • Gis a nonempty subset of N that contains the goal states.

References

  1. ^Nykamp, Duane. “State space definition”. Math Insights. Retrieved 17 November 2019.
  2. ^ Jump up to:ab Papernick, Norman. “Infinite States and Infinite State Transitions”. Carnegie Mellon University. Retrieved 12 November 2019.
  3. ^ Jump up to:ab c Nykamp, Duane. “The idea of a dynamical system”. Math Insights. Retrieved 12 November 2019.
  4. ^Laubenbacher, R. Pareigis, B. (2001). “Equivalence Relations on Finite Dynamical Systems” (PDF). Advances in Applied Mathematics. 26 (3): 237–251. doi:10.1006/aama.2000.0717.
  5. ^Zhang, Weixong (1999). State-space search: algorithms, complexity, extensions, and applications. Springer. ISBN 978-0-387-98832-0.
  6. ^ Jump up to:ab c Abbeel, Pieter. “Lecture 2: Uninformed Search”. UC Berkeley CS188 Intro to AI. Retrieved 30 October 2019.
  7. ^Abbeel, Pieter. “Lecture 3: Informed Search”. UC Berkeley CS

Ofer Abarbanel – Executive Profile

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library

Ofer Abarbanel online library