Planejamento
Hierárquico e
Planejamento Reativo
Ana Emilia de Melo Queiroz
Tópicos Avançados em Inteligência
Artificial Simbólica
CIn - UFPE
Planejamento Hierárquico e
Planejamento Reativo: Roteiro
• Planejamento Hierárquico
• Planejamento Reativo
• Sem Sensor
• Condicional
• Execução e Monitoramento
• Planejamento Contínuo
Planejamento Hierárquico e Planejamento Reativo
Decomposição Hierárquica
• Problema
• Instruções muito abstratas não são
implementáveis no mundo real.
• Ex. “Go(Supermarket), Buy(Milk), Buy(Bananas), Go(Home)”
• Instruções detalhadas provocam explosão
combinatória no espaço de busca
• “Avançar(1cm), Girar(40°), ...”
• Solução
• Planejar com refinamento incremental através de
decomposição hierárquica de operadores
abstratos
• Operadores abstratos:
• não direitamente executáveis (não primitivos)
• com várias decomposições em ações menos
abstratas
Planejamento Hierárquico e Planejamento Reativo
Exemplo de decomposição hierárquica
BuildHouse
Decomposes to
Obtain
Permit
Construction
Hire
Builder
Pay
Builder
Decomposes to
Build
Foundation
Build
Frame
Build
Roof
Build
Walls
Build
Interior
Planejamento Hierárquico e Planejamento Reativo
Decomposição Hierárquica
• O que é preciso?
• Estender STRIPS para
• Incluir operadores abstratos
• Definir quem são ou não os operadores abstratos
• Redefinir POP
• Novo operador: Decompose(a,p) - A
ação a pode ser decomposta em um
plano p.
Planejamento Hierárquico e Planejamento Reativo
Exemplo de Decompose(a,p)
• Exemplo
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}))
Planejamento Hierárquico e Planejamento Reativo
Decomposição Hierárquica
• Algoritmo
• Construir POP inicial ao maior nível de abstração
• Recursivamente decompor ações abstratas até
POP final conter apenas de operadores
primitivos (que podem ser executados pelo
agente)
• Verificar consistência global do POP final
• Vantagens de Sub-POPs independentes:
• Espaço de busca reduzido
• Conhecimento composicional
• Uso e reuso de sub-POPs pre-fabricados ou já
planejados
Planejamento Hierárquico e Planejamento Reativo
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
Planejamento Hierárquico e Planejamento Reativo
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ê
Planejamento Hierárquico e Planejamento Reativo
De POP-HD-STRIPS
para POP-HAD STRIPS
• Duas 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: Op(Action:Buy(x),
Effect:Have(x) ^ ¬Have(Money),
Precond:1:Sells(store,x)
2:At(store)
3:Have(Money))
Planejamento Hierárquico e Planejamento Reativo
E se as coisas não saírem como
planejadas?
• Monitoramento da Ação:
• Verificação, com percepção, das precondições do passo corrente
• Monitoramento da Execução:
• Verificação, com percepção, das précondições do segmento restantes.
• Condições de lidar com pré-condições:
• não planejadas
• já satisfeitas
• Ex: Robô dirigindo carro...
Planejamento Hierárquico e Planejamento Reativo
Detecção das falhas do plano
• Formas de monitoramento dependentes
da percepção.
Indeterminância:
• Limitada (numerável):
• ex. :abrir uma lata de tinta
• Ilimitada (não enumerável):
• ex.: dirigir, planejamento econômico
Planejamento e Execução
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
• POP e POP-TIRC-HAD:
• Funcionam quando:
• Ambiente acessível, estático, determinístico
• Conhecimento completo e correto
• Perceber, depois planejar, depois agir
cegamente.
• Domínios não determinísticos e ou
parcialmente observável:
• Ambiente inacessível, dinâmicos, estocásticos
• Conhecimento incompleto e incorreto
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejando com Indeterminância
•
•
•
•
Planejamento Sem Sensor.
Planejamento Condicional.
Monitoramento e Execução.
Planejamento Contínuo.
• Obs:Os primeiros dois métodos
trata da indeterminância limitada,
os outros da indeterminância
ilimitada.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução:Planejamento
Sem Sensor
• Adotar uma estratégia conhecida e bem
sucedida.
• Exemplo: Um médico que prescreve um
antibiótico de amplo espectro.
• Não trata indeterminânica ilimitada.
• Aplicado a técnica clássica.
• Coerção: métodos para contornar a
incerteza que força o mundo a um
estado conhecido.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Condicional ou
Planejamento de Contingência
• Plano condicional / Conjunto de planos /
Possíveis situações
• Ações de Efetuação x Ações de Percepção:
• objetivo ação de efetuação: alterar
ambiente
• objetivo ação de percepção: alterar
conhecimento do ambiente (ex, checar o
preço de algum objeto).
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução: Execução de um
plano condicional
• Condição é verificada na B.C. e deve ser
conhecida naquele ponto do plano.
• Conhecimento = Seq. de percepções + Seq.
de ações + B.C inicial.
• Para um plano condicional ser executável: “o
agente deve inserir ações de percepção para
testar condição”.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Condicional Ambiente
Completamente Observável
• Ele conhece o estado corrente mas não
está habilitado a predizer os efeitos de
suas ações.
• Construção de passos condicionais no
plano em tempo de planejamento.
• Verificação destas condições em tempo
de execução.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Condicional: Ambiente
Completamente Observável. O que é preciso?
• Estender SRIPS para suportar o não determinismo.
• Efeitos disjuntivos.
• Uma ação podendo ter um ou mais efeitos.
• Ex: Um aspirador que tenta ir para esquerda e pode falhar.
• Action(left,PRENCOND:AtR,EFFECT:ATL).
• Action(left,PRENCOND:AtR,EFFECT:AtR v AtL).
•Efeitos condicionais
•Dependendo do estado no qual a ação está sendo
executada. Não trata indeterminância
•Ex: Aspirador que às vezes suja o quadrado destino,
porém ele só suja se o quadrado estiver limpo.
•Action(left,PRECOND: AtR,EFFECT:AtL v (AtL ^ when
CleanL:~CleanL)).
•Passos Condicionais
•If AtL ^ CleanL then Rigth else Suck
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Condicional: Ambiente
Parcialmente Observável
• Percepção parcial do estado atual.
• Admitir que o estado atual pertence a um
conjunto de estados.
• Estados de crenças do agente.
• Ex: O agente do aspirador. Ele conhece o
estado do quadrado em que está, mas ele não
conhece o outro quadrado.
• Representação do estado de crença.
• {(AtR ^ CleanR ^ CleanL).(AtR ^ CleanR ^
~CleanL}
• Este formato de representação pode ser muito cara
se existir várias proposições booleanas definidas
sobre o estado.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Monitoramento e Execução
• Qualquer técnica de planejamento pode ser
utilizada:(Clássica, Sem Sensor ou Condicional).
• A diferença é que ele precisará fazer o
monitoramento da execução.
• Avaliação da adequação do plano à nova
situação.
• E se alguma coisa não sai como esperado?
• O Replanejamento é utilizado para tratar as
indeterminâncias ilimitadas que podem ocorrer.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Monitoramento e Execução
• Começar execução com plano completo e
correto dados conhecimento e suposições
inicialmente disponíveis
• Usar percepções durante a execução para
adquirir conhecimento complementar e
verificar suposições
• Replanejar fim do plano para se adequar as
situações não antecipadas.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Monitoramento da Execução
•
Plano completo inicial:
• whole_plan que começa em
S e vai até G.
•
•
•
•
•
•
O agente executa o plano até o
ponto E.
As precondições são verificadas.
Ele verifica que as prencodições
são satisfeitas atualmente no
estado O e não no estado E.
Ele então chama o seu algoritmo
de planejamento que retorno um
reparo para o plano.
Este reparo começa em O e vai
até algum ponto P do plano
inicial.
Um novo plano resulta da
concantenação do repair com a
continuação.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Contínuo ou Situado
• Persiste indefinidamente no ambiente:
• Ele vive sempre mudando a formulação de seus
objetivos, planejamento e fases de atuação.
• Em vez de ter o planejador e o monitor de
execução como processos separados, ter um
único processo presente em um agente de
monitoramento contínuo.
• Suas atividades incluem
• Executar alguns passo do plano que devem ser executados
• Refinamento do plano para satisfazer as precondições
abertas
• Resolver os conflitos
• Modificar o plano tomando como referencial as
informações obtidas durante a execução.
Planejamento Hierárquico e Planejamento Reativo
Planejamento e Execução
Planejamento Contínuo: POP-con
• Assumindo ambiente completamente
observável. A mesma técnica pode ser
utilizada para ambientes parcialmente
observáveis.
• Como exemplo usaremos o mundo dos
blocos.
• A ação é mover(x,y). Mover x para y.
• Action(Move(x,y),PRECOND:Clear(x) ^ Clear(y) ^
On(x,z),
• EFFECT:On(x,y) ^ Clear(z) ^ ~On(x,z) ^
~Clear(y)).
Ex: Mundo dos blocos
A
B
E
C
F
D
G
Estado Inicial
A
C
D
B
E
F
G
Objetivo
Ação: Mover (x, y)
Op( Ação: Mover (x, y),
Precond: Limpo (x) ^ Limpo (Y) ^ EmCima (x, z),
Efeito: EmCima (x,y) ^ Limpo (z) ^
~ EmCima(x, z) ^ ~ Limpo (y)
A
B
E
C
F
Plano Inicial
D
G
Estado Inicial
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,G)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (B)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,G)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
B
E
C
F
Plano Inicial
D
G
Estado Inicial
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,G)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (B)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,G)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
B
E
C
F
Plano Inicial
D
G
Estado Inicial
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,G)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (B)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,G)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
B
E
C
F
Plano Inicial
D
G
Estado Inicial
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,G)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (B)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,G)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
Eis que de repente...
A
D
B
E
C
F
G
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
Eis que de repente...
A
D
B
E
C
F
G
A próxima ação seria:
Mover (D, B), mas as pré-condições
limpo (D) ^ limpo (B) ^ EmCima (D,G)
não são mais válidas
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
D
B
E
C
F
• Estendendo um link
causal
G
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
D
B
E
C
F
• Eliminando passos
redundantes
G
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
Mover (D,B)
Fim
A
D
B
E
C
F
• Eliminando passos
redundantes
G
EmCima (C,F)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,F)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
Fim
C
A
Início
D
B
E
• Um Agente desajeitado...
F
G
NaMesa (A)
EmCima (B,E)
EmCima (C,A)
EmCima (D,B)
Limpo (F)
Limpo (C)
Limpo (D)
Limpo (G)
EmCima (C,D)
EmCima (D,B)
Fim
C
A
D
B
E
• Adicionando um novo
passo...
F
G
EmCima (C,A)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,A)
EmCima (D,B)
Limpo (F)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
Fim
C
A
D
B
E
• Adicionando um novo
passo...
F
G
EmCima (C,A)
Limpo (C)
Limpo (D)
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,A)
EmCima (D,B)
Limpo (F)
Limpo (C)
Limpo (D)
Limpo (G)
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
Fim
A
Início
C
D
B
E
• Finalmente...
F
G
NaMesa (A)
EmCima (B,E)
EmCima (C,D)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
EmCima (C,D)
EmCima (D,B)
Fim
A
Início
C
D
B
E
• E o agente situado pode
buscar um novo objetivo
F
G
NaMesa (A)
EmCima (B,E)
EmCima (C,D)
EmCima (D,B)
Limpo (A)
Limpo (C)
Limpo (D)
Limpo (G)
EmCima (C,D)
EmCima (D,B)
Fim
Discussão
• O planejamento contínuo pode ser visto como similar ao POP
a medida que ele é um ciclo de percepção,correção de
falhas e atuação.
• Em cada iteração POP procura as falhas do plano efetuar a
correção.
• Pré-condições em aberto
• Conflitos Causais.
• O agente planejador contínuo ele pode tratar um número
maior de falhas.
• Falta de objetivos
• O agente pode adicionar um novo objetivo
• Pré-condições em aberto.
• Adicionar um link causal para a pré-condição em aberto
• Conflito Causal
• Escolher restrições de ordem ou de variáveis para resolver o conflito.
• Link não suportado
• Se existir um link Sart
remove o link.
• ...
P
A e p não é mais verdadeiro em Start, então
Quadro Comparativo
Ambientes Determinísticos
Ambientes não Determinísticos
Limitadas
Ilimitadas
POP
POP-Sem Sensor
- coerção
Monitoração e
Execução
POP-TI
POP Condicional
Planejamento
Contínuo
POP-RC
POP-HAD