Manual del estudiante de Ingeniería en Sistemas de UTN/Inteligencia Artificial/Planificación

Un programa de planeamiento genera una estrategia para lograr determinadas metas a partir de una situación inicial. El tomar decisiones obvias o importantes en forma temprana permite reducir el factor de ramificación que genera una búsqueda, disminuyendo la necesidad de backtraking. El planificador puede trabajar independientemente sobre las submetas, aunque luego necesitará combinar los subplanes en un plan global. Esto presenta especial dificultad cuando avanzar sobre una submeta afecta a otra.

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 leguaje 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.
  • Poscondiciones.

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 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)

Generación de planes

La descripción de los operadores en planeamiento permite proceder con un enfoque hacia atrás, que regresa desde la descripción parcial de un estado hasta la descripción parcial del estado precedente. Este enfoque es preferible en los casos en que la descripción del objetivo tiene pocos elementos, para los cuales hay pocos operadores que pueden producirlos.

El planificador de orden parcial

El planificador de orden parcial trabaja independientemente sobre las submetas, sin atender al orden de las operaciones. Se establecen vínculos causales entre los estados, que indicarán que una operación lleva de un estado al otro. Se formará así un grafo llamado plan de orden parcial. Una solución parcial es una linealización del plan de orden parcial.

• Una precondición/submeta puede considerarse alcanzada si no puede ser removida por un paso posterior.
• Un plan es completo si se han alcanzado todas las precondiciones.
• Un plan es consistente si:
  • No hay ciclos en los vínculos.
  • No hay conflictos entre los vínculos causales.
• Un plan consistente y completo es una solución.

Toda linealización del plan de orden parcial es una solución de orden total, que al ejecutarse partiendo desde el estado inicial, hará que se llegue al estado meta.

Si se usa la estrategia de mínimo compromiso, las variables que no sean parámetros de un operador, como no necesitan matchear con nada por el momento, no quedarán ligadas, y se dejará esa decisión para más adelante, evitando el backtracking.