A 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 [N, A, S, G] 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
- ^Nykamp, Duane. “State space definition”. Math Insights. Retrieved 17 November 2019.
- ^ Jump up to:ab Papernick, Norman. “Infinite States and Infinite State Transitions”. Carnegie Mellon University. Retrieved 12 November 2019.
- ^ Jump up to:ab c Nykamp, Duane. “The idea of a dynamical system”. Math Insights. Retrieved 12 November 2019.
- ^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.
- ^Zhang, Weixong (1999). State-space search: algorithms, complexity, extensions, and applications. Springer. ISBN 978-0-387-98832-0.
- ^ Jump up to:ab c Abbeel, Pieter. “Lecture 2: Uninformed Search”. UC Berkeley CS188 Intro to AI. Retrieved 30 October 2019.
- ^Abbeel, Pieter. “Lecture 3: Informed Search”. UC Berkeley CS
Ofer Abarbanel – Executive Profile
Ofer Abarbanel is a 25 year securities lending broker and expert who has advised many Israeli regulators, among them the Israel Tax Authority, with respect to stock loans, repurchase agreements and credit derivatives. Founder of TBIL.co STATX Fund.