Desenvolvimento de Sistemas
Baseados em Conhecimento
Planejamento em Ambientes Incertos
Roteiro
• Indeterminação do ambiente e suas soluções
• Planejamento Condicional
• Monitoramento da execução com replanejamento
• Planejamento contínuo (situado)
Ambientes: Informação
• Ambientes observáveis, estáticos e deterministas
• Como se planeja nestes casos?
– Planejar e depois executar de “olhos vendados”
• Que técnicas se aplicam?
–
–
–
–
Busca em espaço de estados (STRIPS)
POP
Planejamento hierárquico
Escalonamento (tempo+recurso)
Ambientes: Informação
• Que incerteza há em ambientes não observáveis,
dinâmicos ou não deterministas?
• Informação incompleta
– Parcialmente observável, não determinista ou ambos
– Modelo do mundo fraco, mas correto!
» Ex. a porta do banheiro está aberta ou fechada? Minhas chaves
podem abri-la ou não?
• Informação incorreta
– O mundo não casa com o modelo dele
» Ex. Eu vou na garage pegar o carro para ir ao trabalho, mas o carro
foi roubado
Ambientes: Graus de Indeterminação
• Indeterminação Limitada (bounded indeterminacy)
– Percepções são parciais e/ou ações têm efeitos imprevisíveis mas
as conseqüências podem ser listadas
» Ex. jogar a moeda (cara ou coroa)
• Soluções
– Planejamento/busca sem sensor (sensorless)
– Planejamento condicional
Ambientes: Graus de Indeterminação
• Indeterminação Ilimitada (unbounded indeterminacy)
– Conjunto de pré-condições ou efeitos desconhecidos é grande
demais
» Domínios dinâmicos como economia, estratégia militar,...
• Soluções
– Monitoramento da execução com replanejamento
– Planejamento contínuo
Soluções: visão intuitiva
• Exemplo para comparar soluções
– Estado inicial: uma cadeira, uma mesa e algumas latas de tinta,
tudo com cores desconhecidas
– Estado final: cadeira e mesa com a mesma cor
Soluções para Indeterminação Limitada
• Caso do “Sensorless problem”: agente sem sensores!
• Planejamento sem sensor (sensorless planning)
– Constrói planos seqüenciais normais (execução sem percepção),
mas considera todas as circunstâncias independentemente do
estado inicial
» Ex. Médico ao dar antibiótico de largo espectro
• Noção importante: Coerção!
– Agir para forçar o mundo para estados desejáveis
Exemplos...
• Cadeira+Mesa
– Abrir uma lata e pintar cadeira e mesa com ela (mesmo que algum
dos móveis já esteja com esta cor)
• Aspirador versão 1.0: sem sensor
– Início: {1,2,3,4,5,6,7,8}, Objetivo => {7,8}
– Dir => {2,4,6,8}, Esq => {1,3,5,6}, Sugar => {4,5,7,8}
– Solução: [Dir, Sugar, Esq, Sugar]
Soluções para Indeterminação Limitada
• Caso do Problema Contingencial
– o ambiente parcialmente observável ou efeito das ações
desconhecido => nova informação após cada ação
• Planejamento conditional
– Constrói, a priori, um plano (fixo) com diferentes
ramificações para diferentes contingentes.
– Percebe o ambiente para saber que ramo seguir
• Plano Cadeira+Mesa
Percebe as cores da cadeira e da mesa
Se iguais, então termina
senão,
percebe rótulos das latas
se houver alguma com a mesma cor de um dos
mobiliários, então aplica-a ao outro
Caso contrário, pinta ambos com a mesma cor.
Soluções para Indeterminação Ilimitada
• Monitoramento da execução com replanejamento
– Usa qualquer uma das técnicas precedentes para construir o
plano, mas
– Monitora a execução para ver se o plano pode ter sucesso no
atual estado ou precisa ser revisto
– Replaneja no caso de algo estar errado
• Como se aplica ao exemplo da Cadeira+Mesa?
• Plano
– Se por acaso a pintura deixou alguma cor antiga aparecendo,
repintar a mobília em questão
Soluções para Indeterminação Ilimitada
• Planejamento contínuo (situado)
– Capaz de abandonar e formular novos objetivos
– Capaz de tratar eventos inesperados, mesmo durante a
construção do plano
• Exemplo Cadeira+Mesa
– Se alguém está jantando, adia a pintura para o outro dia!
Planejamento Condicional
• Usado quando temos:
– Ambientes completamente observáveis + efeitos imprevisíveis das
ações
– Ambientes parcialmente observáveis
Planejamento Condicional
• Ambientes completamente observáveis
– O agente sabe seu estado atual, mas se o ambiente for não determinista,
ela não saberá o efeito de suas ações
• Ex. Aspirador versão 2.0:
– às vezes... suja o destino quando se move para lá
– às vezes... suja se sugar em um local limpo
• Plano condicional: Como construí-lo?
• Primeiro passo: estender STRIPS...
– Efeitos disjuntivos: ação com um ou mais efeitos
» Action(Left, Precond: AtR, Effect: AtL  AtR)
– Efeitos condicionais: efeito depende do estado onde a ação foi executada
» Action(Suck, Precond:, Effect: (when AtLeft: CleanL)  (when AtRight, CleanR)
Estado inicial 
And-Or
Tree
.
Objetivo 
State nodes (agente)
Chance nodes (natureza)
• .
OR
AND
AND
OR
OR
AND
AND
AND
AND
Planejamento Condicional
• Solução em uma And-Or tree
– A solução é uma sub-árvore
» Cujas folhas são todas iguais ao objetivo
» Que especifica uma ação a cada nó de estado
» Que inclui todas as conseqüências dos nós de “azar”.
Planejamento Condicional
• Ambientes parcialmente observáveis e não deterministas
– Os testes condicionais (percepções) nem sempre funcionam...
» Ex. aspirador só sabe se tem sujeira no quarto em que está
– Belief state (estado de crença):
» Ao invés de estado único, deve-se lidar explicitamente com a
ignorância para sempre estar consciente do que se sabe (ou do que
não se sabe)!
» Representado como um conjunto de estados (possíveis)
• Solução
– Grafos And-Or em estados de crença
– Combina planejamento condicional com sersorless
Planejamento Condicional
Aspirador alternativo
• Deixa, as vezes, sujeira
quando sai de
uma posição limpa
• Não sabe se há sujeira
no quadrado ao lado
Estado
de crença
Planejamento Condicional
• Representação dos estados de crença
– descrição completa
» Crença A = {(atR  CleanR  CleanL), (atR  CleanR  CleanL)}
• Representação das ações
Action(Left, Precond: AtR,
Effect: AtL  (AtL  when CleanL: CleanL))
Monitoramento da execução e
replanejamento
• Monitoramento da execução
– Checar as percepções para ver se tudo está indo de acordo com o
plano (lidar com imprevistos)
• Dois tipos de monitoramento
– Monitoramento da ação: para ver se a próxima é aplicável
» Ex. a porta está fechada
– Monitoramento do plano: ver se o plano ainda é viável
» Ex. não tem mais $ suficiente
• Replanejamento
– Se algo inesperado acontece, pedir ao planejador um novo plano
ou tentar reparar o plano antigo
Monitoramento da execução e
replanejamento
• Exemplo:
?
– Aspirador que quando se desloca para lugar limpo suja-o
– Basta não se preocupar com isto...
» Plano [Left]
» Se não dá para executar Finish (tem sujeira), replaneja e encontra o
plano [Suck]
• A estratégia monitoramento + replanejamento pode ser
aplicada em tudo
– Ambiente total ou parcialmente acessível
– Espaço de estados ou de planos
– Planos condicionais ou não...
Monitoramento da execução e
replanejamento
• Reparo e continuação (Repair and continuation)
– Em vez de replanejar tudo, encontrar um conserto...
• Exemplo
–
–
–
–
Whole plan = plano inteiro (inicial), S= start, G = goal
Plan = plano que resta
O agente deveria chegar em E mas foi para O (action monitoring)
Então tenta encontrar um plano que leve de O a qualquer ponto de
WholePlan
Monitoramento da execução e
replanejamento
• Exemplo: de cadeira azul, mesa verde, lata de tinta azul e lata de
tinta vermelha para tudo pintado da mesma cor
• Formalmente
– Init (Color(Chair,Blue)  Color(Table,Green)  PaintCan(BC),
ContainsColor(BC,Blue), PaintCan(RC), ContainsColor(RC,Red))
– Goal (Color(Chair, x)  Color(Table, x))
– Action (Paint (object,color)
PRECOND: HavePaint(color)
EFFECT: Color(object,color))
– Action (Open (can)
PRECOND: PaintCan(can)  ContainsColor(can,color)
EFFECT: HavePaint(color))
• A solução seria
– [Start; Open(BC); Paint(Table,Blue); Finish]
Monitoramento da execução e
replanejamento
• Execução/reparo
– Agente executa Start; Open(BC); Paint(Table,Blue)
– Mas, antes de executar Finish, ele verifica que esqueceu uma
mancha verde na mesa...
– Neste caso, Repair = [] (já que não conhece a ação pinta
mancha), e retoma plano inteiro (inicial) em Paint(Table,Blue),
Finish
• Observação
– Funciona naturalmente como um laço que verifica se ficou ok e
caso contrário refaz
Monitoramento da execução e
replanejamento
• Porém, ...as vezes monitoramento de ação não é o
bastante
– Só detecta a falha tarde demais porque verifica, a cada passo,
somente se o próximo é executável
– Exemplo: decidir pintar tudo de vermelho
» depois de pintar a cadeira, descobrir que não tem tinta suficiente para
a mesa
– É preciso, em qualquer estado, detectar falhas que inviabilizem o
resto do plano
Monitoramento da execução e
replanejamento
• Monitorando plano
– Verifica, a cada passo, as pré-condições para o sucesso do plano
inteiro
» Exceto as pré-condições que serão alcançadas por outros passos do
plano remanescente
– Com isto, corta a execução de planos “amaldiçoados” o mais cedo
possível
– Entretanto, problemático em ambientes parcialmente acessíveis
» Agente pode não detectar coisas que estão dando errado
» Pode-se perder mais tempo verificando todas as condições do futuro
plano do que agindo
– Solução: escolher as verificações relevantes e torcer para tudo dar
certo
» mantendo monitoramento das ações sempre!
Monitoramento da execução e
replanejamento (outras limitações)
• Não há garantias formais
– que o plano será concebido e executado com sucesso
• Dificuldade em distinguir problemas difíceis de “fúteis” (s/
solução)
– O agente ficar bloqueado
» Ex. tentando abrir a porta do quarto com a chave errada
– Soluções
» Tentar aleatoriamente reparos diferentes para ver se dá sorte
» Aprendizagem por reforço
• Não pode formular novos objetivos
Planejamento Contínuo (Situado)
• Não é um mero resolvedor de problemas
• Diferenças básicas
–
–
–
–
Cria plano incrementalmente (dentro de limites de tempo)
Pode começar a executar um plano mesmo incompleto
Continua planejando durante a execução
Pode mudar de objetivo
• Ou seja, é capaz de intercalar *continuamente*
– Execução de passos (de percepção e efetivação)
– Monitoramento
– Replanejamento
Planejamento Contínuo (Situado)
• Exemplo no mundo dos blocos
– Action: Mover (x, y), “mover x para cima de y”
PRECOND: Limpo(x)  Limpo(y)  EmCima(x,z)
EFFECT: EmCima (x,y)  Limpo(z)  EmCima(x,z)  Limpo(y)
– O agente escolheu o objetivo abaixo
A
B
E
C
F
D
G
Estado Inicial
A
C
D
B
E
F
Objetivo
G
Planejamento Contínuo (Situado)
•
Supondo que nada acontece
enquanto se planeja, o plano é
rapidamente encontrado com POP...
Ele será executado em seguida!
C
D
A
B
E
C
F
D
G
A
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)
B
E
G
Objetivo
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,G)
Limpo (D)
Limpo (B)
F
Mover (D,B)
Fim
Planejamento Contínuo (Situado)
• Imagine agora que um
evento externo da natureza
ocorra...
A
B
E
C
F
Estado Inicial
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)
D
G
A
D
B
E
G
Novo Estado Inicial
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
C
F
Fim
Plano incompleto!
Mover (D,B)
Planejamento Contínuo (Situado)
C
D
• Estendendo um link causal
A
B
E
C
F
D
G
A
Estado Inicial
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)
B
E
G
Objetivo
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
EmCima (D,y)
Limpo (D)
Limpo (B)
F
Mover (D,B)
Fim
Plano completo mas
redundante!
Planejamento Contínuo (Situado)
C
D
• Eliminando passos redundantes
A
B
E
C
F
D
G
A
Estado Inicial
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)
B
E
F
G
Objetivo
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
Fim
Planejamento Contínuo (Situado)
• Mas o agente é desastrado e coloca C em cima de A ao invés de D
durante a execução
A
B
E
C
F
D
G
Estado Inicial
Início
NaMesa (A)
EmCima (B,E)
EmCima (C,A)
EmCima (D,B)
Limpo (F)
Limpo (C)
Limpo (D)
Limpo (G)
C
A
D
B
E
C
D
F
G
Novo Estado Inicial
A
B
E
F
G
Objetivo
EmCima (C,D)
EmCima (D,B)
Fim
Planejamento Contínuo (Situado)
• Adicionando um novo passo
C
A
D
B
E
C
D
F
G
A
Novo Estado Inicial
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)
B
E
F
G
Objetivo
Mover (C,D)
EmCima (C,D)
EmCima (D,B)
Fim
Planejamento Contínuo (Situado)
C
D
• Finalmente o agente situado pode
buscar um novo objetivo
A
B
E
F
G
Estado inicial
Início
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
No Mundo Real...
• Combina-se várias abordagens de planejamento
– Ex. Fabricantes de carro -> pneu estepe e air bag = planos
condicionais de furos e batidas
– Para motoristas, são possibilidades => replanejamento
• Cria-se planos condicionais só para as contingências que
trazem graves conseqüências
– Ex. Em um Rally, vale a pena assegurar o estepe e air bag
• Mesmo este super-agente, tem ainda defeitos???
– Sim... os agentes estudados não sabem encontrar um
compromisso entre probabilidade de sucesso e custo da
construção de um plano
» Decision-theoretical Agents
Implementação 4 (I4)
• Título do problema:
– Problema de Logística
• Objetivo:
– abaixo:
• Tecnologia a ser usada:
– PDDL (Planning Domain Description Language)