**IAIC** Planificación # Introducción Hemos visto que un problema de **Planificación** es aquel en el que no solo estamos interesados en encontrar una solución, sino también una sucesión de acciones que nos permiten pasar de un estado inicial, que viene dado, a uno final que verifica las condiciones deseadas (ya sea un estado concreto, o del que solo sabemos qué debe verificar). Algunos ejemplos de problemas de planificación de juguete podrían ser los conocidos: 1. Puzzles clásicos, como el *problema del granjero, el lobo y el río*, el de *misioneros y caníbales*, o el *problema de las jarras*. 2. Rompecabezas de piezas deslizantes, cubo de Rubik, etc. 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 representació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, discusión y ensayo y error. 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 a él. Vamos a usar como ejemplo concreto a lo largo de esta entrada un problema de planificación muy famoso inspirado en el **mundo de bloques** (`blockworld`), 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 bloques disponemos de: * Algunas cajas/bloques. * Una superficie (mesa) sobre la que podemos situar las cajas. * Las cajas se pueden apilar unas sobre otras (sin límite de altura). * Un brazo mecánico con capacidad para agarrar, mover y soltar las cajas (de una en una) desplazándose sobre la mesa. 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,\dots\}$. Ni la propia mesa ni el brazo mecánico es necesario que intervengan como objetos del mundo, pero sí compondrán parte de la representación por medio de las acciones y los predicados siguientes: * $on(A,B)$: la caja $A$ está sobre la $B$. * $ontable(A)$: la caja $A$ está directamente sobre la mesa. * $clear(A)$: la caja $A$ no tiene nada más encima. * $handempty$: el brazo está libre (no tiene agarrada ninguna caja). * $holding(A)$: 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, con el fin de que se puedan aplicar sin cambios sobre una colección, 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 u 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). El lenguaje **PDDL** supone un estándar que ha sido refinado en versiones posteriores (actualmente, va por la versión PDDL3.1, pero hay otras muchas variantes, como PDDL+, PPDDL, MA-PDDL, etc.) 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. 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. En general, permiten una aproximación a lo que podríamos llamar **Planificación Simbólica**. # Planificación independiente del dominio !!!note La filosofía central incorporada en PDDL y, consecuentemente, en muchos planificadores, es que las técnicas aplicadas para resolver un problema no deben saber nada sobre el problema que están resolviendo. Es decir, las técnicas que aplicamos para resolver, por ejemplo, un problema de logística, podríamos aplicarlas también a un problema de fabricación. Esto es interesante porque, a diferencia de otros campos de la Inteligencia Artificial, como el Aprendizaje Automático, no dependemos de que haya información preexistente sobre el problema, o un camino de ejemplo hacia una solución. Todo lo que necesitamos es el estado inicial, las acciones que podemos aplicar y el estado final deseado. A menudo, estos tres elementos de información están fácilmente disponibles por la propia naturaleza de los problemas que un planificador intenta resolver. Por ejemplo, si estamos planificando la construcción de un gran estadio, sabemos lo que hay que hacer para que el estadio esté terminado, sabemos que actualmente no hay ningún estadio construido y conocemos las distintas acciones que se pueden realizar para cambiar el estado y acercarlo a la posición en la que deseamos que esté (construir armazones, instalar tuberías, izar banderas, etc.). No necesitamos saber cómo se construyeron los estadios anteriores, ni qué orden se utilizó (por ejemplo, construir los cimientos, luego los armazones, etc.). Esta falta de necesidad de conocimientos significa que podemos aplicar la planificación a problemas que no se han resuelto anteriormente. Además, si suponemos que las soluciones anteriores a un problema de planificación no son óptimas (es decir, no son todo lo buenas que podrían ser), la aplicación de una técnica como el aprendizaje nos entrenaría esencialmente para resolver problemas de forma subóptima. Por lo tanto, necesitamos una evaluación metódica, objetiva y que evite aprender de enfoques anteriores que no sean óptimos (es decir, independientes del dominio). # Planificación Simbólica !!!def La **Planificación Simbólica** es un término general para los enfoques de planificación y razonamiento automatizados que describen el mundo y su dinámica en términos de símbolos de alto nivel, normalmente utilizando la Lógica de Primer Orden. PDDL es una forma de representar dicho conocimiento simbólico, pero existen muchos otros formalismos. A continuación vamos a ver las definiciones generales de *dominios de planificación*, *problemas*, *estados* y *acciones*. Estas definiciones se aplican tanto a PDDL como a los mencionados STRIPS y ADL. Las variantes de PDDL también comparten estas definiciones básicas, aunque las amplían para incorporar más funcionalidad y expresividad.  !!!note:Fundamentos de PDDL * **Requerimientos**: Características del lenguaje PDDL que se usarán en la definición del problema: * `:strips` (lenguaje básico) * `:typing` (definición de tipos en parámetros y constantes) * `:adl` (lenguaje avanzado con cuantificadores, efectos condicionales, etc.) * `:equality` (uso de comparaciones de igualdad) * `:fluents` (lenguaje avanzado con funciones de coste y optimización) * **Tipos**: Tipos de las constantes/parámetros que se usarán en el problema * **Predicados**: Predicados que representan el problema * **Acciones**: Operadores de planificación para resolver el problema Primero introducimos el concepto de **fluentes**, que utilizamos para definir variables de estado (relacionales) que pueden cambiar con el tiempo, pero también tienen otros usos extendidos, como incluir funciones (de hecho son variables numéricas), comparaciones aritméticas entre funciones, operaciones aritméticas entre funciones, añadir costes en los efectos de las acciones, optimización del plan a partir de los valores de las funciones, etc. !!!def:Definición: Fluentes Un **fluente** $F$ de aridad $n$ es un predicado (booleano) o función (no booleana) con $n$ argumentos objeto, que describe alguna propiedad o relación sobre esos argumentos que puede cambiar con el tiempo. Un **fluente fundamentado** $f$ es un fluente definido sobre un conjunto particular de objetos. Los argumentos pueden ser opcionalmente tipados. !!!tip: Ejemplo El fluente `(on ?x ?y)` se llama `on`, tiene aridad $n = 2$, y describe si algún objeto denotado por la variable `?x` está apilado encima de `?y`. El fluente fundamentado `(on a b)` indica que el objeto `a` está apilado sobre el objeto `b` cuando es verdadero. Los estados del mundo pueden describirse simbólicamente en términos de fluentes y sus valoraciones en un momento determinado: !!!def:Definición: Estados Dado un conjunto finito de fluentes $\cal{F}$, un estado $s$ se compone de un conjunto de objetos (opcionalmente tipados) $\cal{O} := objects(s)$, y valoraciones de fluentes $\cal{F}(\cal{O})$ definidas sobre todos los objetos en $\cal{O}$ de los tipos apropiados. Cada fluente fundamentado se refiere a una variable de estado. Para un fluente fundamentado $f∈ \cal{F}(\cal{O})$, utilizamos la notación $s [f]=v$ para denotar que $f$ tiene valor $v$ en el estado $s$. !!!tip:Ejemplo Dado el fluente `(on ?x ?y)` y un estado `s` con `objects(𝑠) = {a, b}`, la expresión `s[(on a b)] = true` significa que el objeto `a` está encima de `b` en el estado `s`. La semántica de las acciones se especifica mediante esquemas de acción, que describen las condiciones previas y los efectos de las acciones en términos de los objetos sobre los que operan. !!!def:Definición: Esquema de Acción Un **esquema de acción**, $\cal{A}$, también conocido como **operador de planificación**, es una tupla $(params(\cal{A}), precond(\cal{A}), effect(\cal{A}))$, donde: - $params(\cal{A})$ es una lista de variables parámetro (opcionalmente tipadas), que sirven como marcadores de posición para los objetos sobre los que opera una acción concreta. - $precond(\cal{A})$ es una fórmula lógica, definida usando un conjunto de fluentes $\cal{F}$ sobre las variables en $params(\cal{A})$, que especifica las precondiciones bajo las cuales una acción $\cal{A}(o)$ con argumentos de objeto $o$ puede ser ejecutada. - $effect(\cal{A})$ es una fórmula, definida sobre las variables en $params(\cal{A})$, que especifica los efectos de una acción $\cal{A}(o)$ con argumentos $o$. Los efectos pueden ser asignaciones a fluentes en un estado, o expresiones más generales con condiciones o elecciones probabilísticas. Algunos formalismos también admiten esquemas para acciones cuyas precondiciones o efectos se aplican a lo largo del tiempo, con definiciones ampliadas en consecuencia. !!!def:Definición: Acciones Una **acción**, $a= \cal{A}(o)$ se define mediante un esquema de acción $\cal{A}$ y argumentos $o$, que especifican los objetos sobre los que opera $a$. Se dice que una acción está **disponible** o es **aplicable** en un estado $s$ si $precond(\cal{A})$ se cumple en $s$ cuando las variables en $params(\cal{A})$ se sustituyen por sus valores concretos $o$. Se dice que es **relevante** para un estado $s$ si alguna valoración fluente en $s$ podría alcanzarse posiblemente por algún efecto de $a$. !!!note:Sintaxis de las Acciones ~~~~ (:action nom-action1 :parameters (?V1 - tipo1 ?V2 - tipo2) :precondition (and (pred1 ?V1) (exists (?V3 - tipo2) (pred2 ?V3)) ) :effect (not (pred2 ?V2)) ) ~~~~ Una vez definidos los estados y las acciones, pasamos a definir los dominios de planificación y los problemas. !!!def:Definición: Dominios de planificación Un **dominio de planificación simbólica**, $\cal{D}$, es una tupla $(\cal{T} , \cal{F}, \cal{A}, \dots)$ donde $\cal{T}$ es un conjunto (opcional) de tipos de objetos, $\cal{F}$ un conjunto de fluentes que describen estados, precondiciones y efectos, y $\cal{A}$ un conjunto de esquemas de acción que definen la semántica de las acciones en $\cal{D}$. Algunos formalismos amplían los dominios con otros componentes, como constantes de objeto o axiomas para predicados derivados. Un dominio de planificación especifica efectivamente la dinámica de transición (levantada) de un modelo simbólico de primer orden del mundo. Cuando todos los efectos son deterministas, $\cal{D}$ define un sistema de transición de estados sobre todos los estados posibles $\cal{S}$ cuando se empareja con un conjunto de objetos $\cal{O}$ sobre los que se definen los estados. Cuando los efectos son estocásticos, $\cal{D}$ define una distribución de transición $T(s'|s, a)$ sobre los estados sucesores $s'$ condicionada a un estado $s$ y una acción $a$. !!!note:Sintaxis del Dominio ~~~~ (define (domain nom-domain) (:requirements :adl :typing) (:types tipo1 tipo2) (:predicates (pred1 ?V1 - tipo1) (pred2 ?V1 - tipo2) ) (:action nom-action1...) (:action nom-action2...) ) ~~~~ !!!Tip:Ejemplo Por ejemplo, usando el lenguaje definido en PDDL podríamos dar una formalización del mundo de bloques como (observa que las variables comienzan por el símbolo `?`): ~~~~ (define (domain blocksworld) (:requirements :strips :typing :equality) (:types block) (:predicates (on ?x ?y - block) (ontable ?x - block) (clear ?x - block) (handempty) (holding ?x - block)) (:action pick-up :parameters (?x - block) :precondition (and (clear ?x) (ontable ?x) (handempty)) :effect (and (not (ontable ?x)) (not (clear ?x)) (not (handempty)) (holding ?x))) (:action put-down :parameters (?x - block) :precondition (holding ?x) :effect (and (not (holding ?x)) (clear ?x) (handempty) (ontable ?x))) (:action stack :parameters (?x ?y - block) :precondition (and (holding ?x) (clear ?y) (not (= ?x ?y))) :effect (and (not (holding ?x)) (not (clear ?y)) (clear ?x) (handempty) (on ?x ?y))) (:action unstack :parameters (?x ?y - block) :precondition (and (on ?x ?y) (clear ?x) (handempty) (not (= ?x ?y))) :effect (and (holding ?x) (clear ?y) (not (clear ?x)) (not (handempty)) (not (on ?x ?y)))) ) ~~~~ !!!def:Definición: Problemas de planificación Un **problema de planificación simbólica**, $\cal{P}$ es una tupla $(\cal{D}, s_0, g, \dots)$, donde $\cal{D} = (\cal{T} , \cal{F}, \cal{A}, \dots )$ es un dominio de planificación, $s_0$ es un estado inicial definido sobre objetos con tipos en $\cal{T}$ y fluentes en $\cal{F}$, y $g$ es el objetivo a alcanzar, especificado como una fórmula lógica (por ejemplo, una conjunción de fluentes a satisfacer). Además de una fórmula de objetivo, un problema de planificación también puede incluir otras especificaciones, como una métrica de coste a minimizar, y restricciones temporales en el plan. La tarea de un algoritmo de planificación es encontrar una secuencia de acciones desde el estado inicial (un plan) o un mapeo de estados a acciones (una política) que lleve a satisfacer u optimizar las especificaciones del problema. !!!note:Sintaxis del Problema ~~~~ (define (problem nom-problem) (:domain nom-domain) (:objects obj1T1 obj2T1 obj3T1 - tipo1 obj1T2 obj2T2 obj3T2 - tipo2 ) (:init (pred1 obj1T1) (pred1 obj2T1) (pred1 obj3T1) (pred2 obj1T2) (pred2 obj2T2) (pred2 obj3T2) ) (:goal (forall (?V - tipo1) (pred1 ?V)) ) ) ~~~~ 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 ver, desde un punto de vista práctico cómo crear aplicar los algoritmos de búsqueda que hemos visto al contexto de los problemas de planificación haciendo uso de PDDL, comenzaremos dando un recorrido práctico de cómo trabaja la planificación simbólica con la librería `PDDL.jl` que usaremos en las prácticas. !!!tip:Ejemplo de Problema ~~~~ (define (problem blocksworld-1) (:domain blocksworld) (:objects a b - block ) (:init (handempty) (ontable a) (ontable b) (clear a) (clear b) ) (:goal (and (clear a) (ontable b) (on a b) ) ) ) ~~~~ !!!note El siguiente contenido se ha extraído de los tutoriales que ofrece PDDL.jl en su [sitio web](https://juliaplanners.github.io/PDDL.jl/stable/). # PDDL.jl Supondremos que ya tenemos instalada la librería en nuestro ecosistema de Julia (ya sea por medio del gestor de paquetes si hacemos uso del REPL, o implícitamente por la carga de la librería si hacemos uso de Pluto). En cualquier caso, el primer paso es cargar el espacio de nombres en la ejecución actual de Julia: ```julia using PDDL ``` ## Carga de dominios y problemas Un dominio **PDDL** define la *física* de alto nivel o la dinámica de transición de una tarea de planificación. Un ejemplo clásico es [Blocksworld](https://en.wikipedia.org/wiki/Blocks_world), un dominio en el que los bloques pueden apilarse unos sobre otros o colocarse sobre una mesa (es el mismo código que pusimos anteriormente como ejemplo): ```lisp (define (domain blocksworld) (:requirements :strips :typing :equality) (:types block) (:predicates (on ?x ?y - block) (ontable ?x - block) (clear ?x - block) (handempty) (holding ?x - block)) (:action pick-up :parameters (?x - block) :precondition (and (clear ?x) (ontable ?x) (handempty)) :effect (and (not (ontable ?x)) (not (clear ?x)) (not (handempty)) (holding ?x))) (:action put-down :parameters (?x - block) :precondition (holding ?x) :effect (and (not (holding ?x)) (clear ?x) (handempty) (ontable ?x))) (:action stack :parameters (?x ?y - block) :precondition (and (holding ?x) (clear ?y) (not (= ?x ?y))) :effect (and (not (holding ?x)) (not (clear ?y)) (clear ?x) (handempty) (on ?x ?y))) (:action unstack :parameters (?x ?y - block) :precondition (and (on ?x ?y) (clear ?x) (handempty) (not (= ?x ?y))) :effect (and (holding ?x) (clear ?y) (not (clear ?x)) (not (handempty)) (not (on ?x ?y)))) ) ``` Supongamos que esta definición de dominio se guarda en un fichero llamado `blocksworld.pddl` en el directorio actual. Podemos cargar el dominio Blocksworld llamando a `load_domain`: ```julia domain = load_domain("blocksworld.pddl") ``` A continuación, podemos inspeccionar el nombre de dominio y la lista de nombres de acción: ```julia-repl julia> PDDL.get_name(domain) :blocksworld julia> PDDL.get_actions(domain) |> keys .|> string 4-element Vector{String}: "pick-up" "unstack" "put-down" "stack" ``` Los dominios PDDL sólo definen la semántica general de la tarea de planificación que se aplica a cualquier conjunto de objetos o metas. Para definir completamente una tarea de planificación, también necesitamos cargar un **problema PDDL**, que define un estado inicial, y un objetivo a alcanzar: ```lisp (define (problem blocksworld-problem) (:domain blocksworld) (:objects a b c - block) (:init (handempty) (ontable a) (ontable b) (ontable c) (clear a) (clear b) (clear c)) (:goal (and (clear c) (ontable b) (on c a) (on a b))) ) ``` En este problema, hay 3 bloques, `a`, `b` y `c`, que se colocan inicialmente sobre la mesa (`ontable`), sin ningún otro bloque colocado sobre ellos (`clear`). El objetivo es apilar los bloques de forma que `c` esté sobre `a` y `b`. Supongamos que la definición del problema se guarda en `blocksworld-problem.pddl`. Podemos cargarla llamando a `load_problem`: ```julia problem = load_problem("blocksworld-problem.pddl") ``` A continuación, podemos inspeccionar la lista de objetos y el objetivo a alcanzar: ```julia-repl julia> PDDL.get_objects(problem) |> println Const[a, b, c] julia> PDDL.get_goal(problem) |> write_pddl "(and (clear c) (ontable b) (on c a) (on a b))" ``` ### Carga desde un repositorio Se puede encontrar en línea una amplia variedad de dominios y problemas PDDL estándar, como [este repositorio](https://github.com/potassco/pddl-instances) de instancias de la Competición Internacional de Planificación (IPC). Para facilitar la carga o descarga de estos dominios y problemas, el ecosistema PDDL.jl incluye [PlanningDomains.jl](https://github.com/JuliaPlanners/PlanningDomains.jl), que contiene tanto un repositorio integrado de dominios y problemas como una interfaz para acceder a dominios y problemas de otros repositorios en línea. PlanningDomains.jl puede instalarse desde el Pkg REPL como de costumbre. Una vez instalado, podemos utilizarlo para cargar directamente los dominios y problemas de Blocksworld: ```julia using PlanningDomains domain = load_domain(:blocksworld) problem = load_problem(:blocksworld, "problem-2") ``` También podemos especificar repositorios externos desde los que descargar, como el anteriormente mencionado repositorio de [IPC domains and problems](https://github.com/potassco/pddl-instances): ```julia domain = load_domain(IPCInstancesRepo, "ipc-2000", "blocks-strips-typed") problem = load_problem(IPCInstancesRepo, "ipc-2000", "blocks-strips-typed", "problem-2") ``` ## Estados y Fluentes Ahora que hemos cargado un dominio y un problema, podemos construir el estado inicial (especificado por el archivo del problema) utilizando la función `initstate`: ```julia state = initstate(domain, problem) ``` Conceptualmente, un **estado** consiste en un conjunto de objetos, y un conjunto de hechos verdaderos y relaciones sobre esos objetos. Podemos listar el conjunto de hechos utilizando `PDDL.get_facts`: ```julia-repl julia> PDDL.get_facts(state) Set{Term} with 7 elements: clear(a) ontable(b) clear(b) handempty ontable(a) ontable(c) clear(c) ``` Además de listar hechos, podemos consultar el valor de verdad de términos específicos utilizando la función `satisfy`: ```julia-repl julia> satisfy(domain, state, pddl"(ontable a)") true julia> satisfy(domain, state, pddl"(on a b)") false ``` En este caso, hemos utilizado la macro de cadena `pddl` para construir un `Term` de primer orden. Esto nos permite escribir `pddl"(on a b)"` como azúcar sintáctico para una expresión mucho más complicada como sería `Compound(:on, Term[Const(:a), Const(:b)])`, haciendo uso de las funciones de bajo nivel que trae la librería. Además de consultar si determinados términos son verdaderos o falsos, también podemos pedir a PDDL.jl que devuelva todas las asignaciones satisfactorias de una fórmula lógica con variables libres utilizando la función `satisfiers`: ```julia-repl julia> satisfiers(domain, state, pddl"(and (ontable ?x) (clear ?x))") 3-element Vector{Any}: {X => b} {X => a} {X => c} ``` Nuestra consulta `pddl"(and (ontable ?x) (clear ?x))"` expresa que algún objeto `?x` está en la tabla, y está `clear` (es decir, no tiene otros bloques encima), donde `?x` es la sintaxis PDDL para una variable en una fórmula de primer orden. Como los bloques `a`, `b` y `c` satisfacen la consulta, `satisfiers` devuelve una lista de las correspondientes sustituciones de variables. PDDL no se limita a dominios en los que las propiedades y relaciones de los objetos deben tener valores booleanos. Por ejemplo, el dominio [Zeno Travel](https://github.com/potassco/pddl-instances/blob/master/ipc-2002/domains/zenotravel-numeric-automatic/domain.pddl) incluye propiedades y relaciones numéricas, como la distancia entre dos ciudades o la cantidad de combustible de un avión. También podemos construir e inspeccionar un estado en este dominio: ```julia zt_domain = load_domain(:zeno_travel) zt_problem = load_problem(:zeno_travel, "problem-1") zt_state = initstate(zt_domain, zt_problem) ``` Para inspeccionar todas las propiedades y relaciones (booleanas o no) en este estado, podemos iterar sobre la lista de pares devuelta por `PDDL.get_fluents`: ```julia-repl julia> PDDL.get_fluents(zt_state) |> collect 13-element Vector{Pair}: at(plane1, city0) => true at(person1, city0) => true onboard(plane1) => 0 slow-burn(plane1) => 4 ⋮ fuel(plane1) => 3956 fast-burn(plane1) => 15 zoom-limit(plane1) => 8 capacity(plane1) => 10232 ``` Recordemos que estas propiedades y relaciones son las que formalmente hemos denominado [**fluentes**](https://en.wikipedia.org/wiki/Fluent_(inteligencia_artificial), un término utilizado históricamente en la investigación de la IA para describir hechos sobre el mundo que pueden cambiar con el tiempo. Los fluentes a veces también se denominan "variables de estado", pero evitamos esa terminología para evitar confusiones con las variables en el contexto de los términos y fórmulas de primer orden. De acuerdo con la terminología de la [lógica de primer orden](https://en.wikipedia.org/wiki/First-order_logic), los fluentes booleanos como `(at ?plane ?city)` también se llaman **predicados**, y los fluentes no booleanos como `(fuel ?plane)` se llaman **funciones** (porque asignan objetos a valores). !!! note Predicados omitidos Por concisión, algunas implementaciones de la interfaz PDDL.jl omitirán los predicados que sean falsos de la lista devuelta por `PDDL.get_fluents`, como en el caso anterior. Además de listar flujos, podemos evaluar flujos específicos utilizando la función `evaluate`. A continuación, consultamos la cantidad de combustible en `plane1`: ```julia-repl julia> evaluate(zt_domain, zt_state, pddl"(fuel plane1)") 3956 ``` También podemos evaluar expresiones compuestas de múltiples fluentes. Por ejemplo, podríamos tener curiosidad por saber la cantidad de combustible adicional que puede contener `plane1`. Como azúcar sintáctico para `evaluate(domain, state, term)`, también podemos utilizar la sintaxis `domain[state => term]`: ```julia-repl julia> evaluate(zt_domain, zt_state, pddl"(- (capacity plane1) (fuel plane1))") 6276 julia> zt_domain[zt_state => pddl"(- (capacity plane1) (fuel plane1))"] 6276 ``` Para expresiones *no compuestas* almacenadas directamente en el estado, podemos usar `PDDL.get_fluent` para buscar el valor de un `term` en `state`, o `state[term]` para abreviar: ```julia-repl julia> state[pddl"(on a b)"] # Blocksworld query false julia> zt_state[pddl"(fuel plane1)"] # Zeno Travel query 3956 ``` Como los estados PDDL consisten en conjuntos de objetos (opcionalmente tipados), PDDL.jl proporciona la función `PDDL.get_objects` para listar todos los objetos de un estado, así como todos los objetos de un tipo particular: ```julia-repl julia> PDDL.get_objects(state) |> println # Blocksworld objects Const[c, a, b] julia> PDDL.get_objects(zt_state, :aircraft) |> println # Zeno Travel aircraft Const[plane1] julia> PDDL.get_objects(zt_domain, zt_state, :movable) |> println # Zeno Travel movables Const[person1, plane1] ``` Observe que en la tercera llamada a `PDDL.get_objects`, también proporcionamos el dominio como primer argumento. Esto se debe a que el dominio almacena información sobre la jerarquía de tipos, y el tipo `movable` en el dominio de Zeno Travel es abstracto: no hay objetos en el estado que tengan el tipo `movable`. Sólo hay objetos de sus subtipos "persona" y "avión". Podemos inspeccionar la jerarquía de tipos de un dominio utilizando `PDDL.get_typetree`: ```julia-repl julia> PDDL.get_typetree(zt_domain) Dict{Symbol, Vector{Symbol}} with 5 entries: :object => [:movable, :city] :movable => [:aircraft, :person] :aircraft => [] :person => [] :city => [] ``` Por último, podemos inspeccionar el tipo de un objeto específico utilizando `PDDL.get_objtype`: ```julia-repl julia> PDDL.get_objtype(zt_state, pddl"(person1)") :person ``` ## Acciones y Planes Los dominios PDDL no sólo definen los predicados y funciones que describen un estado, sino también un conjunto de acciones que pueden modificar un estado. Tras aprender a inspeccionar el contenido de un estado, ahora podemos modificarlo mediante acciones. En PDDL, y en planificación simbólica en general, distinguimos entre **esquemas de acción**, que especifican la semántica general de una acción, y **acciones fundamentadas**, que representan instancias de acciones para objetos específicos. Podemos inspeccionar la definición de un esquema de acción en un dominio utilizando `PDDL.get_action`, como la definición de `stack` que aparece a continuación: ```julia-repl julia> PDDL.get_action(domain, :stack) |> write_pddl |> print (:action stack :parameters (?x ?y - block) :precondition (and (holding ?x) (clear ?y) (not (= ?x ?y))) :effect (and (not (holding ?x)) (not (clear ?y)) (clear ?x) (handempty) (on ?x ?y))) ``` El esquema `stack` tiene dos **parameters** (o argumentos) de tipo `block`. Esto significa que las instancias del esquema `stack` deben aplicarse a dos objetos `block`. El esquema también especifica una fórmula de **precondition**, que debe cumplirse para que la acción sea ejecutable (es decir, esté disponible) en el estado actual. Por último, el esquema contiene una fórmula **effect**, que especifica los hechos que se añadirán o eliminarán en el siguiente estado. En los dominios con fluentes no booleanos, los efectos también pueden asignar o modificar los valores de los fluentes. Para referirnos a una aplicación específica de este esquema de acción a los bloques `a` y `b` (es decir, una acción de suelo), podemos simplemente escribir `pddl"(stack a b)"`, que construye un `Term` con `stack` como nombre, y con `a` y `b` como argumentos: ```julia-repl julia> pddl"(stack a b)" |> dump Compound name: Symbol stack args: Array{Term}((2,)) 1: Const name: Symbol a 2: Const name: Symbol b ``` Si no se especifica, deberá quedar claro por el contexto si nos referimos a esquemas de acción o a acciones sobre el terreno. Para nuestro estado inicial en el dominio Blocksworld, podemos iterar sobre la lista de acciones básicas disponibles (es decir, aquellas con precondiciones satisfechas) utilizando la función `available`: ```julia-repl julia> available(domain, state) |> collect 3-element Vector{Compound}: pick-up(a) pick-up(b) pick-up(c) ``` Observa que `available` devuelve un iterador sobre dichas acciones, por lo que tenemos que hacer un `collect` sobre este iterador para obtener un `Vector` como resultado. Como ahora sabemos qué acciones están disponibles, podemos `execute` una de ellas para obtener otro estado: ```julia-repl julia> next_state = execute(domain, state, pddl"(pick-up a)"); julia> satisfy(domain, next_state, pddl"(holding a)") true ``` Vemos que tras ejecutar la acción `pddl"(pick-up a)"`, el bloque `a` está ahora agarrado. Por el contrario, si intentamos ejecutar una acción no disponible, PDDL.jl arrojará un error: ```julia-repl julia> next_state = execute(domain, state, pddl"(stack a b)"); ERROR: Precondition (and (holding ?x) (clear ?y) (not (= ?x ?y))) does not hold. ⋮ ``` En lugar de utilizar `execute`, también podemos utilizar la función `transition`. Para dominios escritos en PDDL estándar, estas funciones tienen el mismo comportamiento, pero hay extensiones de PDDL que incluyen eventos y procesos que son manejados únicamente por `transition`. Ten en cuenta que tanto `execute` como `transition` no mutan el estado original pasado como argumento. Para versiones mutantes, vea `execute!` y `transition!`. ### Ejecución y simulación de planes Ahora que sabemos cómo ejecutar una acción, podemos ejecutar una serie de acciones (es decir, un plan) para alcanzar nuestro objetivo en el dominio Blocksworld. Podemos hacerlo llamando repetidamente a `transition`: ```julia state = initstate(domain, problem) state = transition(domain, state, pddl"(pick-up a)") state = transition(domain, state, pddl"(stack a b)") state = transition(domain, state, pddl"(pick-up c)"); state = transition(domain, state, pddl"(stack c a)"); ``` Y, a continuación, comprobar que efectivamente se cumple nuestro objetivo: ```julia-repl julia> goal = PDDL.get_goal(problem) # Our goal is stack `c` on `a` on `b` and(clear(c), ontable(b), on(c, a), on(a, b)) julia> satisfy(domain, state, goal) true ``` En lugar de llamar repetidamente a `transition`, podemos utilizar la función `PDDL.simulate` para simular directamente el resultado final de una secuencia de acciones: ```julia state = initstate(domain, problem) plan = @pddl("(pick-up a)", "(stack a b)", "(pick-up c)", "(stack c a)") end_state = PDDL.simulate(EndStateSimulator(), domain, state, plan) ``` Como antes, el objetivo se cumple en el estado final: ```julia-repl julia> satisfy(domain, end_state, goal) true ``` El primer argumento de `PDDL.simulate` es una instancia concreta de un `Simulator`, que controla qué información se recoge a medida que progresa la simulación. Por defecto, el primer argumento es un `StateRecorder`, lo que hace que `DDL.simulate` devuelva la trayectoria de todos los estados encontrados, incluido el primero: ```julia-repl julia> traj = PDDL.simulate(domain, state, plan); julia> eltype(traj) GenericState julia> length(traj) 5 ``` Por supuesto, nuestro objetivo no es calcular mentalmente, y ejecutar manualmente, los planes, así que vamos a ver cómo podemos usar todas estas funciones para crear versiones de algoritmos que ya hemos visto para resolver problemas de planificación automáticamente. # Planificadores Utilizando la interfaz PDDL.jl es sencillo implementar algoritmos de planificación que resuelvan problemas en dominios PDDL. Como todos los detalles específicos del dominio y la implementación están encapsulados por la interfaz, el mismo algoritmo puede funcionar en múltiples dominios, e incluso en múltiples representaciones del mismo dominio. Vamos a ver com ejemplos dos planificadores sencillos: las búsquedas hacia adelante y hacia atrás. ## Búsqueda hacia adelante (Forward Search) El algoritmo acepta un `Domain` y un `Problem`, luego construye el estado inicial con la función `initstate`. También extrae la fórmula del objetivo utilizando `PDDL.get_goal`. A continuación, el algoritmo busca en el espacio de estados, expandiendo de forma iterativa los sucesores de cada estado y acción disponible en un orden BFS: ```julia function forward_bfs(domain::Domain, problem::Problem) # Initialize state and extract goal state = initstate(domain, problem) goal = PDDL.get_goal(problem) # Initialize search queue plan = [] queue = [(state, plan)] while length(queue) > 0 # Pop state and plan state, plan = popfirst!(queue) # Check if goal is satisfied if satisfy(domain, state, goal) # Return plan if goal is satisfied return plan end # Iterate over available actions and add successors to queue for action in available(domain, state) next_state = transition(domain, state, action) next_plan = [plan; action] push!(queue, (next_state, next_plan)) end end # Return nothing upon failure return nothing end ``` Como puede verse, la búsqueda se realiza extrayendo un estado y el plan correspondiente de la cola de búsqueda en cada iteración y comprobando si el estado satisface el objetivo mediante `satisfy`. Si se cumple el objetivo, se devuelve el plan. Si no, el estado se expande iterando sobre cada acción `available`, y construyendo el estado sucesor para esa acción usando la función `transition`. El estado sucesor y su plan correspondiente se añaden a la cola. La búsqueda continúa hasta que se agota la cola o se cumple el objetivo. !!! note Eficiencia de la implementación Aunque es fácil de entender, la implementación de BFS presentada aquí es ineficiente en memoria porque almacena el plan para cada estado como parte de la cola de búsqueda. En su lugar, las implementaciones eficientes de planificadores que utilizan BFS deberían basarse en el [algoritmo de Djikstra](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm). ## Búsqueda hacia atrás (Regression/Backward Search) PDDL.jl también soporta la planificación mediante **búsqueda hacia atrás**, también conocida como [**búsqueda de regresión**](https://artint.info/2e/html/ArtInt2e.Ch6.S3.html). La búsqueda hacia atrás funciona tratando la condición de objetivo como un estado *parcial* o *abstracto* que sólo especifica que algunos predicados deben ser verdaderos. Entonces busca en el espacio todas las acciones que podrían alcanzar el estado abstracto actual (llamadas acciones **relevantes**), e invirtiendo la semántica de cada acción (llamada **regresión**). El resultado es un estado abstracto sucesor que representa la imagen previa de la acción: el conjunto de todos los estados que podrían haber alcanzado el estado abstracto actual a través de esa acción. A continuación se muestra una versión BFS de la búsqueda hacia atrás. ```julia function backward_bfs(domain::Domain, problem::Problem) # Construct initial state and goal state init_state = initstate(domain, problem) state = goalstate(domain, problem) # Initialize search queue plan = [] queue = [(state, plan)] while length(queue) > 0 # Pop state and plan state, plan = popfirst!(queue) # Return plan if initial state implies the current abstract state if all(evaluate(domain, init_state, fluent) == val for (fluent, val) in PDDL.get_fluents(state)) return plan end # Iterate over relevant actions and add pre-image to queue for action in relevant(domain, state) next_state = regress(domain, state, action) next_plan = [action; plan] push!(queue, (next_state, next_plan)) end end # Return nothing upon failure return nothing end ``` Este algoritmo es muy similar al anterior: Primero construye un estado inicial (usando `initstate`) y un estado objetivo abstracto (usando `goalstate`) a partir del dominio y el problema. A continuación, busca en BFS desde el estado objetivo abstracto, iterando sobre las acciones que son `relevant` para alcanzar el estado abstracto actual, luego calcula la preimagen inducida por cada acción utilizando `regress` y añade el estado resultante a la cola. La búsqueda termina cuando el estado inicial se encuentra en la preimagen de alguna acción, es decir, todos los fluentes que son verdaderos en la preimagen son también verdaderos en el estado inicial. !!! note ¡Atención! PDDL.jl actualmente sólo proporciona implementaciones correctas de las operaciones de búsqueda de regresión (`relevant` y `regress`) para dominios de estilo STRIPS, que es más limitado que PDDL. Esto significa que la búsqueda por regresión no está soportada actualmente para dominios con fluentes no booleanos, precondiciones negativas, precondiciones disyuntivas, precondiciones cuantificadas o efectos condicionales. ## Otros planificadores Aunque PDDL.jl hace que sea relativamente fácil implementar algoritmos de planificación desde cero, el rendimiento y la (re)usabilidad de estos algoritmos requieren un diseño más cuidadoso. Por ello, el ecosistema PDDL.jl también incluye la biblioteca [**SymbolicPlanners.jl**](https://github.com/JuliaPlanners/SymbolicPlanners.jl), que proporciona una amplia gama de algoritmos y heurísticas de planificación que tienen un [rendimiento comparable](https://github.com/JuliaPlanners/SymbolicPlanners.jl#performance) al de otros sistemas de planificación de uso común. A continuación, mostramos cómo utilizar SymbolicPlanners.jl para resolver un problema Blocksworld mediante [búsqueda A*](https://en.wikipedia.org/wiki/A*_search_algorithm) con la [heurística aditiva](https://doi.org/10.1016/S0004-3702%2801%2900108-4): ```julia using PDDL, PlanningDomains, SymbolicPlanners # Load Blocksworld domain and problem domain = load_domain(:blocksworld) problem = load_problem(:blocksworld, "problem-4") state = initstate(domain, problem) goal = PDDL.get_goal(problem) # Construct A* planner with h_add heuristic planner = AStarPlanner(HAdd()) # Solve the problem using the planner sol = planner(domain, state, goal) ``` Podemos comprobar que, en efecto, la solución resultante verifica los objetivos perseguidos: ```julia-repl julia> goal and(on(d, c), on(c, b), on(b, a), on(a, e)) julia> collect(sol) 10-element Vector{Any}: unstack(b, a) put-down(b) unstack(a, d) stack(a, e) pick-up(b) stack(b, a) pick-up(c) stack(c, b) pick-up(d) stack(d, c) julia> satisfy(domain, sol.trajectory[end], goal) true ``` Esta librería adicional de planificadores incluye: * Planificación hacia delante del espacio de estados (A*, BFS, etc.) * Planificación hacia atrás (regresión) * Planificación basada en políticas (RTDP, RTHS, MCTS, etc.) * Heurística de distancia relajada (Manhattan, hadd, hmax, etc.) * Simulación de políticas y planes * Marco modular para la especificación de objetivos, recompensas y costes. * Soporte para dominios PDDL con flujos numéricos y tipos de datos personalizados.