Tema 8

Razonamiento y Planificación Automática

Sistemas basados en
STRIP
 Índice
Esquema 3

Ideas clave 4
8.1. ¿Cómo estudiar este tema? 4
© Universidad Internacional de La Rioja (UNIR)

8.2. STRIPS 4
8.3. PDDL 15
8.4. GOAP 17
8.5. Referencias bibliográficas 24

A fondo 25

Test 28
 © Universidad Internacional de La Rioja (UNIR)

Planificación clásica

STRIPS PDDL GOAP

Operadores y
Definición Aplicación
propiedades
Aplicaciones Diferencias
Planificación
frente a
hacia delante
STRIPS
Planificación
hacia atrás

Heurística de
STRIPS

Razonamiento y Planificación Automática

Esquema

Tema 8. Esquema
3
 Ideas clave

8.1. ¿Cómo estudiar este tema?

En este tema trataremos de definir los planificadores tradicionales basados en la

descripción de STRIPS (Fikes y Nilsson, 1971) y su evolución en el lenguaje de
definición de planes PDDL (McDermott, Ghallab, Howe, Knoblock, Ram y Veloso,
1998).

Por último, presentaremos una adaptación de los sistemas STRIPS pensada para
sistemas con reacción en tiempo real, para poder crear sistemas que puedan
reaccionar a entornos cambiantes de modo eficiente. El sistema GOAP, ideado por
Jeff Orkin, adapta los estándares de STRIPS para estos entornos.

8.2. STRIPS

Definición y Base

Partiremos de una información que conoce a priori un agente y tenemos una

representación de los conocimientos basada en la idea de los mecanismos de
búsqueda. Por ello contaremos con:

 Un estado inicial: símbolo (s0).

© Universidad Internacional de La Rioja (UNIR)

 Un conjunto de estados sucesores producidos por una función expandir(s,a)

que a partir de un estado s y una acción a genera un estado sucesor s’.
Así, por ejemplo, a partir de un estado s7 se pueden generar los estados
sucesores (s7  {s8, s10, s12, s27, s112}).

Razonamiento y Planificación Automática

4
Tema 8. Ideas clave
  Un estado meta G, que la función meta(s) evalúa como final o no. Por ejemplo,
dado el estado s112, la función meta evalúa si G está contenido en s112, en cuyo
caso diría que s112 es un estado meta (s112  true).
 Una función de coste c asociado a la aplicación de una acción a en un estado s.
Por ejemplo, aplicar la acción a en el estado s7 tendría un coste, c(s7 , a)  5.
 Una o varias funciones heurísticas: h* (s7  235).

Con esta información tenemos una abstracción completa de las características de

los estados, pero en esta abstracción tenemos una pérdida de información acerca
de la conformación de los estados (por ejemplo: «¿bloque C encima de bloque A?»,
«¿el agente se encuentra en Praga?»)

Esto nos genera varios problemas potenciales que derivan en un aumento de la

complejidad para poder representar la información y el conocimiento (por ejemplo,
para definir la función expandir), y hace más difícil el mantenimiento del
conocimiento. Es por esto por lo que buscamos otros mecanismos para poder
trabajar con la información en estos agentes inteligentes. Para ello, tendremos en
cuenta que los estados presentan una «estructura» y definiremos un estado no por
su nombre, sino por el conjunto de sus propiedades o proposiciones.

Elementos básicos de STRIPS

A principios de los años 70, se creó el lenguaje estandarizado para formalizar un

problema de planificación (Fikes, 1971). STRIPS fue creado para describir los
componentes necesarios para que un agente planificador pudiera resolver
problemas complejos en los que la estructura de los estados era determinante para
entender qué proceso sería necesario llevar a cabo para resolver el problema de
© Universidad Internacional de La Rioja (UNIR)

modo racional.

Este estándar sigue muy vigente en la definición de paradigmas de planificación

actual con la creación de nuevos modelos como son PDDL (Planning Domain

Razonamiento y Planificación Automática

5
Tema 8. Ideas clave
 Definition Language, de sus siglas en Ingles) y/o GOAP (Goal-Oriented Action
Planning, de sus siglas en Ingles).

Para esta sección emplearemos el problema de apilado de bloques, ver figura 1,

(dominio del mundo de los bloques), en el que, desde una configuración de partida
de un conjunto de bloques, deseamos crear una configuración final de los mismos
por medio de operaciones de apilado y desapilado.

Figura 1. Bloques apilados.

Existen dos componentes básicos en una definición de problema de STRIPS:

 Proposiciones
 Operadores

Proposiciones

Para describir un estado, tendremos en cuenta el conjunto de proposiciones

relevantes que lo caracteriza. Estas proposiciones, inicialmente, son expresadas por
© Universidad Internacional de La Rioja (UNIR)

medio de valores booleanos, es decir, de existencia o no existencia en el estado

actual.

Razonamiento y Planificación Automática

6
Tema 8. Ideas clave
 Por ejemplo, para el problema del mundo de los bloques, con tres bloques
tendríamos las siguientes proposiciones relevantes para caracterizar estados:

Figura 2. Proposiciones para el mundo de los bloques.

Para el caso del ejemplo de la figura 1, el estado representado en la imagen estaría

formado por las siguientes proposiciones:

Figura 3. Ejemplo de proposiciones de un apilado.

Es importante tener en cuenta que no todas las combinaciones de proposiciones

son consistentes. Por ejemplo, {on(C,B), on(B,C)} no representa un estado válido
porque es inconsistente que B este sobre C y al mismo tiempo C este sobre B. A este
tipo de situaciones se les conoce como mutex.

Operadores

Expresan las acciones que el agente contempla en el problema y por las cuales
desea resolver el estado actual y transformar el entorno para alcanzar la meta o
estado final.

Se definen por una signatura del tipo:

© Universidad Internacional de La Rioja (UNIR)

<nombre>(<PC>,<A>,>E>)
Conjunto de proposiciones que deben estar presentes en un
PC Precondición estado para poder aplicar dicho operador.
Conjunto de proposiciones que se añadirán al estado tras aplicar el
A Lista de añadir operador.

Razonamiento y Planificación Automática

7
Tema 8. Ideas clave
 Son aquellas proposiciones que se quitarán del estado tras la
E Lista de eliminar aplicación del operador. Debería ser un subconjunto de PC.

Tabla 1. Componentes de un operador de STRIPS.

Figura 4. Ejemplos de operadores en el mundo de los bloques.

En el esquema definido por STRIPS, los operadores se ejecutan teniendo en cuenta

que un operador sea aplicable. Diremos que un operador es aplicable a un estado si
las precondiciones del operador son un subconjunto del estado S: PC(Op) ⊆ S.

Cuando aplicamos un operador a un estado S, produciremos un nuevo estado S’

derivado en el cual deberemos eliminar las proposiciones descritas en E y
añadiremos las presentes en A.

S’ ← S – E(Op) ∪ A(Op)

Y asumiremos que, todas aquellas proposiciones que no se especifican, no se dan y,

aquellas que no se modifican, se quedan como estaban. Esto se define como la
asunción de mundo cerrado.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

8
Tema 8. Ideas clave
 Figura 5. Esquema de ejecución de un operador STRIPS.

Planificación hacia adelante

La primera idea que nos surge para resolver un problema de planificación

expresado por medio de estos operadores y propiedades STRIPS es crear una
planificación que explore el espacio de búsqueda de estados, comenzando desde el
estado inicial, y aplicando operadores como se hace en los problemas de búsqueda
normales.

De este modo, y asumiendo el proceso de exploración y búsqueda que se basa en la

existencia de un conjunto de acciones candidatas en un estado determinado,
crearemos dicha función de expansión por medio de la identificación de todos
© Universidad Internacional de La Rioja (UNIR)

aquellos operadores que sean aplicables en el estado. Una vez identificamos todos
los operadores aplicamos la función de expansión (S, a) para todo a que
pertenezcan a los operadores. Generando de esta manera nuevos estados S’ que
serán los nodos hijos del estado S.

Razonamiento y Planificación Automática

9
Tema 8. Ideas clave
 Con esta idea, aplicamos algoritmos como los de búsqueda en amplitud,
profundidad e incluso búsquedas heurísticas de A*.

Figura 6. Ejemplo de planificación hacía adelante.

Pero rápidamente nos damos cuenta de que el factor de ramificación es muy

elevado y supone un problema porque el estado inicial se describe por todas las
proposiciones que podrían ser relevantes (por ejemplo, las posiciones de diez
bloques) y la descripción del estado meta suele ser parcial, es decir, solo contiene lo
que realmente importa (por ejemplo, las posiciones de tres bloques).

Planificación regresiva o hacia atrás

Dada la problemática de la planificación hacía adelante, surge la idea de aplicar

operadores en orden inverso; es decir, para poder reducir el conjunto de
propiedades no satisfechas de estado meta, aplicamos operadores de tal modo que
podamos conseguir encontrar la secuencia de operadores que nos regresan desde
el estado meta hasta el estado inicial.
© Universidad Internacional de La Rioja (UNIR)

Regresar un estado S’ por un operador Op consiste en encontrar el conjunto de

proposiciones menos restrictivo (más débil) que permitiría aplicar el operador al
estado S. Para alcanzar dicho conjunto, lo que hacemos es eliminar del estado la
lista de A del operador y añadir aquellos elementos que no tenemos en PC.

Razonamiento y Planificación Automática

10
Tema 8. Ideas clave
 S ← S’ – A(Op) ∪ PC(Op)

Pero para conseguir la aplicabilidad de dicho operador, ningún elemento de S’ es

eliminado (e. d.: S’ ∩ E(Op) = ∅).

Hay que tener cuidado porque en este proceso de aplicación no todos los estados
que se obtienen de la regresión son consistentes.

Figura 7. Regresión de un estado STRIPS de S’->S.

Figura 8. Ejemplo de regresión en el mundo de los bloques. Eliminación de los estados inconsistentes.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

11
Tema 8. Ideas clave
 Heurística STRIPS

Aun contando con un factor de ramificación menor y un crecimiento de la

exploración guiado por las metas, debemos combatir la complejidad de la
planificación. Al igual que en las búsquedas, la idea es buscar un conocimiento a
priori que nos mejore la complejidad, es decir, una heurística.

La heurística STRIPS consiste en encontrar los planes parciales para alcanzar cada
una de las proposiciones que se encuentran en el estado objetivo o meta. Para
construir el plan final, concatenaremos todos los subplanes parciales que tengamos
que construir.

Podemos definir la planificación de tipo STRIPS de la siguiente manera.

Figura 9. Planificación de tipo STRIPS.

© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

12
Tema 8. Ideas clave
 Figura 10. Uso de la heurística de STRIPS.

Pero pueden surgir problemas por el orden de exploración de las soluciones:

Figura 11. El orden de exploración puede suponer problemas.

© Universidad Internacional de La Rioja (UNIR)

El orden de elección de metas y/u operadores influye en los planes obtenidos.

Razonamiento y Planificación Automática

13
Tema 8. Ideas clave
 Figura 12. Algoritmo no determinista de la heurística STRIPS.

La heurística STRIPS es una heurística fuerte que implica que las metas son
independientes, pero para conseguir alguna propiedad o proposición se puede estar
destruyendo de modo cíclico otra proposición, quedando atrapado en un bucle de
destrucción de proposiciones. De este modo, no se podría alcanzar un plan global
óptimo a partir de los subplanes parciales debido a que, por diseño, la linealización
de la heurística de STRIPS no permite intercalar acciones de dos submetas
independientes. Para poder solucionarlo, deberíamos poder intercalar operadores
de los distintos subplanes.
© Universidad Internacional de La Rioja (UNIR)

Figura 13. El plan óptimo para un caso del mundo de los cubos.

Razonamiento y Planificación Automática

14
Tema 8. Ideas clave
 Figura 14. Anomalía de Sussman

Hay metas que suponen la destrucción de submetas obtenidas: anomalía de

Sussman.

8.3. PDDL

El Planning Domain Description Language (PDDL) fue creado por Drew McDermott y
su equipo. Se basaba en los estándares especificados de STRIPS y ADL (McDermott,
1998). El objetivo inicial era crear un lenguaje común y estándar de creación de
planes para emplear como benchmark entre planificadores, y así poder comparar
agentes de planificación en competiciones o estudios. En la actualidad, es un
estándar que presenta varias versiones, desde la 1.0 a la 3.1, cada una de ellas con
diferentes niveles de expresividad (si bien es cierto que actualmente no hay ningún
planificador que soporte la versión 3.1 completa).

Se basa en una descripción de los componentes de un planificador en dos

conjuntos: uno de definición del dominio y otro de definición del problema.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

15
Tema 8. Ideas clave
 Figura 15. Definición del dominio del planificador.

Figura 16. Definición del problema.

En general, en las especificaciones de PDDL se representa el conjunto de objetos del

mundo (constantes, en mayúsculas) y se usan variables para representar cualquier
objeto del universo. Para expresar proposiciones de los objetos se emplean
símbolos de predicado y los operadores los representamos por medio de símbolos
de acciones.
© Universidad Internacional de La Rioja (UNIR)

Figura 17. Ejemplo de descripción de proposiciones. Fuente: (Graciani, 2016)

A la hora de construir un problema completo, usamos elementos atómicos formar

literales que pueden ser afirmativos o negativos. En nuestra definición de un

Razonamiento y Planificación Automática

16
Tema 8. Ideas clave
 problema pueden existir átomos y literales o fluents. Los fluents son átomos
instanciados con objetos del estado del mundo. Por ejemplo, SOBRE (B, A) es un
fluent que indica que el objeto B se encuentra sobre el objeto A. En toda la
definición, el elemento clave son los estados, que definiremos por medio de
conjuntos de fluents.

Figura 18. Ejemplo de objetivos en PDDL. Fuente: (Graciani, 2016).

Al igual que en la descripción de STRIPS, la hipótesis del mundo cerrado hace que
los fluents que no sean nombrados explícitamente en una descripción sean
considerados como falsos.

8.4. GOAP

El sistema Goal - Oriented Action Planning (GOAP) fue creado por Jeff Orkin en 2004
© Universidad Internacional de La Rioja (UNIR)

(Symbolic Representation of Game World State: Toward real-time planning in

games) con el fin de adaptar un sistema planificador como STRIPS a un entorno de
simulación juegos. Fue implementado por primera vez en el videojuego F.E.A.R., de
Monolith (2005) (Orkin, 2006).

Razonamiento y Planificación Automática

17
Tema 8. Ideas clave
 Puedes ver más sobre F.E.A.R en el siguiente enlace:
[Link]

Figura 19. Portada del videojuego F.E.A.R, de Monolith (2005).

Fuente: [Link]

Orkin se basó en la arquitectura de agentes C4 del MIT y extendió ideas del

planificador de STRIPS. Posee cuatro diferencias con STRIPS:

 Establece costes a las acciones con el fin de poder asignar prioridad a unas
acciones frente a otras, que es una consideración necesaria para el diseño de
agentes en videojuegos.
 Elimina las listas de añadir y eliminar objetos y las convierte en una única lista de
modificaciones del estado en la que las proposiciones pueden ser modificadas de
manera más flexible que por simple operación booleana.
 Añade precondiciones procedurales que permiten mayor flexibilidad a la hora de
© Universidad Internacional de La Rioja (UNIR)

expresar condiciones que se deban dar en el entorno para poder aplicar un

operador.
 Añade efectos procedurales con la misma filosofía de poder modificar el entorno
con mayor flexibilidad.

Razonamiento y Planificación Automática

18
Tema 8. Ideas clave
 La primera consideración es que representa las proposiciones de un estado dentro
de un vector multitipado, en lugar de considerar las proposiciones como valores
booleanos aislados.

Ejemplo:
(AtLocation, Wearing) = (Home, Tie)

Figura 20. Ejemplo de par

estado valor que representa una propiedad GOAP.

El resto de elementos de definición del dominio del problema y del entorno siguen
las especificaciones de STRIPS. Contamos con precondiciones necesarias en una
acción (operador) que produce cambios en las proposiciones del entorno para
alcanzar una meta.
© Universidad Internacional de La Rioja (UNIR)

Figura 21. Ejemplo de problema análogo en STRIPS y GOAP.

Fuente: adaptada de Orkin (2006).

Razonamiento y Planificación Automática

19
Tema 8. Ideas clave
 La idea es tener varios modelos de agente que puedan emplear el mismo motor de
planificación con solo tener que definir distintos conjuntos de acciones, lo cual es de
mucha importancia en entornos como el de los videojuegos, donde debemos
diseñar varios tipos de agentes que resuelvan el problema con distintas
capacidades.

Figura 22. Varios agentes con el mismo problema, pero varios conjuntos de acciones distintas.

Fuente: adaptada de Orkin (2006).

En tiempo de diseño, en estos entornos es importante poder tener en cuenta

distintas preferencias que caractericen a los personajes de un modo sencillo. Para
ello, en GOAP se permite precisar un coste específico de cada acción y, en el
proceso de búsqueda de planes, se puede aplicar un algoritmo como A* para hacer
una búsqueda de costes mínimos en la consecución de un plan.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

20
Tema 8. Ideas clave
 Figura 23. Aplicando distintos costes a las acciones en GOAP.
Fuente: adaptada de Orkin (2006).

Para resolver el problema de las cláusulas de mundo cerrado y permitir mecanismos

de aceleración del cómputo dentro del motor, se suprimen las listas de añadir y
eliminar y se crea una única lista de modificaciones.

Figura 24. Ejemplo de operador de STRIPS.

Fuente: adaptada de Orkin (2006).
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

21
Tema 8. Ideas clave
 Figura 25. Ejemplo de operador de GOAP.
Fuente: adaptada de Orkin (2006).

Y un vector de proposiciones multitipado para almacenar los valores que alcanzarán

las variables del estado tras la aplicación de un operador.

Figura 26. Posible vector de proposiciones para un sistema GOAP.

Entenderemos en GOAP que las acciones son clases y, como tales, representan las
precondiciones como un array de variables de estado del mundo. Estas
precondiciones serán como una función para permitir filtros adicionales. Esta
© Universidad Internacional de La Rioja (UNIR)

función permite la ejecución de cualquier trozo de código que fuera necesario.

Razonamiento y Planificación Automática

22
Tema 8. Ideas clave
 Figura 27. Acciones con precondiciones procedurales.
Fuente: Orkin (2006).

Sucede lo mismo con las acciones que se podrán programar como un efecto
procedural. Esto nos permite delegar el proceso de cambio en el entorno y
gestionar interrupciones que se puedan producir del plan en tiempo real.

Figura 28. Acciones procedurales.

Fuente: Orkin (2006).
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

23
Tema 8. Ideas clave
 Figura 29. Una acción puede suponer varios ciclos de reloj, por lo que no son atómicas.

8.5. Referencias bibliográficas

Fikes, R. y. (1971). STRIPS: A New Approach to the Application of Theorem Proving

to Problem Solving. Artificial Intelligence, 2(3-4), 189-208.

Graciani, C. y. (2016). Curso de inteligencia artificial. . Curso de inteligencia artificial.

. Sevilla: Universidad de Sevilla.

McDermott, D. G. (1998). PDDL–the planning domain definition language–version

1.2. . Yale Center for Computational Vision and Control, Tech. Rep. . CVC TR-98-
003/DCS TR-1165.

Orkin, J. (2004). Symbolic Representation of Game World State: Toward real-time

planning in games. Proceedings of the AAAI Workshop on Challenges in Game
© Universidad Internacional de La Rioja (UNIR)

Artificial Intelligence, 5, 26-30.

Orkin, J. (2006). Three states and a plan: the AI of FEAR. Proceedings of the 2006
Game Developers Conference (GDC ’06). San José, California.

Razonamiento y Planificación Automática

24
Tema 8. Ideas clave
 A fondo
GOAP

La charla de Game Developers Conference 2015 sobre GOAP.

Accede al vídeo a través del aula virtual o desde la siguiente dirección web:
[Link]

GOAP C++

Gutiérrez, C. (s.f.). GOAP AI [Mensaje en un blog]. Carlosplusplus. Recuperado de:

[Link]

Un ejemplo de programación de GOAP en un engine de C++.

© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

25
Tema 8. A fondo
 STRIPS en juegos

Becker, K. (2015). Artificial Intelligence Planning with STRIPS, a Gentle Introduction.

[Mensaje en un blog]. Primary Objecs. Recuperado de:
[Link]
strips-a-gentle-introduction/

Introducción sobre STRIPS y su aplicación en los juegos.

GOAP

Ejemplo de implementación de GOAP.

Accede a la página web a través del aula virtual o desde la siguiente dirección web:
[Link]
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

26
Tema 8. A fondo
 Jeff Orking

Página web de Jeff Orking en la que puedes encontrar información sobre el GOAP.

Accede a la página web a través del aula virtual o desde la siguiente dirección web:
[Link]

Bibliografía adicional

McDermott, D. (2000). The 1998 AI Planning Systems Competition. AI Magazine,

21(2), 35-55.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

27
Tema 8. A fondo
 Test
1. ¿Qué afirmación sobre STRIPS es verdadera?
A. STRIPS define problemas de búsqueda.
B. Los operadores STRIPS se pueden proyectar en las acciones de un agente.
C. STRIPS es un planificador de orden parcial.

2. Una propiedad definida para STRIPS es:

A. De tipo entero.
B. De tipo booleano.
C. De cualquier tipo.

3. Una planificación hacia delante:

A. Tiene un factor de ramificación potencialmente muy alto.
B. Empieza en las metas a conseguir y explora las acciones hasta el estado
inicial.
C. Se descompone en tareas.

4. Un operador de STRIPS está compuesto de:

A. Precondiciones, lista de acciones y lista de estados.
B. Precondiciones, lista de adición y lista de eliminación.
C. Precondiciones y lista de modificación.

5. PDDL es:
A. Un lenguaje estándar para la definición de problemas de planificación.
B. Un algoritmo de tareas jerárquicas.
© Universidad Internacional de La Rioja (UNIR)

C. Un estándar con una especificación única, la 1.7.

Razonamiento y Planificación Automática

28
Tema 8. Test
 6. Las acciones en GOAP:
A. Son atómicas.
B. Son secuenciales.
C. Son procedurales.

7. La heurística de STRIPS:
A. Descompone el problema en subplanes que concatena para resolver cada
una de las proposiciones abiertas en el estado meta.
B. No usa operadores.
C. Emplea planificación hacia delante.

8. Las tareas pueden tener acciones que no se implementen directamente en el

entorno:
A. Sí, porque pueden ser parte de una jerarquía de controladores.
B. No, todas las tareas deben ejecutar acciones concretas del mundo.
C. No, porque las tareas pueden descomponerse siempre en subtareas.

9. La anomalía de Sussman:
A. Deriva de las acciones que se concatenan en orden inverso.
B. Presenta el problema de destruir y construir de modo infinito submetas.
C. No se da en STRIPS.

10. En GOAP:
A. Existe una lista de añadir y otra de eliminar en los operadores.
B. Todas las acciones deben tener el mismo coste.
C. Existe una única lista de modificación de proposiciones en los operadores.
© Universidad Internacional de La Rioja (UNIR)

Razonamiento y Planificación Automática

29
Tema 8. Test