PDDL: uma linguagem padrão para especificação de problemas e heurísticas de planejamento

Jacques RobinCIn-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 basepermite usar qualquer combinação de uma grande variedade

de extensõesque 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ínioassim 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 objetivosdas pré-condições das açõesdas condições dos efeitos condicionaisas 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> ) [<extension-def>] [<require-def>] [<types-def>] [<constants-

def>] [<domain-vars-defs>] [<predicates-def>] [<timeless-def>]

[<safety-def>] <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 ESe P é falso a ação não é executadaSe 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