En inteligencia artificial y programación de computadoras , la planificación del espacio estatal es un proceso que se utiliza en el diseño de programas para buscar datos o soluciones a problemas. En un algoritmo informático que busca un dato en una estructura de datos, por ejemplo, un programa que busca una palabra en un diccionario informático, el espacio de estado es un término colectivo para todos los datos que se van a buscar. 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 una meta, para encontrar un procedimiento o el mejor procedimiento para lograr la meta. El universo de posibles soluciones a buscar se denomina espacio de estados. Planificación del espacio estatal es el proceso de decidir qué partes del espacio de estado buscará el programa y en qué orden.
Definición
Los algoritmos de planificación clásica más simples (ver Planificación automatizada ) son los algoritmos de búsqueda de espacio de estados. Estos son algoritmos de búsqueda en los que el espacio de búsqueda es un subconjunto del espacio de estado: 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 las principales muestras de planificación espacial estatal .
Búsqueda hacia adelante
La búsqueda hacia adelante es un algoritmo que busca hacia adelante desde el estado inicial del mundo para tratar de encontrar un estado que satisfaga la fórmula del objetivo.
Búsqueda hacia adelante (O, s 0 , g)
s = s 0 P = el plan vacío círculo si s satisface g entonces devuelve P aplicable = {a | a es una instancia básica de un operador en O, y el precond (a) es verdadero en s} si aplica = ∅ entonces devuelva el fallo elegir de forma no determinista una acción a de la que corresponda s = γ (s, a) P = Pa
Búsqueda hacia atrás
La búsqueda hacia atrás es un algoritmo que comienza con el estado objetivo y vuelve a su estado inicial. Este método a veces se denomina "propagación inversa".
Búsqueda hacia atrás (O, s 0 , g)
s = s 0 P = el plan vacío círculo si s satisface g entonces devuelve P relevante = {a | a es una instancia de tierra de un operador en O que es relevante para g} si es relevante = ∅ entonces devuelve el fallo elegir de forma no determinista una acción de entre las relevantes P = aP s = γ −1 (s, a)
Ver también
Referencias
- Ghallab, Malik; Nau, Dana S .; Traverso, Paolo (2004), Planificación automatizada: teoría y práctica , Morgan Kaufmann , ISBN 1-55860-856-7