Luiz Eduardo Quintanilha Malheiro
1 INF 1771 Inteligência Artificial Aula 07 Agentes Lógicos Edirlei Soares de Lima
2 Introdução Humanos possuem conhecimento e raciocinam sobre este conhecimento. Exemplo: João jogou uma pedra na janela e a quebrou Agentes Baseados em Conhecimento ou Agentes Lógicos.
3 Agente Baseado em Conhecimento Podem lidar mais facilmente com ambientes parcialmente observáveis. O agente pode usar as suas percepções e conhecimento do mundo para inferir aspectos ainda desconhecidos do ambiente. São flexíveis e podem assumir novas tarefas na forma de objetivos explicitamente descritos.
4 Agente Baseado em Conhecimento O componente central de um agente baseado em conhecimento é sua base de conhecimento. A base de conhecimento é formada por um conjunto de sentenças expressadas através de uma linguagem lógica de representação de conhecimento. Deve ser possível adicionar novas sentenças à base e consultar o que se conhece. Ambas as tarefas podem envolver inferência (derivação de novas sentenças a partir de sentenças antigas).
5 Agente Baseado em Conhecimento Agente genérico baseado em conhecimento: function KB-AGENT(percept) returns an action static: KB, a knowledge base t, a counter, initially 0, indicating time TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t)) action ASK(KB,MAKE-ACTION-QUERY(t)) TELL(KB,MAKE-ACTION-SENTENCE(action, t)) tt + 1 return action end
6 Agente Baseado em Conhecimento Processo de execução de um agente baseado em conhecimento: (1) Informa a base de conhecimento o que o agente esta percebendo do ambiente; (2) Pergunta a base de conhecimento qual a próxima ação que deve ser executada. Um extensivo processo de raciocínio lógico é realizada sobre a base de conhecimento para que sejam decididas as ações que devem ser executadas. (3) Realiza a ação escolhida e informa a base de conhecimento sobre a ação que esta sendo realizada.
7 Agente Baseado em Conhecimento Porque utilizar uma linguagem lógica de representação de conhecimento? Facilita a criação dos agentes. É possível dizer o que o agente sabe através de sentenças lógicas. O agente pode adicionar novas sentenças a sua base de conhecimento enquanto ele explora o ambiente. Abordagem declarativa de criação de sistemas.
9 O Mundo de Wumpus O ambiente contém: Salas conectadas por passagens; Ouro em alguma sala; Poços sem fundo nos quais cairá qualquer um que passar pela sala, exceto o Wumpus; Wumpus: monstro que devora qualquer guerreiro que entrar em sua sala. O Wumpus pode ser morto pelo agente, mas o agente só tem uma flecha.
10 O Mundo de Wumpus Medida de desempenho: por pegar ouro, se cair em um poço ou for devorado pelo Wumpus, -1 para cada ação executada, -10 pelo uso da flecha. Ambiente: malha 4x4 de 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. Ações posiveis: O agente pode mover-se para frente, virar à esquerda, virar à direita, agarrar um objeto e atirar a flecha.
11 O Mundo de Wumpus Sensores: 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;
12 O Mundo de Wumpus Passo 1: Sensores: [nada, nada, nada, nada, nada] Conclusão: [1,2] e [2,1] são seguros Movimento escolhido: [2,1]
13 O Mundo de Wumpus Passo 2: 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]
14 O Mundo de Wumpus Passo 3: 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]
15 Lógica A base de conhecimento de um agente é formada por um conjunto de sentenças expressadas através 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.
16 Tipos de Lógica 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 paraconsistente: lógica especializada no tratamento de bases de dados que contenham inconsistências....
17 Conceitos Lógica Sintaxe: especifica todas as sentenças que são bemformadas. Exemplo na aritmética: x+y=4, x4y+=. Semântica: Especifica o significado das sentenças. A 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.
18 Conceitos Lógica Modelo: um mundo possível. A frase m é modelo de a indica que a sentença a é verdadeira no modelo m. 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.
19 Consequência lógica no 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. Possíveis modelos: 2³=8
21 Consequência lógica no Mundo de Wumpus A base de conhecimento (BC) é falsa em modelos que contradizem o que o agente sabe. Nesse caso, há apenas 3 modelos em que a base de conhecimento é verdadeira: BC
22 Consequência lógica no Mundo de Wumpus Considerando a possível conclusão: a¹ = não existe nenhum poço em [1,2] BC a¹ É possivel afirma que BC a¹
23 Consequência lógica no Mundo de Wumpus Considerando a possível conclusão: a² = não existe nenhum poço em [2,2] BC a² É possivel afirma que BC a²
24 Inferência Lógica O exemplo anterior: Ilustra a consequência lógica. Mostra como a consequência lógica pode ser aplicada para produzir inferência lógica (derivar conclusões). O algoritmo ilustrado no exemplo se chama model checking. Ele numera todos os possíveis modelos para checar se a é verdade em todos os modelos onde BC é verdade.
25 Agente Baseado em Conhecimento Como representar a base de conhecimento do agente? Lógica Proposicional Lógica de Primeira ordem Outras linguagens lógicas
26 Lógica Proposicional Lógica simples. A sentenças são formadas por conectivos como: e, ou, então. É necessário definir: Sintaxe (sentenças válidas). Semântica (modo pelo qual a verdade das sentenças é determinada). Consequência lógica (relação entre uma sentença e outra que decorre dela). Algoritmo para inferência lógica.
27 Sintaxe em Lógica Proposicional A sintaxe da lógica proposicional define as sentenças permitidas. É formada por: Símbolos: nomes em letras maiúsculas (P, Q, R,...) que podem assumir verdadeiro e falso; Sentenças atômicas: constituídas por elementos sintáticos indivisíveis (símbolo proposicional); Sentenças complexas: são construídas a partir de sentenças mais simples com a utilização de conectivos lógicos: (não), (e), (ou), (implica), (dupla implicação) Sentença cujo principal conectivo é : conjunção Sentença cujo principal conectivo é : disjunção
29 Exempos de Sentenças Validas P Verdadeiro P Q (P Q) S (P Q) R S (P Q) (P Q) R S
30 Implicação Lógica ( ) P Q Se P é verdade então Q também é verdade. Exemplo: Se está chovendo então as ruas estão molhadas.
31 P Q Equivalência Lógica ( ) Se P é verdade então Q também é verdade. Se Q é verdade então P também é verdade. Exemplo: Se dois lados de um triangulo são iguais então os dois ângulos da base do tribulo são iguais. A equivalência por ser substituída por duas sentenças de implicação: (P Q) (Q P)
32 Semântica em Lógica Proposicional Descreve como calcular o valor verdade de qualquer sentença com base em um mesmo modelo. É necessário definir como calcular a verdade de sentenças atômicas e como calcular a verdade de sentenças formadas com cada um dos cinco conectivos (,,,, ). Sentenças atômicas: Verdadeiro é verdadeiro e falso é falso em todo modelo. O valor-verdade de todos os outros símbolos proposicionais deve ser especificado diretamente no modelo. Sentenças complexas: As regras em cada conectivo são resumidas em uma tabela-verdade.
33 Tabela-verdade para os Conectivos Para os cinco conectivos lógicos apresentados, teremos: * (*) Lógica proposicional não exige relação de causa e efeito entre P e Q. Deve-se entender esta relação como se P é verdadeira, então Q é verdadeira. Caso contrário, não estou fazendo nenhuma afirmação. Exemplo: 5 é ímpar implica que Tóquio é capital do Japão (V) 5 é par implica que João é inteligente (V)
34 Exemplo: Mundo de Wumpus Vocabulário de símbolos proposicionais: Seja P i,j verdadeiro se existe poço em [i,j] Seja B i,j verdadeiro se existe brisa em [i,j]
35 Exemplo: Mundo de Wumpus Base de Conhecimento: R1: P 1,1 Não há poço em [1,1]. R2: B 1,1 (P 1,2 P 2,1 ) R3: B 2,1 (P 1,1 P 2,2 P 3,1 ) Um quadrado tem uma brisa se e somente se existe um poço em um quadrado vizinho (todos os quadrados devem ser declarados). R4: B 1,1 R5: B 2,1 Percepções adquiridas pelo agente do mundo em que ele se encontra.
36 Inferência - Mundo de Wumpus Inferência: derivação de novas sentenças a partir de sentenças antigas. Objetivo: decidir se BC α para alguma sentença α. Exemplos: P 1,2? P 2,2? Algoritmo: enumerar todos os modelos e verificar se α é verdadeira em todo modelo no qual BC é verdadeira. Símbolos proposicionais relevantes: B 1,1, B 2,1, P 1,1, P 1,2, P 2,1, P 2,2, P 3,1 7 símbolos 2 7 =128 modelos possíveis
37 Tabela Verdade Mundo de Wumpus Em três desses modelos toda a base de conhecimento é verdadeira. Nesses três modelos, P 1,2 é verdadeira. Dessa maneira conclui-se que não existe poço em [1,2]. P 2,2 é verdadeira em dois dos três modelos e falsa em um. Assim, não podemos dizer ainda se existe um poço em [2,2].
38 Equivalência Duas sentenças α e β são logicamente equivalentes (α β) se são verdadeiras no mesmo conjunto de modelos. (α β) (β α) comutatividade de (α β) (β α) comutatividade de (α β) γ α (β γ) associatividade de (α β) γ α (β γ) associatividade de α α eliminação de dupla negação (α β) ( β α) contraposição (α β) ( α β) eliminação de implicação (α β) ((α β) (β α)) eliminação de bicondicional (α β) ( α β) de Morgan (α β) ( α β) de Morgan (α (β γ)) ((α β) (α γ)) distributividade de sobre (α (β γ)) ((α β) (α γ)) distributividade de sobre
39 Padrões de Raciocínio em Logica Proposicional Modus Ponens: A partir de uma implicação e a premissa da implicação, pode-se inferir a conclusão. Eliminação de E: De uma conjunção, podese inferir qualquer um dos conjuntores. Resolução Unitária: De uma disjunção, se um dos disjuntores é falso, então pode-se inferir que o outro é verdadeiro.
40 De Volta ao Mundo de Wumpus Base de Conhecimento: R1: P 1,1 Não há poço em [1,1]. R2: B 1,1 (P 1,2 P 2,1 ) R3: B 2,1 (P 1,1 P 2,2 P 3,1 ) Um quadrado tem uma brisa se e somente se existe um poço em um quadrado vizinho (todos os quadrados devem ser declarados). R4: B 1,1 R5: B 2,1 Percepções adquiridas pelo agente do mundo em que ele se encontra.
41 Provando P 1,2 em Wumpus Eliminação bicondicional em R2: R2: B 1,1 (P 1,2 P 2,1 ) R6: (B 1,1 (P 1,2 P 2,1 )) ((P 1,2 P 2,1 ) B 1,1 ) Eliminação de e em R6: R7: (P 1,2 P 2,1 ) B 1,1 Contraposição em R7: R8: B 1,1 (P 1,2 P 2,1 ) Modus Ponens (R4 + R8) R4: B 1,1 R9: (P 1,2 P 2,1 ) Regra de Morgan em R9: R10: P 1,2 P 2,1 Eliminação de e em R10: P 1,2 De uma conjunção, pode-se inferir qualquer um dos conjuntores. A partir de uma implicação e a premissa da implicação, pode-se inferir a conclusão.
42 Prova Lógica A aplicação de uma sequencia de regras de inferências para derivar uma conclusão é chamado de prova lógica. A aplicação de inferências logicas é uma alternativa a enumeração de modelos vista anteriormente. Como saber quais regras de inferência devem ser utilizadas?
43 Limitações da Lógica Proposicional A lógica proposicional é simples de mais para representar alguns problemas do mundo real. Em problemas complexos pode ser necessário a utilização de um número muito grande de sentenças para a criação de um agente realmente inteligente.
44 Leitura Complementar Russell, S. and Novig, P. Artificial Intelligence: a Modern Approach, 2nd Edition, Prentice-Hall, Capítulo 7: Logical Agents
Mundo do Wumpus. Inteligência Artificial. Beatriz F. M. Souza. Prof. Orivaldo Lira Tavares
Mundo do Wumpus Beatriz F. M. Souza Prof. Orivaldo Lira Tavares Inteligência Artificial Departamento de Ciência da Computação Universidade Federal do Espírito Santo (UFES), Vitória, ES Brasil 15 de junho