Planejamento e Execução
Jacques Robin (CIn-UFPE)
Fernanda Marques
Simone Correia
Conteúdo

Planejamento Condicional
• Execução e geração de um plano condicional.
• Extensão da linguagem

Replanejamento
• Monitoramento: ação x execução
• Planejamento situado

Extensões e Discussões
• Planejamento condicional x replanejamento
• Coerção e abstração.
Introdução

POP e POP-TIRC-HAD-DUNC:
• Funcionam quando:


Ambiente acessível, estático, determinístico
Conhecimento completo e correto
• Só perceber, depois só planejar, depois agir cegamente

Em ambientes mais desafiadores:
• Abordagens:



1. Planejamento condicional
2. Monitoriamento da execução
3. Planejamento situado
• Perceber, depois juntamente planejar, perceber e agir
1. Planejamento condicional

Plano condicional:
• representa conjunto de planos,
• um para cada possível situação de execução

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).
• Ação de percepção pode:


ter efeitos colaterais no ambiente
desencadear sub-plano com ações de efetuação
2. Monitoramento da 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.
 Ex., o agente descobre não ter $ suficiente para comprar
todos os itens.

Conserto de um pneu vazio: operadores,
objetivo, condições iniciais

Operadores:
- Op(Action: Remove(x), Precond: On(x),
Effect: Off(x)^ClearHub(x)^notOn(x))
- Op(Action: PutOn(x), Precond: Off(x)^ClearHub(x),
Effect: On(x)^notClearHub(x)^not Off(x))
- Op(Action: Inflate(x), Precond: Intact(x)^ Flat(x),
Effect: Inflated(x)^notFlat(x))
Objetivo: On(x)^Inflated(x)
 Condições iniciais:

Inflated(Spare)^Intact(Spare)^Off(Spare)^On(Tire1)^ Flat(Tire1)
Concerto de um pneu vazio: planos
POP: [Remove(Tire1). PutOn(Spare)]
 Conhecimento incompleto: Intact(Tire1)
 Planejador condicional (CPOP):

• If(Intact(Tire1), [Inflate(Tire1)],
[Remove(Tire1), PutOn(Spare)])
• Mais eficiente do que POP
Execução de um plano condicional
Condição é verificada na BC e deve ser conhecida
naquele ponto do plano
 Conhecimento = BC inicial + deduções a partir das
seqüências de percepções e ações
 Para plano condicional ser executável: inserção de ações
de percepção testando as condições
 Ex,:

• Ação de percepção = CheckTire (x)
• Novo Operador :
Op(Action: CheckTire(x), Precond: Tire(x),
Effect: KnowsWhether(“Intact(x)”))
Construir um plano condicional
Contexto = condições necessárias para executar os
passos condicionais
 Inflate(Tire1), contexto: Intact(Tire1)
 Propagação de contexto
 Passos condicionais e links condicionais
 Introdução de passo condicional pode resolver ameaça
 Contexto x Precondição:

• precondição: associada a uma ação
• contexto: associado a uma possível instanciação do plano
condicional
Geração do Plano
Start
On(Tire1)
Flat(Tire1)
Inflated(Spare)
On(x)
Inflated(x)
Finish
true
Start
On(Tire1)
On(Tire1)
Flat(Tire1)
Inflated(Spare)
Inflated(Tire1)
Finish
true
Flat(Tire1)
Intact(Tire1)
Inflate(Tire1)
Intact(Tire1)
Start
On(Tire1)
Flat(Tire1)
Inflated(Spare)
On(Tire1)
Inflated(Tire1)
Finish
Intact(Tire1)
Flat(Tire1)
Intact(Tire1) Inflate(Tire1)
Check(Tire1)
Intact(Tire1)
On(x)
Inflated(x)
Intact(Tire1)
Finish
Not Intact(Tire1)
Start
On(Tire1)
On(Tire1)
Flat(Tire1)
Inflated(Spare)
Check(Tire1)
Inflated(Tire1)
Finish
Intact(Tire1)
Flat(Tire1)
Intact(Tire1) Inflate(Tire1)
Intact(Tire1)
Intact(Tire1)
On(Spare)
Inflated(Spare)
Finish
NotIntact(Tire1)
Plano completo: alguma ameaça?
Start
On(Tire1)
Flat(Tire1)
Inflated(Spare)
On(Tire1)
Inflated(Tire1)
Finish
(Intact(Tire1))
Flat(Tire1)
Inflate(Tire1)
Intact(Tire1)
(Intact(Tire1))
On(Spare)
Intact(Tire1)
Inflated(Spare)
Check(Tire1)
NotIntact(Tire1)
Remove(Tire1)
(NotIntact(Tire1))
Finish
(NotIntact(Tire1))
PutOn(Spare)
(NotIntact(Tire1))
Estendendo a linguagem de planejamento
Percepção não binária, ex.: Color(x,c)
 Planos parametrizados com variável de execução.

• ex., [SenseColor(table), KnowsWhat(“Color(table, c)”),
GetPaint(c), Paint(Chair,c)].

Variáveis de execução
• Não se unificam entre si, nem com constantes, apenas com
variáveis de planejamento

Loops:
• ex,: While (Knows(“UnevenColor(chair)”),
[Paint(chair, c), CheckColor(chair)])

Planejamento condicional e programação automática
E se as coisas não saírem como planejadas?

Monitoramento da Ação:
• Verificação, com percepção, das pre-condições do próximo passo

Monitoramento da Execução:
• Verificação, com percepção, das pré-condições do segmento de
plano restante.

Condições de lidar com pré-condições:
• não planejadas
• já satisfeitas

Ex., robô dirigindo carro
Detecção das falhas do plano

2 tipos de causas de falhas:
• Não determinismo ou inacessibilidade enumerável
 ex., abrir lata de tinta (normal, vazia, derrame)
 pode usar C-POP-D
• Não determinismo ou inacessibilidade não enumerável
 ex., dirigir, planejamento econômico
 requer replanejamento
Replanejamento

Q
A
R

P

Início
Agora
Fim
Escolher a melhor
continuação
Verificar as
precondições
Executar
Replanejamento

Q
R
A
P
A’
P’


Início
Agora
Fim
Escolher a melhor
continuação
Verificar as
precondições
Executar
Replanejamento

Q
A
R
A’

P
P’

Q’
Início
Agora
Fim
Q = R + P ( Plano inicial )
Q’= R + P’ ( Plano Final )
Escolher a melhor
continuação
Verificar as
precondições
Executar
Ex: Pintar cadeira da mesma cor da mesa
Pega( Tinta)
n/ Tem ( tinta )
Ex: Pintar cadeira da mesma cor da mesa
Cor ( cadeira ) <> Cor ( mesa) e
Tem (tinta)
Pega( Tinta)
n/ Tem ( tinta )
Pinta
Ex: Pintar cadeira da mesma cor da mesa
Cor ( cadeira ) <> Cor ( mesa) e
Tem (tinta)
Pinta
Cor (cadeira) =
Cor (mesa) (100%)
Pega( Tinta)
n/ Tem ( tinta )
Verifica
Fim
Ex: Pintar cadeira da mesma cor da mesa
Cor ( cadeira ) <> Cor ( mesa) e
Tem (tinta)
Pinta
Cor (cadeira) =
Cor (mesa) (100%)
Pega( Tinta)
Verifica
n/ Tem ( tinta )

Comportamento de loop
• emergente da interação (re)planejador-ambiente
• sem conceito de loop da linguagem de planejamento
• pode servir de base para aprendizagem
Fim
Ex: Pintar cadeira da mesma cor da mesa
Cor ( cadeira ) <> Cor ( mesa) e
Tem (tinta)
Pinta
Cor (cadeira) =
Cor (mesa) (100%)
Pega( Tinta)
n/ Tem ( tinta )

Replaneja:
• P = {fim} --> P’ = {pinta,verifica,fim}
• P’ = {pinta,verifica,fim}
--> P’’ = {pega(tinta),pinta, verifica,fim}
Verifica
Fim
Agente de Planejamento Situado
Gera um plano inicial
 Logo começa a executá-lo mesmo incompleto
 Continua planejando durante a execução, intercalando:

• execução de passos (de percepção e efetuação)
• refinamento e ajuste do plano diante de defeitos e mudanças não
antecipadas no ambiente.
Ex: Mundo dos blocos
A
B
E
C
F
D
G
Estado Inicial
A
C
D
B
E
F
G
Objetivo
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
D
G
Plano Inicial
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
A próxima ação seria:
Mover (D, B), mas as pré-condições
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
Extendendo 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
Eleminando 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
F
Um Agente Aloprado...
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
F
Adicinando um novo passo...
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:
• plano revisado final completo e correto
• agente situado procura 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
Planejamento condicional x replanejamento
(# passos)
Planejamento Condicional: # condições = e
 Replanejamento: planos frágeis nem sempre podem ser
completados
 Um sistema híbrido
 Conclusão: deve-se considerar probabilidades e custos
dos resultados.

Outros métodos para contornar a
incerteza: coerção e agregação

Coerção:
• forçar o mundo a um estado conhecido.
• ex., Objetivo: Color(Chair,c)^Color(Table,c)
• Solução: pintar a cadeira e a mesa com mesma tinta

Objetivo de manutenção:
• proibir coerção de algumas propriedades de alguns objetos
• ex., Color(Chair,c)^Color(Table,c)^Maintain(Color(Table,x))

Agregação:
• agrupar objetos de comportamento individual não determinístico
• em classes de comportamento global determinístico
Abstração,
arquitetura híbridas e multi-agentes
Ambiente Determinístico
Agente Planejador
Simbólico Declarativo
Grau de
Abstração
Ambiente Não-Determinístico
Agente Reativo
Simbólico Procedimental
ou Sub-Simbólico
Download

planning3