State space (computer science)

"State space" redirects here. For other uses, see State space (disambiguation).
Vacuum World, a shortest path problem with a finite state space

In computer science, a state space is a discrete space representing 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.

  1. ^ Cite error: The named reference MISSD was invoked but never defined (see the help page).
  2. ^ Cite error: The named reference CMUINF was invoked but never defined (see the help page).
  3. ^ Cite error: The named reference MIDYNS was invoked but never defined (see the help page).