Aula21_22_23 - Etapa02 - I A - Agentes Resolução de Problemas

Prévia do material em texto

INTELIGÊNCIA ARTIFICIAL
BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO
SEMESTRE: 6º 
Prof. Me. Rhyan Ximenes
INTELIGÊNCIA ARTIFICIAL 1
Lattes: lattes.cnpq.br/2089613781353862
http://lattes.cnpq.br/2089613781353862
Agentes de Resolução de Problemas
• Agentes que utilizam representações atômicas, onde os estados do
mundo são considerados como um todo;
• A formulação de problemas é o processo de decidir que ações e
estados devem ser considerados, dado um objetivo;
• A formulação de objetivos, baseada na situação atual e na
medida de desempenho do agente, é o primeiro passo para a
resolução de problemas.
INTELIGÊNCIA ARTIFICIAL 2
Agentes de Resolução de Problemas
• Algoritmos de busca sem informação, não fornecem nenhuma
informação sobre o problema a não ser sua definição;
• Embora alguns desses algoritmos possam resolver qualquer
problema solucionável, nenhum deles pode fazê-lo de forma
eficiente;
• Os algoritmos de busca informada, por outro lado, podem ter
sucesso a partir de alguma orientação sobre onde procurar soluções.
INTELIGÊNCIA ARTIFICIAL 3
Algoritmos de busca
Agentes de Resolução de Problemas
• Os agentes inteligentes devem maximizar sua medida de
desempenho;
• Esse objetivo é às vezes simplificado se o agente adotar um objetivo
que deseja satisfazer.
INTELIGÊNCIA ARTIFICIAL 4
Agentes de Resolução de Problemas
• Um agente na cidade de Arad, na Romênia, aproveitando uma
viagem de férias;
• A medida de desempenho do agente contém muitos fatores:
• Melhorar seu conhecimento do idioma romeno, ver as paisagens,
apreciar a vida noturna, e assim por diante;
• O problema de decisão é complexo e envolve muitos compromissos e
leitura cuidadosa de guias de viagem.
INTELIGÊNCIA ARTIFICIAL 5
Imagine:
Agentes de Resolução de Problemas
• Nesse caso, faz sentido para o agente adotar o objetivo de chegar a
cidade Bucareste;
• Considerando que um objetivo seja um conjunto de estados do
mundo, exatamente os estados em que o objetivo é satisfeito;
• O primeiro passo para a resolução de problemas é a formulação de
objetivos baseada na situação atual e na medida de desempenho do
agente.
INTELIGÊNCIA ARTIFICIAL 6
Agentes de Resolução de Problemas
• A tarefa do agente é descobrir como agir, agora e no futuro, para que
atinja o estado objetivo;
• O agente precisa decidir que tipo de ações e estados deve considerar;
INTELIGÊNCIA ARTIFICIAL 7
Figura 1. Veículos autônomos
Fonte: pixabay.com
Agentes de Resolução de Problemas
• Se tentasse considerar ações detalhadas como “mover o pé esquerdo
para a frente uma polegada” ou “girar o volante um grau para a
esquerda”, provavelmente nunca conseguiria sair do lugar nem
chegaria a Bucareste;
• Quanto mais detalhes, mais incertezas no mundo e muitos passos
precisará para chegar a uma solução.
INTELIGÊNCIA ARTIFICIAL 8
Figura 2. Abstração de um bicicleta
Fonte: pixabay.com
Agentes de Resolução de Problemas
• A formulação de problemas é o processo de decidir que ações e
estados devem ser considerados, dado um objetivo;
• No exemplo da cidade de Bucareste, supõe-se que o agente vai
considerar ações no nível de dirigir desde uma cidade importante até
outra;
• Cada estado corresponderá, portanto, a estar em uma determinada
cidade.
INTELIGÊNCIA ARTIFICIAL 9
Exemplo: Viajar Pela Romênia 
INTELIGÊNCIA ARTIFICIAL 10
• O agente tem como objetivo dirigir para Bucareste e está considerando
para onde ir a partir de Arad.
Três 
possibilidades:
1 – Zerind;
2 – Sibiu;
3 - Timisoara
Uma delas atinge
o objetivo?
Figura 3. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Exemplo: Viajar Pela Romênia 
INTELIGÊNCIA ARTIFICIAL 11
• Agente tem como objetivo dirigir para Bucareste e está considerando
para onde ir a partir de Arad.
O agente não conhece
suficiente o estado que
resulta da execução de
cada ação.
Figura 4. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Exemplo: Viajar Pela Romênia 
INTELIGÊNCIA ARTIFICIAL 12
• Agente tem como objetivo dirigir para Bucareste e está considerando
para onde ir a partir de Arad.
Se o agente não tiver
nenhuma informação
adicional, se o ambiente
for desconhecido no
sentido definido, ele não
terá escolha a não ser
tentar uma das ações de
forma aleatória.
Figura 5. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Exemplo: Viajar Pela Romênia 
INTELIGÊNCIA ARTIFICIAL 13
• Agente tem como objetivo dirigir para Bucareste e está considerando
para onde ir a partir de Arad.
O agente tem um mapa
da Romênia.
Finalidade: Fornecer ao
agente informações
sobre os estados em que
ele próprio pode visitar e
sobre as ações que ele
pode executar.
O agente pode usar essas
informações passando
por cada cidade, para
descobrir o percurso que
eventualmente chegue a
Bucareste.
Figura 6. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Exemplo: Viajar Pela Romênia 
INTELIGÊNCIA ARTIFICIAL 14
• Agente tem como objetivo dirigir para Bucareste e está considerando
para onde ir a partir de Arad.
Pode-se concluir que:
Um agente com várias
opções imediatas de
valor desconhecido pode
decidir o que fazer
examinando primeiro
ações futuras que levam
eventualmente a estados
de valor conhecido.
Figura 7. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Agentes de Resolução de Problemas
• Busca é um processo de procura pela melhor sequência de ações
possíveis;
• Um agente com várias opções imediatas pode decidir o que fazer
comparando diferentes sequências de ações;
• Os Agentes de resolução de problemas decidem o que fazer
encontrando sequências de ações que levam a estados que são
desejáveis;
• Um algoritmo de busca recebe um problema como entrada e devolve
uma solução sob a forma de uma sequência de ações;
• Depois que uma solução é encontrada, as ações recomendadas
podem ser executadas.
INTELIGÊNCIA ARTIFICIAL 15
Definição de Problema
• A definição do problema é a primeira e mais importante etapa do
processo de resolução de problemas de inteligência artificial por meio de
buscas.
• Consiste em analisar o espaço de possibilidades de resolução do
problema, encontrar sequências de ações que levem a um objetivo
desejado.
INTELIGÊNCIA ARTIFICIAL 16
Figura 8. Quebra-cabeça
Fonte: pixabay.com
Problemas e Soluções bem Definidos
• Um problema pode ser definido formalmente por cinco
componentes:
• O estado inicial;
• Uma descrição das ações possíveis que estão disponíveis para o
agente;
• Uma descrição do que cada ação faz;
• O teste de objetivo;
• Uma função de custo de caminho.
INTELIGÊNCIA ARTIFICIAL 17
Problemas e Soluções bem Definidos
• O estado inicial em que o agente começa;
• Por exemplo: O estado inicial do agente na Romênia poderia ser
descrito como Em(Arada).
INTELIGÊNCIA ARTIFICIAL 18
Figura 9. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Problemas e Soluções bem Definidos
• Um agente simples de resolução de problemas;
• I - Formula um objetivo e um problema; II - busca uma sequência de
ações que resolvem o problema e III - executa as ações, uma
de cada vez. Quando essa sequência se completa, ele formula outro
objetivo e recomeça.
INTELIGÊNCIA ARTIFICIAL 19
Figura 10. Algoritmo agente de resolução de problemas
Fonte: Norvig e Russel (2004) 
Problemas e Soluções bem Definidos
• Uma descrição das ações possíveis que estão disponíveis para o
agente;
• Dado um estado particular s, AÇÕES(s) devolve um conjunto de ações
que podem ser executadas em s. Cada uma das ações é aplicável em s.
• Por exemplo, a partir do estado Em(Arad), as ações aplicáveis são:
{Ir(Sibiu), Ir(Timisoara), Ir(Zerind)}.
INTELIGÊNCIA ARTIFICIAL 20
Figura 11. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Problemas e Soluções bem Definidos
• Uma descrição do que cada ação é especificado por
uma função RESULTADO( s, a) que devolve o estado que resulta de
executar uma ação a em estado s.
• Usa-se também o termo sucessor para nos referirmos a qualquer
estado acessível a partir de determinado estado por uma única ação• Por exemplo: RESULTADO (Em(Arad), Ir (Zerind)) = Em (Zerind);
• Juntos, o estado inicial, as ações e o modelo de transição
definem implicitamente o espaço de estados do problema — o
conjunto de todos os estados acessíveis a partir do estado inicial, por
qualquer sequência de ações.
INTELIGÊNCIA ARTIFICIAL 21
Problemas e Soluções bem Definidos
• O teste de objetivo determina se um estado é um estado objetivo;
• O objetivo do agente na Romênia é o conjunto unitário
{Em(Bucareste)};
• Por exemplo, no xadrez, o objetivo é alcançar um estado
chamado “xeque-mate”, em que o rei do oponente está sob ataque e
não consegue escapar;
INTELIGÊNCIA ARTIFICIAL 22
Figura 12. Mapa de cidades romenas
Fonte: Norvig e Russel (2004) 
Figura 13. Xeque-mate
Fonte: pixabay.com
Problemas e Soluções bem Definidos
• Uma função de custo de caminho atribui um custo 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;
• Para o agente que tenta chegar a Bucareste, o tempo é essencial e,
assim, o custo de um caminho poderia ser seu comprimento em
quilômetros;
INTELIGÊNCIA ARTIFICIAL 23
Problemas e Soluções bem Definidos
• O custo de um caminho pode ser descrito como a soma dos custos das
ações individuais ao longo do caminho;
• O custo do passo de adotar a ação s para alcançar o estado s´ é
denotado por c(s, a, s´);
• A qualidade da solução é medida pela função de custo de caminho, e
uma solução ótima tem o menor custo de caminho entre todas as
soluções.
INTELIGÊNCIA ARTIFICIAL 24
Medição de Desempenho
• Completeza: O algoritmo oferecer a garantia de encontrar uma solução
quando ela 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: Quanto de memória é necessário para
executar a busca?
INTELIGÊNCIA ARTIFICIAL 25
Agentes de Resolução de Problemas
• A formulação do problema;
• Processo de decidir que ações e estados devem ser considerados,
dado um objetivo;
• Tarefa do agente será descobrir que sequência de ações o levará
a um estado objetivo.
• Levar em consideração a abstração: Abstrair a descrição do estado e
as próprias ações;
• A abstração é útil se a execução de cada uma das ações na solução é
mais fácil que o problema original.
INTELIGÊNCIA ARTIFICIAL 26
Agentes de Resolução de Problemas
• A abordagem de resolução de problemas é aplicada a uma ampla
série de ambientes de tarefas;
• Alguns dos mais conhecidos problemas fazem distinção entre
problemas de mundos simplificados e problemas do mundo real;
INTELIGÊNCIA ARTIFICIAL 27
Agentes de Resolução de Problemas
• Um mundo simplificado ou mini problema;
• Se destina a ilustrar ou exercitar diversos métodos de resolução de
problemas;
• São problemas com descrição concisa e exata.
• Um problema do mundo real;
• São problemas cujas soluções de fato interessam às pessoas;
• Tais problemas tendem a não apresentar uma única descrição
consensual;
• São aqueles cujas soluções de fato preocupam as pessoas.
INTELIGÊNCIA ARTIFICIAL 28
Problema do Mundo Simplificado
• Ele pode ser formulado como um problema da seguinte forma: 
• Estados ;
• Estado inicial;
• Ações;
• Modelo de Transição;
• Teste de objetivo;
• Custo do caminho.
INTELIGÊNCIA ARTIFICIAL 29
Problema do Mundo Simplificado
• Estados:
• São determinados tanto pela posição do agente como da sujeira;
• O agente está em uma entre duas posições, cada uma das quais pode
conter sujeira ou não. Desse modo, há 2 × 22 = 8 estados do mundo
possíveis;
• Um ambiente mais amplo com n posições tem n · 2n estados.
• Estado inicial:
• Qualquer estado pode ser designado como o estado inicial.
• Ações:
• Nesse ambiente simples, cada estado tem apenas três ações:
Esquerda, Direita e Aspirar;
• Ambientes mais amplos podem também incluir Em Cima e Embaixo.
INTELIGÊNCIA ARTIFICIAL 30
Problema do Mundo Simplificado
• Modelo de transição:
• As ações têm seus efeitos esperados, a não ser as ações: mover para a
Esquerda no quadrado mais à esquerda, mover para a Direita, no
quadrado mais à direita, e Aspirar, no quadrado limpo, que não tem
nenhum efeito;
INTELIGÊNCIA ARTIFICIAL 31
Figura 14 . Espaço de estado completos do mundo do aspirador de pó
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• 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.
INTELIGÊNCIA ARTIFICIAL 32
Figura 15 . Espaço de estado completos do mundo do aspirador de pó
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Características 
• Determinístico;
• Completamente observáveis;
• Estáticos;
• Completamente conhecidos;
• Exemplo: 
• Mundo do aspirador de pó: 
• Percebe em que quadrado está e se existe sujeira no quadrado; 
• Ele pode mover-se para direita ou para esquerda, aspirar à sujeira 
ou não fazer nada.
INTELIGÊNCIA ARTIFICIAL 33
Figura 16 . Espaço de estado completos
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Estados: Definidos pela posição do robô e sujeira (8 estados);
• Estado inicial: qualquer um (estado) ;
• Função sucessor: qualquer uma das ações (esquerda, direita, aspirar);
• Teste de objetivo: Verificar se todos os quadrados limpos;
• Custo do caminho: cada passo=1, custo do caminho = número de
passos do caminho.
INTELIGÊNCIA ARTIFICIAL 34
Figura 17 . Espaço de estado completos do mundo do aspirador de pó
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Características
• Determinístico;
• Completamente observáveis;
• Estáticos;
• Completamente conhecidos;
• Exemplo:
• O quebra-cabeça de oito peças: consiste de um tabuleiro 3×3
com oito peças numeradas e um quadrado vazio;
• Uma peça adjacente ao quadrado vazio pode deslizar para esse
quadrado;
• O objetivo é alcançar um estado objetivo especificado, como o do lado
direito da figura.
INTELIGÊNCIA ARTIFICIAL 35
Figura 18. Problema: Quebra-cabeça 8 peças
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Estados: posição das 8 peças e do vazio;
• Estado inicial: qualquer estado;
• Função sucessor: esq., dir., acima, abaixo;
• Teste de objetivo: verifica se o estado corresponde à configuração
do objetivo;
• Custo do caminho: cada passo=1; caminho=num. de passos do
caminho.
INTELIGÊNCIA ARTIFICIAL 36
Figura 19. Problema: Quebra-cabeça 8 peças
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Características
• Determinístico;
• Completamente observáveis;
• Sequencial;
• Estáticos;
• Completamente conhecidos;
• Exemplo:
• O objetivo do problema de oito rainhas é posicionar oito rainhas em um
tabuleiro de xadrez de modo que nenhuma rainha ataque qualquer
outra (uma rainha ataca qualquer peça situada na mesma linha, coluna
ou diagonal).
INTELIGÊNCIA ARTIFICIAL 37
Figura 20. Problema: 8 rainhas
Fonte: Norvig e Russel (2004) 
Problema do Mundo Simplificado
• Estados: qualquer disposição de rainhas;
• Estado inicial: nenhuma rainha;
• Função sucessor: colocar 1 rainha em qualquer vazio;
• Teste: 8 rainhas no tab., nenhuma atacada
• Custo do caminho: cada passo=1; caminho=num. de passos do 
caminho.
INTELIGÊNCIA ARTIFICIAL 38
Figura 21. Problema: 8 rainhas
Fonte: Norvig e Russel (2004) 
Problemas do Mundo Real
• Problema de roteamento
• Encontrar a melhor rota(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
INTELIGÊNCIA ARTIFICIAL 39
Problemas do Mundo Real
• Considere os problemas de viagens aéreas que devem ser resolvidos
através de um site da Web de planejamento de viagem:
• Estados: Cada estado inclui uma posição (por exemplo, um aeroporto) e
o tempopresente;
• Estado inicial: Especificado pela pergunta do usuário;
• Ações: Pegar qualquer voo a partir da posição atual, em qualquer classe
de assento, partindo após o instante atual, deixando tempo suficiente
para translado no aeroporto, se necessário;
INTELIGÊNCIA ARTIFICIAL 40
Problemas do Mundo Real
• Considere os problemas de viagens aéreas que devem ser resolvidos
através de um site da Web de planejamento de viagem:
• Modelo de transição: O estado resultante de pegar um voo terá o
destino do voo como a posição atual e a hora de chegada do voo como o
instante atual.
• Teste de objetivo: Estamos no destino final especificado pelo usuário?
• Custo do caminho: Valor da moeda, do tempo de espera, horário do voo,
procedimentos de imigração e de atendimento ao cliente, etc.
INTELIGÊNCIA ARTIFICIAL 41
Referências Bibliográficas
LUGER, George F. Inteligência Artificial-: Estruturas e estratégias para a
solução de problemas complexos. Bookman, 2004.
NORVIG, Peter; RUSSELL, Stuart J. Inteligência artificial. 2ed. Rio de
Janeiro: Elsevier, 2004
Notas de aulas da profa. Raquel Silveira (IFCE)
INTELIGÊNCIA ARTIFICIAL 42