Resolución de un problema simple de planificación automática con PDDL #2

In english, can be found here: https://medium.com/@ramonbarrioslascar/simple-classical-planning-problem-solved-with-pddl-9c8825ebb3b2

Figura 1. Diagrama del universo o dominio del problema a resolver

En este problema usamos un mapa como el de la Figura 1, en un universo de ubicaciones, (un puerto, una ciudad, un par de fábricas que procesan y un almacén que despacha). En el mismo se tienen cinco ubicaciones o locaciones, una cantidad de contenedores que “llegan” por el muelle y que “salen” por el almacén, y teniendo una serie de restricciones (como sitios que reciben con un límite y sitios que simplemente no; como que hay que procesar los elementos en las fábricas antes de ser despachados y como que solo se despacha desde el almacén) y el planificador debe reportar las acciones para lograr la meta declarada: Todos los contenedores deben ser despachados. Se creó el dominio en PDDL que se lista a continuación, mismo que resuelve como se muestra en la Figura 2:

Figura 2. Diagrama del estado final deseado al resolver el problema

(define (domain carga)
    (:requirements
        :adl
        :fluents
    )
    (:types
        tren          - object
        contenedor    - object
        ubicacion     - location
        puerto        - ubicacion
        ciudad        - ubicacion
        almacen       - ubicacion
        fabrica       - ubicacion
    )
    (:functions
        (carga-maxima ?t - tren)       ; con cuánto máximo puede un tren
        (carga-actual ?t - tren)       ; cuánto lleva ahora un tren
        (capacidad ?f - ubicacion)     ; cuánto máximo recibe el lugar
        (ocupacion ?f - ubicacion)     ; cuánto tiene ahora el lugar
    )
    (:predicates
        (ruta ?ori - ubicacion ?dst - ubicacion)
                                       ; hay ruta de ORI a DST?
        (esta ?o - object ?u - ubicacion)
                                       ; está el objeto O en la ubicación U? 
        (cargado ?c - contenedor ?t - tren)
                                       ; está el objeto C en el tren T?
        (procesado ?c - contenedor)    ; fue procesado el contenedor C?
        (despachado ?c - contenedor)   ; fue despachado el contenedor C?
        (procesadora ?u - fabrica)     ; si U procesa
        (despachadora ?u - almacen)    ; si U despacha
    )
    (:action ir
        :parameters (?t - tren ?ori - ubicacion ?dst - ubicacion)
        :precondition (and
            (or
                (ruta ?ori ?dst)       ; hay cómo ir de ORI a DST
                (ruta ?dst ?ori)       ; hay cómo ir de DST a ORI
            )
            (esta ?t ?ori)             ; el tren está en ORI
            (not (esta ?t ?dst))       ; y no está en DST
        )
        :effect (and
            (not (esta ?t ?ori))       ; ya no está en ORI
            (esta ?t ?dst)             ; y está en DST
        )
    )
    (:action cargar
        :parameters (?t - tren ?o - contenedor ?u - ubicacion)
        :precondition (and
            (esta ?t ?u)               ; el tren está en una ubicación
            (esta ?o ?u)               ; el objeto está en una ubicación
            (not (cargado ?o ?t))      ; el objeto no está cargado
            (<= (+ (carga-actual ?t) 1) (carga-maxima ?t))
                                       ; el tren tiene capacidad (actual+1<=máx)
        )
        :effect (and
            (not (esta ?o ?u))         ; el objeto no está en la ubicación
            (cargado ?o ?t)            ; el objeto está en el tren
            (increase (carga-actual ?t) 1)
                                       ; se cargó el tren y usó capacidad
                                       ; (actual += 1)
            (decrease (ocupacion ?u) 1)
                                       ; disminuyó la ocupación (actual-=1)
        )
    )
    (:action descargar
        :parameters (?t - tren ?o - contenedor ?u - ubicacion)
        :precondition (and
            (esta ?t ?u)               ; el tren está en la ubicación
                                       ; (donde debe descargar)
            (cargado ?o ?t)            ; tiene un objeto cargado
            (not (esta ?o ?u))         ; el objeto no está en la ubicación
            (<= (+ (ocupacion ?u) 1) (capacidad ?u))
                                       ; debe haber al menos un cupo para recibir
        )
        :effect (and
            (not (cargado ?o ?t))      ; ahora el objeto no está cargado
            (esta ?o ?u)               ; pero está en la ubicación
            (decrease (carga-actual ?t) 1)
                                       ; y se liberó capacidad en el tren
                                       ; (actual-=1)
            (increase (ocupacion ?u) 1)
                                       ; aumentó la ocupación en este sitio
                                       ; (ocupación+=1)
        )
    )
    (:action procesar
        :parameters (?o - contenedor ?u - fabrica)
        :precondition (and
            (procesadora ?u)           ; aquí se procesa
            (esta ?o ?u)               ; el objeto está en la ubicación
            (not (procesado ?o))       ; no se ha procesador aún
            (not (despachado ?o))      ; no se ha despachado aún
        )
        :effect (and
            (procesado ?o)             ; ha sido procesado
                                       ; (y todo lo demás igual)
        )
    )
    (:action despachar
        :parameters (?o - contenedor ?u - almacen)
        :precondition (and
            (despachadora ?u)          ; aquí se despacha
            (esta ?o ?u)               ; el objeto está en la ubicación
            (procesado ?o)             ; ha sido procesado antes
            (not (despachado ?o))      ; pero no se ha despachado aún
        )
        :effect (and
            (despachado ?o)            ; ha sido despachado
                                       ; (y todo lo demás igual)
            (decrease (ocupacion ?u) 1)
                                       ; disminuyó la ocupación del sitio
                                       ; (ocupación-=1)
        )
    )
)

De notar:

• Se usan numerosos requerimientos, por eso se incluye :adl, que según la documentación equivale a incluir :strips, :typing, :disjunctive-preconditions, :equality, :quantified-preconditions y:conditional-effects. Se necesitan tipos (para poder filtrar donde el planner intenta ciertas acciones), precondiciones disyuntivas (porque se usa or), igualdad (porque se usa =). También se requiere de :fluents, porque se hacen operaciones y comparaciones matemáticas
• En el dominio hay dos tipos base: tren, y contenedor; hay ubicaciones (location), y cuatro subtipos del tipo ubicación: puerto, ciudad, almacén y fábrica.
• Hay cuatro funciones, que son atributos numéricos que se pueden leer y escribir de cada objeto que los tenga: carga-maxima, que es el atributo de la capacidad máxima de un objeto (lo tienen los trenes); carga-actual, que es el atributo de la capacidad usada de un objeto (lo tienen los trenes); capacidad, que es el atributo de la capacidad máxima de una ubicación; ocupacion, que es la capacidad usada de una ubicación.
• Hay siete predicados, que son lo que se puede sensar y validar como verdadero o falso, o forzar para uno de esos dos valores. Son ruta() que es verdadero si hay ruta entre dos ubicaciones; esta() que devuelve si un objeto (puede ser un tren o cualquier otro, como un contenedor) está en una ubicación; cargado() que es verdadero si un objeto está cargado o montado en otro (un contenedor en un tren); procesado() que es verdadero si un objeto (un contenedor) ya se procesó en una ubicación (en una fábrica); despachado() que es verdadero si un objeto (un contenedor) ya fue “procesado” en una ubicación (en el almacén) y se considera como fuera del mapa; procesadora() que es verdadero si en la ubicación (fábrica) se procesan objetos (contenedores), cosa que hay que hacer antes de despacharlos; despachadora() que es verdadero sin en la ubicación (almacén) se procesan para enviar fuera del mapa a los objetos (contenedores).
• Hay cinco acciones, que son “las cosas que hacen cambios”: ir(), que son los desplazamientos de un objeto (un tren) de una ubicación (origen) a otra (destino); cargar(), que toma un objeto (contenedor) de una ubicación y lo monta a otro (tren) teniendo en cuenta las limitaciones del segundo; descargar(), que toma un objeto (contenedor) montado en otro (tren) y lo deja en una ubicación teniendo en cuenta las limitaciones de esta y liberando capacidad del otro (tren); procesar() que en una ubicación con el predicado procesadora() lo marca como procesado, y despachar() que en una ubicación con el predicado despachadora() lo marca como despachado y además lo remueve del mapa, liberando capacidad en la ubicación.

Teniendo todo, especificamos el problema en PDDL como se lista:

(define (problem llevar-y-procesar-carga)
    (:domain carga)
    (:objects
        A                         - almacen
        F1 F2                     - fabrica
        P                         - puerto
        C                         - ciudad
        Tren                      - tren
        K1 K2 K3 K4 K5 K6 K7 K8   - contenedor
    )
    (:init
                                       ; datos de contenedores
        (esta K1 P)                    ; K1 en el puerto y es contenedor
        (esta K2 P)                    ; K2 en el puerto y es contenedor
        (esta K3 P)                    ; K3 en el puerto y es contenedor
        (esta K4 P)                    ; K4 en el puerto y es contenedor
        (esta K5 P)                    ; K5 en el puerto y es contenedor
        (esta K6 P)                    ; K6 en el puerto y es contenedor
        (esta K7 P)                    ; K7 en el puerto y es contenedor
        (esta K8 P)                    ; K8 en el puerto y es contenedor


                                       ; datos del tren
        (esta Tren P) (= (carga-maxima Tren) 4) (= (carga-actual Tren) 0)

                                       ; datos de las locaciones
        (ruta A P)                     ; hay cómo ir de A ←→ P
        (ruta A C)                     ; hay cómo ir de A ←→ C
        (ruta A F2)                    ; hay cómo ir de A ←→ F2
        (ruta C P)                     ; hay cómo ir de C ←→ P
        (ruta C F1)                    ; hay cómo ir de C ←→ F1
        (ruta C F2)                    ; hay cómo ir de C ←→ F2
        (procesadora F1)               ; hay cómo procesar en F1
        (= (capacidad F1) 3)           ; F1 puede recibir 3
        (= (ocupacion F1) 0)           ; F1 inicia sin contenedores
        (procesadora F2)               ; hay cómo procesar en F2
        (= (capacidad F2) 1)           ; F2 puede recibir 1
        (= (ocupacion F2) 0)           ; F2 inicia sin contenedores
        (despachadora A)               ; hay cómo despachar en A
        (= (capacidad A) 2)            ; A solo recibe 2 sin haber despachado
        (= (ocupacion A) 0)            ; A inicia sin contenedores
        (= (capacidad C) 0)            ; C no puede recibir
        (= (ocupacion C) 0)            ; C inicia sin contenedores
        (= (capacidad P) 0)            ; P inicia sin contenedores
        (= (ocupacion P) 1000)         ; P inicia ocupadísimo
    )
    (:goal
        (and
            (despachado K1)            ; K1 ha sido procesado y despachado
            (despachado K2)            ; K2 ha sido procesado y despachado
            (despachado K3)            ; K3 ha sido procesado y despachado
            (despachado K4)            ; K4 ha sido procesado y despachado
            (despachado K5)            ; K5 ha sido procesado y despachado
            (despachado K6)            ; K6 ha sido procesado y despachado
            (despachado K7)            ; K7 ha sido procesado y despachado
            (despachado K8)            ; K8 ha sido procesado y despachado
        )
    )
)

Nótese cómo se dan valor verdadero especificando en :init las rutas entre ubicaciones, la ubicación de cada puerto, ciudad, fábrica y almacén, contenedor y tren; cuánto tienen y cuánto pueden tener ocupado cada ubicación y el tren; y dónde se procesa y se despacha, y se pide que los contenedores ya estén despachados (:goal).

Resultados: Luego de la ejecución de un planificador — que usa A* — resuelve a un plan de 75 pasos que se muestra. Nótese que el plan no es óptimo, ya que manualmente se determinó que son necesarios 9 pasos para recoger un contenedor, pasarlo por todas las etapas necesarias y despacharlo, y siendo 8 contenedores, manualmente, uno a uno, y sin planificación extra se necesitarían 72 pasos — pero lograr el óptimo con un planificador no es la finalidad de esta actividad — .

Plan Completo (75 pasos)

cargar(tren, k4, p)
    cargar(tren, k1, p)
    cargar(tren, k2, p)
    ir(tren, p, a)
    descargar(tren, k1, a)
    ir(tren, a, p)
    cargar(tren, k3, p)
    ir(tren, p, a)
    ir(tren, a, f2)
    descargar(tren, k2, f2)
    ir(tren, f2, c)
    procesar(k2, f2)
    ir(tren, c, p)
    cargar(tren, k6, p)
    ir(tren, p, c)
    ir(tren, c, f2)
    cargar(tren, k2, f2)
    descargar(tren, k4, f2)
    ir(tren, f2, a)
    descargar(tren, k2, a)
    despachar(k2, a)
    ir(tren, a, p)
    cargar(tren, k5, p)
    ir(tren, p, c)
    procesar(k4, f2)
    ir(tren, c, f2)
    cargar(tren, k4, f2)
    descargar(tren, k6, f2)
    procesar(k6, f2)
    cargar(tren, k6, f2)
    ir(tren, f2, a)
    descargar(tren, k4, a)
    despachar(k4, a)
    descargar(tren, k6, a)
    despachar(k6, a)
    ir(tren, a, p)
    cargar(tren, k7, p)
    ir(tren, p, a)
    ir(tren, a, f2)
    descargar(tren, k7, f2)
    procesar(k7, f2)
    cargar(tren, k7, f2)
    descargar(tren, k3, f2)
    procesar(k3, f2)
    cargar(tren, k3, f2)
    ir(tren, f2, a)
    descargar(tren, k3, a)
    despachar(k3, a)
    descargar(tren, k7, a)
    despachar(k7, a)
    ir(tren, a, p)
    cargar(tren, k8, p)
    ir(tren, p, a)
    ir(tren, a, f2)
    descargar(tren, k8, f2)
    procesar(k8, f2)
    cargar(tren, k8, f2)
    descargar(tren, k5, f2)
    procesar(k5, f2)
    cargar(tren, k5, f2)
    ir(tren, f2, a)
    descargar(tren, k5, a)
    despachar(k5, a)
    descargar(tren, k8, a)
    despachar(k8, a)
    cargar(tren, k1, a)
    ir(tren, a, f2)
    descargar(tren, k1, f2)
    procesar(k1, f2)
    cargar(tren, k1, f2)
    ir(tren, f2, a)
    descargar(tren, k1, a)
    despachar(k1, a)

Nota: PDDL en Julia lista las acciones a modo de función *nombre_acción*(*argumentos*).

En la Figura 3, se muestra parte de un notebook en lenguaje Julia con parte de la ejecución.

Figura 3. Parte de la ejecución de un notebook en lenguaje Julia resolviendo el problema