Inteligência Artificial Lucas S. Figueiredo Aula 4 Buscas Locais

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

Inteligência Artificial
Lucas Silva Figueiredo
lsf.cin@gmail.com 
Google Classroom 9gfkdd
1
recapitulando
Agentes
Agentes e Ambientes
Nome
Vt
Título 
4
Ambiente da Tarefa (Task Environment)
PEAS: tabela descritiva do agente
Resumo da Classificação
VISIBILIDADE
total
X
parcial
AGENTES
único
X
multi
PREVISIBILIDADE
determinístico
X
estocástico
INTERAÇÃO
episódica
X
sequencial
SINCRONIA
estático
X
dinâmico
PERCEPTS
discreto
X
contínuo
COMPORTAMENTO
conhecido
X
não-conhecido
Nome
Vt
Título 
6
Tipos de Agentes
Reflexivo Simples
Reflexivo Baseado em Modelos
Baseados em Objetivos
Baseados na Utilidade
	
Espaço de Estados
Descrição do conjunto de estados do ambiente dadas todas as possíveis ações do agente em cada estado
Espaço de Estados
Busca em Largura
Ciclos das Etapas
Expandir 
Teste do Objetivo
Marcar
Selecionar
nó da fronteira com grau de parentesco mais próximo da raiz
[usar fila]
Busca em Profundidade
Ciclos das Etapas
Expandir 
Teste do Objetivo
Marcar
Selecionar
nó da fronteira com grau de parentesco mais próximo da raiz
[usar pilha]
Busca de 
Custo-Uniforme
Ciclos das Etapas
Teste do Objetivo
continua a busca até não existir fronteira
Expandir
Selecionar 
menor custo
Marcar
Busca Gulosa
O Melhor Primeiro
Busca A*
Priorizar com base em
Distância percorrida +
Distância do objetivo
notícias e posições
notícias e posições
notícias e posições
aula de hoje
Buscas Locais
Enconomia de Memória e Ambientes Desconhecidos
Agentes com 
Visibilidade Total
Ambientes totalmente observáveis
Agentes com 
Visibilidade Parcial
Ambientes parcialmente observáveis
Ambientes infinitos
Visão do Espaço de Estados
State-space Landscape
A visibilidade do agente é limitada e por isso uma busca local é necessária
Visão do Espaço de Estados
Localidade 
	estado atual
Elevação 
	direção para o objetivo
Mínimos Global e Local
mínimo local
mínimo global
função de custo =
função objetivo invertida
espaço de estados
estado atual e direção da busca
platô
platô
visão (landscape) do
espaço de estados
Máximos Global e Local
máximo 
local
máximo 
global
função objetivo
espaço de estados
platô
platô
estado atual e direção da busca
visão (landscape) do
espaço de estados
Busca Subindo a Montanha
Hill-climbing Search
Essa busca é também chamada de Busca Local Gulosa, por avançar para um estado vizinho que está a priori na direção correta sem considerar o impacto futuro desta decisão
Busca Subindo a Montanha
Tipo de busca local
Avança sempre para o 
vizinho indicado pela elevação
Risco de não encontrar a solução 
global por 2 razões
	1. ficar preso em uma solução local
	2. ficar perdido em um platô
Busca Subindo a Montanha
S
escala
melhor ---------------------------pior
Busca Subindo a Montanha : Visão
S
8 vizinhos
escala
melhor ---------------------------pior
Busca Subindo a Montanha
S
máximo 
global
máximos 
locais
escala
melhor ---------------------------pior
Busca Subindo a Montanha 
S
ordem de desempate: esquerda, baixo, direita, cima
escala
melhor ---------------------------pior
Busca Subindo a Montanha
Uma pequena modificação na posição inicial do agente pode trazer um grande impacto no resultado da busca
Busca Subindo a Montanha 
S
ordem de desempate: esquerda, baixo, direita, cima
escala
melhor ---------------------------pior
Busca Subindo a Montanha
S
escala
melhor ---------------------------pior
ordem de desempate: esquerda, baixo, direita, cima
Buscas Subindo a Montanha
Reiniciadas Aleatoriamente
Random Restart 
Hill-climbing Search
Buscas reinicializadas aleatoriamente para dar novas oportunidades ao agente para que seu objetivo seja encontrado
Buscas Subindo a Montanha
Reiniciadas Aleatoriamente
2
1
5
4
3
escala
melhor ---------------------------pior
Teleporte?
E se o agente pudesse reiniciar sua busca a partir de outro ponto no espaço de estados?
No caso do agente preso no deserto isso faz pouco sentido. Mas imagine um agente com visibilidade local que busca resolver o Jogo dos Oito 
(também conhecido como racha cuca)
Arrefecimento Simulado
Simulated Annealing
Simular uma alta energia inicial do agente para que ele possa ir para caminhos custosos (gastando energia) para não ficar preso em um máximo (ou mínimo) local e atingir seu objetivo
Buscas por Arrefecimento Simulado
11
13
1
9
12
14
2
10
8
15
3
7
16
17
4
5
6
18
T = 100
OK
M = 10; P = T – M = 90%; OK;
T = T – M = 90
OK
OK
OK
M = 10; P = T – M = 80%; OK; T = 80
OK
OK
M = 20; P = T – M = 60%; X ; T = 80
OK
…
18. Objetivo atingido
melhor ---------------------------pior
Busca Local em Feixe
Local Beam Search
Diversos nós usados como estados inciais
Busca realizada em paralelo, cada busca dá um passo por rodada
Similar as buscas Reiniciadas Aleatoriamente, mas existe uma diferença
Busca Local em Feixe
Buscas em paralelo
Nós raiz são iniciados aleatoriamente
Vizinhos ordenados com base na elevação
Cada busca compartilha informações
Regiões com maior erro são abandonadas
Busca Local em Feixe
2
7
1
8
5
4
3
6
Iteração 1
escala
melhor ---------------------------pior
Busca Local em Feixe
6
5
1
4
2
3
8
7
Iteração 2
escala
melhor ---------------------------pior
Busca Local em Feixe
1
Iteração 2
escala
melhor ---------------------------pior
Algoritmos Genéticos
Genetic Algorithms
Algoritmos Genéticos simulam a seleção natural,
colocando uma população à prova ao longo de gerações na 
busca por um objetivo compartilhado por todos
864275_1
→
“Mutações podem ser causadas por erros de cópia do material durante a divisão celular, por exposição a radiação ultravioleta ou ionizante, mutagênicos químicos, ou vírus.” 
https://pt.wikipedia.org/wiki/Muta%C3%A7%C3%A3o
Desafio 2
http://rednuht.org/genetic_cars_2/
resumo
buscas locais
subindo a montanha
reinicialização
arrefecimento
algoritmos genéticos
referência