En informática , un espacio de estados es un espacio discreto que representa el conjunto de todas las configuraciones posibles de un "sistema". [1] Es una abstracción útil para razonar sobre el comportamiento de un sistema dado y se utiliza ampliamente en los campos de la inteligencia artificial y la teoría de juegos .
Por ejemplo, el problema del juguete Vacuum World tiene un espacio de estados finito y discreto en el que hay un conjunto limitado de configuraciones en las que pueden estar el vacío y la suciedad. Un sistema "contra", donde los estados son los números naturales que comienzan en 1 y se incrementan con el tiempo [2] tiene un espacio de estados discreto infinito. La posición angular de un péndulo no amortiguado [3] es un espacio de estados continuo (y por lo tanto infinito).
Los espacios de estado son útiles en informática como un modelo simple de máquinas. Formalmente, un espacio de estado se puede definir como una tupla [ N , A , S , G ] donde:
Un espacio de estados tiene algunas propiedades comunes:
Por ejemplo, el mundo de la aspiradora tiene un factor de ramificación de 4, ya que la aspiradora puede terminar en 1 de 4 cuadrados adyacentes después de moverse (suponiendo que no puede permanecer en el mismo cuadrado ni moverse en diagonal). Los arcos del mundo de la aspiradora son bidireccionales, ya que se puede llegar a cualquier cuadrado desde cualquier cuadrado adyacente, y el espacio de estados no es un árbol, ya que es posible entrar en un bucle moviéndose entre 4 cuadrados adyacentes.
Los espacios de estados pueden ser infinitos o finitos, y discretos o continuos.
El tamaño del espacio de estados para un sistema dado es el número de posibles configuraciones del espacio. [3]
Si el tamaño del espacio de estados es finito, calcular el tamaño del espacio de estados es un problema combinatorio . [4] Por ejemplo, en el rompecabezas de las ocho reinas , el espacio de estados se puede calcular contando todas las formas posibles de colocar 8 piezas en un tablero de ajedrez de 8x8. Esto es lo mismo que elegir 8 posiciones sin reemplazo de un conjunto de 64, o
Esto es significativamente mayor que el número de configuraciones legales de las damas, 92. En muchos juegos, el espacio de estados efectivos es pequeño en comparación con todos los estados alcanzables/legales. Esta propiedad también se observa en ajedrez , donde el espacio de estados efectivos es el conjunto de posiciones que se pueden alcanzar mediante movimientos legales del juego. Esto es mucho más pequeño que el conjunto de posiciones que se pueden lograr colocando combinaciones de las piezas de ajedrez disponibles directamente en el tablero.
Todos los espacios de estados continuos pueden describirse mediante una función continua correspondiente y, por lo tanto, son infinitos. [3] Los espacios de estados discretos también pueden tener un tamaño infinito ( contablemente ), como el espacio de estados del sistema "contador" dependiente del tiempo, [2] similar al sistema en la teoría de colas que define el número de clientes en una fila, que tendría un espacio de estados {0, 1, 2, 3, ...}.
Explorar un espacio de estados es el proceso de enumerar los posibles estados en busca de un estado objetivo. El espacio de estados de Pacman , por ejemplo, contiene un estado objetivo cuando se han comido todas las bolitas de comida y se explora moviendo a Pacman por el tablero. [5]
Un estado de búsqueda es una representación comprimida de un estado mundial en un espacio de estados y se utiliza para la exploración. Los estados de búsqueda se utilizan porque un espacio de estados a menudo codifica más información de la necesaria para explorar el espacio. Comprimir cada estado mundial a solo la información necesaria para la exploración mejora la eficiencia al reducir la cantidad de estados en la búsqueda. [5] Por ejemplo, un estado en el espacio de Pacman incluye información sobre la dirección en la que se encuentra Pacman (arriba, abajo, izquierda o derecha). Dado que no cuesta nada cambiar las direcciones en Pacman, los estados de búsqueda para Pacman no incluirían esta información y reducirían el tamaño del espacio de búsqueda por un factor de 4, uno por cada dirección en la que Pacman podría estar mirando.
Los algoritmos de búsqueda estándar son eficaces para explorar espacios de estados discretos. Los siguientes algoritmos muestran tanto completitud como optimalidad en la búsqueda de un espacio de estados. [5] [6]
Estos métodos no se extienden naturalmente a la exploración de espacios de estados continuos. Explorar un espacio de estados continuos en busca de un estado objetivo dado es equivalente a optimizar una función continua arbitraria , lo cual no siempre es posible (véase optimización matemática) .
