**SVRAI**
Problemas de Planificación
Hemos visto que en un problema de **Planificación** estamos interesados en buscar la sucesión de acciones que nos permiten pasar de un estado inicial a uno final que verifica las condiciones deseadas.
Algunos ejemplos de problemas planificación de juguete podrían ser:
1. Juegos clásicos, como el *problema del granjero, el lobo y el río*.
1. Rompecabezas de piezas deslizantes.
1. Problemas de logística, como el problema de apilamiento de contenedores (muy similar al clásico problema del mundo de bloques).
Estos problemas se caracterizan porque tienen una descripción concisa y exacta, muy diferentes de los problemas del mundo real. En todos ellos lo que nos interesa no es (únicamente) llegar a un estado final (que muchas veces conocemos a priori, como en los dos primeros ejemplos), sino los pasos necesarios para llegar al mismo.
![](img/world-blocks-planning.jpeg align="right") Vamos a usar como ejemplo concreto este último problema de planificación, sobre el que mostraremos las definiciones que nos interesan y que pueden ser comunes a muchos otros problemas de planificación (sean de juguete o del mundo real). Concretamente, en este problema de cajas disponemos de:
1. Algunas cajas.
1. Una superficie (mesa) sobre la que podemos situar las cajas.
1. Las cajas se pueden apilar sobre la mesa (sin límite de altura).
1. Tenemos un brazo robótico que puede llevar una (solo una) caja cargada.
En consecuencia, las acciones disponibles en este mundo podrían ser:
1. **pickup**: recoge una caja de la mesa.
1. **putdown**: suelta una caja sobre la mesa.
1. **stack**: apila una caja encima de otra.
1. **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 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** tienen 3 partes fundamentales:
1. Un **nombre**.
2. Una **precondición**, que viene dada como fórmula lógica acerca de los predicados. 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 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.
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 `?`):
~~~~none
set Plan:Universe [["A" "B" "C" "D" "E"]]
set Plan:Predicates ["on" "ontable" "clear" "handempty" "holding"]
set Plan:actions [
["(pickup ?x)"
["(clear ?x)" "(ontable ?x)" "(handempty)"]
["-(ontable ?x)" "-(clear ?x)" "-(handempty)" "(holding ?x)"]
[0]]
["(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:
~~~~none
set Plan:actions-costs [["pickup" 1] ["putdown" 1] ["stack" 1] ["unstack" 1]]
~~~~
Las características principales de **STRIPS** 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).
El lenguaje **PDDL** supone un estándard que ha sido refinado en versiones posteriores (actualmente, la versión **PDDL+**) y se basa en una separación de ficheros escritos en **LISP** para el dominio del problema y para los objetos, 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.
# 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 las 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:
~~~~none
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:
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 correcta (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 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.
~~~~none
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 estados:
* 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 qe se mostraron anteriormente.
* 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 al estado modificando su contenido.
Por supuesto, este mecanismo es muy primitivo, sobre todo porque generar todas las acciones concretar (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 (una versión futura del planificador en NetLogo trabajará en esta dirección), con el fin de poder abordar problemas mucho más grandes.
## 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, 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 FF
El __planificador 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 que 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.
Para ello, 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 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.
Luego, se usa la longitud (es decir, el número de acciones) del plan relajado como un valor heurístico (por ejemplo, para A*) para el problema original.
El pseudocódigo para calcular el Grafo de Planificación Relajado (RPG) podría ser :
~~~~none
computeRPG(A,s_i,g)
F_0=s_i, t=0
Mientras g ⊆ F_t hacer:
hacer t=t+1
A_t = {a \in A | precond(a) ⊆ F_t }
F_t=F_{t−1}
Para cada a∈ A_t hacer:
F_t=F_t ⋃ effects^+(a)
Si F_t=F_{t−1} , devolver false
Devolver [F_0,A_1,F_1,...,A_t,F_t]
~~~~
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:
~~~~none
extractRPSize([F_0,A_1,F_1,...,A_k,F_k],g)
Si g ⊆ F_k, devolver false
M = max {firstlevel(g_i, [F_0,..., F_k]) | g_i ∈ g }
Para cada t desde 0 a M hacer:
G_t = {g_i ∈ g | firstlevel(g_i, [F_0,..., F_k]) = t }
Para cada t desde M a 1 hacer:
Para todo g_t ∈ G_t hacer:
seleccionar a: firstlevel(a,[A_1,...,A_t])=t y g_t ∈ effects^+(a)
Para cada ∈ precond(a) hacer:
G_{firstlevel(p, [F_0,..., F_k])} = G_{firstlevel(p, [F_0,..., F_k])} ⋃ {p}
Devolver el número de acciones seleccionadas
~~~~
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). De hecho, actualmente esta aproximación supone el estado del arte en algoritmos de planificación.