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 determinado y se usa 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 discreto en el que hay un conjunto limitado de configuraciones en las que pueden estar la aspiradora y la suciedad. Un sistema de "contador", 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 tanto infinito).
Los espacios de estados son útiles en informática como modelo simple de máquinas. Formalmente, un espacio de estados se puede definir como una tupla [ N , A , S , G ] donde:
Un espacio de estados tiene algunas propiedades comunes:
Por ejemplo, Vacuum World 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 de Vacuum World 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, discretos o continuos.
El tamaño del espacio de estados para un sistema dado es el número de configuraciones posibles 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 reinas, 92. En muchos juegos, el espacio de estados efectivo es pequeño en comparación con todos los estados legales/alcanzables. Esta propiedad también se observa en el ajedrez , donde el espacio de estados efectivo es el conjunto de posiciones que pueden alcanzarse mediante movimientos legales para el 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 tanto, son infinitos. [3] Los espacios de estados discretos también pueden tener un tamaño ( contablemente ) infinito, 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 línea, que tendría espacio de estados {0, 1, 2, 3, ...}.
Explorar un espacio de estados es el proceso de enumerar posibles estados en busca de un estado objetivo. El espacio de estado de Pacman , por ejemplo, contiene un estado objetivo cada vez que 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 del mundo solo con 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 mira Pacman (arriba, abajo, izquierda o derecha). Dado que no cuesta nada cambiar de dirección en Pacman, los estados de búsqueda de Pacman no incluirían esta información y reducirían el tamaño del espacio de búsqueda en un factor de 4, uno para 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 exhiben integridad y optimización 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 continuo en busca de un estado objetivo dado equivale a optimizar una función continua arbitraria , lo cual no siempre es posible; consulte optimización matemática .
