Planificación: Fundamentos (y NetLogo)

Hemos visto en una entrada anterior que un problema de Planificación es aquel en el que estamos interesados en buscar una sucesión de acciones que nos permiten pasar de un estado inicial, que nos viene dado, a uno final que verifica las condiciones deseadas.

Algunos ejemplos de problemas de planificación de juguete podrían ser los conocidos:

1. Juegos clásicos, como el problema del granjero, el lobo y el río.
2. Rompecabezas de piezas deslizantes.
3. Problemas de logística, como el problema de apilamiento de contenedores (muy similar al clásico problema del mundo de bloques), en donde no solo interesa encontrar un plan de resolución, sino aquellos que son óptimos respecto a ciertas restricciones/costes de los recursos necesarios para ejecutarlo.

Todos estos problemas de juguete se caracterizan porque tienen una descripción concisa y exacta, muy diferente del caso de los problemas del mundo real, donde la representación puede ser no tan evidente y requiere de un tiempo previo de análisis. Sin embargo, en todos ellos no nos interesa (únicamente) llegar a un estado final (que muchas veces conocemos a priori, como en los dos primeros ejemplos anteriores), sino los pasos necesarios para llegar al mismo.

Vamos a usar como ejemplo concreto a lo largo de esta entrada un problema de planificación conectado con el de mundo de bloques, y lo utilizaremos para mostrar las definiciones que nos interesan, que pueden ser comunes a muchos otros problemas de planificación (sean de juguete o del mundo real), y su representación formal. Concretamente, en este problema de cajas disponemos de:

• Algunas cajas.
• Una superficie (mesa) sobre la que podemos situar las cajas.
• Además, las cajas se pueden apilar unas sobre otras (sin límite de altura).
• Y disponemos de un brazo mecánico que puede llevar una (y solo una) caja cargada a la vez, desplazándose sobre la mesa y con capacidad para soltar y agarrar las cajas.

En consecuencia, una forma de modelar este problema sería considerando como objetos del mundo las diversas cajas que tenemos en la mesa $\{A,B,C,...\}$. Ni la propia mesa, ni el brazo mecánico, es necesario que intervengan como objetos del mundo, pero sí compondrán parte del conjunto por su relación con las cajas por medio de los predicados siguientes:

• $on(A,B)$: para reflejar que la caja $A$ está sobre la $B$.
• $ontable(A)$: para representar que la caja $A$ está directamente sobre la mesa.
• $clear(A)$: para representar que la caja $A$ no tiene nada más encima.
• $handempty$: indica que el brazo está libre (no tiene agarrada ninguna caja).
• $holding(A)$: indica que el brazo está agarrando la caja $A$.

Además, las acciones disponibles en este mundo podrían ser:

• $pickup$: recoge una caja de la mesa.
• $putdown$: suelta una caja sobre la mesa.
• $stack$: apila una caja encima de otra.
• $unstack$: recoge una caja de encima de otra.

En la aproximación que haremos para resolver el problema, vamos a dar un lenguaje genérico de especificación del Espacio de Estados asociado con el fin de poder usar mecanismos genéricos de resolución de búsqueda para resolver el problema de planificación. Como siempre sucede cuando buscamos soluciones a muchos problemas similares, nuestro interés es hacer uso de lenguajes que sean lo más generales posibles, que se puedan aplicar sin cambios sobre una bolsa, lo más grande posible, de problemas diversos.

Aunque el número de lenguajes de especificación sigue creciendo cada año, los más importantes (y en los que se basan todos los demás de una forma y otra) son:

1. STRIPS (Stanford Research Institute Problem Solver), de Richard Fikes & Nils Nilsson, 1971.
2. ADL (Action Description Language), de Edwin Pednault Pednault, 1987.
3. PDDL (Planning Domain Definition Language), de Drew McDermott, 1998 (este, o variaciones actualizadas de él, se ha convertido en el estándar actual).

En todos ellos se hace uso de una estructura interna en los estados que describen el problema por medio de una versión simplificada de la Lógica de Predicados de Primer Orden, algo más cercana a la tradicional Lógica Proposicional, una lógica en la que tenemos mejores algoritmos de resolución.

Para la descripción del mundo y de las acciones que podemos tomar en él tenemos objetos (una cantidad finita) en nuestro dominio/universo, representados por símbolos y agrupados según el tipo, y estos objetos verifican algunas propiedades y están relacionados entre sí de alguna manera (por medio de predicados). Por ejemplo, en el dominio del problema anterior, un tipo de objeto es $box$ y cada caja se representaría con un símbolo único, por ejemplo, $A$, $B$, etc. O una caja está situada sobre otra, algo que se expresa por medio de un predicado binario en el que intervienen ambas cajas ($on(A,B)$).

De esta forma, un estado del mundo es simplemente un conjunto de propiedades que se verifican sobre los conjuntos del mundo. Como es un problema de planificación, las acciones pueden modificar estos predicados, y lo que es cierto en un momento del proceso puede dejar de serlo más adelante (es una diferencia fundamental con un sistema de reglas basado en lógica clásica).

En general, en todos los modelos anteriores las acciones estás construidas a partir de 3 partes fundamentales:

1. Un nombre.
2. Una precondición, que viene dada como una fórmula lógica acerca de los predicados. Su significado es que si la precondición de la acción se verifica en el estado actual del mundo, entonces la acción se puede llevar a cabo y modificar, eventualmente, el estado actual. Concretamente, cuando esa fórmula es una conjunción de predicados, para que la acción se pueda ejecutar es necesario que el estado contenga todos los literales (predicados) positivos de la precondición y ninguno de los negativos.
3. Un efecto, que tiene dos partes claramente diferenciables: un conjunto de predicados positivos, y otro de negativos. Cuando una acción se lleva a cabo, el efecto contiene la información que modifica el mundo.

Por ejemplo, usando la librería desarrollada en NetLogo para la definición y resolución de (sencillos) problemas de planificación haciendo uso de búsquedas, podríamos dar una formalización del mundo de bloques como (observa que las variables comienzan por el símbolo ?, hemos destacado las partes de la primera acción por medio de comentarios):

set Plan:Universe A
set Plan:Predicates ["on" "ontable" "clear" "handempty" "holding"]
set Plan:actions [
  ["(pickup ?x)"                                                  ; Nombre
    ["(clear ?x)" "(ontable ?x)" "(handempty)"]                   ; Precondición 
    ["-(ontable ?x)" "-(clear ?x)" "-(handempty)" "(holding ?x)"] ; Efecto 
    [0]]                                                          ; Dominio
  ["(putdown ?x)"
    ["(holding ?x)"]
    ["-(holding ?x)" "(clear ?x)" "(handempty)" "(ontable ?x)"]
    [0]]
  ["(stack ?x ?y)"
    ["(holding ?x)" "(clear ?y)"]
    ["-(holding ?x)" "-(clear ?y)" "(clear ?x)" "(handempty)" "(on ?x ?y)"]
    [0 0]]
  ["(unstack ?x ?y)"
    ["(on ?x ?y)" "(clear ?x)" "(handempty)"]
    ["(holding ?x)" "(clear ?y)" "-(clear ?x)" "-(handempty)" "-(on ?x ?y)"]
    [0 0]]
  ]

Adicionalmente, y con el fin de poder usar algoritmos de búsqueda informada, podemos necesitar asociar un coste a cada tipo de acción del lenguaje:

set Plan:actions-costs [ ["pickup" 1] ["putdown" 1] ["stack" 1] ["unstack" 1] ]

Las características principales de STRIPS, el primer lenguaje formal que se definió para representar problemas de planificación, son:

1. Sólo se especifica aquello que cambia.
2. Hipótesis de mundo cerrado (los predicados que no se explicitan en un estado, es que son falsos en ese estado).
3. Sólo se permiten literales positivos en la descripción de estados.
4. Sólo se permiten conjunciones de literales simples en el objetivo.
5. El resultado de aplicar una acción conlleva añadir al estado actual la parte positiva del efecto de la acción, y eliminar los predicados negativos.
6. Las variables no pueden tener tipos (pero se pueden añadir predicados para simularlos, aunque puede complicar el problema).

Las diferencias que se introducen con ADL son:

1. Hipótesis de mundo abierto (lo que no se menciona no se conoce).
2. Puede haber literales positivos y negativos en los estados.
3. En el objetivo se admiten conjunciones y disyunciones.
4. La ejecución de una acción añade los literales positivos y negativos y elimina los contrarios de los positivos y los contrarios de los negativos (para eliminar contradicciones directas).
5. Las variables sí pueden tener tipos (en el ejemplo anterior, los tipos disponibles vendrían dados como sublistas dentro del Universo, y en cada acción se indica como último término a qué tipos pertenece cada variable involucrada en la acción).

Así pues, las diferencias más llamativas entre ambos lenguajes son:

El lenguaje PDDL supone un estándard que ha sido refinado en versiones posteriores (actualmente, va por la versión PDDL+) y se basa en una separación de ficheros escritos en LISP para el dominio del problema y para el universo, el estado inicial y objetivo concretos (se pueden plantear muchos problemas para un dominio concreto, de esta forma ahorramos esfuerzo), pero añade pocas novedades esenciales a los modelos anteriores, salvo una mayor potencia expresiva en el lenguaje lógico implementado.

Búsqueda de planes

Una vez definido el problema de planificación como un problema de búsqueda dirigido por medio de estados modificables por la ejecución de acciones, el siguiente paso es dar estrategias de búsqueda que saquen provecho del contexto en el que estos problemas están definidos y de la estructura específica de las acciones que modifican los estados.

Para ello, debemos declarar cuál será el estado inicial, y cuál el final:

set Plan:Initial ["(clear C)" "(clear E)" "(ontable A)"
                    "(ontable D)" "(on C B)" "(on B A)"
                    "(on E D)" "(handempty)"]
  set Plan:Goal ["(on B A)" "(on C B)" "(on D C)" "(on E D)"
                 "(clear E)" "(ontable A)" "(handempty)"]

Los dos tipos de búsqueda que podemos determinar en planificación no son distintos de aquellos que se definen en búsquedas generales, aunque los algoritmos específicos desarrollados tengan particularidades. La idea básica es aplicar algoritmos de búsqueda estándar (por ejemplo, BFS, A*, etc.) al problema de planificación, por lo que:

1. El espacio de búsqueda es un subconjunto del espacio de estados.
2. Los nodos corresponden a estados del mundo.
3. Las aristas corresponden a transiciones entre estados.
4. La ruta en el espacio de búsqueda corresponde al plan.

Búsqueda hacia adelante

La búsqueda hacia adelante es sólida (si se devuelve un plan, de hecho será una solución) y es completa (si existe una solución, se encontrará)... aunque puede llegar a ser muy ineficiente en algunos casos. A pesar de ello, como es la aplicación más directa de algoritmos conocidos, es el método que usamos en la librería desarrollada para nuestro curso de IA general.

En la versión actual de la librería disponible en NetLogo simplemente se generan todas las acciones concretas posibles a partir del esquema general y los objetos del universo, y se lanza una búsqueda (puede ser BFS o A*) hacia adelante hasta encontrar un estado que satisfaga las condiciones del objetivo.

set Plan:Herbrand-actions map [a -> (list (first a) a)] Plan:build-actions
  let plan A* Plan:Initial Plan:Goal false true

Gracias a que tenemos procedimientos de búsqueda en espacios de estados, basta que demos una idea de cómo se refleja nuestro mundo en ese espacio de estados y cómo afecta la ejecución de las acciones al cambio de los mismos:

• Un estado es, simplemente, el conjunto de literales (positivos y negativos) que se verifican en el mundo. Dos ejemplos de ello son los estados iniciales y finales que se mostraron anteriormente y que sirven como parámetros de entrada al algoritmo de búsqueda.
• Una acción $a=(p,e)$, donde $p$ es la precondición y $e$ el efecto se aplica de la siguiente forma sobre $s$, un estado cualquiera. Notemos por $p^+$ y $e^+$ el conjunto de literales positivos de $p$ y $e$, respectivamente (y de forma análoga, $p^-$ y $e^-$ los negativos):
  • Si $p^+\subseteq s$ y
  • $\neg(p^-)\cap s=\emptyset$ ($\neg(p^-)$ representa los opuestos de los literales negativos de $p$)
  • Entonces el nuevo estado, $s'=s\cup e^+ - e^-$ (esta operación puede implicar el cambiar literales positivos por negativos o viceversa).

Es decir, si las precondiciones de la acción son compatibles con el estado actual, entonces los efectos se añaden/quitan al estado modificando su contenido.

Por supuesto, este mecanismo es muy primitivo, sobre todo porque generar todas las acciones concretas (lo que llamamos acciones de Herbrand) consume muchos recursos (en tiempo y memoria) y dificulta enormemente la generación del grafo de estados que ha de recorrer el algoritmo de búsqueda. En este sentido, sería mucho más interesante considerar únicamente las reglas aplicables a partir del estado concreto actual que se está expandiendo con el fin de poder abordar problemas mucho más grandes (una versión futura del planificador en NetLogo trabajará en esta dirección).

Búsqueda hacia atrás

Alternativamente, podemos buscar hacia atrás desde un estado objetivo hacia el estado inicial. Para ello debemos definir previamente dos conceptos nuevos:

• Una acción $a$ es relevante para un objetivo $g$ si:

1. $g\cap effects(a)\neq \emptyset$.
2. $g^+\cap effects^-(a)= \emptyset$.
3. $g^-\cap effects^+(a)= \emptyset$.

Esencialmente, lo que dice es que la acción debe contribuir a la consecución del objetivo (la primera condición) y no debe interferir con ella (las dos últimas condiciones). Esto es equivalente a la aplicabilidad.

• El conjunto de regresión de $g$ para una acción relevante $a$ se define como:

$$\gamma^{−1}(g,a)=(g−efectos(a)) \cup precond(a)$$

Es decir, es el inverso de la función de transición de estado.

Al buscar hacia atrás, a veces terminamos con acciones que siguen teniendo variables libres. En teoría, podríamos ramificarnos a todas las acciones posibles de ésta simplemente sustituyendo todos los valores posibles de la variable (algo parecido a como hemos hecho con las acciones de Herbrand), pero eso aumentaría mucho el factor de ramificación. En cambio, podemos hacer una búsqueda en la que simplemente nos quedamos con estos operadores parcialmente instanciados en lugar de acciones. A este método se le llama planificación de menor compromiso, y también consigue reducir considerablemente los recursos necesarios para la búsqueda.

El planificador Fast-Forward

El planificador Fast-Forward (FF) es uno de los algoritmos más efectivos que se tienen actualmente en planificación. Este algoritmo realiza una búsqueda hacia adelante en el espacio de estados, usando una estrategia básica con heurística, como puede ser A* o un proceso de escalada. Pero lo hace de forma más inteligente que como hemos explicado anteriormente (que sería por fuerza bruta).

El problema principal para poder ejecutar un algoritmo A* es la definición de una función heurística adecuada que realmente oriente la búsqueda del plan. Hasta el momento, a nadie se le ha ocurrido una heurística general que funcione relativamente bien para los algoritmos de planificación, y parece poco probable que pueda existir una heurística tan general, parece que dependerá siempre de las acciones concretas que se pueden ejecutar en el estado del mundo. Por otra parte, la búsqueda por fuerza bruta hace inviable la planificación cuando el mundo es algo más complicado (por número de acciones posibles, o por tamaño del mundo), por lo que una solución de compromiso en la que podamos orientar la búsqueda con información adicional se hace más que deseable.

Para este fin este algoritmo utiliza lo que se conoce como el Grafo de Planificación Relajado, que ignora la lista negativa de todas las acciones, y permite extraer una heurística inicial. Este problema relajado se puede hacer en tiempo polinomial haciendo uso del encadenamiento (que vimos en los sistemas basados en reglas) de la siguiente forma:

• Encadenamiento hacia adelante para construir un grafo de planificación relajado.
• Encadenamiento hacia atrás para extraer un plan relajado del grafo.

La información que se extrae del plan relajado no es válida directamente para resolver el problema general (no suele ser solución), sin embargo, sí que se usa la longitud del plan relajado, es decir, el número de acciones, como un valor heurístico (por ejemplo, para A*) para el problema original, dando una cota que puede ser utilizada para, ahora sí, buscar un plan en el grafo de planificación del problema original.

El pseudocódigo para calcular el Grafo de Planificación Relajado (RPG) podría ser:

El pseudocódigo para extraer posteriormente un plan de este RPG (en particular, el tamaño del plan, ya que este es un cálculo heurístico) podría ser:

La función $firstlevel$ nos dice en qué capa (por índice) aparece un objetivo $g_i$ por primera vez en el grafo de planificación.

Debe tenerse en cuenta que esta heurística no es admisible (no se garantiza que devuelva un plan mínimo), pero en la práctica es bastante precisa, por lo que es una técnica que se usa con frecuencia (o ideas inspiradas en ella) y que funciona en muchísimos casos (de nuevo, si el problema crece mucho, es preferible tener una respuesta aproximada a no tener ninguna). De hecho, actualmente esta aproximación de planificación FF supone el estado del arte en algoritmos de planificación.