Ontologies Reasoning Components Agents Simulations Resolução de Problemas por Meio de Busca Exaustiva Jacques Robin André Felipe Santana

  • View
    217

  • Download
    2

Embed Size (px)

Text of Ontologies Reasoning Components Agents Simulations Resolução de Problemas por Meio de Busca...

  • Resoluo de Problemas por Meio de Busca Exaustiva

    Jacques RobinAndr Felipe Santana

  • O que um problema?Qualquer situao a ser resolvida por uma seqncia aes a ser executada, com vistas a atingir um objetivo;Na descrio acima:Situao = estado inicial;Seqncia de Aes = operaes que iro gerar uma sucesso de estados;Objetivo = estado final (ou conjunto de) desejado;

    Metfora da resoluo de problemas por meio de busca:Transformar um problema de raciocnio de um agente diretamente em um problema de navegao num espao de estados, no qual, a partir de um estado inicial, um agente pode buscar uma seqncia de aes que conduzem ao estados final desejado.

    A soluo de um problema conjunto de seqncias de aes que levam de um estado inicial ao estado objetivado

    Uma soluo tima uma seqncia de aes que leva de um estado inicial ao estado objetivado com o menor custo*.

  • Romnia: ir de Arad a Bucharest

  • Antes de qualquer coisa...Formular o problemaFormular o objetivo: definir um estado final que satisfaz o agenteex: Estar em Bucareste

    Especificar o problema em termos de:Estado Inicialex: Estou em AradFuno Sucessor S(x) = conjunto de pares ao-estadoex: S(Arad) = { (AradZerind, Zerind), (AradSibiu, Sibiu), ......}Teste do Objetivo: condio que capaz de determinar se o estado final foi alcanadoex: Estou em Bucareste?Custo (path cost)ex: soma de distancias, n de aes executadas, etc.

  • A Formulao do Problema define o Espao de Estados possveisO Espao de Estados definido implicitamente pelo estado inicial juntamente com todos os estados alcanveis atravs da funo sucessora S(x).Forma um grafo onde os ns representam estados e os arcos entre os ns representam aes.Entretanto:

  • A Formulao do Problema exige Abstrao do Mundo RealO mundo real absurdamente complexo: espao de estados tem que ser abstrado para a resoluo de problemas.

    Estado (abstrato) = conjunto de estados reais

    Ao (abstrata) = combinao complexa de aes reais, onde cada ao abstrata deveria ser mais fcil que o problema original.Ex: AradZerind representa um complexo de rotas possveis, paradas para descanso, etc.

    Soluo (abstrata) = conjunto de caminhos reais que so solues no mundo real para o problema.

  • Importncia de uma Formulao adequada do ProblemaO Espao de Estados derivado da formulao do problema impacta na eficincia de busca da soluoEx: Problema das 8 Rainhas Dispor 8 rainhas num tabuleiro de xadrez, sem que qualquer uma delas esteja sob ataque das demais:no pode haver mais de uma rainha em uma mesma linha, coluna ou diagonalsomente o custo da busca conta (n de passos para a soluo)

  • Importncia de uma Formulao adequada do ProblemaProblema das 8 Rainhas - Formulao 1:estado inicial: nenhuma rainha no tabuleirooperadores: adicionar uma rainha a qualquer quadrado vazioteste do objetivo: 8 rainhas no tabuleiro sem ataque mtuo?.... E assim por diante, at 64 x 63 x 62 x ..... x 57 1,8 x 1014 seqncias possveis a serem testadas

  • Importncia de uma Formulao adequada do ProblemaProblema das 8 Rainhas - Formulao 2:estado inicial: nenhuma rainha no tabuleirooperadores: adicionar uma rainha a qualquer quadrado da coluna mais a esquerda que no contm nenhuma rainhateste do objetivo: 8 rainhas no tabuleiro sem ataque mtuo?.... E assim por diante, at 88 1,7 x 107 seqncias possveis a serem testadas

  • Mais um exemplo...Aspirador de pestados =estado inicial =teste de trmino =operadores = custo da soluo =

  • Busca em um Espao de EstadosUma vez o problema bem formulado... usa-se um mtodo de busca para encontrar o estado final desejado.

    Mtodos genricos de busca:Busca exaustiva ou cegaNo sabe qual o melhor n da fronteira a ser expandido = menor custo de caminho desse n at um n final (objetivo).Busca heurstica - informadaEstima qual o melhor n da fronteira a ser expandido com base em funes heursticas => conhecimento

  • Busca em um Espao de EstadosGrafo do espao de estados do problemaA cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora

  • Busca em um Espao de EstadosGrafo do espao de estados do problemaA cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessora

  • Busca em um Espao de EstadosAradFagarasOradeaR.VilceaAradLugojAradOradeaSibiuTimisoaraZenridAradGrafo do espao de estados do problemaA cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessorafronteira

  • Busca em um Espao de EstadosAradFagarasOradeaR.VilceaAradLugojAradOradeaSibiuTimisoaraZenridAradGrafo do espao de estados do problemaA cada passo, a rvore de busca expandida a partir de sua fronteira, pelos operadores definidos na sua funo sucessorafronteira

  • Estratgias de BuscaSo definidas pela ordem de expanso de ns

    Avaliao de desempenho de uma estratgia dimenses:Completude: se sempre encontra uma soluo, se ela existe;Complexidade de Tempo: em funo do n de ns gerados/expandidos;Complexidade de Espao: em funo do n mximo de ns armazenados em memria;Otimizao: se sempre encontra a soluo de menor custo

    Complexidade de tempo e espao mensurada em termos de:b (branching) - fator mximo de ramificao da rvore de busca;d (depth) profundidade da soluo de menor custo;m profundidade mxima do espao de estados (que pode ser infinita)

  • Estratgias de Busca CegaBusca em Largura (Breadth-first);

    Busca de Custo Uniforme;

    Busca em Profundidade (Depth-first);

    Busca em Profundidade Limitada (Depth-limited)

    Busca de Aprofundamento Iterativo (Iterative deepening)

    Busca Bidirecional

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (A)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (B,C)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (C,D,E)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (D,E,F,G)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (E,F,G,H,I)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (F,G,H,I,J,K)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (G,H,I,J,K,L,M)KMIOJLHN

  • Busca em Largura (Breadth-first)Expande sempre o n menos profundo ainda no expandido;Fronteira uma fila do tipo FIFO, i.e., novos sucessores so postos no fimABCEFDGFronteira = (H,I,J,K,L,M,N,O)KMIOJLHN

  • Desempenho da Busca em Largura (Breadth-first)Completa?

    Tempo?

    Espao?

    tima?

    Sim, desde que b (fator de ramificao) seja finito1 + b + b2 + b3 + ... + bd + b(bd 1) = O(bd+1), i.e., exponencial em d (fator de profundidade)O(bd+1) (armazena cada ndulo na memria)Em geral, no. Sim quando o custo constante a cada passo Espao o grande problema; pode facilmente gerar ndulos a 10MB/sec, o que em 24h chegaria a 860GB !!!!!

  • Busca de Custo UniformeExpande sempre o prximo n ainda no expandido que possui caminho de menor custo Fronteira = fila de ns ordenada pelo custo do caminho at cada nACEBDCidades:11051555ABCD1515Fronteira = (B,C,D)ABCD11515Fronteira = (C, EB ,D)EBABCD111015Fronteira = (Ec, EB ,D)EBEc

  • Desempenho da Busca de Custo Uniforme

    Completa?

    Tempo?

    Espao?

    tima?

    Sim, desde que o custo de cada n 0N de ns com custo(n) < custo(soluo tima)Sim, j q os ndulos expandem em ordem crescente de custo(n) N de ns com custo(n) < custo(soluo tima)Se o custo dos ns de um mesmo nvel for igual, o desempenho equivalente ao da Busca em Largura

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (A)

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (B,C)

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (D,E,C)

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (H,I,E,C)

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (I,E,C)

  • Busca em Profundidade (Depth-first)Expande sempre o n mais profundo ainda no expandido;Fronteira uma fila do tipo LIFO, i.e., novos sucessores so postos no incioABCEFDGJLHNKMIOFronteira = (E,C)

  • Busca em Profundidade (Depth-firs