INF 1771 – Inteligência Artificial
Aula 07 – Agentes Lógicos
Edirlei Soares de Lima
<elima@inf.puc-rio.br>
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.
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.
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).
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))
t++
return action
end
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 está sendo realizada.
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.
O Mundo de Wumpus
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.
O Mundo de Wumpus
•
•
Medida de desempenho: +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.
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 possíveis: O agente pode mover-se
para frente, virar à esquerda, virar à
direita, agarrar um objeto e atirar a flecha.
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;
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]
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]
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]
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.
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.
...
Conceitos Lógica
•
•
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
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.
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.
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.
[
•
2
Possíveis modelos:
³=8
Possíveis Modelos
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
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¹
Consequência lógica no Mundo de Wumpus
•
Considerando a possível conclusão:
–
a² = “não existe nenhum poço em [2,2]”
a²
BC
É possivel afirma que
BC╞ a²
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.
Agente Baseado em Conhecimento
•
Como representar a base de conhecimento do
agente?
–
–
–
Lógica Proposicional
Lógica de Primeira ordem
Outras linguagens lógicas
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.
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
Gramática da Lógica Proposicional
•
•
•
•
Sentença → SentençaAtômica | SentençaComplexa
SentençaAtômica → Verdadeiro | Falso | Símbolo
Símbolo → P | Q | R | ...
SentençaComplexa → ¬Sentença
|
|
|
|
(Sentença ∧ Sentença)
(Sentença ∨ Sentença)
(Sentença ⇒ Sentença)
(Sentença ⇔ Sentença)
Exempos de Sentenças Validas
•
•
•
•
•
•
•
P
Verdadeiro
P ∧ Q
(P ∨ Q) ⇒ S
(P ∧ Q) ∨ R ⇒ S
¬(P ∨ Q)
¬(P ∨ Q) ⇒ R ∧ S
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.
Equivalência Lógica (⇔)
•
P ⇔ Q
–
–
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)
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.
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)
Exemplo: Mundo de Wumpus
•
Vocabulário de símbolos
proposicionais:
–
–
Seja Pi,j verdadeiro se existe
poço em [i,j]
Seja Bi,j verdadeiro se existe
brisa em [i,j]
Exemplo: Mundo de Wumpus
Base de Conhecimento:
Não há poço em [1,1].
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,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: ¬B1,1
R5: B2,1
Percepções adquiridas pelo agente do
mundo em que ele se encontra.
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:
P1,2? P2,2?
Algoritmo: enumerar todos os modelos e verificar se α é
verdadeira em todo modelo no qual BC é verdadeira.
–
Símbolos proposicionais relevantes:
B1,1, B2,1, P1,1, P1,2, P2,1, P2,2, P3,1
–
7 símbolos → 27=128 modelos possíveis
Tabela Verdade – Mundo de Wumpus
•
•
Em três desses modelos toda a base de conhecimento é verdadeira.
Nesses três modelos, ¬P é verdadeira. Dessa maneira conclui-se
1
,2
que não existe poço em [1,2].
•
P é verdadeira em dois dos três modelos e falsa em um. Assim,
2
,2
não podemos dizer ainda se existe um poço em [2,2].
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 ∧
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, pode-
se 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.
De Volta ao Mundo de Wumpus
Base de Conhecimento:
Não há poço em [1,1].
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,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: ¬B1,1
R5: B2,1
Percepções adquiridas pelo agente do
mundo em que ele se encontra.
Provando ¬P1,2 em Wumpus
•
Eliminação bicondicional em R2:
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R6: (B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1)
Eliminação de “e” em R6:
R7: (P1,2 ∨ P2,1) ⇒ B1,1
Contraposição em R7:
R8: ¬B1,1 ⇒¬(P1,2 ∨ P2,1)
Modus Ponens (R4 + R8)
•
•
•
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.
R4: ¬B1,1
R9: ¬(P1,2 ∨ P2,1)
•
•
Regra de Morgan em R9:
R10: ¬P1,2 ∧¬P2,1
Eliminação de “e” em R10: ¬P1,2
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?
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.
Leitura Complementar
•
Russell, S. and Norvig, P. Artificial Intelligence: a
Modern Approach, 2nd Edition, Prentice-Hall,
2003.
•
Capítulo 7: Logical Agents