STRIPS (STanford Research Institute Problem Solver) , es un lenguaje clásico utilizado en planificación. Si bien ya no se utiliza el planficador STRIPS, existen numerosos planificadores que utilizan lenguajes “a la STRIPS”. Aquellos problemas de planificación que pueden representarse mediante STRIPS, se dice que tratan en un mundo STRIPS.
Representación de Estados
En STRIPS los estados son representados mediante conjunciones de literales (se representan por un conjunto de hechos que son verdaderos en un estado del mundo) sin variables ni funciones .
En el caso del problema de Alquilar una película, comprar una pizza y cargar nafta el estado inicial se podrá representar como:
En(Casa) ? ?Tiene(Pelicula) ? ? Tiene(Pizza)? ?TieneMucha(auto, nafta)
En forma similar al Prolog, muchos planificadores utilizan la hipótesis del mundo cerrado, es decir que si un hecho no está representado explícitamente entonces es falso. A esto se le llama en Prolog negación por falla.
Representación de Objetivos
Los objetivos son también una conjunción de literales en donde pueden haber variables. Una meta puede ser por ejemplo:
En(Case) ^Tiene(Pelicula) ^ Tiente(Pizza) ^ TieneMucha(auto, nafta)
O con variables:
En(x) ^ Alquila(x,Pelicula)
La diferencia entre las consultas dadas a Prolog en forma de meta y la meta de un planificador, es que en el primer caso se trata de demostrar la verdad de la meta a partir de hechos y reglas en el programa lógico, mientras que los planificadores se trata de encontrar una secuencia de acciones (plan) que haga verdadera la meta.
Las variables se consideran existencialmente cuantificadas.
Representación de Acciones
Una acción u operador se representa por tres elementos:
-
Especificación de la acción: Nombre de la acción y parámetros.
-
Precondiciones: Establecen los hechos que deben ser verdaderos antes de poder aplicar la acción. Las acciones están inherentemente ligadas a las precondiciones. Se explicitan mediante una conjunción de literales positivos.
-
Efectos: Conjunción de literales, posiblemente negados que describen como cambia el mundo al ejecutarse la acción. Los efectos pueden dividirse en dos listas DelList y AddList
La AddList indica los hechos que son agregados al estado del mundo y la DelList los hechos que como consecuencia de la acción son negados.
Veamos un ejemplo de un operador que representa la acción de prender un objeto (por ejemplo el televisor). Para prender el televisor es necesario que esté apagado, siendo entonces ésta la precondición. Una vez ejecutada la acción de prender, entonces está prendido y no está apagado, siendo éstos los efectos.
O = Op(Action: Prender(x), Prec: Apagado(x), Effect: Prendido(x), -Apagado(x))
En donde:
AddList(O) = Prendido(x)
DelList(O) = Apagado(x)
Prec(O)= Apagado(x)
Los operadores con variables forman lo que llama operadores esquema que denotan una familia operadores (uno para cada instanciación posible) . Esto es similar a lo que hacíamos con los axiomas esquemas.
Un operador O es aplicable en un estado S cuando es posible instanciar las variables que contiene, de tal forma que las precondiciones sean válidas en S. Es decir, un operador es aplicable cuando:
Definimos al estado sucesor de la aplicación del operador O en S a un estado donde son verdaderos los efectos de O. Sea Sx el estado sucesor de S luego de la acción O se verifica que:
Con ambas listas instanciadas.