Resolução de Problemas por meio de Busca

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resolução de problemas por meio de busca
Prof. Pedro Luiz Santos Serra
Agentes de resolução de problemas
Agente: É um elemento qualquer capaz de perceber seu ambiente por meio de sensores e de agir sobre este ambiente por intermédio de atuadores.
Agentes de resolução de problemas: Tratam-se de agentes com poder de decisão, ou seja, decidem o que fazer quando encontra seqüência de ações que levam a estados desejáveis.
Devem maximizar sua medida de desempenho.
Formulação de objetivos: é o primeiro passo para a resolução de problemas. Baseada na situação atual e na medida de desempenho do agente.
Prof. Pedro Luiz Santos Serra
2
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
Vera 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.
Prof. Pedro Luiz Santos Serra
3
Agentes de resolução de problemas
Prof. Pedro Luiz Santos Serra
4
Agentes de resolução de problemas
Objetivo: É um conjunto de estados do mundo.
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: É o processo de procura pela melhor seqüência em função das diversas opções existentes de ações possíveis que levam a estados de valor conhecido.
Prof. Pedro Luiz Santos Serra
5
Agentes de resolução de problemas
Prof. Pedro Luiz Santos Serra
6
Um algoritmo de busca recebe um problema como entrada e retorna uma solução sob a forma de uma seqüência de ações.
As ações recomendadas podem ser executadas (fase de execução).
Forma-se então o ciclo: 
Formular – Buscar – Executar
Agentes de resolução de problemas
Prof. Pedro Luiz Santos Serra
7
função AGENTE DE RESOLUÇÃO DE PROBLEMAS – SIMPLES		(percepção) retorna uma ação				
entradas: 		percepção, uma percepção			
variáveis estáticas: seq, uma seqüência de ações, inicialmente vazia
		estado, alguma descrição do estado atual do mundo
objetivo, um objetivo, inicialmente nulo		
problema, uma formulação do problema		
Agentes de resolução de problemas
Prof. Pedro Luiz Santos Serra
8
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 seqüências de ações únicas. Isto impossibilita a ocorrência de ações inesperadas. Na teoria de controle, denomina-se sistemas similares como laço de repetição aberto ou sistema de malha aberta.
Prof. Pedro Luiz Santos Serra
9
Problemas e soluções bem definidos
Quatro elementos podem definir um problema:
Estado inicial: Trata-se do estado em que o agente começa. 
Por ex.: Em(Arad)
Uma descrição das ações possíveis que 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:
	{<Ir(Sibiu), Em(Sibiu)>,<Ir(Timisoara),Em(Timisoara)>,<Ir(Zerind),Em(Zerind)>}
Prof. Pedro Luiz Santos Serra
10
Agentes de resolução de problemas
Prof. Pedro Luiz Santos Serra
11
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 seqüência de estados conectados por uma seqüência de ações.
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.
Prof. Pedro Luiz Santos Serra
12
Problemas e soluções bem definidos
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.
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.
Prof. Pedro Luiz Santos Serra
13
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.
Prof. Pedro Luiz Santos Serra
14
Exemplos de Problemas - Miniproblemas
Miniproblemas: destina-se a ilustrar ou exercitar diversos métodos de resolução de problemas.
Aspirador de Pó:
Estados: O agente está em uma entre duas posições (Esquerda ou Direita), cada uma das quais pode conter sujeira ou não. 
Estado Inicial: Qualquer estado pode ser designado como o estado inicial.
Função Sucessor: Gera os estados válidos que resultam da tentativa de executar as três ações (Esquerda, Direita e Aspirar).
Teste de Objetivo: Verifica se todos os quadrados estão limpos.
Custo de Caminho: Cada passo custa 1, e assim o custo do caminho é o número de passos do caminho.
Prof. Pedro Luiz Santos Serra
15
Exemplos de Problemas
Prof. Pedro Luiz Santos Serra
16
O mini-problema do Aspirador de Pó: Espaço de Estados
Exemplos de Problemas
Quebra-cabeças de 8 peças (blocos deslizantes):
Prof. Pedro Luiz Santos Serra
17
 Estado inicial Estado objetivo 
Exemplos de Problemas
Quebra-cabeças de 8 peças (blocos deslizantes):
Estados: Especifica a posição de cada uma das oito peças e do espaço vazio em um dos nove quadrados.
Estado inicial: Qualquer estado pode ser designado como o estado inicial.
Função sucessor: Gera os estados válidos que resultam da tentativa de executar as quatro ações (o espaço vazio se desloca para a Esquerda, Direita, Acima ou Abaixo).
Teste de objetivo: Verifica se o estado corresponde à configuração de objetivo.
Custo de caminho: Cada passo custa 1, e assim o custo de caminho é o número de passos do caminho.
Prof. Pedro Luiz Santos Serra
18
Exemplos de Problemas
O quebra-cabeças de 8 peças (blocos deslizantes):
É um problema da classe NP-completos: Trata-se de uma classificação de problemas, em Inteligência Artificial. Problemas denominados NP-completos, são o extremo de uma classe de problemas NP considerados de difícil solução. Tratam-se de problemas cujo tempo de solução de problemas não pode ser atribuido à uma função polinomial (tempo polinomial);
O quebra cabeças de 8 peças tem 9!/2 = 181.440 estados acessíveis e é resolvido com facilidade;
O quebra cabeças de 15 peças (em um tabuleiro de 4 x 4) tem, aproximadamente 1,3 trilhão de estados;
O quebra cabeças de 24 peças tem cerca de 1025 estados e são bastante difíceis de resolver de forma ótima com as máquinas e algorítmos atuais.
Prof. Pedro Luiz Santos Serra
19
Exemplos de
Problemas
Problema de 8 rainhas: Posicionar 8 rainhas em um tabuleiro de xadrez de tal forma que nenhuma rainha ataque outra.
Prof. Pedro Luiz Santos Serra
20
Exemplos de Problemas
Problema de 8 rainhas:
Estados: qualquer disposição de 0 a 8 rainhas no tabuleiro é um estado.
Estado inicial: Nenhuma rainha no tabuleiro.
Função sucessor: Colocar uma rainha em qualquer quadrado vazio.
Teste de objetivo: 8 rainhas estão no tabuleiro e nenhuma é atacada.
NESSA FORMULAÇÃO TEMOS 3 x 1014 SEQÜÊNCIAS POSSÍVEIS PARA INVESTIGAR.
Prof. Pedro Luiz Santos Serra
21
EXEMPLOS DE PROBLEMAS
Problema de 8 rainhas:
UMA FORMULAÇÃO MELHOR SERIA A RESTRIÇÃO DA COLOCAÇÃO DE UMA RAINHA EM QUALQUER QUADRADO QUE JÁ ESTIVESSE SOB ATAQUE:
Estados: Os estados são disposições de n rainhas (0  n  8), uma por coluna nas n colunas mais à esquerda, sem que nenhuma rainha ataque outra.
Função sucessor: Adicione uma rainha a qualquer quadrado na coluna vazia mais à esquerda de tal modo que ela não seja atacada por qualquer outra rainha.
ESSA FORMULAÇÃO REDUZ O ESPAÇO DE ESTADOS PARA 2057, E AS SOLUÇÕES SÃO FÁCEIS DE ENCONTRAR.
Prof. Pedro Luiz Santos Serra
22
Exemplos de Problemas
Problemas do mundo real  Problemas de Roteamento.
Problema de passagem aérea:
Estados: Cada um é apresentado por uma posição (por exemplo: um aeroporto – GRU) e pela hora atual.
Estado inicial: É especificado pelo problema.
Função sucessor: Retorna os estados resultantes de tomar qualquer vôo programado (talvez especificado com mais detalhes pela classe e posição da poltrona) que parte depois da hora atual somada ao tempo de trânsito no aeroporto, desde o aeroporto atual até outro.
Teste de objetivo: Verifica o destino após algum tempo previamente especificado.
Custo de caminho: Depende do custo monetário, do tempo de espera, do tempo de vôo, dos procedimentos alfandegários e de imigração, da qualidade da poltrona, da hora do dia, do tipo de aeronave, dos prêmios por milhagem em vôos freqüentes e assim por diante.
Prof. Pedro Luiz Santos Serra
23
Busca por soluções
Árvore de Busca: 
Gerada pelo estado inicial e pela função sucessor (definem o espaço de estado)
Grafo de busca: 
Também pode ser utilizado ao invés da árvore de busca. Empregado quando o mesmo estado pode ser alcançado a partir de vários caminhos.
Prof. Pedro Luiz Santos Serra
24
Busca de soluções
Prof. Pedro Luiz Santos Serra
25
Raiz da árvore de busca
Nó de busca ou Estado Inicial
A expansão consiste na geração de um novo conjunto de estados. No caso 3 novos estados foram gerados.
Estratégia de Busca
Busca de Soluções
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.
Prof. Pedro Luiz Santos Serra
26
Busca de Soluções
NÓ: Estrutura de dados de anotação usada para representar a árvore de busca;
ESTADO: Corresponde a uma configuração do mundo.
 NÓS estão em caminhos específicos, definidos por ponteiros NÓ-PAI.
 Dois NÓS diferentes podem conter o mesmo estado do mundo, se esse estado for gerado por meio de dois caminhos de busca diferentes.
Prof. Pedro Luiz Santos Serra
27
Busca de Soluções
BORDA: Coleção de nós gerados (ainda não expandidos);
NÓ-FOLHA: São elementos da BORDA. Cada elemento da BORDA é um NÓ-FOLHA.
Supondo que a implementação de nós seja uma fila. As operações sobre uma fila são:
CRIAR-FILA(elemento, ...)  cria uma fila com o(s) elemento(s) dado(s);
VAZIA?(fila)  retorna verdadeiro caso não exista nenhum elemento na fila;
PRIMEIRO(fila)  retorna o primeiro elemento da fila;
REMOVER-PRIMEIRO(fila)  retorna PRIMEIRO(fila) e o remove da fila;
INSERIR(elemento,fila)  insere um elemento na fila e retorna a fila resultante.
INSERIR-TODOS(elementos,fila) insere um conjunto de elementos na fila e retorna a fila resultante.
Prof. Pedro Luiz Santos Serra
28
Busca de Soluções
Algorítmo Geral de Busca em Árvore:
Prof. Pedro Luiz Santos Serra
29
Busca de Soluções
Medição de desempenho de resolução de problemas.
Quatro aspectos são empregados para avaliação do desempenho de um algorítmo:
Completeza: O algorítmo oferece a garantia de encontrar uma solução quando existir?
Otimização: A estratégia encontra a solução ótima?
Complexidade de tempo: Quanto tempo ele leva para encontrar uma solução?
Complexidade de espaço: Quanta memória é necessária para executar a busca?
Prof. Pedro Luiz Santos Serra
30
Busca de Soluções
Em IA a complexidade é expressa em termos de três quantidades:
b Fator de ramificação: número máximo de sucessores de qualque nó;
d  Profundidade do nó-objetivo menos profundo;
m  o comprimento máximo de qualquer caminho no espaço de estados.
Com freqüência o tempo é medido em termos do número de nós gerados durante a busca e o espaço é medido em termos de número de nós armazenados na memória.
Prof. Pedro Luiz Santos Serra
31
Busca de Soluções
Custo de Busca  depende da complexidade de tempo mas também pode incluir um termo para uso da memória;
Custo Total  Combina o custo de busca e o custo de caminho da solução encontrada.
Ex.: Localizar uma rota desde Arad até Bucareste:
Custo de Busca  Período de tempo exigido pela busca;
Custo de Solução  Comprimento total do caminho em quilometros;
Custo Total  Soma do Custo de Busca com o Custo de Solução.
Prof. Pedro Luiz Santos Serra
32