PDDL:
uma linguagem padrão para
especificação de problemas e
heurísticas de planejamento
Jacques Robin
CIn-UFPE
PDDL:
Planning Domain Definition Language
1a linguagem padrão para expressão de problemas de
planejamento
Possibilita:
 interoperabilidade entre planejadores
 repositórios de tarefas benchmark pré-codificadas de
planejamento
 competições de planejamento
Criado em 1998 para a 1a competição de planejamento
Expressividade variável:
 parte de STRIPS como base
 permite usar qualquer combinação de uma grande variedade de
extensões
 que incluem a maioria daquelas descritas no capítulo 12 do
AIMA mais algumas outras
Expressividade de PDDL: cobre muitas
extensões de STRIPS
Decomposição hierárquica (pp. 371-379 do AIMA)
Efeitos condicionais (pp. 381-382 do AIMA)
Efeitos universalmente quantificados (pp. 383 do AIMA)
 i.e., as conjunções de literais positivos e negativos que
constituam os efeitos podem conter variáveis universalmente
quantificadas localmente declaradas
Axiomas:
 implicações lógicas, com conclusão restrita a um único literal
positivo, que
 representam relações sempre verificadas em qualquer situação
do domínio
 assim permitem que as ações representam apenas as mudanças
entre situações
Expressividade de PDDL: cobre muitas
extensões de STRIPS
Qualquer formula sem função da lógica da 1a ordem, com
semântica de mundo fechado ou aberto a escolher, para
especificação:
 dos estados objetivos
 das pré-condições das ações
 das condições dos efeitos condicionais
 as premissas dos axiomas
Variáveis tipadas (pp. 383-384 do AIMA)
Objetivos a manter durante expansão de uma ação
abstrata, ou até processo de planejamento inteiro
Medidas de fluentes (fluents) e avaliação de expressões
aritméticas de cálculo e comparação para representar
restrições quantitativas de recursos
(pp. 386-388 do AIMA)
Exemplo introdutório:
transporte de objetos em mala
(define (domain briefcase-world)
(:requirements :strips :equality :typing :conditional-effects)
(:types location physobj)
(:constants (briefcase –physobj))
(:predicates (at ?O –physobj ?L – location)
(in ?O1 ?O2 – physobj))
(:action move-briefcase
:parameters (?From ?To – location)
:precondition (and (at briefcase ?From) (not (= ?From ?To)))
:effect (and (at briefcase ?To) (not (at briefcase ?From))
(forall (?O)
(when (and (in ?O briefcase) (not (= ?O briefcase)))
(and (at ?O ?To) (not (at ?O ?from)))))))
Exemplo introdutório:
transporte de objetos em mala (cont.)
(:action put-in
:parameters (?O –physobj ?L – location)
:precondition (not (= ?O briefcase))
:effect (when (and (at ?O ?L) (at briefcase ?L)) (in ?O briefcase)))
(:action take-out
:paramenters (?O –physobj)
:precondition (not (= ?O briefcase))
:effect (not (in ?X briefcase))))
(define (problem get-paid)
(:domain briefcase-world)
(:init (location home) (location office) (physobj paycheck)
(physobj dictionary) (at briefcase home) (at paycheck home)
(at dictionary home) (in paycheck briefcase))
(:goal (and (at briefcase office) (at dictionary office) (at paycheck home)))
Definição de domínios
 <domains> ::= (define (domain <name> )
def>]











[<extension-def>] [<require-def>] [<types-def>] [<constants-def>]
[<domain-vars-defs>] [<predicates-def>] [<timeless-def>] [<safety-
<structure-def>*)
<extension-def> ::= (:extends <domain-name>+)
 ex, (:extends briefcase-world block-world)
 causa herança de requirements, types, constants, actions, axioms e timeless entre domínios
<require-def> ::= (:requirements <require-key>+)
<types-def> ::= (:types <typed list(name)>)
<constants-def> ::= (:constants <typed list(name)>)
<domain-vars-def> ::= (:domain-variables <typed list(domain-var-declaration)>)
<domain-var-declaration> ::= <name> | <name> <constant>
<predicates-def> ::= (:predicates <atomic-formula-skeleton>+)
<atomic-formula-skeleton> ::= (<predicate> <typed list(variable)>)
<predicate> ::= <name>
<variable> ::= ?<name>
<structure-def> ::= <action-def> | <axiom-def>
Ações
 <action-def> ::= (:action <name>


:parameters <typed list(variables)>
<action-def-body>)
<action-def-body> ::= [:vars <typed list(variables)>]
[:precondition <goal>]
[:expansion <action-spec>]
[:maintain <goal>]
[:effect <effect>]
parâmetros x variáveis:
 parâmetros universalmente quantificados na precondição e no efeito
 variáveis quantificadas existencialmente na precondição, mas universalmente


no efeito
ex, (:action spray-paint :parameters (?C –color) :vars (?L –location)
:precondition (at robot ?L)
:effect (forall (?O –physobj) (when (at ?O ?L) (color ?O ?C)))
a cor pode variar, mas, em um ponto dados da execução do plano, o robô pode
estar apenas em uma única locação
Fórmulas sem funções da lógica da 1a ordem
 Autorizadas como:
 pré-condição de ação
 condição de efeito condicional de ação
 premissa de axioma
 objetivo de problema
 <goal> ::= <literal> | (and <goal>*) | (or <goal>*) | (not <goal>) | (imply
<goal> <goal>)
<goal> ::= (exists <typed list(variables)> <goal>)
<goal> ::= (forall <typed list(variables)> <goal>)
<literal> ::= <atomic-formula> | (not <atomic-formula>)
<atomic-formula> ::= (predicate term*)
<term> ::= <name> | <variable>
Fórmulas sem funções
da lógica da 1a ordem: exemplo de uso
:precondition
(and (lift-at ?f)
(imply (exists (?p - conflict_A)
(or (and (not (served ?p)) (origin ?p ?f))
(and (boarded ?p) (not (destin ?p ?f)))))
(forall (?q - conflict_B)
(and (or (destin ?q ?f)
(not (boarded ?q)))
(or (served ?q))))))
(not (origin ?q ?f)))))))
Efeitos
 <effect> ::= literal | (and <effect>*) | (when <goal> <effect>)
<effect> ::= (forall <typed list(variable)> <effect>)
<effect> ::= (change <fluent> <expression>)
Pré-condição P de ação x condição C de efeito
condicional E
 Se P é falso a ação não é executada
 Se C é falso a ação é executada, sem o efeito E
Decomposição hierárquica:
ordenamento dos sub-passos
 Decomposição puramente seqüencial ou puramente paralela
 <action-spec> ::= (<name> <term>*)
 <action-spec> ::= (series <action-spec>*) | (parallel <action-spec>*)
 Decomposição híbrida de ordem parcial
 <action-spec> ::= (constrained (<action-spec>+) <action-constraint>*
<action-constraint> ::= (series <action-constraint>*) | (parallel <action-constraint>)
<action-spec> ::= (tag <action-label> <action-spec> <action-label>)
<action-label> ::= <name> | (< <name>) | (> <name>)
 ex, (constrained ((series (tag (A) (> end-a)) (B))
(series (C) (tag (< beg-d) D (> end-d))))
(in-context (series end-a end-d) :maintain (P)))
 ex, (constrained (tag (parallel (tag (act1) (> end-act1)) (act2) ... (actN))
(> alldone))
(in-context (series end-act1 alldone) :maintain (condition)))
Decomposição hierárquica:
opções múltiplas de expansão
 Opções explicitamente declaradas:
<action-spec> ::= (choice <action-spec>*)
 Opções implícitas geradas por instanciação de variáveis durante
execução:
 <action-spec> ::= (forsome <typed list(variable)> <action-spec>)
 um opção por cada instanciação válida da lista de variáveis
 <action-spec> ::= (foreach <typed list(variable)> <goal> <action-spec>)
 um opção por cada instanciação válida da lista de variáveis
que tornam <goal> verdadeiro
Decomposição hierárquica: exemplo
(:action unload :parameters (?P –package ?V –vehicle ?L –location)
:expansion
(choice ...
(forsome (?C –crane)
(in-context
(constrained (series (tag (pick-up-package-vehicle ?P ?C ?V ?L) (> end-n1))
(tag (< beg-n2) (put-down-package-ground) ?P ?C ?L)))
(in-context (series end-n1 beg-n2) :maintain (and (at-package ?P ?C)
(at-equipment ?C ?L)))
:precondition (and (flatbed ?V) (empty ?C)
(at-package ?P ?V) (at-vehicle ?V ?L) (at-equipment ?C ?L))))))
Invariantes e manutenção de objetivos
 Propriedades invariantes do domínio
 <timeless-def> ::= (:timeless <literal (name)>+)
 ex, (:timeless (on briefcase-tag briefcase))
 Objetivo a manter durante plano inteiro
 <safety-def> ::= (:safety <goal>)
 ex, (:safety (forall (?F) (or (file ?F) (written-to-tape ?F))))
 Objetivo a manter durante passo de uma expansão
 <action-spec> ::= (in-context <action-spec> <action-def-body>)
 :maintain declara objetivo a manter durante passo especificado por <action

spec> de uma expansão
:pré-condição declara pré-condição adicional para uma ação do contexto
durante o passo especificado por <action-spec> de uma expansão
ex, (series (clear ?Area)
(in-context (shell ?Area)
:precondition (not (exists (?U -unit)
(and (friendly ?U) (in ?U ?Area))))))
Axiomas
Representam relações entre objetos do mesmo estado
Complementam ações que representam relações entre
objetos de estados diferentes
Permite fatorar do código das ações conseqüências
comuns, próprias a um estado é não a uma transição dada
Axiomas
 <axiom-def> ::= (:axiom :vars <typed list(variables)>
:context <goal>
:implies <literal>)
 Um axioma é uma regra dedutiva da 1a ordem:
 :vars contém variáveis implicitamente universalmente quantificadas
 :context indica premissa da regra
 :implies codifica conclusão da regras
 Planejadores implementando axiomas devem embutir motor de inferência
 pelo sub-conjunto da lógica da 1a ordem formado pelas fórmulas implicativas
 mais expressivo do que Prolog e sistemas de produção
 ex, (:axiom :vars (?O1 ?O2 -physobj)
:context (on ?O1 ?O2) :implies (above ?O1 ?O2))
(:axiom :vars (?O1 ?O2 -physobj)
:context (exists (?O3 -physobj)
(and (on ?O1 ?O3) (above ?O3 ?O2))
:implies (above ?O1 ?O3))
Fluentes e expressões aritméticas
(:action pour
:parameters (?Source ?Dest -container)
:vars (?Sfl ?Dfl -(fluent number) ?Dcap -number)
:precondition (and (content ?Source ?Slf) (content ?Dtest ?Dfl)
(capacity ?Dest ?Dcap) (fluent-test (<= (+ ?Sfl ?Dfl) ?Dcap)))
:effect (when (and (contents ?Source ?Sfl) (contents ?Dest ?Dfl))
(and (change ?Sfl 0) (change ?Dfl (+ ?Dfl ?Sfl)))))
(fluent-eval (sum (?P -person ?W -number)
(and (aboard ?P ?Elevator) (weight ?P ?W))
?W))
Definição de problemas
Heurísticas de planejamento