ThemeGallery PowerTemplate

INF 1771 Inteligncia ArtificialAula 03 Resoluo de Problemas por Meio de BuscaEdirlei Soares de Lima

LOGOIntroduoAgentes Autnomos:Entidades autnomas capazes de observar o ambiente e agir de forma a atingir determinado objetivo.Tipos de Agentes:Agentes reativos simples;Agentes reativos baseado em modelo;Agentes baseados em objetivos;Agentes baseados na utilidade;Agentes baseados em aprendizado;

LOGOProblema de BuscaBucharestAradSibiuTimisoaraZerindLOGOProblema de Busca

LOGODefinio do ProblemaA definio do problema a primeira e mais importante etapa do processo de resoluo de problemas de inteligncia artificial por meio de buscas.

Consiste em analisar o espao de possibilidades de resoluo do problema, encontrar sequncias de aes que levem a um objetivo desejado.LOGODefinio de um ProblemaEstado Inicial: Estado inicial do agente. Ex: Em(Arad)

Estado Final: Estado buscado pelo agente. Ex: Em(Bucharest)

Aes Possveis: Conjunto de aes que o agente pode executar. Ex: Ir(Cidade, PrximaCidade)

Espao de Estados: Conjunto de estados que podem ser atingidos a partir do estado inicial. Ex: Mapa da Romnia.

Custo: Custo numrico de cada caminho. Ex: Distncia em KM entre as cidades.

LOGOConsideraes em Relao ao AmbienteEsttico: O Ambiente no pode mudar enquanto o agente est realizando a resoluo do problema.

Observvel: O estado inicial do ambiente precisa ser conhecido previamente.

Determinstico: O prximo estado do agente deve ser determinado pelo estado atual + ao. A execuo da ao no pode falhar.LOGOExemplo: Aspirador de PEspao de Estados: 8 estados possveis (figura ao lado);

Estado Inicial: Qualquer estado;

Estado Final: Estado 7 ou 8 (ambos quadrados limpos);

Aes Possveis: Mover para direita, mover para esquerda e limpar;

Custo: Cada passo tem o custo 1, assim o custo do caminho definido pelo numero de passos;

LOGOExemplo: Aspirador de P

LOGOExemplo: 8-PuzzleEspao de Estados: 181.440 possveis estados;

Estado Inicial: Qualquer estado;

Estado Final: Figura ao lado Goal State;

Aes Possveis: Mover o quadrado vazio para direita, para esquerda, para cima ou para baixo;

Custo: Cada passo tem o custo 1, assim o custo do caminho definido pelo numero de passos;

15-puzzle (4x4) 1.3 trilhes estados possveis.24-puzzle (5x5) 10 estados possveis.

LOGOExemplo: XadrezEspao de Estados: Aproximadamente possveis estados (Claude Shannon, 1950);

Estado Inicial: Posio inicial de um jogo de xadrez;

Estado Final: Qualquer estado onde o rei adversrio est sendo atacado e o adversrio no possui movimentos vlidos;

Aes Possveis: Regras de movimentao de cada pea do xadrez;

Custo: Quantidade de posies examinadas;

LOGOExemplo: 8 Rainhas (Incremental)Espao de Estados: Qualquer disposio de 0 a 8 rainhas no tabuleiro (1.8 x 10 possveis estados);

Estado Inicial: Nenhuma rainha no tabuleiro;

Estado Final: Qualquer estado onde as 8 rainhas esto no tabuleiro e nenhuma esta sendo atacada;

Aes Possveis: Colocar uma rainha em um espao vaio do tabuleiro;

Custo: No importa nesse caso;

* O jogo possui apenas 92 possveis solues (considerando diferentes rotaes e reflexes). E apenas 12 solues nicas.

LOGOExemplo: 8 Rainhas (Estados Completos)Espao de Estados: Tabuleiro com n rainhas, uma por coluna, nas n colunas mais a esquerda sem que nenhuma rainha ataque outra (2057 possveis estados);

Estado Inicial: Nenhuma rainha no tabuleiro;

Estado Final: Qualquer estado onde as 8 rainhas esto no tabuleiro e nenhuma esta sendo atacada;

Aes Possveis: Adicionar uma rainha em qualquer casa na coluna vazia mais esquerda de forma que no possa ser atacada;

Custo: No importa nesse caso;

LOGOExercciosTorre de Hani?

Canibais e Missionrios?

LOGOExercciosTorre de Hani:Espao de Estados: Todas as possveis configuraes de argolas em todos os pinos (27 possveis estados).Aes Possveis: Mover a primeira argola de qualquer pino para o pino da direita ou da esquerda.Custo: Cada movimento tem 1 de custo.

Canibais e Missionrios:Espao de Estados: Todas as possveis configuraes validas de canibais e missionrios em cada lado do rio (16 possveis estados).Aes Possveis: Mover 1 ou 2 personagens (canibais ou missionrios) para o outro lado do rio. O nmero de canibais em um determinado lado do rio no pode ser maior do que o nmero de missionrios.Custo: Cada movimento tem 1 de custo.LOGOExerccios

LOGOExerccios

LOGOAplicaes em Problemas ReaisClculo de Rotas:Planejamento de rotas de avies;Sistemas de planejamento de viagens;Caixeiro viajante;Rotas em redes de computadores;Jogos de computadores (rotas dos personagens);

AlocaoSalas de aula;Mquinas industriais;LOGOAplicaes em Problemas ReaisCircuitos Eletrnicos:Posicionamento de componentes;Rotas de circuitos;

Robtica:Navegao e busca de rotas em ambientes reais;Montagem de objetos por robs;

LOGO19Como Encontrar a Soluo?Uma vez o problema bem formulado, o estado final (objetivo) deve ser buscado no espao de estados.

A busca representada em uma rvore de busca:Raiz: corresponde ao estado inicial;Expande-se o estado corrente, gerando um novo conjunto de sucessores; Escolhe-se o prximo estado a expandir seguindo uma estratgia de busca;Prossegue-se at chegar ao estado final (soluo) ou falhar na busca pela soluo;LOGOBuscando SoluesExemplo: Ir de Arad para BucharestAradSibiuTimissoaraZerindAradFagarasOradesRimnico VilceaLOGOBuscando SoluesO espao de estados diferente da rvore de buscas.

Exemplo:

20 estados no espao de espaos;

Nmero de caminhos infinito;

rvore com infinitos ns;LOGOCdigo Descritivo Busca em rvoreFuno BuscaEmArvore(Problema, Estratgia) retorna soluo ou falhaInicio Inicializa a arvore usando o estado inicial do Problemaloop do se no existem candidatos para serem expandidos ento retorna falha Escolhe um n folha para ser expandido de acordo com a Estratgiase Se o n possuir o estado final ento retorna soluo correspondentese no expande o n e adiciona os ns resultantes a arvore de buscaFimLOGOPseudocdigo Busca em rvoreFuno BuscaEmArvore(Problema, fronteira) retorna soluo ou falhaInicio fronteira InsereNaFila(FazN(Problema[EstadoInicial]), fronteira) loop do se FilaVazia(fronteira) ento retorna falha n RemovePrimeiro(fronteira) se n[Estado] for igual a Problema[EstadoFinal] ento retorna Soluo(n) fronteira InsereNaFila(ExpandeFronteira(n, Problema), fronteira)Fim

A funo Soluo retorna a sequncia de ns necessrios para retornar a raiz da arvore.Considera-se fronteira uma estrutura do tipo fila.

LOGOMedida de DesempenhoDesempenho do Algoritmo:(1) O algoritmo encontrou alguma soluo?(2) uma boa soluo? Custo de caminho (qualidade da soluo).(3) uma soluo computacionalmente barata?Custo da busca (tempo e memria).

Custo TotalCusto do Caminho + Custo de Busca.LOGOMtodos de BuscaBusca Cega ou Exaustiva:No sabe qual o melhor n da fronteira a ser expandido. Apenas distingue o estado objetivo dos no objetivos.

Busca Heurstica:Estima qual o melhor n da fronteira a ser expandido com base em funes heursticas.

Busca Local:Operam em um nico estado e movem-se para a vizinhana deste estado.LOGOBusca CegaAlgoritmos de Busca Cega:Busca em largura;Busca de custo uniforme;Busca em profundidade;Busca com aprofundamento iterativo;LOGOBusca em LarguraEstratgia: O n raiz expandido, em seguida todos os ns sucessores so expandidos, ento todos prximos ns sucessores so expandidos, e assim em diante. ABDECFGLOGOBusca em LarguraPode ser implementado com base no pseudocdigo da funo BuscaEmArvore apresentado anteriormente. Utiliza-se uma estrutura de fila (first-in-first-out) para armazenar os ns das fronteira.

Complexidade:

* Considerando o numero de folhas b = 10 e cada n ocupando 1KB de memria

Profundidade (d)NsTempoMemria211000.11 ms107 KB4111,10011 ms10.6 MB6101.1 seg1 GB8102 min103 GB10103 horas10 TB121013 dias1 PB14103.5 anos99 PB

LOGOBusca de Custo UniformeEstratgia: Expande sempre o n de menor custo de caminho. Se o custo de todos os passos for o mesmo, o algoritmo acaba sendo o mesmo que a busca em largura.ABEFDGHC75170118717599111LOGOBusca de Custo UniformeA primeira soluo encontrada a soluo tima se custo do caminho sempre aumentar ao logo do caminho, ou seja, no existirem operadores com custo negativo.

Implementao semelhante a busca em largura. Adiciona-se uma condio de seleo dos ns a serem expandidos.

Complexidade: Onde:C = custo da soluo tima; = custo mnimo de uma ao;

LOGOBusca em ProfundidadeABEFDCMNPQEstratgia: Expande os ns da vizinhana at o n mais profundo.LOGOBusca em ProfundidadePode ser implementado com base no pseudocdigo da funo BuscaEmArvore apresentado anteriormente. Utiliza-se uma estrutura de pilha (last-in-first-out) para armazenar os ns das fronteira.

Pode tambm ser implementado de forma recursiva.

Consome pouca memria, apenas o caminho de ns sendo analisados precisa armazenado. Caminhos que j foram explorados podem ser descartados da memria.

LOGOBusca em ProfundidadeUso de memria pela busca em largura em uma arvore com 12 de profundidade: 1000 TB.

Uso de memria pela busca em profundidade em uma arvore com 12 de profundidade: 118 KB.

Problema: O algoritmo pode fazer uma busca muito longa mesmo quando a resposta do problema esta localizado a poucos ns da raiz da rvore.LOGO34Busca com Aprofundamento IterativoABEFDCMNPQLimit 0Limit 1GHPQLimit 2Limit 3Estratgia: Consiste em uma busca em profundidade onde o limite de profundidade incrementado gradualmente. LOGOBusca com Aprofundamento IterativoCombina os benefcios da busca em largura com os benefcios da busca em profundidade.

Evita o problema de caminhos muito longos ou infinitos.

A repetio da expanso de estados no to ruim, pois a maior parte dos estados est nos nveis mais baixos.

Cria menos estados que a busca em largura e consome menos memria. LOGOBusca BidirecionalEstratgia: A busca se inicia ao mesmo tempo a partir do estado inicial e do estado final.ABDECGNMLOGOComparao dos Metodos de Busca CegaCriterioLarguraUniformeProfundidadeAprofundamento IterativoBidirecionalCompleto?Sim Sim ,NoSim Sim , timo?Sim SimNoSim Sim , TempoEspao

b = fator de folhas por n.d = profundidade da soluo mais profunda.m = profundidade mxima da rvore. completo se b for finito. completo se o custo de todos os passos for positivo. timo se o custo de todos os passos for idntico. se ambas as direes usarem busca em largura.LOGOComo evitar estados repetidos?Estados repetidos sempre vo ocorrer em problema onde os estados so reversveis.

Como evitar?No retornar ao estado pai.No retorna a um ancestral.No gerar qualquer estado que j tenha sido criado antes (em qualquer ramo).Requer que todos os estados gerados permaneam na memria.

LOGOBusca HeursticaAlgoritmos de Busca Heurstica:Busca GulosaA*

A busca heurstica leva em conta o objetivo para decidir qual caminho escolher.

Conhecimento extra sobre o problema utilizado para guiar o processo de busca.LOGOBusca HeursticaComo encontrar um barco perdido?

Busca Cega -> Procura no oceano inteiro.

Buca Heurstica -> Procura utilizando informaes relativas ao problema. Ex: correntes martimas, vento, etc.LOGOBusca HeursticaFuno Heurstica (h) Estima o custo do caminho mais barato do estado atual at o estado final mais prximo.So especficas para cada problema.

Exemplo:Encontrar a rota mais curta entre duas cidades:h(n) = distncia em linha reta direta entre o n n e o n final.LOGOBusca GulosaEstratgia: Expande os ns que se encontram mais prximos do objetivo (uma linha reta conectando os dois pontos no caso de distancias), desta maneira provvel que a busca encontre uma soluo rapidamente.

A implementao do algoritmo se assemelha ao utilizado na busca cega, entre tanto utiliza-se uma funo heurstica para decidir qual o n deve ser expandido.LOGOBusca GulosaArad 366 Mehadia 241 Bucharest 0Neamt 234 Craiova 160 Oradea 380 Drobeta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea193 Fagaras 176 Sibiu 253 Giurgiu 77 Timisoara 329 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374 Hirsova 151 Urziceni 80 AradSibiuTimissoaraZerindFagarasAradOradeaRimnicu VilceaSibiuBucharest

2533293743663661763801932630LOGOBusca GulosaIr de Iasi para Fagaras?

LOGOA*Estratgia: Combina o custo do caminho g(n) com o valor da heurstica h(n)g(n) = custo do caminho do n inicial at o n nh(n) = valor da heurstica do n n at um n objetivo (distancia em linha reta no caso de distancias espaciais)f(n) = g(n) + h(n)

a tcnica de busca mais utilizada.

LOGOA*Arad 366 Mehadia 241 Bucharest 0Neamt 234 Craiova 160 Oradea 380 Drobeta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea193 Fagaras 176 Sibiu 253 Giurgiu 77 Timisoara 329 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374 Hirsova 151 Urziceni 80 AradSibiuTimissoaraZerindFagarasAradOradeaRimnicu VilceaSibiuBucharest

CraiovaPitestiSibiuRimnicu VilceaBucharestCraiova0+366=366140+253=393118+329=44775+374=449280+366=646239+176=415291+380=671220+193=413338+253=591450+0=450366+160=526317+100=417300+253=553418+0=418455+160=615414+193=607LOGOA*A estratgia completa e tima.

Custo de tempo:Exponencial com o comprimento da soluo, porm boas funes heursticas diminuem significativamente esse custo.

Custo memria: Guarda todos os ns expandidos na memria.

Nenhum outro algoritmo timo garante expandir menos ns.

LOGODefinindo HeursticasCada problema exige uma funo heurstica diferente.

No se deve superestimar o custo real da soluo.

Como escolher uma boa funo heurstica para o jogo 8-Puzzle?

LOGODefinindo HeursticasComo escolher uma boa funo heurstica para o jogo 8-Puzzle?

h = nmero de elementos fora do lugar.

h = soma das distncias de cada nmero sua posio final (movimentao horizontal e vertical).

Qual das heursticas melhor?

LOGOExemplo - A*123451X234LOGOExemplo - A*Qual o espao de estados?

Quais so as aes possveis?

Qual ser o custo das aes?LOGOExemplo - A*Heurstica do A*: f(n) = g(n) + h(n)g(n) = custo do caminhoh(n) = funo heurstica

Qual seria a funo heurstica h(n) mais adequada para este problema?

A distancia em linha reta uma opo.LOGOExemplo - A*Como calcular a heurstica h(n)?

Distancia de Manhattan

LOGOExemplo - A*O prximo passo gerar a rvore de busca e expandir os ns que tiverem o menor valor resultante da funo heurstica f(n).

f(n) = g(n) + h(n)LOGOExemplo - A*[1,1][1,2][2,1][1,2] = f(n) = ?? + ??[2,1] = f(n) = ?? + ??

LOGOExemplo - A*123451X234LOGOExemplo - A*[1,1][1,2][2,1][1,1] = f(n) = ?? + ??[2,2] = f(n) = ?? + ??

[1,1][2,2]LOGOExemplo - A*123451X234LOGOBusca LocalEm muitos problemas o caminho para a soluo irrelevante.

Jogo das n-rainhas: o que importa a configurao final e no a ordem em que as rainhas foram acrescentadas.

Outros exemplos:Projeto de Circuitos eletronicos;Layout de instalaes industriais;Escalonamento de salas de aula;Otimizao de redes;LOGOBusca LocalAlgoritmos de busca local operam sobre um unico estado corrente, ao invs de vrios caminhos.

Em geral se movem apenas para os vizinhos desse estado.

O caminho seguido pelo algoritmo no guardado.LOGOBusca LocalVantagens:Ocupam pouqussima memria (normalmente constante).Podem encontrar solues razoveis em grandes ou infinitos espaos de estados.

So uteis para resolver problemas de otimizao.Buscam por estados que atendam a uma funo objetivo.LOGOBusca LocalPanorama do Espao de Estados:

Location = Estado;

Elevation = Valor de custo da funo heurstica;

Busca-se o maximo ou minimo global;LOGOSubida de Encosta (Hill-Climbing)Estratgia:Se move de forma contnua no sentido do valor crescente da heurstica;

Termina ao alcanar um pico em que nenhum vizinho possui um valor mais alto;

No mantm nenhuma rvore de busca, somente o estado e o valor da funo objetivo;

No examina antecipadamente valores de estados alm de seus vizinhos imediatos;

como tentar encontrar o topo do monte Everest em meio a um denso nevoeiro e sofrendo de amnsia.LOGOSubida de Encosta (Hill-Climbing)Processo:

Inicialize (aleatoriamente) o ponto x no espao de estados do problema.

A cada iterao, um novo ponto x selecionado aplicando-se uma pequena perturbao no ponto atual, ou seja, selecionando-se um ponto x que esteja na vizinhana de x.

Se este novo ponto apresenta um melhor valor para a funo de avaliao, ento o novo ponto torna-se o ponto atual.

O mtodo terminado quando nenhuma melhora significativa alcanada, um nmero fixo de iteraes foi efetuado, ou um objetivo foi atingido.LOGOPseudocdigo Hill-ClimbingFuno Hill-Climbing(Problema) retorna um estado que o maximo localInicio EstadoAtual FazN(Problema[EstadoInicial]) loop do Vizinho SucessorDeMaiorValor(EstadoAtual) se Vizinho[Valor] for menor ou igual EstadoAtual[Valor] ento retorna EstadoAtual EstadoAtual VizinhoFim

LOGOSubida de Encosta (Hill-Climbing)Problemas:Mximos Locais:

LOGOSubida de Encosta - ExemploAes Possveis:Pegar um bloco e colocar ele sobre a mesa.Pegar um bloco e colocar ele sobre outro bloco.

Heurstica:+1 para cada bloco em cima do bloco onde ele deve estar.-1 para cada bloco em cima do bloco errado.

LOGOSubida de Encosta - Exemplo

Mximo LocalLOGOSubida de Encosta (Hill-Climbing)Problemas:Plancies:

LOGOSubida de Encosta (Hill-Climbing)Problemas:Encostas e Picos:

LOGOSubida de Encosta (Hill-Climbing)No timo e no completo.

Variaes:Random-Restart Hill-Climbing;LOGO