Agentes que raciocinam com base na
lógica de primeira ordem
Engajamentos, sintaxe e semântica da LPO
Uso da LPO em agentes baseados em conhecimento
Aplicação ao mundo do Wumpus
Representando mudanças no mundo
Deduzindo propriedades escondidas do mundo
1
Lógica de Primeira Ordem - LPO
É um formalismo de referência para representação
de conhecimento

o mais estudado e o melhor formalizado
Satisfaz em grande parte os seguintes critérios:

adequação representacional
 permite representar o mundo (expressividade)

adequação inferencial
 permite inferência

eficiência aquisicional
 facilidade de adicionar conhecimento

modularidade
2
Engajamento Ontológico
Natureza da realidade, descrição do mundo
Na Lógica Proposicional, o mundo consiste em fatos.
Na Lógica de Primeira Ordem, o mundo consiste em:

objetos: “coisas” com identidade própria
 ex. pessoas, casas, Wumpus, caverna, etc.

relações entre esses objetos
 ex. irmão-de, tem-cor, parte-de, adjacente, etc.

propriedades (que distinguem esses objetos)
 ex. vermelho, redondo, fundo, fedorento, etc.

funções: um ou mais objetos se relacionam com um único
objeto
 ex. dobro, distância, pai_de, etc.
3
Engajamento Ontológico
Além disso, a LPO exprime:


fatos sobre todos objetos do universo ()
fatos sobre objetos particulares
()
Exemplos:

1+1=2
 objetos: 1, 2; relação: =; função: +.

Todas as Cavernas adjacentes ao Wumpus são fedorentas.
 objetos: cavernas, Wumpus; propriedade: fedorentas; relação:
adjacente.
A LPO não faz engajamentos ontológicos para tempo,
categorias e eventos...

neutralidade favorece flexibilidade
4
Engajamento Epistemológico
Estados do conhecimento (crenças)
A LPO tem o mesmo engajamento epistemológico
que a lógica proposicional

tudo é verdadeiro ou falso
Para tratar incerteza, usamos


Outras lógicas (de n-valoradas, fuzzy, paraconsistente, etc.)
Probabilidade
5
Resumo
Linguagem
Engajamento Engajamento
Ontológico
Epistemológico
L. Proposicional
Fatos
V, F, ?
LPO
Fatos, objetos,
relações
V, F, ?
L. Temporal
Fatos, objetos,
relações, tempo
V, F, ?
Probabilidade
Fatos
Grau de crença:
0-1
L. Difusa
Grau de verdade
sobre fatos,
objetos, relações
Grau de crença:
0-1
6
Sistema Formal em LPO
Cálculo
= Cálculo de Predicados
Linguagem Regras de derivação
= LPO
= regras de inferência
Teoria
Axiomas
= fatos +
regras
síncronas
sintaxe + semântica
causais
Teoremas
= fatos derivados
(axiomas + regras
de derivação)
diacrônicas
de diagnóstico
Base de Conhecimento = fatos e regras básicos (só axiomas!)
Memória de Trabalho = fatos particulares à instância do problema e
fatos derivados
Máquina de Inferência = regras de inferência
LPO: Sintaxe
Sentença  SentençaAtômica | Sentença Conectivo Sentença
| Quantificador Variável,... Sentença
|  Sentença | (Sentença)
SentençaAtômica  Predicado(Termo,...) | Termo = Termo | Verdade | Falso
Termo Função(Termo,...) | Constante | Variável
Conectivo  
Quantificador 
Constante A | X | João | ...
Variável a | x | s | ...
(letras minúsculas)
Predicado Vermelho | Tem-cor | IrmãoDe | ...
Função Mãe | MelhorAmigo | ...
8
LPO: Semântica
Constantes e Variáveis denotam Objetos:



ex. Caetano, aluno, cadeira, estrela...
uma interpretação especifica a que objeto no mundo
cada constante e cada variável livre se refere.
o mesmo objeto pode ser referenciado por mais de
um símbolo:
 ex. “Vênus” e “A estrela Dalva” referem-se ao
mesmo objeto (planeta) no universo.
OBS.: Ocultei os outros slides sobre semântica...
9
LPO em agentes baseados
em conhecimento
Representação
do mundo
Representação
Representação
lógica inicial
lógica atualizada
Conhecimento de
lógica
Mecanismo
de inferência
No mundo :
Pedro possui um cachorro.
Todo dono de cachorro é um protetor dos animais.
Nenhum protetor dos animais mata um animal.
Na Lógica:
x cachorro(x)  possui(Pedro,x)
x y (cachorro(y)  possui(x,y))  protetorAnimais(x)
x protetorAnimais(x)  y animal(y)  mata(x,y)
17
Propriedades da Inferência Lógica
Corretude

gera apenas sentenças válidas
Composicionalidade:

o significado de uma sentença é função do de suas partes
Monotonicidade

Tudo que era verdade continua sendo depois de uma inferência
Localidade

inferência apenas com comparações locais (porção da BC).
Localidade e composicionalidade ---> modularidade --->
reusabilidade e extensibilidade
18
Uso de LPO em agentes
baseados em conhecimento
função Agente-BC(percepção) retorna uma ação
Tell(BC, Percepções-Sentença(percepção,t))
ação  Ask(BC Pergunta-Ação(t))
Tell(BC, Ação-Sentença(ação,t))
t t+1
retorna ação
Onde...


função Pergunta-Ação cria uma query tal como: a Ação(a,6)
função ASK devolve uma lista de instanciações:
{a / Pegar} - Pegar é atribuída à variável ação.

TELL gravar a ação escolhida na BC.
19
LPO em agentes baseados
em conhecimento
Axiomas = fatos e regras básicos e fatos do problema
Teoremas = fatos derivados
Pesquisa = ASK


Quantificador : a resposta é booleana
Quantificador : a resposta é uma lista de
instanciações/substituições de variáveis - binding
 ASK (BC, x Irmã(x,Caetano))
->
{x/Betânia,x/Irene}
 ASK (BC, x (Irmã(x,Caetano)  Cantora(x))) ->
{x/Betânia}
20
Hipótese do Mundo Fechado
Tudo que não estiver presente na base é
considerado falso
Isto simplifica (reduz) a BC

Ex. Para dizer que os países Nova Zelândia, África do
Sul, Irlanda e França gostam do jogo Rugby, não
precisa explicitamente dizer que os outros não
gostam...
21
Um Agente LPO para o
Mundo do Wumpus
Interface entre o agente e o ambiente:

sentença de percepções, que inclui as percepções e o tempo
(passo) em que elas ocorreram, e.g.:
 Percepção ([Fedor, Brisa, Luz, nada, nada], 6)
Ações do agente:

Girar(Direita), Girar(Esquerda), Avançar, Atirar, Pegar, Soltar e
Sair das cavernas
Três arquiteturas de Agentes baseados em LPO:



Agente reativo
Agente com Modelo do Mundo
Agente baseado em Objetivo
22
Agente reativo baseado em LPO
Possui regras ligando as seqüências de percepções a ações

Essas regras assemelham-se a reações
f,b,c,g,t Percepção([f,b,Luz,c,g], t) Ação(Pegar, t)
Essas regras dividem-se entre


Regras de (interpretação) da percepção
b,l,c,g,t Percepção([Fedor,b,l,c,g], t) Fedor (t)
f,l,c,g,t Percepção([f,Brisa,l,c,g], t)  Brisa (t)
f,b,c,g,t Percepção([f,b,Luz,c,g], t)  Junto-do-Ouro (t)
...
Regras de ação
t Junto-do-Ouro (t) Ação(Pegar, t)
23
Limitações do agente reativo puro
Como já vimos, um agente reativo puro nunca sabe
quando parar


estar com o ouro e estar na caverna (1,1) não fazem
parte da sua percepção (se pegou, esqueceu).
esses agentes podem entrar em laços infinitos.
Para ter essas informações, o agente precisa guardar
uma representação do mundo.
24
Agentes LPO com Estado Interno
Guardando modelo interno do mundo

sentenças sobre como o mundo está agora
 “agente está com o ouro”

as sentenças serão atualizadas quando:
 O agente receber novas percepções e realizar ações
 ex. o agente pegou o ouro,..
Questão

Como manter, com simplicidade, o modelo do mundo
corretamente atualizado?
25
Representando Mudanças no Mundo
Como representar as mudanças?
Ex., “O agente foi de [1,1] para [1,2]”
1. Apagar da BC sentenças que já não são verdade

 ruim: perdemos o conhecimento sobre o passado, o
que impossibilita previsões de diferentes futuros.
2. Cada estado é representado por uma BC diferente:
 ruim: pode explorar situações hipotéticas, porém não
pode raciocinar sobre mais de uma situação ao mesmo
tempo.

ex. “existiam buracos em (1,2) e (3,2)?”
26
Cálculo Situacional
Solução: Cálculo situacional !


uma maneira de escrever mudanças no tempo em LPO
Permite a representação de diferentes situações na
mesma BC
O mundo consiste em uma seqüência de situações

situação N ===ação===> situação N+1
Utiliza uma função Resultado para representar as
mudanças no mundo:

Resultado (ação,situação N) = situação N+1
27
Cálculo Situacional
Predicados que mudam com o tempo têm um
argumento de situação adicional

Ao invés de Em(Agente,local) teremos
(Em(Agente,[1,1],S0)  Em(Agente,[1,2],S1))
Predicados que denotam propriedades que não mudam
com o tempo não necessitam de argumentos de
situação

Parede(0,1) e Parede(1,0)
28
Exemplo de cálculo situacional
Result(Forward,S0) = S1
Result(Turn(Right),S1) = S2
Result(Forward,S2) = S3
29
Representando Mudanças no Mundo
Axiomas estado-sucessor
Descrição completa de como o mundo evolui

uma coisa é verdade depois 
[uma ação acabou de torná-la verdade
ela já era verdade e nenhuma ação a tornou falsa ]

Ex. a,x,s Segurando(x, Resultado(a,s)) 
[(a = Pegar Presente (x, s) Portável(x))
 (Segurando (x,s) (a  Soltar)]
É necessário escrever uma axioma estado-sucessor para cada
predicado que pode mudar seu valor no tempo.
O que muda no mundo do Wumpus?

Pegar ouro, localização e direcionamento do agente
30
Guardando localizações
O agente precisa lembrar por onde andou e o que viu


para poder deduzir onde estão os buracos e o Wumpus,
para garantir uma exploração completa das cavernas
O agente precisa saber:

localização inicial = onde o agente está
Em (Agente,[1,1],S0 )

orientação: a direção do agente (em graus)
Orientação (Agente,S0 ) = 0

localização um passo à frente: função de locais e orientações
x,y
x,y
x,y
x,y
PróximaLocalização ([x,y ],0)
= [x+1,y ]
PróximaLocalização ([x,y ],90) = [x,y+1 ]
PróximaLocalização ([x,y ],180) = [x-1,y ]
PróximaLocalização ([x,y ],270) = [x,y-1 ]
31
Guardando localizações
A partir desses axiomas, pode-se deduzir que quadrado está
em frente ao agente “ag” que está na localização “l”:
ag,l,s Em (ag,l,s ) 
localizaçãoEmFrente (ag,s) =
PróximaLocalização (l,Orientação (ag,s))
Podemos também definir adjacência:
l1,l2 Adjacente (l1,l2 ) d l1 = PróximaLocalização (l2,d )
E detalhes geográficos do mapa:
x,y Parede([x,y ]) (x =0 x =5 y =0 y =5)
32
Guardando localizações
Resultado das ações sobre a localização do agente:

Axioma Estado-Sucessor: avançar é a única ação que muda a
localização do agente (a menos que haja uma parede)
a,l,ag,s Em(ag,l,Resultado(a,s)) 
[(a = Avançar l = localizaçãoEmFrente(ag,s)  Parede(l))
 (Em(ag,l,s) a  Avançar)]
Efeito das ações sobre a orientação do agente:

Axioma ES: girar é a única ação que muda a direção do agente
a,d,ag,s Orientação(ag,Resultado(a,s)) = d 
[(a = Girar(Direita) d = Mod(Orientação(ag,s) - 90, 360)
 (a = Girar(Esquerda) d = Mod(Orientação(ag,s) + 90, 360)
(Orientação(ag,s) = d   (a = Girar(Direita) a =
33
Girar(Esquerda))]
Deduzindo Propriedades do Mundo
Agora que o agente sabe onde está, ele pode
associar propriedades aos locais:

 l,s Em(Agente,l,s)  Brisa(s)  Ventilado(l)
 l,s Em(Agente,l,s)  Fedor(s)  Fedorento(l)
Observem que os predicados Ventilado e Fedorento
não necessitam do argumento de situação
Sabendo isto, o agente pode deduzir:


onde estão os buracos e o Wumpus, e
quais são as cavernas seguras (predicado OK).
34
Tipos de regras
Regras Diacrônicas (do grego “através do tempo”)

descrevem como o mundo evolui (muda ou não) com o
tempo
x,s Presente(x,s) Portável(x) 
Segurando(x,Resultado(Pegar,s))
Regras Síncronas:

relacionam propriedades na mesma situação (tempo).
 o,s Em(Agente,l,s)  Brisa(s)  Ventilado(l)


possibilitam deduzir propriedades escondidas no
mundo
Existem dois tipos principais de regras síncronas:
 Regras Causais e Regras de Diagnóstico.
35
Tipos de regras
Regras Causais assumem causalidade


algumas propriedades escondidas no mundo causam
a geração de certas percepções.
Exemplos
 as cavernas adjacentes ao Wumpus são fedorentas :
 l1, l2,s Em (Wumpus,l1,s)  Adjacente (l1,l2) 
Fedorento (l2)
 Se choveu, a grama está molhada

Sistemas que raciocinam com regras causais são
conhecidos como Sistemas Baseados em Modelos.
36
Tipos de regras
Regras de Diagnóstico:


Raciocínio abdutivo: supõe a presença de propriedades
escondidas a partir das percepções do agente.
Ex., a ausência de fedor ou brisa implica que esse local e os
adjacentes estão OK.
 x,y,g,u,c,s Percepção ([nada, nada, g,u,c],t) 
Em (Agente,x,s)  Adjacente(x,y)  OK(y)
 se a grama está molhada, então é porque o aguador ficou ligado

Sistemas que raciocinam com regras de diagnóstico são
conhecidos como Sistemas de Diagnóstico
É perigoso misturar numa mesma BC regras causaias e de
diagnóstico!!!

se choveu é porque o aguador estava ligado...
37
Modularidade das Regras
As regras que definimos até agora não são modulares:





mudanças nas crenças do agente sobre algum aspecto do mundo
requerem mudanças nas regras que lidam com outros aspectos que
não mudaram.
Para tornar essas regras mais modulares, separamos fatos sobre
ações de fatos sobre objetivos:
assim, o agente pode ser “reprogramado” mudando-se o seu
objetivo.
Ações descrevem como alcançar resultados.
Objetivos descrevem a adequação (desirability) de estados
resultado, não importando como foram alcançados.
Descrevemos a adequação das regras e deixamos que a
máquina de inferência escolha a ação mais adequada.
38
Modularidade: Adequação das Regras
Escala, em ordem decrescente de adequação:


ações podem ser: ótimas, boas, médias, arriscadas e mortais.
O agente escolhe a mais adequada
 a,s Ótima(a,s)  Ação(a,s)
 a,s Boa(a,s)  ( b Ótima(b,s))  Ação(a,s)
 a,s Média(a,s)  ( b (Ótima(b,s) Boa(b,s) ))  Ação(a,s)
 a,s Arriscada(a,s)  ( b (Ótima(b,s) Boa(b,s) Média(a,s) )) 
Ação(a,s)
Essas regras são gerais, podem ser usadas em situações
diferentes:

uma ação arriscada na situação S0 (onde o Wumpus está vivo)
pode ser ótima na situação S2, quando o Wumpus já está morto.
39
Sistema de Ação-Valor
Sistema baseado em regras de adequação

Não se refere ao que a ação faz, mas a quão desejável ela é.
Prioridades do agente até encontrar o ouro:





ações ótimas: pegar o ouro quando ele é encontrado, e sair
das cavernas.
ações boas: mover-se para uma caverna que está OK e ainda
não foi visitada.
ações médias: mover-se para uma caverna que está OK e já
foi visitada.
ações arriscadas:mover-se para uma caverna que não se sabe
com certeza que não é mortal, mas também não é OK
ações mortais: mover-se para cavernas que sabidamente
contêm buracos ou o Wumpus vivo.
40
Agentes Baseados em Objetivos
O conjunto de ações-valores é suficiente para prescrever uma
boa estratégia de exploração inteligente das cavernas.


quando houver uma seqüência segura de ações , ele acha o
ouro
Porém... isso é tudo o que um agente baseado em LPO pode
fazer.
Depois de encontrar o ouro, a estratégia deve mudar...

novo objetivo: estar na caverna (1,1) e sair.
 s Segurando(Ouro,s)  LocalObjetivo ([1,1],s)
A presença de um objetivo explícito permite que o agente
encontre uma seqüência de ações que alcançam esse
objetivo.
41
Como encontrar seqüências de ações
(1) Busca:


Usar Busca pela Melhor Escolha para encontrar um caminho até
o objetivo.
Nem sempre é fácil traduzir conhecimento em um conjunto de
operadores, e representar o problema (ambiente) em estados
para poder aplicar o algoritmo.
(2) Inferência:


Idéia: escrever axiomas que perguntam à BC uma seqüência de
ações que com certeza alcança o objetivo.
Porém: para um mundo mais complexo isto se torna muito caro
 como distinguir entre boas soluções e soluções mais dispendiosas
(onde o agente anda “à toa” pelas cavernas)?
42
Agentes Baseados em Objetivos
(3) Planejamento:

envolve o uso de um sistema de raciocínio dedicado, projetado
para raciocinar sobre ações e conseqüências para objetivos
diferentes.
ficar rico e feliz
pegar o ouro
ações e conseqüências
sair das cavernas
ações e conseqüências
43