Planejamento Hierárquico
Jacques Robin
CIn-UFPE
Planejamento de Ordem Parcial (POP) com
linguagem STRIPS
mais expressivo que resolução de problema
 porque usa a lógica para representar operadores
declarativamente e composicionalmente
 restrição da lógica da 1a ordem com cálculo das situações
 restrito demais para domínios complexos de muitas
aplicações reais
 necessidade de achar um melhor compromisso
expressividade/eficiência
 aumentar formalismo e relaxar algumas restrições

Limitações de POP-STRIPS

Planejamento a um único nível de granularidade:
• de POP-STRIPS para POP-HAD-STRIPS

Precondições e efeitos não contextuais:
• de POP-STRIPS para POP-DUNC

Representação do tempo:
• de POP-STRIPS para POP-TI-STRIPS

Representação de recursos globalmente limitados:
• de POP-STRIPS para POP-RC-STRIPS

As aplicações reais mais complexas requerem:
• POP-TIRC-HAD-DUNC! :)
Decomposição Hierárquica:
Planejar com refinamento incremental

Hierarquia de operadores abstratos:
• não direitamente executáveis (não primitivos)
• com várias decomposições em termos de ações menos abstratas
Construir POP inicial ao maior nível de abstração
 Recursivamente decompor ações abstratas
 Até POP final conter apenas de ações primitivas
 Verificar consistência global do POP final
 Sub-POPs largamente independentes:

• espaço de busca reduzido
• conhecimento composicional
• uso e reuso de sub-POPs pre-fabricados ou já planejados
Exemplo de operador não primitivo
Decompose(o,p)
Decompose(Construction,
Plan(STEPS:{S1:Build(Foundation),S2:Build(Frame),
S3: Build(Roof), S4:Build(Walls),
S5: Build(Interior)}
Orderings:{S1<S2<S3<S5, S2<S4<S5},
Bindings:{},
Links:{S1 Foundation S2, S2 Frame S3, S2 Frame S4,
S3 Roof S5, S4 Walls S5}))
Exemplo de decomposição hierárquica
Build
House
Decomposes to
Obtain
Permit
Construction
Pay
Builder
Hire
Builder
Decomposes to
Build
Roof
Build
Foundation
Build
Frame
Build
Interior
Build
Walls
POP-HD-SCRIPT
Function POP-DH(plan,operators,methods) return plan
inputs: plan, an abstract plan with start and goal steps( and possibly
other steps)
loop do
if Solution?(plan) then return plan
Sneed, c
Select-Sub-Goal(plan)
Choose-Operator(plan,operators,Sneed,c)
Snomprim
Select-Nonprimitive(plan)
Choose-Decomposition((plan,methods,Snonprim)
Resolve-Threats(plan)
end
Solução abstrata x primitiva

P solução abstrata para O, se P decomposição
consistente e completa de O a um nível de abstração
dado, i.e., se
1. P é internamente consistente.
2. todo efeito de O é atingido por pelo menos 1 passo de P.
3. toda pré-condição dos passos de P é satisfeita por um passo em
P ou ser uma das pré-condições de O

P solução primitiva para O, se P verifica 1, 2, 3 e
também:
4. todo passo de P é primitivo
Propriedades necessárias para garantir POPHD mais eficiente do que POP
Downward solution property (DSP): P solução abstrata =>
P abstração de pelo menos uma solução primitiva P1
 Upward solution property (USP): P plano abstrato
inconsistente => P abstração de nenhuma solução
primitiva P1
 Ação principal: sub-ação A1 de ação abstrata A
conectada a todas as pré-condições e efeitos de A

Propriedades necessárias para garantir POPHD mais eficiente do que POP
DSP e USP nem sempre verificadas
 Toda decomposição de toda ação abstrata contém uma
única ação principal => USP verificada
 DSP ou USP verificada => pior caso da busca para uma
solução primitiva drasticamente reduzida
 Mesmo quando DSP ou USP não são verificadas, detalhar
soluções abstratas em primeiro ainda é uma boa
heurística

Upward solution property: contra-exemplo
•efeito ~watch de GiveComb ameaça precond watch de GiveChain
•efeito ~hair de GiveChain ameaça precond hair de GiveComb
Busca e decomposição hierárquica


Consistente incompleto
Consistente completo


Inconsistente
X: pode ser podado
X
X
X

X
X
X
X
X
Downward Solution Property
X

X
X
X
X
X
Upward Solution Property
X
Decomposição e compartilhamento
Maioria das decomposições das ações abstratas
independentes umas das outras
 Mas as vezes a única solução primitiva envolve
compartilhamento de ações entre decomposições
 2 possibilidades:

• quando escolher decomposição de uma ação abstrata, verificar
oportunidades e restrições de compartilhamento
• escolher decomposição sem compartilhamento, e depois usar
regras de revisão (chamadas críticas) para tornar o plano
primitivo resultante em uma solução com ações corretamente
compartilhadas
Exemplo da necessidade de compartilhar
Curtir Lua-de-mel &
fazer bebê
Casar-se &
Casar-se & ir
para lua-de-mel
ter um bebê
Curtir lua de mel &
fazer bebê
Casar-se
Ir para lua
de mel
Ter bebê
De POP-HD-STRIPS
para POP-HAD STRIPS

2 formas ortogonais de planejamento hierárquico:
• hierarquia de ações de vários níveis de abstração para decomposição
• hierarquia de precondições de vários níveis de prioridade para
aproximação

Podem ser combinadas para reduzir busca: começar por planos
completos e consistentes embora abstratos e aproximativos
Exemplo de operador com precondições a 3 níveis de prioridades:

Hierarquia de aproximação  ! Ação principal  UDP verificada

Op(Action:Buy(x),
Effect:Have(x) ^ ¬Have(Money),
Precond:1:Sells(store,x)
2:At(store)
3:Have(Money))