Buscar

Trabalho Mundo de Wumpus

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 18 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 18 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 18 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

FACULDADE DE TECNOLOGIA DE CARAPICUÍBA
ALEXANDRE TAVARES SILVA
AGENTES LÓGICOS:
MUNDO DE WUMPUS
CARAPICUÍBA/SP
2014
ALEXANDRE TAVARES SILVA
AGENTES LÓGICOS:
MUNDO DE WUMPUS
Trabalho sobre Agentes Lógicos usando como estudo de caso “O Mundo de Wumpus” apresentado ao professor Luiz Henrique da disciplina de Inteligência Artificial do 6º Semestre do Curso de Tecnologia em Análise e Desenvolvimento de Sistemas da Faculdade de Tecnologia de Carapicuíba, do Centro Estadual de Educação Tecnológica Paula Souza, como requisito para avaliação parcial.
Aluno: Alexandre Tavares Silva RA: 1430431213021
CARAPICUÍBA/SP
2014
LISTA DE FIGURAS
Figura 1 - Agente baseado em conhecimento genérico	7
Figura 2 - Um Mundo de Wumpus Típico.	9
Figura 3 - Explorando o Mundo de Wumpus Passo 01	11
Figura 4 - Explorando o Mundo de Wumpus Passo 02	11
Figura 5 - Explorando o Mundo de Wumpus Passo 03	12
Figura 6 - Consequência Lógica - Mundo de Wumpus	14
Figura 7 - Consequência Lógica - Possíveis Modelos	15
Figura 8 - Consequência lógica falsa	16
Figura 9 - Consequência Lógica - Conclusão 1	16
Figura 10 - Consequência Lógica - Conclusão 2	17
Figura 11 - Correspondência entre o mundo e a representação	18
SUMÁRIO
1. INTRODUÇÃO	6
1.1. AGENTES BASEADOS EM CONHECIMENTO	6
1.2. PROCESSOS DE EXECUÇÃO	6
2. MUNDO DE WUMPUS	8
2.1. HISTÓRIA	8
2.2. MUNDO DE WUMPUS - O JOGO	8
2.2.1. Medidas de desempenho	10
2.2.2. Ambiente	10
2.2.3. Sensores	10
2.2.4. Atuadores	10
2.2.5. Explorando o Mundo de Wumpus	11
3. LÓGICA	13
3.1. TIPOS DE LÓGICA	13
3.2. CONCEITOS DE LÓGICA	13
3.2.1. Consequência Lógica no Mundo de Wumpus	14
3.3. INFERÊNCIA LÓGICA	17
REFERÊNCIAS BIBLIOGRÁFICAS	19
1. INTRODUÇÃO
	Os agentes lógicos admitem que as proposições são verdadeiras, falsas ou desconhecidas. Na prática, os agentes quase nunca têm acesso a toda a verdade sobre os seus ambientes, o que os leva a agir sob a incerteza.
 Como o mundo real é muito mais complexo do que qualquer jogo, é impossível a construção de uma descrição completa e correta de como todas as funções de um agente funcionarão.
	O trabalho a seguir irá demonstrar como agentes podem formar representações do mundo, usar um processo de inferência para derivar novas representações e utilizar essas novas representações para deduzir o que fazer. O jogo “Mundo de Wumpus” será utilizado como estudo de caso.
1.1. AGENTES BASEADOS EM CONHECIMENTO
Como não poderia ser diferente, o componente principal de um agente baseado em conhecimento é a sua própria base de conhecimento, que aqui será mencionado pela representação KB (do inglês Knowledge Base). 
Uma base de conhecimento (KB) é formada por um conjunto de sentenças, que na verdade são representações de conhecimento de alguma proposição do mundo.
É importante que seja possível adicionar novas sentenças à base de conhecimento e que se consulte o que está contido na base. As operações de adição e consulta de conhecimento recebem o nome de TELL (informe) e ASK (pergunte) respectivamente. É importante salientar que ambas as operações podem ser envolvidas por um processo de inferência, ou seja, a derivação de novas sentenças a partir de sentenças antigas.
1.2. PROCESSOS DE EXECUÇÃO 
A seguir são enumeradas as etapas que compõem a execução de um agente baseado em conhecimento:
Informa à base de conhecimento o que o agente está percebendo do ambiente;
Pergunta para a base de conhecimento o que deve ser executado na próxima ação. Um extenso processo de raciocínio lógico é executado sobre as sentenças da base de conhecimento para que sejam decididas as ações que devem ser executadas.
Realiza a ação escolhida e informa a base de conhecimento sobre o que está sendo executado.
	
	A Figura 1 representa um esboço de um programa baseado em conhecimento. Como todos os agentes baseados em conhecimento, ele recebe uma percepção como entrada e retorna uma ação. O agente mantém uma base de conhecimento, KB, que pode conter um conhecimento inicial.
Figura 1 - Agente baseado em conhecimento genérico
	A resposta de uma pergunta (ASK) à base de conhecimento deve seguir o que foi informado anteriormente (TELL). Nada é inventado na medida em que o processo de inferência se desenrola.
	É importante utilizar uma lógica de representação de conhecimento porque facilita a criação de agentes. Desta maneira é possível dizer o que o agente sabe por meio de sequências lógicas. Além disso, o agente pode adicionar novas sentenças a sua base de conhecimento enquanto está explorando o ambiente. 
2. MUNDO DE WUMPUS
2.1. HISTÓRIA
O Mundo do Wumpus foi proposto em 1972 por Gregory Yob, projetista de jogos para computador. Motivado pela insistência de os jogos da época serem baseados em grades cartesianas, decidiu então criar um novo tipo de jogo para computador. A ideia do jogo era fazer com que o agente não mais caminhasse por entre campos de um ambiente, mas sim por entre arestas de uma figura geométrica: as arestas funcionariam como espécie de corredores que levariam o agente para diferentes estados.
Esta característica inovadora concedeu ao Mundo do Wumpus a consagração de ser o primeiro jogo do tipo primeira pessoa (o jogador é um personagem no ambiente e deixa de ser representado por uma animação), como por exemplo, WolfEinstein, Doom, Quake, entre outros.
2.2. MUNDO DE WUMPUS - O JOGO
O mundo do Wumpus é caracterizado por um labirinto repleto de abismos, habitado por um terrível monstro, chamado Wumpus. Além disso, o mundo também esconde perigosas armadilhas. O objetivo do jogo é matar o Wumpus, urgindo das armadilhas encontradas pelo caminho. Manter-se vivo é a principal tarefa para se concluir o objetivo. Porém, isso não é muito fácil, no interior da caverna, deve-se ficar muito atento às indicações de perigo uma vez que o agente é dotado de percepções, como por exemplo, ele é capaz de sentir a brisa que sai dos abismos espalhados pela caverna. Também é possível sentir o mau cheiro exalado pelo terrível Wumpus. Após essa perigosa busca, deve-se encontrar a saída para que jogo termine.
Com esse cenário foi criado o primeiro Mundo do Wumpus ("Hunt lhe Wumpus"), mas com o passar do tempo muitas versões foram criadas e muitas características iniciais foram alteradas. Existem também preciosas barras de ouro, que são utilizadas para avaliar o desempenho dos agentes.
A seguir serão descritas em mais detalhes as características principais desta versão do Wumpus:
O ambiente é discreto, dividido em várias casas ou campos. Nessas casas ficam alojadas as barras de ouro, poços e o Wumpus. O Wumpus pode ocupar o mesmo espaço que as barras de ouro. O poço (ou abismo) preenche uma casa inteira;
Os poços são sem fundo e qualquer um que passar por ele cairá, exceto o Wumpus.
O ambiente é cíclico, ou seja, não existem paredes fixas que limitam um espaço do ambiente;
O agente pode mover-se para qualquer casa adjacente; pegar barras de ouro que estão na mesma casa e disparar uma flecha para matar o monstro (a flecha pode matar o monstro somente em casas adjacentes);
As percepções do agente se limitam em: sentir a brisa dos abismos que estiverem nas casas adjacentes; sentir o mau cheiro do Wumpus se ele estiver em uma das casas adjacentes; perceber o brilho das barras de ouro, se elas estiverem na mesma casa do agente; escutar o grito emitido pelo monstro quando este for atingido pela flecha; perceber a existência de paredes na casa que o agente estiver;
Para que possamos avaliar melhor o desempenho do algoritmo são atribuídos pontos a cada ação do agente, o agente começa com zero ponto e a cada movimento ele perde um, mas se consegue pegar uma barra de ouro ele ganha mil pontos, caso ele seja morto ele perde dez mil pontos e caso ele mate o Wumpus, ganha dez mil pontos;
A Figura 2 representa uma amostra do ambiente do Mundo de Wumpus. É dada a definição precisa do ambiente de tarefa, como sugerea descrição PEAS.
Figura 2 - Um Mundo de Wumpus Típico.
2.2.1. Medidas de desempenho
	A seguir as medidas de desempenho para o agente do Mundo de Wumpus:
+1.000 por pegar ouro, 
-1.000 se cair em um poço ou for devorado pelo Wumpus, 
-1 para cada ação executada, 
-10 pelo uso da flecha.
2.2.2. Ambiente 
	A seguir serão descritos os detalhes do ambiente do Mundo de Wumpus:
O ambiente do Mundo de Wumpus é formado por uma malha 4x4 contendo salas. 
O agente sempre começa no quadrado identificado como [1,1] voltado para a direita. As posições do Wumpus, ouro e poços são escolhidas aleatoriamente.
Quadrados próximos ao Wumpus fedem.
Quadrados próximos ao poço possuem brisa.
O agente possui apenas uma flecha.
Atirar mata o Wumpus apenas se for em frente.
2.2.3. Sensores
	A seguir são detalhados os sensores que compõem o agente do Mundo de Wumpus:
Em quadrados adjacentes ao Wumpus, exceto diagonal, o agente sente o fedor do Wumpus;
Em quadrados adjacentes a um poço, exceto diagonal, o agente sente uma brisa;
Quadrados onde existe ouro o agente percebe o brilho do ouro;
Ao caminhar contra uma parede o agente sente um impacto;
Quando o Wumpus morre o agente ouve um grito;
Sensores: [fedor, brisa, brilho, impacto, grito]
2.2.4. Atuadores
	O agente pode mover-se para frente, virar à esquerda, virar à direita, agarrar um objeto e atirar a flecha.
2.2.5. Explorando o Mundo de Wumpus
	A seguir serão descritos 03 passos que servirão de exemplo para o funcionamento da lógica utilizada para a movimentação do agente no ambiente do Mundo de Wumpus:
Passo 01:
	A Figura 3 demonstra o resultado obtido após análise lógica das percepções.
Figura 3 - Explorando o Mundo de Wumpus Passo 01
Sensores: [nada, nada, nada, nada, nada].
Conclusão: [1,2], [2,1] são seguros.
Movimento escolhido: [2,1].
Passo 02:
	A Figura 4 demonstra o resultado obtido após análise lógica das percepções.
Figura 4 - Explorando o Mundo de Wumpus Passo 02
Sensores: [nada, brisa, nada, nada, nada].
Conclusão: Há poço em [2,2], [3,1] ou ambos.
Movimento escolhido: [1,1] e depois [1,2]
Passo 03:
	A Figura 4 demonstra o resultado obtido após análise lógica das percepções.
Figura 5 - Explorando o Mundo de Wumpus Passo 03
Sensores: [fedor, nada, nada, nada, nada].
Conclusão: 
Há Wumpus em [1,3] ou [2,2]
Wumpus não pode estar em [2,2]
Wumpus em [1,3]
Não existe poço em [2,2]
Poço em [3,1]
[2,2] é seguro
Movimento escolhido: [2,2].
3. LÓGICA
	A base de conhecimento de um agente é formada por um conjunto de sentenças expressadas por meio de uma linguagem lógica de representação de conhecimento.
	O conceito de lógica foi organizado principalmente por Aristóteles. “É o conhecimento das formas gerais e regras gerais do pensamento correto e verdadeiro, independentemente dos conteúdos pensados”.
	“Todo homem é mortal” 
	“Sócrates é um homem” 
	“Logo, Sócrates é mortal” 
	Todo X é Y. Z é X. Portanto, Z é Y.
3.1. TIPOS DE LÓGICA
	A seguir serão descritas as definições de alguns tipos de lógicas existentes:
Lógica proposicional: (ou lógica Booleana) lógica que representa a estrutura de sentenças usando conectivos como: "e", "ou" e "não“.
Lógica de predicados: lógica que representa a estrutura de sentenças usando conectivos como: “alguns”, “todos” e “nenhum”.
Lógica multivalorada: estende os tradicionais valores verdadeiro/falso para incluir outros valores como "possível“ ou um número infinito de "graus de verdade”, representados, por exemplo, por um número real entre 0 e 1.
Lógica modal: o estudo do comportamento dedutivo de expressões como:“é necessário que” e “é possível que”.
Lógica temporal: descreve qualquer sistema de regras e símbolos para representar e raciocinar sobre proposições qualificadas em termos do tempo.
Lógica para consistente: lógica especializada no tratamento de bases de dados que contenham inconsistências.
3.2. CONCEITOS DE LÓGICA
	A seguir serão descritos alguns conceitos sobre lógica que servem de apoio ao entendimento do raciocínio lógico nas questões que remetem ao envolvimento das relações da consequência lógica entre as sentenças, embasando a ideia de que uma sentença é decorrente logicamente de outra sentença.
Sintaxe: especifica todas as sentenças que são bem formadas. Exemplo na aritmética: “x+y=4”, “x4y+=“.
Semântica: Especifica o significado das sentenças. A semântica define verdade de cada sentença com relação a cada “mundo possível”. Exemplo: a sentença “x+y=4” é verdadeira em um mundo no qual x=2 e y=2, mas é falsa em um mundo em que x=1 e y=1. Em lógica padrão 	toda sentença deve ser verdadeira ou falsa com relação a cada modelo possível.
Modelo: um “mundo possível”. A frase “m é modelo de a” indica que a sentença a é verdadeira no modelo m. Apesar de os modelos serem imaginados como ambientes reais em que o agente poderia ou não estar, os modelos nada mais são do que abstrações matemáticas que simplesmente fixam a verdade ou falsidade de cada sentença relevante.
Consequência lógica: utilizada quando uma sentença decorre logicamente de outra. Notação: a╞ b (b decorre logicamente de a). Pode ser aplicada para derivar conclusões, ou seja, para conduzir inferência lógica.
3.2.1. Consequência Lógica no Mundo de Wumpus
	Os conceitos de consequência lógica podem ser aplicados ao raciocínio do Mundo de Wumpus demonstrado anteriormente. A seguir exemplo baseado em análise realizada utilizando-se das percepções do agente combinadas com os conhecimentos agregados ao KB.
A Figura 6 representa o conhecimento que o agente tem do ambiente do mundo de Wumpus.
Figura 6 - Consequência Lógica - Mundo de Wumpus
Base de conhecimento: 
Nada em [1,1];
Brisa em [2,1];
Regras do mundo de Wumpus;
Interesse do agente:
Saber se os quadrados [1,2], [2,2] e [3,1] contém poços. Cada um dos 3 quadrados pode ou não conter poço.
Possíveis modelos: 
2³=8 são o número de possíveis modelos baseados no interesse do agente
	A Figura 7 representa os possíveis modelos (2³=8) obtidos por meio da análise da base de conhecimento.
Figura 7 - Consequência Lógica - Possíveis Modelos
	
	A base de conhecimento (BC) é falsa em modelos que contradizem o que o agente sabe. Nesse caso, há apenas 03 modelos em que a base de conhecimento é verdadeira conforme ilustrado na Figura 8.
Figura 8 - Consequência lógica falsa
	Considerando a possível conclusão: a¹ = “não existe nenhum poço em [1,2]”, é possível afirma que: BC╞ a¹. Tal fato é observado na Figura 9.
Figura 9 - Consequência Lógica - Conclusão 1
	Considerando a possível conclusão: a² = “não existe nenhum poço em [2,2]”, é possível afirma que: BC╞ a². Tal fato é observado na Figura 10.
Figura 10 - Consequência Lógica - Conclusão 2
3.3. INFERÊNCIA LÓGICA
	O exemplo apresentado anteriormente descrevendo o processo de consequência lógica aplicado a uma situação definida para o Mundo de Wumpus demonstra como tais conceitos podem ser aplicados para produzir uma inferência lógica (derivar conclusões).
	O Algoritmo utilizado no exemplo se chama Model Checking (Verificação de Modelos). Este modelo enumera todos os possíveis modelos para checar se “a” é verdade em todos os modelos onde “BC” é verdade.
Algoritmo de inferência correto: deriva apenas sentenças permitidas, ou seja, preserva a verdade. A correção é uma propriedade altamente desejável.
Algoritmo de inferência completo: é assim chamado quando puder derivar qualquer consequência lógica. A propriedade da completude também é desejada. Existem procedimentos de inferência completos para lógicas que são suficientemente expressivas para dar conta da base de conhecimento.
	Foi descrito um processo de raciocínio cujas conclusões oferecem a garantia de serem verdadeiras em qualquer mundo no qual as premissas são verdadeiras.
	Em particular, se a BC é verdadeira no mundo real, qualquer sentença derivada de BC por um processo de inferência correto também será verdadeira no mundo real. Portanto, embora um processo deinferência opere sobre a sintaxe, o processo corresponde ao relacionamento no mundo real, no qual algum aspecto do mundo real é o caso, em virtude de outros aspectos do mundo real serem o caso. 	Essa correspondência entre o mundo e a representação está ilustrada na Figura 11.
Figura 11 - Correspondência entre o mundo e a representação
	Sentenças são configurações físicas do agente e o raciocínio é um processo de construção de novas configurações físicas a partir de configurações antigas. O raciocínio lógico deve assegurar que as novas configurações representam aspectos do mundo que na realidade decorrem dos aspectos que as antigas configurações representam.
REFERÊNCIAS BIBLIOGRÁFICAS
NORVIG, PETER, RUSSELL, STUART, Inteligência Artificial 3º Edição, Elsevier Brasil, 2014.
Lima, Edirlei. Aula 05 - Introdução à Lógica, disponível em: http://edirlei.3dgb.com.br/aulas/ia/IA_Aula_05_Logica.pdf, acesso em 17/10/2014.
Quinet, Marcos. Inteligência Artificial, disponível em: 
http://www.professores.uff.br/mquinet/09_IA.pdf, acesso em 17/10/2014.
FEI, Lógica Proposicional, disponível em:
http://fei.edu.br/~psantos/slidesia/cap7-logica_proposicional-.ppt, acesso em 17/10/2014.

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes