PDDL
Lenguajes para planificación
Lenguajes para la descripción de problemas de planificación:
STRIPS [Stanford Research Institute Problem Solver]
Richard Fikes & Nils Nilsson, SRI International, 1971
ADL [Action Description Language]
Language]
Edwin Pednault,
Pednault, IBM Research,
Research, 1987
PDDL [Planning Domain Definition Language]
Drew McDermott, Yale University, 1998
International Planning Competition
@ ICAPS [International Conference on Automated Planning and Scheduling]
http://ipc.icaps--conference.org/
http://ipc.icaps
1
STRIPS
Representación de estados en STRIPS k
Estado inicial = {
at(p,l
at(p,l),
), at(q,l
at(q,l),
), at(r,l
at(r,l),
), at(k,l
at(k,l),
), c2 p q
in(c1,p), in(c2,p), c1
top(c2,p), r
l
on(c2,c1), on(c1,p),
empty(k),
unloaded(r)
}
Representación de objetivos en STRIPS
Objetivo = { on(c1,r) } 2
STRIPS
Representación de acciones en STRIPS
Acción
Nombre de la acción
Precondiciones
Proposiciones que deben cumplirse para poder aplicar la acción.
acción.
Efectos
Consecuencias de la aplicación de la acción.
acción.
“Add list” (proposiciones que pasan a ser ciertas)
ciertas)
“Delete list” (proposiciones que pasan a ser falsas)
falsas)
3
STRIPS
Representación de acciones en STRIPS k
move(r,l,m))
move(r,l,m
pre: adjacent(l,m
adjacent(l,m),
), at(r,l
at(r,l))
c2 p q
add: at(r,m
at(r,m))
c1
del: at(r,l
at(r,l)) r
l
load(k,l,c,r))
load(k,l,c,r
pre: at(k,l
at(k,l),), holding(k,c
holding(k,c),
), at(r,l
at(r,l),
), unloaded(r)
add: empty(k), loaded(r,c
loaded(r,c))
del: holding(k,c
holding(k,c), ), unloaded(r)
put(k,l,c,d,p))
put(k,l,c,d,p
pre: at(k,l
at(k,l),
), at(p,l
at(p,l),
), holding(k,c
holding(k,c),
), top(d,p
top(d,p))
add: empty(k), in(c,p
in(c,p),
), top(c,p
top(c,p),
), on(c,d
on(c,d))
del: holding(k,c
holding(k,c),), top(d,p
top(d,p)) 4
STRIPS
Representación de acciones en STRIPS k
move(r,l,m))
move(r,l,m
pre: adjacent(l,m
adjacent(l,m),
), at(r,l
at(r,l))
c2 p q
eff:
eff: at(r,m
at(r,m),
), ¬at(r,l
at(r,l))
c1
r
l
load(k,l,c,r))
load(k,l,c,r
pre: at(k,l
at(k,l),
), holding(k,c
holding(k,c),
), at(r,l
at(r,l),
), unloaded(r)
eff:
eff: empty(k), loaded(r,c
loaded(r,c),
), ¬holding(
holding(k,c
k,c),
), ¬unloaded(r)
put(k,l,c,d,p))
put(k,l,c,d,p
pre: at(k,l
at(k,l),
), at(p,l
at(p,l),
), holding(k,c
holding(k,c),
), top(d,p
top(d,p))
add: empty(k), in(c,p
in(c,p),
), top(c,p
top(c,p),
), on(c,d
on(c,d),
), ¬holding(
holding(k,c
k,c),
), ¬top(
top(d,p
d,p))
5
STRIPS
Sólo se especifica aquello que cambia.
Hipótesis de mundo cerrado
(lo que no se menciona es falso).
Sólo literales positivos en la descripción de estados.
Sólo conjunciones de literales simples en el objetivo.
P∧¬
∧¬QQ como efecto añade P y elimina Q
Las variables no pueden tener tipos. 6
ADL
Sólo se especifica aquello que cambia.
Hipótesis de mundo abierto
(lo que no se menciona no se conoce).
Literales positivos y negativos en los estados.
Conjunciones y disjunciones en el objetivo.
P∧¬
∧¬QQ como efecto añade {P, ¬Q} y elimina {¬
{¬P, Q}
Las variables sí pueden tener tipos. 7
PDDL
Planning Domain Definition Language
http://cs--www.cs.yale.edu/homes/dvm/
http://cs
Estándar para la representación de tareas de
planificación “clásica
clásica”” utilizado desde 1998
en AIPS [International Conference on AI Planning &
Scheduling], ahora ICAPS [International Conference
on Automated Planning and Scheduling].
Inspirado en UCPOP, un planificador de orden parcial
desarrollado en la Universidad de Washington e
implementado inicialmente en Common Lisp,
utiliza la sintaxis del lenguaje de programación LISP. 8
PDDL
Componentes PDDL
Objetos (entidades de interés).
interés).
Predicados (propiedades de los objetos
objetos,, true/false).
Estado inicial
Especificación de objetivos
Acciones//operadores (formas de cambiar el estado).
Acciones estado).
9
PDDL
Especificación PDDL
Separada en dos ficheros:
ficheros:
Fichero del dominio
(predicados y acciones)
acciones)
Fichero del problema
(objetos,
objetos, estado inicial y especificación de objetivos).
objetivos).
10
PDDL
Fichero de especificación de dominios PDDL
(define (domain <domain name>)
name>)
<PDDL code for predicates>
<PDDL code for first action>
[...]
<PDDL code for last action>
)
11
PDDL
Fichero de especificación de dominios PDDL
Especificación de predicados (propiedades)
propiedades)
(:predicates (room ?x)
(robot--at ?x))
(robot ?x))
room(x) cierto si y sólo si x es una habitación.
habitación.
robot--at(x) cierto si y sólo si x es una habitación
robot
y, además,
además, el robot está en x.
12
PDDL
Fichero de especificación de dominios PDDL
Especificación de acciones (precondiciones y efectos)
efectos)
(:action move :parameters (?x ?y)
:precondition (and (room ?x) (room ?y)
(robot--at ?x))
(robot
:effect (and (robot-
(robot-at ?y)
(not (robot- ?x)))))
(robot-at ?x)))
13
PDDL
Fichero de especificación de problemas PDDL
(define (problem <problem name>)
name>)
(:domain <domain name>)
name>)
<PDDL code for objects>
<PDDL code for initial state>
<PDDL code for goal specification>
)
14
PDDL
Fichero de especificación de problemas PDDL
Estado inicial
(:init (room cocina)
cocina)
(room comedor
comedor))
(room dormitorio)
dormitorio)
(robot--at comedor
(robot comedor)))
Objetivo
(: goal (robot--at cocina
(robot cocina)))
15
HTN [Hierarchical Task Network]
(at yo (at yo
MiCasa) miCasa)
ir-andando ir-en-bus
(at yo (at yo
ETSII) ETSII)
La planificación jerárquica facilita la representación de
medios alternativos para la realización de tareas a distintos
niveles de abstracción [abstraction gap].
16
HTN [Hierarchical Task Network]
Tarea compuesta Viajar
Métodos enAvion enCoche
Subtareas irEnCoche
irAeropuerto Volar irADestino
(compuestas/primitivas)
Métodos enAutobus enTaxi enMetro enTaxi
Tareas primitivas Pagar irEnBus irEnTaxi Pagar Pagar irEnMetro irEnTaxi Pagar
En vez de buscar un plan que consista en una secuencia de acciones
individuales, tratamos con un menor número de tareas que pueden
corresponder a múltiples acciones cada una de ellas [refinement
planning]
17
HTN [Hierarchical Task Network]
Tarea compuesta Viajar
Métodos enAvion enCoche
Subtareas irEnCoche
irAeropuerto Volar irADestino
(compuestas/primitivas)
Métodos enAutobus enTaxi enMetro enTaxi
Tareas primitivas Pagar irEnBus irEnTaxi Pagar Pagar irEnMetro irEnTaxi Pagar
Dominio de planificación basado en la representación de tareas
[tasks]
tasks] a distintos niveles de abstracción.
Distinción entre tareas compuestas y tareas primitivas (acciones).
Especificación de métodos alternativos para la realización de tareas.
18
HTN--PDDL
HTN
• Estándar para • Extensión desarrollada por • IActivePlanner: Planificador
representar problemas el Grupo de Sistemas desarrollado por el grupo
clásicos de planificación Inteligentes del ISG y transferido a la spin-
Departamento de Ciencias off IActive Intelligent
de la Computación e I.A. Technologies
(DECSAI) de la Universidad
de Granada para
planificación jerárquica.
PDDL HTN-PDDL Planificador
19
HTN--PDDL
HTN
Especificación de dominios HTN- HTN-PDDL
Requisitos,, constantes,
Requisitos constantes, tipos,
tipos, predicados y funciones
(define (domain viajes
viajes))
(:requirements :typing :fluents
:fluents :derived
:derived--predicates
:negative--preconditions ::htn
:negative htn--expansion)
expansion)
(:types Persona Sitio - object
Hogar Aeropuerto - Sitio
(:predicates (en ?p - Persona ?s – Sitio)
Sitio))
(:functions (distancia ?x ?y – Sitio)
Sitio))
…
20
HTN--PDDL
HTN
Especificación de dominios HTN-
HTN-PDDL
Tareas y métodos
(:task irAeropuerto
:parameters (?p – Persona ?c – Hogar ?a – Aeropuerto
Aeropuerto))
(:method enTaxi …)
(:method enBus …)
(:method andando …) ;; Uff !!
)
21
HTN--PDDL
HTN
Especificación de dominios HTN-
HTN-PDDL
Tareas y métodos
(:method enTaxi
:precondition ()
:tasks (
(ir_en_taxi ?p ?c ?a)
(:inline (bind ?tarifa
?tarifa
(* (distancia
(distancia ?c ?a) (precio_km
(precio_km)))
))) ())
(pagar ?p ?tarifa
?tarifa))
)
) 22
HTN--PDDL
HTN
Especificación de dominios HTN-
HTN-PDDL
(:task viajar
:parameters (?p – Persona ?x ?y – Sitio)
Sitio)
(:method enAvion
:precondition (tiene prisa ?p)
:tasks ( ((irAeropuerto
irAeropuerto ?p ?x GRX)
(volar ?p GRX MAD)
(irDestino ?p MAD ?y) )
)
(:method enCoche
:precondition (not (tiene_prisa
(tiene_prisa ?p))
:tasks (irEnCoche ?p ?x ?y)
)
23
)
HTN--PDDL
HTN
Especificación de problemas HTN- HTN-PDDL
Objetos,, estado inicial y objetivos
Objetos
(define (problem UnViaje
UnViaje)) (:domain Viajes
Viajes))
(:objects MiCasa CasaMiPrimo – Hogar
GRX MAD – Aeropuerto
Yo – Persona
)
(:init (en Yo MiCasa)
MiCasa)
(= (distancia
(distancia MiCasa GRX) 20)
)
(:tasks
:tasks--goal
:tasks( (Viajar
(Viajar Yo MiCasa CasaMiPrimo))
CasaMiPrimo))
) 24
)
Planificador HTN
Modelo del mundo
HTN-PDDL Planificador HTN Plan
• Dominio • Búsqueda • Secuencia de
• Problema • Razonamiento acciones
25
Planificador HTN
Descomponer (Viajar Yo
la tarea de nivel superior MiCasa
CasaMiPrimo)
Seleccionar un método
(comprobando las precondiciones, enAvion enCoche
en el orden en que se han escrito)
Descomponer la tarea
irAeropuerto Volar irADestino
siguiendo el orden de las subtareas
Seleccionar un método enTaxi enBus andando
Descomponer/aplicar si primitiva cogerTaxi
26
Planificador HTN
(Viajar Yo
Descomponer
MiCasa
la tarea de nivel superior
CasaMiPrimo)
Seleccionar un método
(comprobando las precondiciones, enAvion enCoche
en el orden en que se han escrito)
Descomponer la tarea
irAeropuerto Volar irADestino
siguiendo el orden de las subtareas
Seleccionar un método enTaxi enBus andando
Descomponer/aplicar si primitiva Pagar irEnBus
27
Dominio Depots
Almacén o Distribuidor Almacén o oDistribuidor
Almacén Distribuidor
Problemas de logística
28
Dominio Depots
Objetos
(:types place locatable - object
depot distributor - place
truck hoist surface - locatable
pallet crate - surface)
Cajas [crate
[crate]]
Pallets [pallet]
Almacenes [depot
[depot]]
Distribuidores [distributor]
Grúas [hoist
[hoist]]
Camiones [truck
[truck]] 29
Dominio Depots
Acciones (tareas primitivas)
primitivas)
(:action
(:action Drive ; Conducir un camión
:parameters (?x - truck ?y - place ?z - place)…
(:action
(:action Lift ; Coger una caja con una grúa
:parameters (?x - hoist ?y - crate ?z - surface ?p - place)…
(:action
(:action Drop ; Dejar una caja con una grúa
:parameters (?x - hoist ?y - crate ?z - surface ?p - place)…
(:action
(:action Load ; Cargar un camión
:parameters (?x - hoist ?y - crate ?z - truck ?p - place)..
(:action
(:action Unload ; Descargar un camión
:parameters (?x - hoist ?y - crate ?z - truck ?p - place)… 30
Dominio Depots
Objetivos (lista de tareas “apilar”)
apilar”)
Tarea objetivo “Main”: (:tasks-
(:tasks-goal :tasks((Main)))
(:task Main :parameters ()
(!
(:method itera
:precondition (AND (apilar
(apilar ?x ?y))
:tasks (
(… ?x ?y ) ; Tarea necesaria para apilar x sobre y
(:inline () (not (apilar
(apilar ?x ?y))) ; Objetivo cumplido
(Main)) ; Descomposición recursiva
)
(:method caso
caso--base :precondition () :tasks ())
) 31
)
Acciones primitivas:
HTN--PDDL durative
HTN durative--actions
– Objetos del dominio: (define (domain
(domain viajes)
(:requirements
(:requirements :typing :fluents
• constantes, :derived
derived-
-predicates :negative
negative--
• tipos preconditions :htn
htn--expansion
expansion)
)
(:constants
(:constants <….>)
• predicados,,
predicados
(:types
(:types Persona Sitio – object
• funciones Hogar Aeropuerto - Sitio
(:predicates
(:predicates (en ?p - Persona ?s – Sitio))
(:functions
(:functions (distancia ?x ?y – Sitio)
(dinero ?p – Persona)
(velocidad-
(velocidad -taxi)
– Acciones primitivas: )
(precio_km
precio_km))
• Representación PDDL
• Parámetros con tipo,
tipo,
• precondiciones, (:durative
(:durative-
-action ir_en_taxi
:parameters (?u – Persona ?o ?d – Sitio)
• efectos, :duration (= ?
?dur
dur (* (distancia ?o ?d)
• duración (velocidad_taxi
velocidad_taxi)) )
:condition (and (en ?u ?o))
:effect (and (
(not
not (en ?u ?o))
(en ?u ?d))) 32
Otros aspectos útiles de PDDL
Valores (:durative-action ir_en_taxi
(:durative-
:parameters (?u – Persona ?o ?d – Sitio)
numéricos/funciones
:duration (= ?dur (* (distancia ?o ?d)
Especificar cómo (velocidad_taxi)
(velocidad_taxi ) )
calcular duraciones de :condition (and (en ?u ?o)
acciones (> (dinero ?u)
Condiciones con (* (precio_km)(distancia ?o ?d))
:effect (and (not (en ?u ?o))
expresiones
(en ?u ?d)))
aritméticas
33
Otros aspectos útiles de PDDL
Valores (:derived (tiene_dinero ?p – Persona ?org ?dst – Sitio)
((> (dinero ?u)
numéricos/funciones
(* (precio_km)(distancia ?o ?d)))
Derived literals: reglas
de inferencia para (:durative-action ir_en_taxi
(:durative-
“derivar” predicados :parameters (?u – Persona ?o ?d – Sitio)
de las precondiciones :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)))
34
Otros aspectos útiles de PDDL
Valores (:derived (tiene_dinero ?p – Persona ?org ?dst – Sitio)
((> (dinero ?u)
numéricos/funciones
(* (precio_km)(distancia ?o ?d)))
Derived literals: reglas
de inferencia para (:durative-action ir_en_taxi
(:durative-
“derivar” predicados de :parameters (?u – Persona ?o ?d – Sitio)
las precondiciones :duration (= ?dur (* (distancia ?o ?d)
(velocidad_taxi) )
Asignación,
:condition (and (en ?u ?o)
incremento/decremento
(tiene_dinero ?u ?o ?d))
de funciones :effect (and (not (en ?u ?o))
(en ?u ?d)))
(:durative-action pagar
(:durative-
:parameters (?u – Persona ?c – number)
:duration (= ?dur 1)
:condition (> (-
(- (dinero ?u) ?c) 0)
:effect (decrease (dinero ?u) ?c)
35
Bibliografía
Stuart Russell & Peter Norvig:
Norvig:
Artificial Intelligence:
A Modern Approach
Prentice--Hall, 3rd edition, 2009
Prentice
ISBN 0136042597
http://aima.cs.berkeley.edu/
Nils J. Nilsson
The Quest for Artificial Intelligence
Cambridge University Press, 2009
ISBN 0521122937
http://ai.stanford.edu/~nilsson/QAI/qai.pdf
36
Bibliografía
Cursos de planificación
MSC Automated Planning
School of Informatics
University of Edinburgh
http://www.inf.ed.ac.uk/teaching/courses/plan/
También en Coursera:
Coursera:
https://www.coursera.org/course/aiplan
CS541: Artificial Intelligence Planning
USC Viterbi School of Engineering
University of Southern California
http://www.isi.edu/~blythe/cs541/ 37
