STRIPS

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

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

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) $\neg$MonoEn(X), MonoEn(Y) Trepar(X) Subirse a la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Abajo) $\neg$NivelMono(Abajo), NivelMono(Arriba) Bajarse(X) Bajarse de la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Arriba) $\neg$NivelMono(Arriba), NivelMono(Abajo) LlevarCaja(X, Y) Llevar la caja de X a Y MonoEn(X), CajaEn(X), NivelMono(Abajo) $\neg$CajaEn(X), CajaEn(Y), $\neg$MonoEn(X), MonoEn(Y) TomarBananas(X) Tomar las bananas en la ubicación X MonoEn(X), BananasEn(X), NivelMono(Arriba) MonoTiene(Bananas)

• Datos: Q996052