STRIPS

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En Inteligencia artificial, STRIPS (Stanford Research Institute Problem Solver) es un generador de planes automatizado. El mismo nombre fue utilizado más tarde para referirse al lenguaje formal de las entradas de este generador de planes.

Definición[editar]

Una instancia de STRIPS se compone de:

  • Un estado inicial.
  • La especificación de estados de meta.
  • Un conjunto de acciones, para cada una de las cuales se incluyen:
    • Precondiciones.
    • Postcondiciones.

Matemáticamente, una instancia de STRIPS es una tupla \langle P,O,I,G \rangle, donde:

  • P es un conjunto de condiciones (es decir, variables proposicionales).
  • O es un conjunto de operadores (es decir, acciones); cada operador es también una tupla \langle \alpha, \beta, \gamma, \delta \rangle, donde cada elemento es un conjunto de condiciones:
    • \alpha representa a las condiciones que deben ser verdaderas para que la acción pueda ejecutarse.
    • \beta representa a las condiciones que deben ser falsas para que la acción pueda ejecutarse.
    • \gamma representa a las condiciones se hacen verdaderas si se ejecuta la acción.
    • \delta representa a las condiciones se hacen falsas si se ejecuta la acción.
  • I es el estado inicial, dado por un conjunto de condiciones que son inicialmente verdaderas (todas las demás se asumen falsas).
  • G es la especificación del estado de meta, que está dada por una dupla \langle N,M \rangle, que especifica qué condiciones deben ser verdaderas y cuales falsas para considerar a un estado como meta.

Un plan para una instancia es una secuencia de operadores que puede ser ejecutada desde el estado inicial, y que lleva hasta un estado meta.

Formalmente, un estado es un conjunto de condiciones, y se representa por el conjunto de condiciones que son verdaderas en él. Las transiciones entre estados se modelan mediante una función de transición, que es una función que mapea estados en otros estados que resultan de aplicarles acciones a los primeros. Ya que los estados se representan por conjuntos de acciones, la función de transición emparentada con la instancia STRIPS \langle P,O,I,G \rangle es una función:

\operatorname{sucesor}: 2^P \times A \rightarrow 2^P,

donde 2^P es el conjunto de todos los subconjuntos de P, y por lo tanto es el conjunto de todos los posibles estados.

La función de transición puede definirse, asumiendo que las acciones siempre pueden ser ejecutadas pero no tienen efecto si sus precondiciones no se cumplen, como:

\operatorname{sucesor}(C,\langle \alpha,\beta,\gamma,\delta \rangle) = (C \backslash \delta) \cup \gamma         Si (\alpha \subseteq C /and \beta \cap C = \varnothing)
  = P De otra forma

La función \operatorname{sucesor} puede extenderse para secuencias de acciones mediante ecuaciones recursivas:

\operatorname{sucesor}(C,[\,\,]) = C
\operatorname{sucesor}(C,[a_1,a_2,\ldots,a_n])=\operatorname{sucesor}(\operatorname{sucesor}(C,a_1),[a_2,\ldots,a_n])

Un plan para una instancia de STRIPS es una secuencia de acciones cuya ejecución ordenada produce un estado que satisface las condiciones de meta, a partir del estado inicial. Formalmente, [a_1,a_2,\ldots,a_n] es un plan para G = \langle N,M \rangle si F=\operatorname{sucesor}(I,[a_1,a_2,\ldots,a_n]) satisface:

  • N \subseteq F
  • M \cap F = \varnothing

Un problema STRIPS de ejemplo[editar]

Hay un mono en el laboratorio, y quiere bananas. Hay tres ubicaciones en el laboratorio: A, B y C. El mono está en la ubicación A. Hay una caja en la ubicación C. Hay bananas en la ubicación B, pero cuelgan del techo. El mono necesita la caja para alcanzar todas las bananas.


Estado inicial
MonoEn(A)
NivelMono(abajo)
CajaEn(C)
BananasEn(B)
Estado meta MonoTiene(Bananas)
Acciones
Acción Descripción Precondición Poscondición
Ir(X, Y) Ir de X a Y MonoEn(X), NivelMono(abajo) \negMonoEn(X), MonoEn(Y)
Trepar(X) Subirse a la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Abajo) \negNivelMono(Abajo), NivelMono(Arriba)
Bajarse(X) Bajarse de la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Arriba) \negNivelMono(Arriba), NivelMono(Abajo)
LlevarCaja(X, Y) Llevar la caja de X a Y MonoEn(X), CajaEn(X), NivelMono(Abajo) \negCajaEn(X), CajaEn(Y), \negMonoEn(X), MonoEn(Y)
TomarBananas(X) Tomar las bananas en la ubicación X MonoEn(X), BananasEn(X), NivelMono(Arriba) MonoTiene(Bananas)