Introducción a la planificación htn



Descargar 29,84 Kb.
Fecha de conversión20.03.2017
Tamaño29,84 Kb.

Introducción a la planificación HTN

  • Lenguaje HTN-PDDL y planificador HTNP
  • Conceptos para realizar la Práctica 2

Indice

Planificación HTN (Hierarchical Task Networks)

  • Hay muchos problemas en los que sólo la representación y razonamiento basados en precondiciones/efectos no es suficiente.
  • La abstracción de tareas permite representar conocimiento para que un planificador pueda usar otros medios para escoger qué acción aplicar

Planificación HTN: Conceptos

  • Representación de acciones a distintos niveles de abstracción
  • Las acciones en cualquier nivel de abstracción se denominan Tareas (Tasks)
  • Distinción entre tareas (acciones) primitivas y tareas compuestas.

Planificación HTN: Conceptos

  • Tarea Primitiva:
    • representa una acción del nivel de abstracción inferior, indivisible y cuya ejecución produce un cambio en el estado del mundo

Planificación HTN: Conceptos

  • Tarea Compuesta:
    • Representa una acción o proceso de alto nivel que debe llevarse a cabo con la intervención de varias tareas de nivel inferior y que, normalmente, presenta distintas alternativas para su realización.

Planificación HTN: Conceptos

  • Método de descomposición
    • Una alternativa o modo de llevar a cabo una tarea, representado como un conjunto de subtareas (compuestas o primitivas) y relaciones de orden entre ellas.
    • Describe qué pasos hay que seguir para descomponer una tarea en una secuencia de tareas primitivas
    • Una tarea compuesta tiene asociados varios métodos de descomposición: formas distintas de descomponer la tarea.

Ejemplo: Representación de un dominio HTN con HTN-PDDL.

  • HTN-PDDL es una extensión de PDDL para representar dominios de planificación HTN basados en tareas primitivas y compuestas
    • PDDL es un estándar para representar acciones de dominios de planificación
    • Es un lenguaje desarrollado por el grupo de trabajo Sepia del Departamento de Ciencias de la Computación e I.A. (DECSAI)
    • Es el lenguaje usado por el planificador HTNP, también desarrollado por el grupo SEPIA
    • HTNP es la parte central de la tecnología transferida a IACTIVE Intelligent Solutions una spin-off creada desde DECSAI para ofrecer soluciones y servicios basados en la tecnología de planificación y scheduling inteligentes.
  • Primero vemos cómo representar tareas primitivas con PDDL y después tareas compuestas y métodos.

Acciones primitivas: PDDL durative-actions

    • Objetos del dominio:
    • Acciones primitivas:
      • Representación PDDL
      • Parámetros con tipo, precondiciones, efectos, duración
  • (define (domain viajes)
  • (:requirements :typing :fluents :derived-predicates :negative-preconditions :htn-expansion)
  • (:constants <….>)
  • (:types Persona Sitio – object
  • Hogar Aeropuerto - Sitio
  • (:predicates (en ?p - Persona ?s – Sitio))
  • (:functions (distancia ?x ?y – Sitio)
  • (dinero ?p – Persona)
  • (velocidad-taxi)
  • (precio_km)
  • )
  • (:durative-action ir_en_taxi
  • :parameters (?u – Persona ?o ?d – Sitio)
  • :duration (= ?dur (* (distancia ?o ?d)
  • (velocidad_taxi) )
  • :condition (and (en ?u ?o))
  • :effect (and (not (en ?u ?o))
  • (en ?u ?d)))

Otros aspectos útiles de PDDL

  • Valores numéricos/funciones
  • (:durative-action ir_en_taxi
  • :parameters (?u – Persona ?o ?d – Sitio)
  • :duration (= ?dur (* (distancia ?o ?d)
  • (velocidad_taxi) )
  • :condition (and (en ?u ?o)
  • (> (dinero ?u)
  • (* (precio_km)(distancia ?o ?d))
  • :effect (and (not (en ?u ?o))
  • (en ?u ?d)))

Otros aspectos útiles de PDDL

  • Valores numéricos/funciones
  • Derived literals: reglas de inferencia para “derivar” predicados de las precondiciones
  • (:derived (tiene_dinero ?p – Persona ?org ?dst – Sitio)
  • ((> (dinero ?u)
  • (* (precio_km)(distancia ?o ?d)))
  • (:durative-action ir_en_taxi
  • :parameters (?u – Persona ?o ?d – Sitio)
  • :duration (= ?dur (* (distancia ?o ?d)
  • (velocidad_taxi) )
  • :condition (and (en ?u ?o)
  • (tiene_dinero ?u ?o ?d))
  • :effect (and (not (en ?u ?o))
  • (en ?u ?d)))

Otros aspectos útiles de PDDL

  • Valores numéricos/funciones
  • Derived literals: reglas de inferencia para “derivar” predicados de las precondiciones
  • Asignación, incremento/decremento de funciones
  • (:derived (tiene_dinero ?p – Persona ?org ?dst – Sitio)
  • ((> (dinero ?u)
  • (* (precio_km)(distancia ?o ?d)))
  • (:durative-action ir_en_taxi
  • :parameters (?u – Persona ?o ?d – Sitio)
  • :duration (= ?dur (* (distancia ?o ?d)
  • (velocidad_taxi) )
  • :condition (and (en ?u ?o)
  • (tiene_dinero ?u ?o ?d))
  • :effect (and (not (en ?u ?o))
  • (en ?u ?d)))
  • (:durative-action pagar
  • :parameters (?u – Persona ?c – number)
  • :duration (= ?dur 1)
  • :condition (> (- (dinero ?u) ?c) 0)
  • :effect (decrease (dinero ?u) ?c)

Tareas Compuestas

  • Tarea compuesta
  • Varios métodos
    • Precondición
    • Descomposición
  • Tareas “inline”
    • Crear acciones “al vuelo” para un uso muy específico
  • Relaciones de orden
    • ( )
    • [ ]
  • (:task irAeropuerto
  • :parameters (?p – Persona ?c – Hogar ?a – Aeropuerto)
  • (:method enTaxi
  • :precondition ()
  • :tasks (
  • (ir_en_taxi ?p ?c ?a)
  • (:inline (bind ?tarifa (* (distancia ?c ?a)
  • (precio_km))) ())
  • (pagar ?p ?tarifa)
  • )
  • (:method enBus
  • :precondition ()
  • :tasks ((:inline (bind ?tarifa (tarifa-bus)) () )
  • (pagar ?p ?tarifa)
  • (ir_en_bus ?p ?c ?a))
  • (:method Andando
  • :precondition ()
  • :tasks (irAndando ?p ?c ?a))
  • );;task

Tareas Compuestas

  • (:task irAeropuerto
  • :parameters (?p – Persona ?c – Hogar ?a – Aeropuerto)
  • (:method enTaxi
  • :precondition ()
  • :tasks (
  • (ir_en_taxi ?p ?c ?a)
  • (:inline (bind ?tarifa (* (distancia ?c ?a)
  • (precio_km))) ())
  • (pagar ?p ?tarifa)
  • )
  • (:method enBus
  • :precondition ()
  • :tasks ((:inline (bind ?tarifa (tarifa-bus)) () )
  • (pagar ?p ?tarifa)
  • (ir_en_bus ?p ?c ?a))
  • (:method Andando
  • :precondition ()
  • :tasks (irAndando ?p ?c ?a))
  • );;task
  • (:task Viajar
  • :parameters (?p – Persona
  • ?x ?y – Sitio)
  • (:method enAvion
  • :precondition (tiene prisa ?p)
  • :tasks (
  • (irAeropuerto ?p ?x GarciaLorca)
  • (Volar ?p GarciaLorca Barajas)
  • (irDestino ?p Barajas ?y)
  • )
  • (:method enCoche
  • :precondition (not (tiene_prisa ?p))
  • :tasks (irEnCoche ?p ?x ?y))
  • )

Problema HTN:

  • se describe a partir de un estado inicial y de un objetivo representando una tarea de alto nivel a llevar a cabo.
  • (define (problem UnViaje) (:domain Viajes)
  • (:objects
  • MiCasa CasaMiPrimo – Hogar
  • GarciaLorca Barajas – Aeropuerto
  • Yo - Persona
  • )
  • (:init
  • (en Yo MiCasa)
  • (= (dinero Yo) 100)
  • (= (distancia MiCasa GarciaLorca) 20)
  • (= (precio-km) 7)
  • )
  • (:tasks-goal
  • :tasks( (Viajar Yo MiCasa CasaMiPrimo))
  • )
  • )

Proceso de planificación HTN: Planificador HTNP

Proceso de planificación HTN: Planificador HTNP

HTNP y la Transferencia Tecnológica

Práctica 2

  • Definir un dominio HTN de forma incremental
    • No se parte de cero
    • Tareas primitivas completas
    • Tareas compuestas incompletas
    • El dominio final tiene que resolver tres problemas
    • Resolver problemas en el dominio ZenoTravel (estándar para contrastar planificadores)

Dominio ZenoTravel

    • Transporte aéreo entre ciudades
    • Personas, ciudades, aviones
    • En concreto: 5 ciudades, 1 avión, 3 personas

Acciones primitivas

    • Embarcar una persona en un avión en una ciudad concreta.
    • Desembarcar una persona en un avión en una ciudad concreta.
    • Volar un avión de una ciudad origen a una ciudad destino a una velocidad lenta
    • Volar un avión de una ciudad origen a una ciudad destino a una velocidad rápida
    • Repostar un avión en una ciudad.

Preámbulo, tipos, predicados y funciones

  • (define (domain zeno-travel)
  • (:requirements
  •   :typing
  •   :fluents
  •  :derived-predicates
  •  :negative-preconditions
  •  :universal-preconditions
  •  :disjuntive-preconditions
  •  :conditional-effects
  •  :htn-expansion
  •   ; Requisitos adicionales para el manejo del tiempo
  •  :durative-actions
  •  :metatags
  • )

Preámbulo, tipos, predicados y funciones

  • (:types aircraft person city - object)
  • (:constants slow fast - object)
  • (:predicates (at ?x - (either person aircraft) ?c - city)
  •             (in ?p - person ?a - aircraft)
  •             (diferente ?x ?y) ) ;;predicado derivado, ver más abajo
  • (igual ?x ?y) ;;predicado derivado, ver más abajo
  •             (hay-fuel ?a ?c1 ?c2) ;;predicado derivado, ver más abajo
  •             )

Preámbulo, tipos, predicados y funciones

  • (:functions
  • (fuel ?a - aircraft) ;;cantidad de fuel actual de un avión
  •            (distance ?c1 - city ?c2 - city) ;;distancia entre dos ciudades
  •            (slow-speed ?a - aircraft); ;;velocidad “lenta” de un avión
  •            (fast-speed ?a - aircraft) ;;velocidad “rápida” de un avión
  •            (slow-burn ?a - aircraft);;razón de consumo de un avión a velocidad lenta
  •            (fast-burn ?a - aircraft);razón de consumo de un avión a velocidad rápida
  •            (capacity ?a - aircraft) ;;capacidad de fuel de un avión
  •            (refuel-rate ?a - aircraft) ;;razón de repostaje de un avión (para calcular ;; el tiempo de repostaje
  •            (total-fuel-used) ;;valor del fuel total usado
  •            (boarding-time) ;;valor constante de tiempo de embarque
  •            (debarking-time) ;;valor constante de tiempo de desembarque
  •            )

Embarcar una persona en un avión en una ciudad concreta.

  • (:durative-action board
  • :parameters (?p - person ?a - aircraft ?c - city)
  • :duration (= ?duration (boarding-time))
  • :condition (and  (at ?p ?c)
  •                   (at ?a ?c))
  • :effect (and  (not (at ?p ?c))
  •                (in ?p ?a)))

Desembarcar una persona en un avión en una ciudad concreta.

  • (:durative-action debark
  • :parameters (?p - person ?a - aircraft ?c - city)
  • :duration (= ?duration (debarking-time))
  • :condition (and (in ?p ?a)
  •                  (at ?a ?c))
  • :effect (and  (not (in ?p ?a))
  •                (at ?p ?c)))

Volar un avión de una ciudad origen a una ciudad destino a una velocidad lenta

  • (:durative-action fly
  • :parameters (?a - aircraft ?c1 ?c2 - city)
  • :duration (= ?duration (/ (distance ?c1 ?c2) (slow-speed ?a)))
  • :condition (and (at ?a ?c1)
  •                  (>= (fuel ?a)(* (distance ?c1 ?c2) (slow-burn ?a))))
  • :effect (and  (not (at ?a ?c1))
  •                (at ?a ?c2)
  •               (increase (total-fuel-used)
  •                          (* (distance ?c1 ?c2) (slow-burn ?a)))
  •                (decrease (fuel ?a)
  •                          (* (distance ?c1 ?c2) (slow-burn ?a)))))

Volar un avión de una ciudad origen a una ciudad destino a una velocidad rápida

  • (:durative-action zoom
  • :parameters (?a - aircraft ?c1 ?c2 - city)
  • :duration (= ?duration (/ (distance ?c1 ?c2) (fast-speed ?a)))
  • :condition (and (at ?a ?c1)
  •                 (>= (fuel ?a) (* (distance ?c1 ?c2) (fast-burn ?a))))
  • :effect (and (not (at ?a ?c1))
  •               (at ?a ?c2)
  •               (increase (total-fuel-used)
  •                           (* (distance ?c1 ?c2) (fast-burn ?a)))
  •               (decrease (fuel ?a)
  •                           (* (distance ?c1 ?c2) (fast-burn ?a)))))

Repostar un avión en una ciudad.

  • (:durative-action refuel
  • :parameters (?a - aircraft ?c - city)
  • :duration (= ?duration (/(- (capacity ?a) (fuel ?a))(refuel-rate ?a)))
  • :condition (and  (> (capacity ?a) (fuel ?a))
  •                  (at ?a ?c))
  • :effect (assign (fuel ?a) (capacity ?a)))

Predicados derivados

  • ;; el consecuente "vacío" se representa como "()" y significa "siempre verdad"
  • ;;un objeto es siempre igual a sí mismo
  • (:derived
  •   (igual ?x ?x) ())
  • ;; dos objetos son diferentes si no son iguales
  • (:derived
  •   (diferente ?x ?y) (not (igual ?x ?y)))
  •  
  • (:derived
  •    (hay-fuel ?a - aircraft ?c1 - city ?c2 - city)
  •   (> (fuel ?a) 1))

Tareas Compuestas

Transportar una persona a una ciudad destino

  • (:task transport-person
  •    :parameters (?p - person ?c - city)
  •   (:method Case1 ; si la persona esá en la ciudad no se hace nada
  •     :precondition (at ?p ?c)
  •     :tasks ()
  •    )
  •  ;si la persona no está en la ciudad destino, pero avion y persona están en la misma ciudad
  • (:method Case2
  •     :precondition (and (at ?p - person ?c1 - city)
  •                        (at ?a - aircraft ?c1 - city))
  •             
  •     :tasks (
  •            (board ?p ?a ?c1)
  •             (mover-avion ?a ?c1 ?c)
  •             (debark ?p ?a ?c )))
  •    )

Mover avión

  • (:task mover-avion
  • :parameters (?a - aircraft ?c1 - city ?c2 -city)
  • (:method fuel-suficiente
  •   :precondition (hay-fuel ?a ?c1 ?c2)
  •   :tasks (
  •          (fly ?a ?c1 ?c2)
  •         )
  •    )
  •   )

Metodología

  • Comprobar que con este dominio básico se resuelve el problema siguiente:
  • (= (distance c1 c2) 100)
  • (= (distance c2 c3) 100)
  • (= (distance c3 c4) 100)
  • (= (distance c4 c5) 100)
  • (= (distance c5 c1) 100)
  • (= (distance c1 c5) 100)
  • (= (distance c1 c3) 150)
  • (= (distance c1 c4) 150)
  • (= (distance c2 c5) 150)
  • (= (distance c2 c4) 150)
  • (= (distance c3 c1) 150)
  • (= (distance c3 c5) 150)
  • (= (distance c4 c2) 150)
  • (= (distance c4 c1) 150)
  • (= (distance c5 c2) 150)
  • (= (distance c5 c3) 150)
  • (= (fuel a1) 100000)
  • (= (slow-speed a1) 10)
  • (= (fast-speed a1) 20)
  • (= (slow-burn a1) 1)
  • (= (fast-burn a1) 2)
  • (= (capacity a1) 100000)
  • (= (refuel-rate a1) 1)
  • (= (total-fuel-used) 0)
  • (= (boarding-time) 1)
  • (= (debarking-time) 1)
  • )
  • (:tasks-goal
  • :tasks(
  • (transport-person p1 c4)
  • (transport-person p2 c5)
  • (transport-person p3 c2))))
  • (define (problem zeno-0)
  • (:domain zeno-travel)
  • (:customization
  • (= :time-format "%d/%m/%Y %H:%M:%S")
  • (= :time-horizon-relative 2500)
  • (= :time-start "05/06/2007 08:00:00")
  • (= :time-unit :hours))
  • (:objects
  • p1 p2 p3 p4 - person
  • c1 c2 c3 c4 c5 - city
  • a1 - aircraft
  • )
  • (:init
  • (at p1 c4)
  • (at p2 c4)
  • (at p3 c5)
  • (at a1 c4)

Metodología

  • (= (distance c1 c2) 100)
  • (= (distance c2 c3) 100)
  • (= (distance c3 c4) 100)
  • (= (distance c4 c5) 100)
  • (= (distance c5 c1) 100)
  • (= (distance c1 c5) 100)
  • (= (distance c1 c3) 150)
  • (= (distance c1 c4) 150)
  • (= (distance c2 c5) 150)
  • (= (distance c2 c4) 150)
  • (= (distance c3 c1) 150)
  • (= (distance c3 c5) 150)
  • (= (distance c4 c2) 150)
  • (= (distance c4 c1) 150)
  • (= (distance c5 c2) 150)
  • (= (distance c5 c3) 150)
  • (= (fuel a1) 100000)
  • (= (slow-speed a1) 10)
  • (= (fast-speed a1) 20)
  • (= (slow-burn a1) 1)
  • (= (fast-burn a1) 2)
  • (= (capacity a1) 100000)
  • (= (refuel-rate a1) 1)
  • (= (total-fuel-used) 0)
  • (= (boarding-time) 1)
  • (= (debarking-time) 1)
  • )
  • (:tasks-goal
  • :tasks(
  • (transport-person p1 c5)
  • (transport-person p2 c5)
  • (transport-person p3 c5)
  • (define (problem zeno-0)
  • (:domain zeno-travel)
  • (:customization
  • (= :time-format "%d/%m/%Y %H:%M:%S")
  • (= :time-horizon-relative 2500)
  • (= :time-start "05/06/2007 08:00:00")
  • (= :time-unit :hours))
  • (:objects
  • p1 p2 p3 p4 - person
  • c1 c2 c3 c4 c5 - city
  • a1 - aircraft
  • )
  • (:init
  • (at p1 c4)
  • (at p2 c4)
  • (at p3 c5)
  • (at a1 c4)

Metodología

  • PROBLEMA 2: Comprobar que NO se resuelve el problema siguiente y volver a modificar el dominio
  • (= (distance c1 c2) 100)
  • (= (distance c2 c3) 100)
  • (= (distance c3 c4) 100)
  • (= (distance c4 c5) 100)
  • (= (distance c5 c1) 100)
  • (= (distance c1 c5) 100)
  • (= (distance c1 c3) 150)
  • (= (distance c1 c4) 150)
  • (= (distance c2 c5) 150)
  • (= (distance c2 c4) 150)
  • (= (distance c3 c1) 150)
  • (= (distance c3 c5) 150)
  • (= (distance c4 c2) 150)
  • (= (distance c4 c1) 150)
  • (= (distance c5 c2) 150)
  • (= (distance c5 c3) 150)
  • (= (fuel a1) 200)
  • (= (slow-speed a1) 10)
  • (= (fast-speed a1) 20)
  • (= (slow-burn a1) 1)
  • (= (fast-burn a1) 2)
  • (= (capacity a1) 300)
  • (= (refuel-rate a1) 1)
  • (= (total-fuel-used) 0)
  • (= (boarding-time) 1)
  • (= (debarking-time) 1)
  • )
  • (:tasks-goal
  • :tasks(
  • (transport-person p1 c5)
  • (transport-person p2 c5)
  • (transport-person p3 c5)
  • (define (problem zeno-0)
  • (:domain zeno-travel)
  • (:customization
  • (= :time-format "%d/%m/%Y %H:%M:%S")
  • (= :time-horizon-relative 2500)
  • (= :time-start "05/06/2007 08:00:00")
  • (= :time-unit :hours))
  • (:objects
  • p1 p2 p3 p4 - person
  • c1 c2 c3 c4 c5 - city
  • a1 - aircraft
  • )
  • (:init
  • (at p1 c4)
  • (at p2 c4)
  • (at p3 c5)
  • (at a1 c4)

Metodología

  • PROBLEMA ·3: Comprobar que NO se resuelve el problema siguiente y modificar el dominio
  • (= (distance c1 c2) 100)
  • (= (distance c2 c3) 100)
  • (= (distance c3 c4) 100)
  • (= (distance c4 c5) 100)
  • (= (distance c5 c1) 100)
  • (= (distance c1 c5) 100)
  • (= (distance c1 c3) 150)
  • (= (distance c1 c4) 150)
  • (= (distance c2 c5) 150)
  • (= (distance c2 c4) 150)
  • (= (distance c3 c1) 150)
  • (= (distance c3 c5) 150)
  • (= (distance c4 c2) 150)
  • (= (distance c4 c1) 150)
  • (= (distance c5 c2) 150)
  • (= (distance c5 c3) 150)
  • (= (fuel-limit) 1500)
  • (= (fuel a1) 200)
  • (= (slow-speed a1) 10)
  • (= (fast-speed a1) 20)
  • (= (slow-burn a1) 1)
  • (= (fast-burn a1) 2)
  • (= (capacity a1) 300)
  • (= (refuel-rate a1) 1)
  • (= (total-fuel-used) 0)
  • (= (boarding-time) 1)
  • (= (debarking-time) 1)
  • )
  • (:tasks-goal
  • :tasks(
  • (transport-person p1 c5)
  • (transport-person p2 c5)
  • (transport-person p3 c5)
  • (define (problem zeno-0)
  • (:domain zeno-travel)
  • (:customization
  • (= :time-format "%d/%m/%Y %H:%M:%S")
  • (= :time-horizon-relative 2500)
  • (= :time-start "05/06/2007 08:00:00")
  • (= :time-unit :hours))
  • (:objects
  • p1 p2 p3 p4 - person
  • c1 c2 c3 c4 c5 - city
  • a1 - aircraft
  • )
  • (:init
  • (at p1 c4)
  • (at p2 c4)
  • (at p3 c5)
  • (at a1 c4)
  • (domain …..
  • (:task transport-person
  •    :parameters (?p - person ?c - city)
  • ………….
  •  ;si la persona no está en la ciudad destino, pero avion y persona están en la misma ciudad
  • (:method Case2
  •     :precondition (and (at ?p - person ?c1 - city)
  •                        (at ?a - aircraft ?c1 - city))
  •             
  •     :tasks (
  •            (board ?p ?a ?c1)
  •             (mover-avion ?a ?c1 ?c)
  •             (debark ?p ?a ?c )))
  • …..
  • …..
  • (:import “Primitivas-Zenotravel.pddl”)
  •   )


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal