Resolução de problemas por meio de busca (resolucao_de_problemas_por_meio_de_busca.ppt)

Prévia do material em texto

*
*
Resolução de problemas por meio de busca
Jeneffer Ferreira Lázaro
Email:jenefferferreira@gmail.com
CAPÍTULO 3 - Stuart Russel e Peter Norving
*
*
Recapitulando – Agentes Inteligentes
Os agentes reativos baseiam em suas ações através de um mapeamento direto de estados em ações.
Tais agentes não podem operar bem em ambientes para os quais esse mapeamento seria grande demais para armazenar e levaria muito tempo para se aprender. 
*
*
Introdução
Os agentes baseados em objetivos podem ter sucesso, considerando ações futuras e a conveniência de seus resultados.
O agentes de resolução de problemas são agentes baseados em objetivos.
Os agentes de resolução de problemas decidem o que fazer encontrando sequencias de ações que levam a estados desejáveis. 
Devem maximizar sua medida de desempenho.
*
*
Agentes de resolução de problemas
Exemplo: Suponha um agente em férias na cidade de Arad na Romênia. Suas medidas de desempenho são:
Melhorar o bronzeado
Melhorar seu conhecimento no idioma Romeno
Ver as paisagens, apreciar a vida noturna (ver como ela é)
Evitar ressacas, etc.
Suponha ainda que o agente tenha uma passagem aérea não-reembolsável para partir de Bucareste no dia seguinte.
Faz sentido adotar o objetivo de chegar a Bucareste. 
Os demais cursos podem ser rejeitados sem nenhuma consideração adicional.
*
*
*
*
Resolução de Problemas por meio de Busca
O objetivo vai ser representado por um conjunto de estados
Ações fazem o agente mudar de um estado para outro
O agente deve encontrar um conjunto de ações (de preferência o melhor) que o levem do estado inicial ao estado final
*
*
Representação da solução de problemas
Podemos representar a solução de problemas como uma sequencia de estados, que leva de um estado inicial até um estado final, onde cada estado é um estado admissível, isto é, produzido a partir de um estado anterior através de uma ação.
*
*
Formulação de objetivos
Baseada na situação atual e na medida de desempenho do agente. 
Os objetivos ajudam a organizar (direciona) o comportamento, limitando os objetivos que o agente está tentando alcançar.
*
*
Formulação de problemas
É o processo de decidir que ações e estados devem ser considerados, em função de um objetivo. 
Considera-se a possibilidade de se atingir um mesmo objetivo através de caminhos (ações e estados) diferentes.
*
*
Busca solução
Um agente com várias opções imediatas, de valor desconhecido, pode decidir o que fazer primeiro examinando várias sequencias possíveis de ações que levem a estados de valor conhecido, e escolher a melhor.
Um algoritmo de busca recebe um problema como entrada (percepção) e retorna uma solução (ação) sob a forma de uma sequencia de ações. 
Depois que uma solução é encontrada, as ações que ela recomenda podem ser executadas. 
*
*
Tarefas para a resolução de problemas
Passos:
Formulação do OBJETIVO
Nível de detalhe das ações
Formulação do PROBLEMA
Decidir quais ações e estados considerar
Busca
Dada uma sequencias de ações, qual a melhor?
Execução
Formulação  Busca  Execução
*
*
Exemplo: Viagem na Romênia
Estamos em Arad, com uma passagem de volta saindo de Bucarest
O objetivo é chegar em Bucarest
Estados (Formulação do problema)
Conjunto de cidades
Ações
Dirigir de uma cidade para outra
Solução
Sequencia de cidades
*
*
Estrutura básica de um agente resolvedor de problemas
*
*
Agentes de resolução de problemas
Agentes de Resolução de problemas ← Agentes de ambiente
Ambiente é estático: não ocorrem mudanças no ambiente durante o processo de formulação e resolução do problema
Ambiente é observável: o estado inicial é conhecido
Ambiente é discreto: os cursos alternativos de ação podem ser enumerados
Ambiente determinístico: As soluções para os problemas são sequencias de ações únicas. Isto impossibilita a ocorrência de ações inesperadas. 
*
*
Problemas e soluções bem definidos
Um problema pode ser definido formalmente por quatro componentes:
Estado inicial: é o estado inicial dado. Por exemplo: Em(Arad)
• Uma descrição das ações possíveis estão disponíveis para o agente. A formulação mais comum utiliza uma função sucessor.
Dado um estado particular x, SUCESSOR(x) retorna um conjunto de pares ordenados <ação, sucessor>, em que cada ação é uma ação válida no estado x e cada sucessor é um estado que pode ser alcançado a partir de x aplicando-se a ação. 
• Ex.: Em(Arad) a função sucessor retornaria:
*
*
Exemplo: viajar pela Romênia
*
*
*
Problemas e soluções bem definidos
Espaço de Estados: É a conjunção do estado inicial e a função sucessor do problema. 
Trata-se do conjunto de todos os estados acessíveis a partir do estado inicial. 
Forma um grafo em que os nós são estados e os arcos entre os nós são ações.
Caminho: Trata-se de uma sequencia de estados conectados por uma sequencia de ações.
*
*
Problemas e soluções bem definidos
Teste de Objetivo: é um teste que determina se um dado estado é um estado objetivo.
É possível a existência de um conjunto de estados objetivos possíveis e o teste simplesmente verifica se o estado dado é um deles.
Custo de caminho: é uma função que atribui um custo (valor) numérico a cada caminho.
O agente de resolução de problemas escolhe uma função de custo que reflete sua própria medida de desempenho. 
No exemplo do agente de Arad, o tempo é essencial e, portanto, considera-se o caminho mais rápido aquele com a menor distância percorrida.
*
*
Problemas e soluções bem definidos
Custo de passo: é o custo por se adotar a ação a para ir do estado x ao estado y, ou seja, denota-se c(x,a,y).
Para o caso do agente que se desloca de Arad à Bucareste, trata-se das distância das rotas entre os diversos municípios interligados entre as duas cidades.
*
*
Problemas e soluções bem definidos
Solução Ótima
Uma solução para um dado problema é um caminho desde o estado inicial até o estado objetivo.
A qualidade da solução é medida pela função de custo de caminho.
Uma solução é considerada ótima quando apresenta o menor custo de caminho entre todas soluções.
*
*
Exemplo: Viagem na Romênia
Estados
Conjunto de cidades
Estado Inicial
Arad
Ações (Função Sucessor)
Dirigir de uma cidade para outra
Teste do Objetivo
Estar em Bucareste
Custo
Distância entre as cidades
*
*
Exemplo: Aspirador de Pó
Estados:
o agente pode estar em 1 de 2 locais possíveis, que podem estar sujos ou limpos (8 estados)
Estado inicial:
qualquer um
Sequencia de ações 
 (Função Sucessor)
esq, dir, aspira
Teste de objetivo:
todos os locais limpos
Custo:
cada ação tem custo 1
*
*
Exemplo: 8-Puzzle
Estados
Posição de cada uma das peças e do espaço no tabuleiro
Estado Inicial
Qualquer um
Ações (Função Sucessor)
Cima, Baixo, Dir, Esq
Teste do objetivo
Checar se a configuração foi atingida
Custo
Cada ação tem custo 1
*
*
Problemas do mundo real
Problema de roteamento
Encontrar a melhor rota de um ponto a outro (aplicações: redes de computadores, planejamento militar, planejamento de viagens aéreas)
Problemas de tour
Visitar cada ponto pelo menos uma vez
Caixeiro viajante
Visitar cada cidade exatamente uma vez
Encontrar o caminho mais curto
*
*
Problemas do mundo real
Projeto de proteínas
Encontrar uma sequência de aminoácidos que serão incorporados em uma proteína tridimensional para curar alguma doença.
Pesquisas na Web
É fácil pensar na Web como um grafo de nós conectados por links
*
*
Em busca de soluções
Depois de formular alguns problemas, agora precisamos resolvê-los.
É feito por meio de uma busca em todo espaço de estados. 
A arvore de busca é gerada pelo estado inicial e pela função sucessor que, juntos definem o espaço de estados. 
Em geral, podemos ter um grafo de busca em lugar de uma árvore de busca, quando o mesmo estadopode ser alcançado a partir de vários caminhos. 
*
*
Em busca de soluções
A raiz da árvore de busca é um nó de busca correspondente ao estado inicial 
exemplo: Em (arad)
O primeiro passo é testar se esse é um estado objetivo.
*
*
*
*
*
Um nó é uma estrutura de dados com cinco componentes:
Estado: O estado no espaço de estados ao que o nó corresponde;
Nó-pai: O nó na árvore de busca que gerou este nó;
Ação: A ação que foi aplicada ao PAI para gerar o nó;
Custo-do-caminho: O custo, tradicionalmente denotado por g(n), do caminho desde o estado inicial até o nó indicado pelos ponteiros do pai.
Profundidade: O número de passos ao longo do caminho desde o estado inicial.
*
*
Critério de Avaliação das Estratégias de Busca
Completeza: sempre encontra uma solução se esta existir
Otimização: encontra a solução ótima (menor custo)
Complexidade de tempo: tempo gasto para encontrar uma solução
Complexidade de espaço: memória necessária para encontrar uma solução.
*
*
*
*
Critérios de avaliação das estratégias de busca
O fator de ramificação de um nó é o seu número de vizinhos.
As complexidades de tempo e espaço são medidas em termos de:
b : Fator de ramificação máximo da árvore de busca.
d : Profundidade da solução de menor custo.
m : Profundidade máxima do espaço de estados
*
*
Buscas sem informação ou busca cega	
Algoritmos que não recebem nenhuma informação sobre o problema além de sua formulação.
É preciso definir
problema
solução
*
*
Busca Cega
Também conhecida como busca exaustiva.
Não sabe qual o melhor nó na fronteira a ser expandido, isto é, não conhece o menor custo de caminho desse nó até um nó final (objetivo)
Estratégias de busca (ordem de expansão dos nós)
Busca em Largura
Busca em Profundidade
Busca em Profundidade Limitada
Busca de Custo Uniforme
Interative Deepening
Busca bidirecional
*
*
Busca Heurística
Estima qual o melhor nó da fronteira a ser expandido com base em funções heurísticas => tem conhecimento.
Estratégia de Busca
Best-first search (melhor escolha)
*
*
Busca em Largura (ou extensão) 
O nó raiz é expandido primeiro e, em seguida, todos os sucessores dele, depois todos os sucessores desses nós...
Todos os nós em uma dada profundidade são expandidos antes de todos os nós do nível seguinte.
*
*
Busca em Largura em uma árvore binária
Objetivo: encontrar o nó D
*
*
Busca em Largura: análise
Completa?
Sim, se a largura máxima da árvore (b) for finita
Ótima?
O nó objetivo mais raso não é necessariamente o nó ótimo
Complexidade de Memória
Mantém todos os nos a serem expandidos
*
*
Busca em Largura: análise
Complexidade de tempo e espaço: 
Espaço de estados em que cada estado tem b sucessores (portanto, a uma profundidade n, bn estados são gerados).
Supondo que a solução esteja a uma profundidade d:
 b + b2 + ...+bd + (bd+1 - b) = O(bd+1)
No pior caso a solução está no último nó de d, portanto todos os irmão do objetivo tem seus filhos gerados (daí vem o d+1);
checa o nó, sem checar se filhos (daqui o “-b”).
*
*
Busca em profundidade
Expande o nó mais profundo na borda atual da árvore
Não havendo mais sucessores, a busca retorna à próxima profundidade acima que não foi explorada.
*
*
*
*
*
Busca em profundidade: análise
Só precisa armazenar um único caminho da raiz até um nó folha, e os nós irmãos não expandidos
Nós cujos descendentes já foram completamente explorados podem ser retirados da memória
Ramificação b e profundidade máxima m, a complexidade espacial é: O(bm)
*
*
Busca em profundidade: análise
Pode fazer uma escolha errada e ter que percorrer um caminho muito longo (as vezes infinito), quando uma opção diferente levaria a uma solução rapidamente (ex. nó C na fig. anterior)
Portanto, a busca em profundidade não é completa e nem ótima!
Esta estratégia deve ser evitada quando as árvores geradas são muito profundas ou geram caminhos infinitos (Se pegar um caminho infinito pode não achar a solução por isso não é completa)
Complexidade temporal: no pior caso, todos os nós são gerados, portanto: 
O(bm)
Para problemas com várias soluções, esta estratégia pode ser bem mais rápida do que a busca em largura 
*
*
Busca por aprofundamento iterativo
Combina busca em profundidade com busca em largura
Faz busca em profundidade aumentando gradualmente o limite de profundidade
Método de busca preferido quando se tem espaço de busca grande e profundidade não conhecida
Evita o problema de caminhos muito longos ou infinitos impondo um limite máximo de profundidade para os caminhos gerados.
*
*
Busca por aprofundamento iterativo
Esta estratégia tenta limites com valores crescentes, partido de zero, até encontrar a primeira solução.
Fixa profundidade = i, executa a busca
Se não chegou a um objetivo, recomeça busca com profundidade = i + n (n qualquer)
Piora o tempo de busca, porém melhora o custo de memória
*
*
*
*
Busca por aprofundamento iterativo - Análise
É ótima e completa
Com n = 1 e operadores com custo iguais
Custo de memória
Necessita armazenar apenas b.d nós para um espaço de estados com fator de ramificação b e limite de profundidade d
Custo de tempo
O(bd)
Bons resultados quando o espaço de estados é grande e de profundidade desconhecida
*
*
Como evitar estados repetidos
Um processo de busca pode perder tempo expandindo nós já explorados antes
Estados repetidos podem levar a laços infinitos
Detecção de estados repetidos: comparar os nós prestes a serem expandidos com nós já visitados. Se o nó já tiver sido visitado, será descartado em vez de expandido.
*
*
Como evitar estados repetidos: Soluções
Não retornar ao estado “pai”
Não retornar a um ancestral
Não gerar qualquer estado que já tenha sido criado antes (em qualquer ramo)
*
*
Exercícios 
*
*
Apresente a ordem de visita dos nós da árvore da figura abaixo para cada uma das estratégias (escolha nós mais à esquerda na árvore em todos os casos): 
Objetivo : nó 12
Busca em profundidade
Busca em profundidade iterativa (aumentando o nível de 1 a cada iteração
Busca em largura
*
*
Apresente a ordem de visita dos nós da árvore da figura abaixo para cada uma das estratégias (escolha nós mais à esquerda na árvore em todos os casos): 
Objetivo : nó L
Busca em profundidade
Busca em profundidade iterativa (aumentando o nível de 1 a cada iteração
Busca em largura
*
*
Apresente a ordem de visita dos nós da árvore da figura abaixo para cada uma das estratégias (escolha nós mais à esquerda na árvore em todos os casos): 
Objetivo : nó L
Busca em profundidade
Busca em profundidade iterativa (aumentando o nível de 1 a cada iteração
Busca em largura
*
*
Referencia
Baseado no Cap. 3 do livro de Stuart Russel e Peter Norving - “Inteligência Artificial”, 2a ed.
*
*
*
*
*
*
Sucessor(Em(arad)) ->
 {<Ir(sibiu), Em(sibiu)>, <Ir(timisoara), Em(timisoara)>, <Ir(zerind), Em(zerind)>}
*
*
*
*
*
*
*
*
*
*