Prévia do material em texto
DECSI - UFOP, CSI 457 Notas de Aula Busca Inteligência Arti�cial Prof. Dr. Talles Henrique de Medeiros Talles Medeiros 2020/1 Contents Contents 1 Busca 3 1.1 Formulando o Problema de Busca . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Exemplos de Problemas de Busca . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Exemplo de viagem por Romênia . . . . . . . . . . . . . . . . . . . . . 4 1.2.2 Exemplo de Quebra Cabeça de 8 Peças . . . . . . . . . . . . . . . . . . 5 1.3 O que é um Espaço de Estados? . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 Grafo de Espaço de Estados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Árvores de Busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5.1 Procurando numa Árvore de Busca . . . . . . . . . . . . . . . . . . . . 8 1.6 A Busca em Profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6.1 As Propriedades da Busca em Profundidade . . . . . . . . . . . . . . . 10 1.7 A Busca em Largura (ou Amplitude) . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7.1 As Propriedades da Busca em Largura . . . . . . . . . . . . . . . . . . 11 1.8 Busca em Profundidade Limitada . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9 Busca de Custo Uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.9.1 As Propriedades da Busca de Custo Uniforme . . . . . . . . . . . . . . 14 1.10 Busca Bidirecional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.11 Busca de Aprofundamento Iterativo . . . . . . . . . . . . . . . . . . . . . . . . 15 1.12 Comparação entre as Estratégias de Busca . . . . . . . . . . . . . . . . . . . . 16 1.13 Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.14 Notas Bibliográ�cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.15 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2 1 Busca 1 Busca Os agentes inteligentes devem maximizar a sua medida de desempenho. Adotar um objetivo a ser satisfeito ajudam a organizar o comportamento, restringindo as ações que ele precisa considerar. A formulação de objetivos, baseada no estado atual e na medida de desempenho é o primeiro passo para a resolução do problema. A formulação do problema corresponde ao processo de decidir que ações e estados devem ser considerados. Para isso é preciso ter informação sobre o ambiente para que o agente saiba quais as melhores ações possíveis é a melhor. Veremos alguns algoritmos de buscam sem informação, que embora possam resolver qualquer problema solucionável, nenhum deles pode fazê-lo de forma e�ciente. Já os algoritmos de busca informada podem ter sucesso a partir de alguma orientação sobre a busca por uma solução. Os problemas são formulados por descrições matemáticas abstratas, que dão uma descrição simpli�cada do mundo real. O processo de remover detalhes do problema real é dito abstração. A habilidade de darmos um nível de abstração adequado o mundo real, permite-nos tratar problemas de grande complexidade a ponto de conseguirmos encontrar soluções para nossos modelos. O processo de procura por uma sequência de ações que alcançam o objetivo é chamado de busca. Um algoritmo de busca recebe uma formulação de um problema como entrada e retorna uma solução na forma de uma sequência de ações. 1.1 Formulando o Problema de Busca Um problema de busca consiste de um espaço de busca, contemplando a representação dos possíveis estados do problema. Uma função sucessora (com ações e custos), indicando os estados resultantes após uma ação. Um estado inicial e um estado alvo. Formalmente podemos de�nir os componentes do problema: • Estado Inicial: O estado inicial que o agente começa o problema. • Ações: Uma descrição das ações disponíveis para o agente em um dado estado particular B . Uma rotina AÇÕES(B) devolve um conjunto de ações que podem ser executadas em B . • Modelo de Transição: Uma rotina RESULTADO(B, 0) devolve o estado que resulta exe- cutar uma ação 0 em um estado B . • Teste de Objetivo: Determina se um estado é um estado objetivo. Às vezes o teste é um estado explícito, que precisa ser veri�cado. Outras vezes é um estado implícito, como 3 1 Busca Figure 1.1: Problemas de Busca envolvem planejamento de ações a serem executadas para se atingir um objetivo, de forma a maximizar o desempenho do agente. o “xeque-mate” no xadrez, que veri�ca se nesse estado o rei está em uma condição de ataque e não consegue escapar. • Custo de Caminho: Uma função que atribui um custo ao caminho. A função de custo deve re�etir a própria medida de desempenho. O custo do passo para executar uma ação 0 sobre o estado B e alcançar o estado B ′ é de�nido como 2 (B, 0, B ′) A solução é uma sequência de ações que transformam o estado inicial para o estado objetivo. A solução ótima tem o menor custo de caminho entre todas as soluções. 1.2 Exemplos de Problemas de Busca 1.2.1 Exemplo de viagem por Romênia • Estados: O estado é dado pela cidade em que se encontra no momento. • Estado Inicial: A cidade de origem da viagem. • Ações: Viajar de uma cidade para outra vizinha. • Modelo de Transição: As ações levem o viajante de uma cidade à outra por meio de uma ação. • Teste de Objetivo: Veri�car se o estado é a cidade de destino. • Custo de Caminho: Cada passo tem o custo referente à distância física da estrada entre as cidades vizinhas. Logo o custo do caminho é a soma dos custos dos passos de cada ação executada até o estado atual. 4 1 Busca Figure 1.2: Agente planejando ação. Figure 1.3: Problemas de Busca são representados por modelos (abstrações) do mundo real, onde alguns detalhes são removidos dessa representação. 1.2.2 Exemplo de �ebra Cabeça de 8 Peças Este exemplo consiste em um tabuleiro 3x3 de 8 peças numeradas e um quadrado vazio. A peça adjacente ao quadrado vazio pode ser deslizada para esse espaço. A formulação pode ser dada por: • Estados: Uma descrição de estado especí�ca uma con�guração do tabuleiro com a posição de cada peça. • Estado Inicial: Uma con�guração do tabuleiro qualquer. • Ações: Mover o espaço vazio para cima, para baixo, para esquerda e para direita. Algumas ações podem estar restritas dependendo de onde o espaço vazio estiver localizado. • Modelo de Transição: Dado um estado e uma ação, ele devolve o estado resultante, ou seja, a troca das peças envolvidas na ação. • Teste de Objetivo: Veri�ca se as peças estão todas nas posições desejadas para o estado objetivo. • Custo de Caminho: Cada passo tem custo unitário. O custo do caminho é o número de passos do caminho. 5 1 Busca Figure 1.4: Viajando pela Romênia usando uma mapa com cidades e estradas que ligam estas cidades. Figure 1.5: Um exemplo típico de um quebra cabeça de 8 peças com seu estado inicial e um estado objetivo. Este quebra-cabeça de blocos deslizantes de 8 peças possui 9!/2 = 181.440 estados acessíveis. O quebra-cabeça de 15 peças (4x4) possui 15!/2 = 1.307.674.368.000 estados, que podem ser resolvidos facilmente por algum algoritmo de busca. Porém um quebra-cabeça de 25 peças (5x5) tem cerca de 25!/2 = 1025 estados e já demandam muitas horas para serem resolvidos. 1.3 O que é um Espaço de Estados? O estado do mundo inclui cada detalhe do ambiente. Em geral representado por estruturas, onde cada componente denota um atributo do estado representado. 6 1 Busca Figure 1.6: O ambiente do Pacman com vários pontos de comida, alguns fantasmas e as possibil- idades de locais que o agente pode se mover por todo o ambiente. 1.1: ESPAÇO DE ESTADOS Um espaço de estados pega somente os detalhes necessários para o planejamento (ab- stração). • Problema: Pacman deve comer todos os pontos. – Estados: {.(x,y), pontos booleanos }. 7 1 Busca – Ações: mover para cima, baixo, esquerda e direita. – Sucessor (Modelo de Transição): atualiza localização e possibilidades de pontos booleanos. – Teste de objetivo:pontos todos em FALSE. Como exemplo, veja um cenário de um jogo de Pacman com as seguintes con�gurações: • Posições do Agente: 120. • Contagem de Comidas (pontos): 30 • Posições do Fantasma: 12 • Ação do Agente: mover-se para cima, baixo, esquerda e direita. O resultado é um número total de estados de�nido por: 120- (230)- (122)-4. O número de estados por caminhamento: 120. O número de estados para todas comidas (pontos): 120- (230). 1.4 Grafo de Espaço de Estados O grafo do espaço de estados é uma representação matemática do problema de busca onde os nós são representações (abstrações) do mundo. Os ARCOS representam as funções sucessoras (ações) que implementam a transição entre os estados. O TESTE DE OBJETIVO é uma con�guração dos nós objetivo, podendo ser somente um estado. No grafo do espaço de estados, cada estado só ocorre uma única vez! Raramente podemos construir este grafo completo na memória, pois é muito grande. Porém é uma ideia útil! 1.5 Árvores de Busca Uma árvore de busca é uma estrutura do tipo ”Se-Então-Senão” com planos e suas respostas. O estado inicial é o nó raiz. Os nós �lhos são os estados sucessores. Os nós exibem os estados, mas correspondem a planos que alcançam esses estados. Para a grande maioria dos problemas de busca, não podemos nunca construir a árvores de busca completa. 1.5.1 Procurando numa Árvore de Busca O procedimento de busca em uma árvore parte da expansão de nós com seus potenciais planos de ação. A �gura 1.8 apresenta 3 nós como possíveis ações a serem executadas. O gerenciamento de uma lista de nós expansíveis (”borda” ) é responsável manter os planos de ação parciais em consideração. Tenta-se expandir o menor número possível de nós quanto for possível. 8 1 Busca Figure 1.7: Grafo de Estados para um ambiente do Pacman, exibindo os estados e seus sucessores conectados por meio de arcos indicativos das transições após uma ação. Figure 1.8: Procurando uma solução na árvore de busca representativa do problema do mapa da Romênia. O algoritmo básico de busca deve ser executado usando uma estratégia própria para visitação de nós até encontrar uma solução ou falhar, partindo de um nó inicial. 1.2: BUSCA GERAL EM ÁRVORE Importantes ideias para este algoritmo básico: • Lista de Nós de Borda • Expansão • Estratégia de Expansão 9 1 Busca Figure 1.9: Algoritmo Geral de Busca em Árvore, recebendo a estrutura do problema formulado e o tipo de estratégia de busca e retornando uma solução ou falha. 1.6 A Busca em Profundidade A estratégia de busca em profundidade, do inglês (Deep First Search - DFS), é baseada na expansão dos nós mais profundos da árvore. Para isso a borda é gerenciada como uma estrutura do tipo LIFO (Last in - First out). A busca prossegue até o nó mais profundo da árvore, onde não há mais sucessores. Figure 1.10: Grafo com Nós para Visitação, sendo S o nó inicial e G o nó objetivo. 1.6.1 As Propriedades da Busca em Profundidade • Completa: Garantia de encontrar uma solução se existe. • Ótima: Garantia de encontrar o caminho de custo mínimo. • Complexidade de Tempo: • Complexidade de Espaço: • Grá�co da Busca na Árvore – 1 é o fator de rami�cação – < é a profundidade máxima – soluções em várias profundidades • Número de nós em toda a árvore: 1 + 1 + 12 + · + 1< = $ (1<) 10 1 Busca Figure 1.11: Grá�co da exploração em profundidade de uma árvore de busca. A �gura 1.11 mostra que a exploração dos nós da árvores durante a busca em profundidade começa pelo nós mais à esquerda e vai aprofundando até não encontrar mais um sucessor. Só então os próximos caminhos serão analisados pelo algoritmo. • Quais nós expandir? – A partir do lado esquerdo na árvore – Poderia processar a árvore completa – Se< é �nito, leva um tempo $ (1<) • Quanto espaço a borda ocupa? Somente possui nós irmãos no caminho para a rais, então ocupa $ (1<). • É Completa? A profundidade< poderia ser in�nita, então é completa se prevenirmos os ciclos. • É Ótima? A busca não é ótima, ela encontra a solução mais à esquerda, independente- mente da profundidade ou do custo. 1.7 A Busca em Largura (ou Amplitude) A estratégia de busca em largura, do inglês Breadth First Search - BFS, é baseada na estratégia de expansão do nó mais raso primeiro, de modo a analisar toda uma camada para somente depois fazer a expansão dos nós da camada seguinte. A implementação dessa estratégia adota uma estrutura do tipo FIFO (First-in First-out) para a Borda. Usando o mesmo grafo da �gura 1.10 é possível representar visualmente a ordem de visitação do procedimento de busca na �gura 1.13. 1.7.1 As Propriedades da Busca em Largura • Quais nós expandir? 11 1 Busca Figure 1.12: A árvore tem destacado em vermelho os caminhos que foram visitados pelo agentes na busca do nó objetivo G. Como esperado, usando a busca em profundidade de�ne um lado da árvore e explora até não encontrar mais sucessores à partir do primeiro nó visitado à partir do início. Figure 1.13: Visualizando o processo de visitação dos nós em uma busca em largura, percorrendo todo um nível da árvore para somente depois visitar o nível inferior. – Processa todos os nós acima da solução mais rasa – Seja a profundidade de solução mais rasa, B – A busca consome um tempo $ (1B) • Quanto espaço a lista de expansíveis ocupa? Aproximadamente até a camada da solução da rasa, então $ (1B). • É Completa? Sim, se a camada B for �nita. • É Ótima? A busca é ótima se e somente se os custos forem todos iguais. 1.8 Busca em Profundidade Limitada A busca em profundidade limitada insere um limitador ; para que a busca não se perca em espaço de estados in�nitos, de forma que o método trata os estados sucessores da profundidade ; como 12 1 Busca Figure 1.14: A busca em largura analisa toda uma camada para depois ir para a camada imedi- atamente abaixo. Encontrando uma solução na camada menos profunda da árvore de busca. inexistentes. Isso resolve o problema de busca in�nita, porém introduz uma incompleteza na busca quando ; < 3 , ou seja, a profundidade da solução mais rasa é maior que o limite de�nido. Na prática, infelizmente, nem sempre conhecemos um bom limite de profundidade antes de resolvermos o problema. A busca pode ser �nalizada por duas condições: falha indicando nenhuma solução; corte indicando nenhuma solução dentro do limite de profundidade. 1.9 Busca de Custo Uniforme A busca de Custo Uniforme, do inglês (Uniform Cost Search - UCS), é baseada em uma estratégia de expansão de nós por meio do custo do próximo nó a ser visitado, optando pelo nó de menor custo. A lista de caminhos expansíveis é uma lista com prioridade de custo cumulativa. Figure 1.15: Exemplo de um grafo com custos para a transição entre os estados. Estes custos permitiram ao algoritmo adotar uma estratégia que custo do caminho até o momento para decidir qual caminho expandir. Os métodos de busca em profundidade e largura encontram um caminho em termo de número 13 1 Busca de ações, mas não o caminho de custo mínimo. O método de custo uniforme é um método similar aos anteriores, mas que encontra o caminho de custo mínimo. Figure 1.16: Contorno com os custos acumulados dos caminhos já analisados pelo método. 1.9.1 As Propriedades da Busca de Custo Uniforme • Quais nós expandir? – Processa todos os nós com custo inferior à solução de custo mínimo. – Se a solução custa�∗ e os arcos custam pelo menos n , então a ”profundidade efetiva” é aproximadamente �∗ n . – Consome um tempo $ (1 (�∗/n) ) • Quanto espaço a lista de expansíveis ocupa? Aproximadamente até a camada da solução, então $ (1 (�∗/n) ). • É Completa? Assumindo que a melhor solução tem um custo �nito e um arco de custo mínimo positivo, então ela é completa. • É Ótima? Sim! Figure 1.17: Propriedades da busca de custo mínimo ser completa e ótima. 14 1 Busca A busca de Custo Uniforme explora os contornos de custo crescente, podendo ser uma busca completa e ótima. O lado negativo é que a busca explora opções em cada direção. Nenhuma informaçãosobre a localização do objetivo é usada. 1.10 Busca Bidirecional A ideia desta busca é executar duas buscas simultâneas, sendo uma a partir do estado inicial e outra a partir do estado objetivo, esperando que as duas buscam se encontrem no meio do caminho. A motivação é que a complexidade de tempo 13/2 +13/2 é menor que 13 . Por exemplo, sendo 1 = 2 e 3 = 6, tem-se: 13/2 + 13/2 < 13 26/2 + 26/2 < 26 8 + 8 < 32 (1.1) A implementação desta estratégia de busca substituto teste de objetivo por uma veri�cação das bordas das duas buscas, que cruzando-se, indica que uma solução foi encontrada. A redução da complexidade de tempo da busca bidirecional é bastante atraente, mas a realização da busca inversa nem sempre é algo trivial. Quando o estado objetivo é um estado explicitamente citado há opção de mapear a busca para obter os estados predecessores a partir do objetivo explicitamente citado. Porém há casos em que o estado objetivo é uma condição mais abstrata, sem uma con�guração explicitamente de�nida. Neste caso, a busca bidirecional é mais complexa de ser usada. 1.11 Busca de Aprofundamento Iterativo Um estratégia usada com frequência em combinação com a busca em profundidade em árvore, encontrando o melhor limite de profundidade. Do inglês, Iterative Deepening Search - IDS, o limite é gradualmente incrementado até encontrar o objetivo, no limite 3 que contém a solução. Basicamente, a busca de aprofundamento iterativo executa a estratégia em profundidade limitada várias vezes, com os limites crescentes. Apesar de parecer um desperdício gerar os estados várias vezes, a grande maioria dos nós estará sempre no nível mais profundo, se a árvore tiver o mesmo (ou quase igual) fator de rami�cação. Pode-se, então, determinar o número de nós gerados por: # (��() = 31 + (3 − 1)12 + (3 − 2)13 + · + (1)13 = $ (13 ). (1.2) Esta complexidade é exatamente a mesma da busca em profundidade. O exemplo a seguir mostra a diferença no número de estados gerados, porém assintoticamente, a tendência é que o custo extra gerado pelo IDS seja baixo para árvores cada vez maiores. Se 1 = 10 e 3 = 5, então: 15 1 Busca # (��() = 50 + 400 + 3000 + 20000 + 100000 = 123450 # (��() = 10 + 100 + 1000 + 10000 + 100000 = 111100 (1.3) 1.12 Comparação entre as Estratégias de Busca Os quatro critérios de�nidos para avaliação das estratégias de busca em árvore permitem uma comparação. Figure 1.18: A tabela permite que sejam comparadas as estratégias de busca quando avaliadas as condições descritas em cada sessão descritiva da estratégia. As anotações sobrescritas são: 0 completa se b é �nito; 1 completa se o custo do passo é ≥∈ para ∈ positivo; 2 ótima se os custos dos passos são todos idênticos; 3 se ambos os sentidos utilizam busca em largura. 1.13 Resumo • Todos esses algoritmos são os mesmos exceto pela estratégia de expansão da lista de caminhos expansíveis. – Conceitualmente, todas as listas são �las de prioridades (coleções de nós com priori- dades anexadas). – Praticamente, para busca em profundidade e largura, pode-se evitar a sobrecarga log= de uma �la de prioridade real, usando pilhas e �las. – Pode até codi�car uma implementação que usa um objeto de en�leiramento variável. • As buscas operam sobre modelos do mundo – O agente não testa todos os planos do mundo real! – O planejamento é TUDO em uma simulação. – Sua busca é somente tão boa quanto o seu modelo! 16 1 Busca Figure 1.19: Um modelo é uma abstração da realidade. Nele temos somente parte do que nos interessa e/ou somos capazes de controlar. Logo, seu modelo será sempre uma representação limitada do problema real. 1.14 Notas Bibliográficas Consulte o livro "Inteligência Arti�cial" de Stuart Russel e Peter Norvig, capítulo 03 (até 3.4 inclusive) para complementar sua leitura desta nota de aula. Pois ela foi baseada nesse capítulo. 1.15 Exercícios 1. Desenhe um grafo representado o espaço de estados do mundo do robô aspirador de pó, contendo 3 salas linha [A - B - C]. Nesse grafo cada nó é um estado do mundo e cada arco será uma transição entre dois estados. Os arcos devem ser direcionados. Considere que cada estado é representado por uma estrutura na forma [-,., /,, ], onde - ∈ �, �,� indica a sala do robô, . ∈ 0, 1 indica se a sala está suja, / ∈ 0, 1 indica se a sala está suja e , ∈ 0, 1 indica se a sala está suja. 2. O problema dos Jarros consiste em 2 jarros com capacidades de 3 e 4L, respectivamente. Nenhum dos jarros contém qualquer medida ou escala, de modo que só se pode saber o conteúdo exato quando eles estão cheios. Sabendo que podemos encher ou esvaziar um jarro, bem como transferir a água de um jarro para outro, determine uma sequência de passos que deixe o jarro de 4L com exatamente 2L. OBS.: Represente os estados desse problema com um par [-,. ], onde - ∈ 0, 1, 2, 3 representa o conteúdo do jarro 1 e . ∈ 0, 1, 2, 3, 4 representa o conteúdo do jarro 2. O estado inicial é B> = [0, 0] e o objetivo é � = [,2]. 3. O problema do fazendeiro consiste no seguinte enunciado: um fazendeiro encontra-se na margem esquerda de um rio, levando consigo um lobo, um repolho e uma ovelha. O fazendeiro precisa chegar até a outra margem do rio com toda sua carga intacta. Para isso ele possui um barco com capacidade para levar ele e mais uma carga junto. O problema é que nunca podem ser deixados à sós o lobo e a ovelha, e a ovelha e o repolho em nenhuma das margens. Determine uma sequência de passo para resolver este problema. 17 Busca Formulando o Problema de Busca Exemplos de Problemas de Busca Exemplo de viagem por Romênia Exemplo de Quebra Cabeça de 8 Peças O que é um Espaço de Estados? Grafo de Espaço de Estados Árvores de Busca Procurando numa Árvore de Busca A Busca em Profundidade As Propriedades da Busca em Profundidade A Busca em Largura (ou Amplitude) As Propriedades da Busca em Largura Busca em Profundidade Limitada Busca de Custo Uniforme As Propriedades da Busca de Custo Uniforme Busca Bidirecional Busca de Aprofundamento Iterativo Comparação entre as Estratégias de Busca Resumo Notas Bibliográficas Exercícios