Inteligencia artificial para videojuegos/Planificación automática

Introducción

La planificación es una actividad racional fundamental, y por ello, es clave en Inteligencia Artificial. De hecho, las búsquedas no son otra cosa que planificar, donde la solución obtenida a través de una secuencia de operaciones es es el plan.
Aunque las búsquedas son un un tipo de planificación, utilizamos el término planificación automática para referirnos a problemas más complejos.
Para profundizar y ser prácticos se necesita una representación factorizada mediante variables. Esto nos anticipa cuestiones de conocimiento y de lógica.

Planificación clásica

Se trata de una resolución basada en objetivos, asumiendo visibilidad completa, estados estáticos y deterministas que sólo altera un único resolutor en dominios estructurados.
Se caracteriza por tener un estado inicial, operadores disponibles en cada estado, precondición y efecto del operador y prueba de objetivo.
Podemos hablar de una mala complejidad teórica, pues puede haber grandes cantidades de estados; aunque puede ser sencillo hallar un plan que no sea óptimo.

Lenguaje de especificación

Para especificar el problema y el dominio usaremos una versión “adaptada” de PDDL (Planning Domain Definition Languaje) con las siguientes características:

Se trabaja con una especie de “base de datos” con conjunciones de predicados lógicos.
También con esquemas de operador que definen implícitamente operadores y modelo de transición.
Listas de borrado y de añadido de lo que cambia en cada paso.

Ejemplo:

//Estado inicial
   Avión (Iberia1430)
   Avión (Iberia3951)
   Ciudad (Madrid)
   Ciudad (Barcelona)
   Ciudad (Sevilla)
   En (Iberia1430, Barcelona)
   En (Iberia3951, Sevilla)

//Objetivo
   En (Iberia1430, Madrid)
   En (a, Sevilla)

//Operadores
   Volar (a, c1, c2)
   Precondición: En (a, c1) ⋀ Avión (a) ⋀ Ciudad (c1) ⋀ Ciudad (c2)
   Efecto: ¬En (a, c1) ⋀ En (a, c2)
   Jubilar (a, c)
   Precondición: En (a, c) ⋀ Avión (a)
   Efecto: ¬En (a, c) ⋀ ¬Avión (a)

//Aplicando Volar (a, c1, c2) a Iberia1430, Barcelona, Madrid resulta en este estado
//Que además pasaría la prueba de objetivo.
   Avión(Iberia1430)
   Avión(Iberia3951)
   Ciudad(Madrid)
   Ciudad(Barcelona)
   Ciudad(Sevilla)
   En(Iberia1430, Madrid)
   En(Iberia3951, Sevilla)

Búsqueda hacia delante y hacia atrás

La definición de un problema de planificación es un problema de búsqueda todavía más complejo, porque cada operador se puede aplicar de muchas formas con la ventaja de que, igual que buscamos operadores aplicables hacia delante, podemos buscar operadores relevantes hacia atrás (desde el objetivo).

Hacia delante (progresión)

Desde que nació la planificación (≃1961) hasta 1998 o así, se consideraba absurdo. Luego se pudo hacer, con heurísticas específicas del dominio muy precisas (nada fáciles de encontrar).
Hoy día lo hacemos derivando automáticamente potentes heurísticas independientes del dominio.

Hacia atrás (regresión)

Es una búsqueda sobre conjuntos de estados (incluso con variables sin instanciar) empezando por cualquiera que cumpla el objetivo y aplicando el operador invertido para ir del conjunto actual a otro que cumpla la precondición, poniendo (o quitando) todo lo que quita (o pone) el efecto.

Obtención de heurísticas

Planifiquemos hacia delante o hacia atrás, una buena heurística es imprescindible.
Se podían obtener heurísticas admisibles relajando el problema a uno donde es fácil conocer el coste. En representaciones atómicas del dominio hacía falta usar mucho ingenio, ahora hay otras formas.
Una IA es capaz de trabajar sobre representaciones factorizadas de los esquemas de operador, y derivar automáticamente desde allí muchas heurísticas útiles:

Añadir más conexiones a los estados: Ignorando la precondición total o parcialmente o ignorando la lista de borrado.
Reducir número de estados agrupándolos: Ignorando algunas proposiciones lógicas o descomponiendo el objetivo (asumiendo que puedes planificar cada parte y luego sumar el total).

Definir el problema relajado, la heurística, calcularla y aplicarla debe salir más barato que resolver el problema original.

Grafo de planificación

Es una estructura de datos que ayuda a conseguir buenas heurísticas.
Como representar todo el árbol tiene coste exponencial, se aproxima polinómicamente. A veces descubre que el objetivo es inalcanzable, y siempre da una estimación admisible de su coste. Se trata de un grafo dirigido y por niveles, siendo éstos todos los operadores que se podrían aplicar y lo que podría tener el estado resultante.
Por ejemplo, en el problema de la tarta:

   Init(Have(Cake))
   Goal(Have(Cake) ^ Eaten(Cake))
   Action(Eat(Cake))
      PRECOND: Have(Cake)
      EFFECT: ¬ Have(Cake) ^ Eaten(Cake)
   Action(Bake(Cake))
      PRECOND: ¬ Have(Cake)
      EFFECT: Have(Cake)

Tras 5 niveles (Estado0, Operador0, Estado1, Operador1 y Estado2) este grafo se ha estabilizado.
El grafo de planificación sólo sirve para estados que se componen de proposiciones lógicas sin variables.
Se produce el mutex entre operadores:

Efectos inconsistentes, el efecto de un operador niega el de otro.
Interferencia, el efecto de un operador niega la precondición del otro.
Necesidades en conflicto, la precondición de un operador niega la del otro.

Entre proposiciones del mismo nivel hay un soporte inconsistente, si una proposición niega otra, o si todos los operadores que generan una son mutex de los operadores que generan la otra.
Una vez construido el grafo, es rico en información:

Si no vemos alguna proposición del objetivo en el último nivel, es que el problema es irresoluble.
Se puede estimar lo que cuesta conseguir una proposición del objetivo con su coste de nivel (Gi), primer nivel en el que aparece en el grafo.
Una conjunción de proposiciones del objetivo se pueden estimar de varias formas, como el máximo coste de nivel de todas ellas, la suma de todos sus costes de nivel o el coste del nivel en que están todas sin mutex.

Algoritmo Graphplan

Propuesto en 1995, consigue la solución (el plan) del propio grafo de planificación.

función GRAPHPLAN (problema) devuelve solución o fallo
   grafo ← GRAFO-PLANIFICACIÓN-INICIAL (problema)
   objetivos ← CONJUNCIONES (problema.objetivo)
   nobuenos ← tabla hash vacía // Pares de objetivos incompatibles a cierto nivel
   para paso = 0 hasta ∞ hacer
      si no hay mutex en objetivos en EstadoNivel del grafo entonces
         solución ← EXTRAER-SOLUCIÓN // Búsqueda hacia atrás especial
         (grafo, objetivos, NIVELES (grafo), nobuenos)
         si solución ≠ fallo entonces devolver solución
      si grafo y nobuenos están estabilizados entonces devolver fallo
      grafo ← EXPANDIR-GRAFO (grafo, problema)

Otros tipos de planificación clásica

Hay más enfoques clásicos:

Satisfactibilidad booleana.
Cálculo situacional.
Satisfacción de restricciones.
Refinamiento de planes parcialmente ordenados.

En videojuegos el primer planificador práctico fue GOAP (2004), que se usó en F.E.A.R (2005) y posteriormente en otros títulos como Deus Ex y Tomb Raider.

Información adicional sobre GOAT

La planificación de acción orientada a objetivos GOAP es un sistema de inteligencia artificial para agentes que les permite planificar una secuencia de acciones para satisfacer un objetivo en particular. La secuencia particular de acciones depende no solo del objetivo sino también del estado actual del mundo y del agente. Esto significa que si se proporciona el mismo objetivo para diferentes agentes o estados del mundo, puede obtener una secuencia de acciones completamente diferente, lo que hace que la IA sea más dinámica y realista. Veamos un ejemplo:

Tenemos un agente, un triturador de madera, que toma troncos y los corta en leña. El chopper se puede suministrar con el objetivo MakeFirewood y tiene las acciones ChopLog, GetAxe y CollectBranches.

La acción ChopLog convertirá un tronco en leña, pero solo si el cortador de madera tiene un hacha. La acción GetAxe le dará un hacha al cortador de madera. Finalmente, la acción CollectBranches también producirá leña, sin requerir un hacha, pero la leña no será tan alta en calidad.

Cuando le damos al agente el objetivo de MakeFirewood, obtenemos estas dos secuencias de acción diferentes:

Necesita leña -> GetAxe -> ChopLog = hace leña
Necesita leña -> CollectBranches = hace leña

Si el agente puede obtener un hacha, entonces puede cortar un tronco para hacer leña. Pero tal vez no puedan conseguir un hacha; Entonces, solo pueden ir y recoger ramas. Cada una de estas secuencias cumplirá el objetivo de MakeFirewood.

GOAP puede elegir la mejor secuencia en función de las condiciones previas disponibles. Si no hay un hacha a mano, entonces el cortador de madera tiene que recurrir a recoger ramas. Recoger las ramas puede llevar mucho tiempo y producir leña de mala calidad, por lo que no queremos que funcione todo el tiempo, solo cuando es necesario.

GOAP desacopla las acciones entre sí para poder centrarse en cada acción individualmente. Esto hace que el código sea modular, y fácil de probar y mantener. Si se desea agregar otra acción, se puede introducir simplemente y no se tiene que cambiar ninguna otra acción. Además, se puede agregar o eliminar acciones sobre la marcha para cambiar el comportamiento de un agente para que sean aún más dinámicos.

Referencia

Participantes

Federico Peinado.
David González Jiménez.
Jorge Rodríguez García
Gonzalo Sanz Lastra