IA_Aula2_Representacao_Resolucao_Problemas

Prévia do material em texto

Representação e 
Resolução de Problemas
Inteligência Artificial
Prof. Me. Orlando da Silva Junior
Agenda
1ª Parte
❑Objetivos de aprendizagem
❑Agentes inteligentes
❑Espaço e estados de busca
2ª Parte
❑Busca em profundidade
❑Busca em largura
❑Busca melhor escolha
❑A*
Prof. Me. Orlando da Silva Junior 2
Objetivos de Aprendizagem
▪ Reconhecer as competências inteligentes em soluções que aplicam Inteligência Artificial
▪ Discutir o emprego das técnicas de Inteligência Artificial em cenários e tipos de problemas
▪ Descrever conceitos teóricos e princípios de funcionamento das técnicas de IA
▪ Experimentar as técnicas e soluções de IA para solução de alguns problemas
Prof. Me. Orlando da Silva Junior 3
Agentes
A. Um agente é apenas alguma coisa que age.
B. Um agente racional é aquele que age de forma a alcançar o
melhor resultado ou, quando há incerteza, o melhor resultado
esperado.
C. Representação do conhecimento e raciocínio permitem que
agentes alcancem boas decisões.
Prof. Me. Orlando da Silva Junior 5
Tipos de agentes
• Baseiam suas ações em um mapeamento direto de estados para ações
• Não podem operar bem em ambientes para os quais este mapeamento 
poderia ser muito grande para armazenar e levaria muito tempo para 
aprender
Agentes reflexivos
• Consideram ações futuras e a desejabilidade de suas saídas
Agentes baseado 
em metas
• Usa representações atômicas (estados do mundo são considerados 
como completos, sem estruturas internas visíveis aos algoritmos 
solucionadores)
Agente solucionador 
de problemas
• Usa representações fatoradas ou estruturadas mais avançadasAgente planejador
Prof. Me. Orlando da Silva Junior 6
Prof. Me. Orlando da Silva Junior 7
I. Devem maximizar sua medida de desempenho.
II. Isso pode ser alcançado se o agente adotar uma meta e 
pretender alcançá-la.
Agentes Inteligentes 
o Imagine uma agente aproveitando o feriado na cidade
de Arad, Romênia.
o A medida de desempenho do agente contém muitos
fatores:
o Quer melhorar seu bronzeado;
o Melhorar o romeno;
o Contemplar as paisagens;
o Aproveitar a vida noturna;
o Evitar ressacas;
o Etc.
o O problema de decisão é um complexo problema
envolvendo muitas leituras cuidadosas de guias.
o Neste momento, suponha que o agente tem uma
passagem não-reembolsável para Bucareste no dia
seguinte.
o Neste caso, faz sentido para o agente adotar o
objetivo de ir à Bucareste.
o Tudo o que não levar à Bucareste no tempo pode ser
rejeitado sem preocupações e o problema de decisão
do agente é simplificado. 8Ghioroc Lake, Arad, Romania.
Fonte: TripAdvisor.
Prof. Me. Orlando da Silva Junior 9
Formulação de metas
▪ Uma meta é um conjunto de estados de 
mundo.
▪ Exatamente aqueles estados os quais a meta é 
cumprida.
▪ A formulação de metas é o primeiro passo 
para solucionar o problema.
▪ Deve ser baseada na situação atual e na medida 
de desempenho do agente.
▪ A tarefa do agente é descobrir como agir, 
agora e no futuro, para alcançar o estado da 
meta.
Prof. Me. Orlando da Silva Junior 10
Fonte: Pexels.
Formulação do problema
É o processo de decidir quais ações e estados considerar, dada uma meta.
Prof. Me. Orlando da Silva Junior 11
Fonte: Pexels.
Busca e execução
12
▪ A busca é o processo de procurar uma
sequência de ações que alcancem a
meta.
▪ Um algoritmo de busca toma um
problema como entrada e devolve
uma solução na forma de uma
sequência de ações.
▪ Uma vez que a solução é encontrada,
as ações que ele recomenda podem
ser realizadas. Esta é a fase de
execução.
Prof. Me. Orlando da Silva Junior 13
1. Após formular um objetivo e um problema para resolver, o agente
chama um procedimento de busca para resolvê-lo.
2. Ele usa a solução para guiar suas ações, fazendo o que a solução
recomenda como próxima coisa a fazer (tipicamente a primeira ação
da sequência).
3. Uma vez que a solução tenha sido executada, o agente irá formular
uma nova meta.
Problemas e soluções bem-definidos
▪Um problema pode ser definido formalmente por 5 componentes:
1. O estado inicial que o agente inicia.
2. Uma descrição de possíveis ações disponíveis ao agente.
3. O modelo de transição descrevendo o que cada ação faz.
4. O teste de meta, que determina se um determinado estado é o estado alvo.
5. Uma função de custo de caminho que atribui um custo numérico a cada caminho.
Prof. Me. Orlando da Silva Junior 14
Prof. Me. Orlando da Silva Junior 15
I. Uma solução para um problema é uma sequência de ações 
que leva do estado inicial à meta alvo.
II. A qualidade da solução é medida por uma função de caminho 
de custo.
III. Uma solução ótima (ou otimizada) tem o menor caminho de 
custo entre todas as soluções.
Solução Ótima
1. Estado inicial:
In(Arad)
2. Ações: ACTIONS(s)
{Go(Sibiu), Go(Timisoara), Go(Zerind)}
3. Modelo de transição: RESULT(s, a)
RESULT(In(Arad), Go(Zerind)) = In(Zerind)
4. Teste de meta:
{In(Bucharest)}
5. Custo de caminho: menor tempo
෍𝑐(𝑠, 𝑎, 𝑠′)
16Ghioroc Lake, Arad, Romania.
Fonte: TripAdvisor.
Exemplo
Prof. Me. Orlando da Silva Junior 17
Fonte: AIMA
Exercícios
1. Qual é a diferença entre um agente reflexivo e um agente baseado em objetivos?
2. Como um agente inteligente pode maximizar sua medida de desempenho?
3. Explique o design de agentes “Formula-Busca-Executa”.
4. Quais são os 5 componentes que definem formalmente um problema? Explique cada 
um deles.
Prof. Me. Orlando da Silva Junior 18
Prof. Me. Orlando da Silva Junior 19
Como solucionar um quebra-cabeças de 8 peças?
Qual a sequência para sair do estado inicial e chegar no estado final desejado?
Desafio
Formule o problema e a solução.
Prof. Me. Orlando da Silva Junior 20
Como solucionar um quebra-cabeças 
de 8 peças?
Qual a sequência para sair do estado 
inicial e chegar no estado final desejado?
Desafio
Formule o problema e a solução.
Estados: cada estado especifica a posição de cada uma
das 8 peças e do espaço em branco no tabuleiro.
1. Estado inicial: qualquer estado.
2. Ações: espaço em branco para a esquerda (L), para
a direita (R), para cima (U) ou para baixo (D).
3. Modelo de transição: RESULT(s, a)
4. Teste de meta: números ordenados e último
espaço em branco.
5. Custo de caminho: quantidade de ações realizadas,
sendo +1 o custo de cada ação.
Estratégias de Busca
Prof. Me. Orlando da Silva Junior
▪ Podemos resolver um problema
tornando-o um problema de
busca.
▪ A sequência possível de ações
começa do estado inicial de uma
árvore de busca com o estado
inicial na raiz.
▪ Os ramos são ações.
▪ Os nós correspondem aos estados
no espaço de estados do
problema.
Prof. Me. Orlando da Silva Junior 22
Fonte: AIMA
Infraestrutura para algoritmos de busca
▪ Algoritmos de busca requerem uma estrutura de dados
para manter o controle que está sendo construído.
▪ Para cada nó 𝑛 da árvore, existe uma estrutura que
contém 4 componentes:
1. Estado: o estado no espaço de estados o qual o nó
corresponde.
2. Pai: o nó na árvore de busca que gerou esse nó.
3. Ação: a ação que foi aplicada ao pai para gerar o nó.
4. Custo do caminho: o custo 𝑔(𝑛) do caminho entre o
estado inicial e o nó.
▪ Depois de construídos os nós, podemos armazená-los em
uma fila, uma fila de prioridades ou uma pilha.
Prof. Me. Orlando da Silva Junior 23
Fonte: AIMA
Como avaliar o desempenho?
Podemos avaliar o desempenho de um algoritmo de 4 formas:
1. Completude (completeness): o algoritmo garante encontrar uma solução quando existe uma?
2. Otimalidade (optmality): a estratégia encontra a melhor solução quando existem soluções diferentes?
3. Complexidade temporal: quanto tempo leva para encontrar uma solução?
4. Complexidade espacial: quanto de memória é necessária para realizar a busca?
Prof. Me. Orlando da Silva Junior 24
Antes de utilizar um algoritmo, precisamos conhecer alguns 
critérios para escolher um dentre eles. 
Busca em Largura
▪ Estratégia
▪ O nó raiz é expandido primeiro.
Então, os sucessores do nó raiz são
expandidos em seguida. E,então, os
sucessores dos sucessores do nó raiz
são expandidos. Etc.
▪ Implementação
▪ Fila: primeiro a entrar, primeiro a sair
▪ Novos nós entram na fila e nós
antigos são expandidos primeiro.
Prof. Me. Orlando da Silva Junior 25
Critério Resposta
Completude Sim
Otimalidade Sim (menor profundidade)
Complexidade 
temporal
𝑂(𝑏𝑑), com nível de profundidade d e 
fator de ramificação b sendo todos os 
nós gerados a partir de b
Complexidade 
espacial
𝑂 𝑏𝑑−1 nós explorados
𝑂 𝑏𝑑 nós na fronteira
Fonte: Wikipédia
Busca em Profundidade
▪ Estratégia
▪ Sempre expande o nó mais profundo
da fronteira atual da árvore. A busca
procede imediatamente para o nível
mais profundo da árvore de busca,
onde os nós não têm sucessores.
Assim que eles são expandidos, eles
são removidos da fronteira para que
a busca “guarde” o próximo nó mais
profundo ainda não explorado.
▪ Implementação
▪ Pilha: último a entrar, primeiro a sair
▪ Novos nós são expandidos primeiro.
Prof. Me. Orlando da Silva Junior 26
Critério Resposta
Completude Não (pode entrar em looping)
Otimalidade Não há garantia.
Complexidade 
temporal
𝑂(𝑏𝑚), com nível de profundidade 
máxima m de cada nó e fator de 
ramificação b
Complexidade 
espacial
𝑂 𝑏 ∙ 𝑚 nós
Fonte: Wikipédia
É possível melhorar a busca?
▪ Podemos usar conhecimento específico do problema (ou seja,
além da definição do próprio problema) para melhorar a busca.
Para tanto, devem-se definir heurísticas.
▪ Uma heurística é uma informação, valor ou quantificação de um
estado quanto à sua relevância ou distância de outros estados
(sobretudo da meta).
▪ Características
▪ Tentam evitar a explosão combinatória
▪ Podem levar a soluções “razoáveis”
▪ A heurística deve mostrar a relevância ou o custo do nó
Prof. Me. Orlando da Silva Junior 27
Busca Melhor Escolha
Prof. Me. Orlando da Silva Junior 28
▪ Estratégia
▪ Busca genérica.
▪ Expande o nó de menor valor da
função de avaliação na fronteira do
espaço de estados.
▪ Atua semelhantemente à busca em
profundidade com backtracking.
▪ Implementação
▪ Fila de prioridades
▪ (N) = custo em relação ao nó meta
Critério Resposta
Completude Sim.
Otimalidade Não há garantia.
Complexidade 
temporal
𝑂(𝑏𝑑)
Complexidade 
espacial
𝑂(𝑏𝑑)
A
B 
(3)
C
(5)
D 
(1)
E 
(4)
F 
(6)
G 
(6)
Exercício Resolvido
No espaço de estados, há o valor da
heurística em cada um dos estados.
Apresente a sequência de estados com
que a árvore será expandida usando o
processo de Melhor Escolha.
Nó meta: J
Resposta: A-B-C-D-G-H-I-E-F-C-J
Prof. Me. Orlando da Silva Junior 29
A 
(9)
B 
(8)
C 
(8)
D 
(7)
E 
(8)
F 
(7)
G 
(8)
H 
(6)
I 
(9)
J
Busca A*
Prof. Me. Orlando da Silva Junior 30
▪ Estratégia
▪ É a busca melhor escolha guiada pela
função de avaliação. Ou seja, a busca
A* usa o custo de cada ramo.
▪ Expande o nó de menor valor da
função de avaliação na fronteira do
espaço de estados.
▪ 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛), em que g é o
custo ao nó inicial e h é a função
heurística.
▪ Implementação
▪ Fila de prioridades
Critério Resposta
Completude Sim.
Otimalidade Sim, para heurísticas admissíveis.
Complexidade 
temporal
𝑂(𝑏𝑑)
Complexidade 
espacial
𝑂(𝑏𝑑)
A
B
(3+1)
C
(5+1)
D 
(1+1)
E 
(4+2)
F 
(6+2)
G 
(6)
Exercício
No espaço de estados, há o valor da
heurística em cada um dos estados.
Apresente a sequência de estados com
que a árvore será expandida usando o
processo A*.
Nó meta: R ou T
Resposta: A-B-C-D-H-I-O-E-F-K-L-G-Q-R-R
Prof. Me. Orlando da Silva Junior 31
A 
(9)
B 
(9)
C 
(9)
D 
(8)
E 
(10)
F 
(8)
H 
(10)
I 
(8)
O 
(12)
T
G 
(9)
J 
(∞)
K 
(10)
L 
(9)
M 
(9)
S 
(8)
V 
(∞)
N 
(10)
Q 
(∞)
R U 
(9)
P
(∞)