Planificación del espacio estatal

En inteligencia artificial y programación informática , la planificación del espacio de estados es un proceso utilizado en el diseño de programas para buscar datos o soluciones a problemas. En un algoritmo informático que busca una estructura de datos en busca de un fragmento de datos, por ejemplo, un programa que busca una palabra en un diccionario informático, el espacio de estados es un término colectivo para todos los datos que se buscarán. De manera similar, los programas de inteligencia artificial a menudo emplean un proceso de búsqueda a través de un universo finito de posibles procedimientos para alcanzar un objetivo, para encontrar un procedimiento o el mejor procedimiento para lograr el objetivo. El universo de posibles soluciones que se buscarán se llama espacio de estados. La planificación del espacio de estados es el proceso de decidir qué partes del espacio de estados buscará el programa y en qué orden.

Los algoritmos de planificación clásicos más simples (ver Planificación automatizada ) son los algoritmos de búsqueda en el espacio de estados. Se trata de algoritmos de búsqueda en los que el espacio de búsqueda es un subconjunto del espacio de estados: cada nodo corresponde a un estado del mundo, cada arco corresponde a una transición de estado y el plan actual corresponde a la ruta actual en el espacio de búsqueda. La búsqueda hacia adelante y la búsqueda hacia atrás son dos de los principales ejemplos de planificación en el espacio de estados .

La búsqueda hacia adelante es un algoritmo que busca hacia adelante desde el estado inicial del mundo para intentar encontrar un estado que satisfaga la fórmula objetivo.

Búsqueda hacia adelante (O, s ₀ , g)

s = s 0
 P = el plan vacío
 bucle
     Si s satisface g entonces devuelve P
     aplicable = {a | a es una instancia básica de un operador en O, y precond(a) es verdadero en s}
     Si corresponde = ∅ entonces devuelve el error
     Elija de forma no determinista una acción entre las aplicables
     s = γ(s, a)
     P = Pa

La búsqueda hacia atrás es un algoritmo que comienza con el estado objetivo y retrocede hasta su estado inicial. Este método a veces se denomina "propagación hacia atrás".

Búsqueda hacia atrás (O, s ₀ , g)

s = s 0
 P = el plan vacío
 bucle
     Si s satisface g entonces devuelve P
     relevante = {a | a es una instancia básica de un operador en O que es relevante para g}
     Si es relevante = ∅ entonces devuelve el error
     Elija de forma no determinista una acción entre las relevantes
     P = aP  
     s = γ −1 (s, a)

• Espacio de estados
• Búsqueda en el espacio de estados

• Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004). Planificación automatizada: teoría y práctica. Morgan Kaufmann . ISBN 1-55860-856-7.