planificación del espacio estatal

En inteligencia artificial y programación informática , la planificación del espacio de estados es un proceso utilizado para diseñar programas que buscan datos o soluciones a problemas. En un algoritmo informático que busca un dato específico en una estructura de datos, por ejemplo, un programa que consulta una palabra en un diccionario, el espacio de estados es el conjunto de todos los datos que se van a buscar. De manera similar, los programas de inteligencia artificial suelen emplear un proceso de búsqueda en un universo finito de posibles procedimientos para alcanzar un objetivo, con el fin de encontrar el procedimiento óptimo para lograrlo. Este universo de posibles soluciones se denomina espacio de estados. La planificación del espacio de estados consiste en decidir qué partes del espacio de estados explorará el programa y en qué orden.

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

En los algoritmos que siguen, por "no determinista" entendemos que el algoritmo de búsqueda en grafos elegido para seleccionar la siguiente rama es arbitrario. Se puede recurrir a la fuerza bruta ( BFS , DFS , IDS , etc.), usar heurísticas ( A* , IDA* , etc.), etc. Esta elección generalmente depende de la naturaleza del problema.

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

Decimos que una acción es aplicable en un estado s si las precondiciones de esta acción son verdaderas en s .

Donde O _es el conjunto de acciones, s₀ el estado inicial y g el estado objetivo:

Búsqueda hacia adelante(O, s 0 , g) s = s 0 P = el plano vacío bucle Si s satisface g, entonces devuelve P. aplicable = {a | a es una instancia básica de un operador en O, y a es aplicable en s} Si corresponde = ∅, entonces devolver error. elegir de forma no determinista una acción a de 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 "retropropagación".

Decimos que una acción es relevante si sus efectos de adición (literales del estado convertidos en verdadero) están en G , y ninguno de sus efectos de eliminación (literales del estado convertidos en falso) está en G.

Donde O _es el conjunto de acciones, s₀ el estado inicial y g el estado objetivo:

Búsqueda hacia atrás(O, s 0 , g) s = s 0 P = el plano 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 un error. elegir de forma no determinista una acción a de entre las relevantes P = aP s = γ −1 (s, a)

• Espacio de estado
• 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.