INF 1771 INF 1771 ...edirlei.3dgb.com.br/.../IA_Aula_14_Planejamento_Nao_  · Efeitos condicionais

  • View
    214

  • Download
    0

Embed Size (px)

Text of INF 1771 INF 1771 ...edirlei.3dgb.com.br/.../IA_Aula_14_Planejamento_Nao_  · Efeitos condicionais

  • INF 1771 INF 1771 INF 1771 INF 1771 IntelignciaIntelignciaIntelignciaInteligncia ArtificialArtificialArtificialArtificial

    Aula 13 Planejamento em Ambientes No-Determinsticos

    Edirlei Soares de Lima

  • LOGO Planejamento ClssicoPlanejamento ClssicoPlanejamento ClssicoPlanejamento ClssicoPlanejamento ClssicoPlanejamento ClssicoPlanejamento ClssicoPlanejamento Clssico

    Em planejamento clssico, o ambiente do problema precisa possuir as seguintes caractersticas:

    Observvel.

    Esttico.

    Determinstico.

    Supe-se que as descries das aes so sempre corretas e completas. Nestas circunstncias, um agente poderia planejar e depois executar o plano de olhos fechados.

  • LOGO Planejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes IncertosPlanejamento em Ambientes Incertos

    Em ambientes incertos, um agente deve:

    Usar seu sensores para descobrir o que est acontecendo no ambiente enquanto o plano est sendo executado.

    Modificar ou substituir o plano se algo inesperado acontecer.

    Os agentes precisam lidar com informaes incompletas e incorretas.

  • LOGO Planejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes No--------DeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticos

    Existem 4 mtodos de planejamento mais comuns usados para lidar com o ambientes no-determinsticos:

    (1) Planejamento sem sensores: Constri-se planos sequenciais normais (sem percepo), mas considera-se todas as circunstncias independentemente do estado inicial.

    (2) Planejamento condicional: Constri-se, a priori, um plano fixo com diferentes ramificaes para diferentes contingentes. Percebe-se o ambiente para saber que ramo seguir.

  • LOGO Planejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes NoPlanejamento em Ambientes No--------DeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticosDeterminsticos

    Mtodos de planejamento para ambientes no-determinsticos:

    (3) Monitoramento da execuo com replanejamento: Usa qualquer uma das tcnicas precedentes para construir o plano, mas monitora a execuo para ver se o plano pode ter sucesso no atual estado ou precisa ser revisto. Replaneja no caso de algo estar errado.

    (4) Planejamento contnuo: Planeja-se continuamente as aes, sendo capaz de tratar eventos inesperados, mesmo durante a construo do plano.

  • LOGO ExemploExemploExemploExemploExemploExemploExemploExemplo

    Problema da Mesa e Cadeira:

    Estado inicial: Uma cadeira, uma mesa e algumas latas de tinta, tudo com cores desconhecidas.

    Estado final: Cadeira e mesa com a mesma cor.

    Planejamento clssico no poderia resolver esse problema, pois o estado inicial no totalmente especificado.

  • LOGO ExemploExemploExemploExemploExemploExemploExemploExemplo

    Planejamento sem sensores:

    Considera todas as circunstncias independentemente do estado inicial.

    Coero - Agir para forar o mundo para estados desejveis.

    Soluo Cadeira+Mesa: Abrir uma lata e pintar cadeira e mesa com ela (mesmo que algum dos mveis j esteja com esta cor).

  • LOGO ExemploExemploExemploExemploExemploExemploExemploExemplo

    Planejamento condicional:

    Constri, a priori, um plano (fixo) com diferentes ramificaes para diferentes contingentes.

    Percebe o ambiente para saber que ramo seguir.

    Plano Cadeira+Mesa: Percebe as cores da cadeira e da mesa

    Se iguais, ento termina Se no,

    percebe o rtulos das latas

    Se houver alguma com a mesma cor de um dosmobilirios, ento aplica-a ao outro

    Se no, pinta ambos com a mesma cor.

  • LOGO ExemploExemploExemploExemploExemploExemploExemploExemplo

    Monitoramento da execuo com replanejamento:

    Monitora a execuo para ver se o plano pode ter sucesso no atual estado ou precisa ser revisto.

    Replaneja no caso de algo estar errado.

    Plano Cadeira+Mesa: Se por acaso a pintura deixou alguma cor antiga aparecendo, pinta-se novamente a moblia em questo.

  • LOGO ExemploExemploExemploExemploExemploExemploExemploExemplo

    Planejamento contnuo:

    Capaz de tratar eventos inesperados, mesmo durante a construo do plano.

    Cadeira+Mesa:

    Se algum est jantando, adia a pintura para o outro dia.

  • LOGO Planejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento Condicional

    Aplicao em ambientes completamente observveis:

    O agente sabe seu estado atual, mas se o ambiente for no determinstico, ela no saber o efeito de suas aes.

    Exemplo Aspirador de P:

    s vezes suja o destino quando se move para l.s vezes suja se sugar em um local limpo.

  • LOGO Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional -------- Aspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de P

    Formalizando o problema em linguagem STRIPS:

    Efeitos disjuntivos a ao possui um ou mais efeitos:

    Action(Left, Precond: AtR, Effect: AtL AtR)

    Efeitos condicionais o efeito depende do estado onde a ao foi executada:

    Action(Suck, Precond:, Effect: (when AtLeft: CleanL) (whenAtRight, CleanR)

    Passos condicionais para testar na execuo:

    If CleanL then Right else Suck

  • LOGO Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional Planejamento Condicional -------- Aspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de PAspirador de P

    Estados:Inicial: AtR CleanL CleanRFinal: AtL CleanL CleanR

    A representao do espao de busca feita em uma rvore and-or.

    A soluo uma sub-rvore onde todos os ns folha levam em algum ponto a soluo do problema.

  • LOGO rvore Andrvore Andrvore Andrvore Andrvore Andrvore Andrvore Andrvore And--------OrOrOrOrOrOrOrOr

    OR

    OR OR

    ANDAND

    AND ANDAND AND

  • LOGO Planejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento CondicionalPlanejamento Condicional

    Ambientes parcialmente observveis e no determinsticos:

    Os testes condicionais nem sempre funcionam...Exemplo: aspirador s sabe se tem sujeira na sala em que ele est.

    Belief state (estado de crena):Ao invs de estado nico, deve-se lidar explicitamente com a ignorncia para sempre estar consciente do que se sabe (ou do que no se sabe).

    Representado como um conjunto de estados possveis.

    Soluo: Grafos And-Or em estados de crena.

    Combina planejamento condicional com planejamento sem sensores.

  • LOGO Grafo AndGrafo AndGrafo AndGrafo AndGrafo AndGrafo AndGrafo AndGrafo And--------Or em Estados de CrenaOr em Estados de CrenaOr em Estados de CrenaOr em Estados de CrenaOr em Estados de CrenaOr em Estados de CrenaOr em Estados de CrenaOr em Estados de Crena

    Acreditava que esquerda estava suja

    Acreditava que esquerda estava limpa

    Estado de crena

  • LOGO Monitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com Replanejamento

    Monitoramento da execuo checa as percepes para ver se tudo est indo de acordo com o plano.

    Existem dois tipos de monitoramento:

    Monitoramento da ao: para ver se a prxima ao aplicvel.

    Exemplo: a porta est fechada.

    Monitoramento do plano: ver se o plano ainda vivelExemplo: no tem mais dinheiro suficiente.

    Replanejamento: Se algo inesperado acontece, pede-se ao planejador um novo plano ou tentar reparar o plano antigo.

  • LOGO Monitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com Replanejamento

    A estratgia monitoramento e replanejamento pode ser aplicada em todos os tipos problemas.

    Ambiente total ou parcialmente acessvel.

    Espao de estados ou de planos.

    Planos condicionais ou no.

  • LOGO Monitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com ReplanejamentoMonitoramento da Execuo com Replanejamento

    Exemplo: Whole plan = plano inteiro (inicial), S= start, G = goal.Plan = plano que resta.O agente deveria chegar em E mas foi para O.Ento tenta encontrar um plano que leve de O a qualquer ponto de WholePlan.

  • LOGO Monitoramen

Recommended

View more >