1
Agentes Baseados em Lógica
Agentes em lógica proposicional
Agentes em lógica de predicados
CIn- UFPE
2
Agentes baseados em Lógica
Proposicional
CIn- UFPE
3
Um Agente-BC para o Mundo do Wumpus
 A Base de Conhecimento consiste em:
• sentenças representando as percepções do agente
• sentenças válidas implicadas a partir das sentenças das
percepções
• regras utilizadas para implicar novas sentenças a partir das
sentenças existentes
 Símbolos:
•
•
•
•
•
•
•
Ax-y significa que “o agente está na caverna (x,y)”
Bx-y significa que “existe um buraco na caverna (x,y)”
Wx-y significa que “o Wumpus está na caverna (x,y)”
Ox-y significa que “o ouro está na caverna (x,y)”
bx-y significa que “existe brisa na caverna (x,y)”
fx-y significa que “existe fedor na caverna (x,y)”
lx-y significa que “existe Brilho na caverna (x,y)”
CIn- UFPE
4
Base de Conhecimento para o Mundo do Wumpus
 Com base nas percepções do estado abaixo, a BC
deverá conter as seguintes sentenças:
f1-1b1-1
f2-1b2-1
f1-2b1-2
4
3
2
1
W!
A
f
ok
V
ok
1
V - caverna
visitada
ok
b V
ok
2
B!
3
4
CIn- UFPE
5
Base de Conhecimento para o Mundo do Wumpus
 O agente também tem algum conhecimento prévio sobre o
ambiente, e.g.:
• se uma caverna não tem fedor, então o Wumpus não está nessa
caverna, nem está em nenhuma caverna adjacente a ela.
 O agente terá uma regra para cada caverna no seu ambiente
R1: f1-1W1-1W1-2W2-1
R2: f2-1W1-1W2-1W2-2W3-1
R3: f1-2W1-1W1-2W2-2W1-3
 O agente também deve saber que, se existe fedor em (1,2),
então deve haver um Wumpus em (1,2) ou em alguma
caverna adjacente a ela:
R4: f1-2W1-3W1-2W2-2W1-1
CIn- UFPE
6
Como Encontrar o Wumpus - Inferência!
 Como mostrar que BC W1-3 é uma sentença válida?
1) construindo a Tabela-Verdade para a sentença
• Satisfabilidade de sentenças é um problema NP-completo
• Existem 12 símbolos proposicionais na BC, então a TabelaVerdade terá 12 colunas => 212 = 4096
(2) usando regras de inferência!
CIn- UFPE
7
Lógica Proposicional: Regras de Inferência
   ,
 Modus Ponens:

/ diz que a sentença 
pode ser derivada de 
por inferência.
 E-eliminação: 1   2  ...   n
i
 1 ,  2 ,...,  n
 E-introdução:
 1   2  ...   n
i
 Ou-introdução:
1 2  ...n
 Eliminação de dupla negação:
 Resolução unitária: 
 Resolução:    ,   
 
 

  ,

   ,   

  
CIn- UFPE
8
Como Encontrar o Wumpus - Inferência!
1. Aplicando Modus Ponens a f1-1e R1,obtemos:
W1-1W1-2W2-1
2. Aplicando E-eliminação a (1), obtemos três sentenças isoladas:
W1-1W1-2W2-1
3. Aplicando Modus Ponens a f2-1e R2,e em seguida aplicando
E-eliminação obtemos:
W1-1W2-1W2-2W3-1
4. Aplicando Modus Ponens a f1-2e R4,obtemos:
W1-3W1-2W2-2W1-1
CIn- UFPE
9
Como Encontrar o Wumpus - Inferência!
5. Aplicando Resolução Unitária, onde  é W1-3W1-2
W2-2e é W1-1obtemos (do passo 2, temos W1-1):
W1-3W1-2W2-2
6. Aplicando Resolução Unitária, onde  é W1-3W1-2e é
W2-2obtemos:
W1-3W1-2
7. Aplicando Resolução Unitária, onde  é W1-3e é W1-2
obtemos:
W1-3!!!
CIn- UFPE
10
Transformando Conhecimento em Ações
 Objetivo
• Definir regras que relacionem o estado atual do mundo às ações
que o agente pode realizar
 Exemplo de Regra:
• o agente está na caverna (1,1) virado para a direita, e
• o Wumpus está na caverna (2,1), então:
A1-1  Dir  W2-1  avançar
 Com essas regras, o agente pode então perguntar à BC
que ação ele deve realizar:
•
•
•
•
devo avançar?
devo girar para a esquerda?
devo atirar?
...
CIn- UFPE
11
Problemas com o Agente Proposicional
 Existem proposições demais a considerar
• ex.: a regra: “não avance se o Wumpus estiver em frente a você“
só pode ser representada com um conjunto de 64 regras.
 Domínios dinâmicos!
• Quando o agente faz seu primeiro movimento, a proposição A1-1
torna-se falsa e A2-1 torna-se verdadeira.
• Soluções:
– “apagar” A(1,1) - não! => o agente precisa saber onde esteve antes.
– usar símbolos diferentes para a localização do agente a cada tempo t
=> a BC teria que ser “reescrita” a cada tempo t.
 Conclusão
• a expressividade da lógica proposicional é fraca demais para nos
interessar
• com a Lógica de Primeira Ordem, 64 regras proposicionais do
agente Wumpus seriam reduzidas a 1
CIn- UFPE
12
Agentes baseados em
lógica da primeira ordem
CIn- UFPE
13
Motivação
 LPO: o formalismo de referência para representação
de conhecimento, o mais estudado e o melhor
formalizado
 LPO 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
 Embora tenha problemas com
• legibilidade e eficiência inferencial
CIn- UFPE
14
Engajamento ontológico
 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, 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.
CIn- UFPE
15
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 coisas
como tempo, categorias, e eventos.
• neutralidade favorece flexibilidade
CIn- UFPE
16
Engajamento epistemológico
 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 (ou não sei)
 Para tratar incerteza
• Outras lógicas (de n-valoradas, fuzzy, para-consistente, etc.)
• Probabilidade
CIn- UFPE
17
Resumo
Linguagem
Eng. Ontolog. Eng. Epistem.
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
CIn- UFPE
18
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 adoram o jogo rugby, não precisa
explicitamente dizer que os outros não adoram...
CIn- UFPE
19
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
 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 puro
• Agente reativo com estado interno
• Agente baseado em Objetivo
CIn- UFPE
20
Agente Puramente Reativo
CIn- UFPE
21
Agente puramente reativo baseado em LPO
 Possui regras ligando as seqüências de percepções às
ações
• Essas regras assemelham-se a reações,
f,b,c,g,t Percepção([f,b,Brilho,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,Brilho,c,g], t)  Junto-do-Ouro (t)
...
• Regras de ação:
t Junto-do-Ouro (t) Ação(Pegar, t)
CIn- UFPE
22
Agente puramente reativo baseado em LPO
 Mas já sabmos que este agente tem autonomia limitada
(embora seja eficiente)
• Não tem objetivo explícito
• Não planeja (pensa no futuro)
• Não tem representação interna do mundo
 Vamos então evoluir de agente...
•
•
•
•
percepção  modelo  modelo’
Modelo’  modelo’’ (talvez)
Modelo’’  ação
ação  modelo’’  modelo’’’
CIn- UFPE
23
Agente Reativo com Estado Interno
CIn- UFPE
24
Agente reativo com estado interno em LPO
 Problema: como representar as mudanças do mundo...
• Ex. O agente foi de [1,1] para [1,2]
• “Apagar” da BC sentenças que já não são verdade? Perdemos
o conhecimento sobre o passado, impossibilitando previsões de
futuro.
 Solução: Cálculo situacional
• uma maneira de escrever mudanças no tempo em LPO.
• representação de diferentes situações na mesma BC
 O Cálculo situacional implementa regras diacrônicas
• descrevem como o mundo evolui (muda ou não) com o tempo
 Existem também as Regras Síncronas
• relacionam propriedades na mesma situação (tempo),
possibilitando deduzir propriedades escondidas no mundo
CIn- UFPE
25
Cálculo Situacional
 O mundo consiste em uma seqüência de situações
• situação N ===ação===> situação N+1
 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
– ex. no mundo do Wumpus:Parede(0,1) e Parede(1,0)
 Para representar as mudanças no mundo: função Resultado
• Resultado (ação,situação N) = situação N+1
CIn- UFPE
26
Exemplo de cálculo situacional
Result(Forward,S0) = S1
Result(Turn(Right),S1) = S2
Result(Forward,S2) = S3
CIn- UFPE
27
Representando Mudanças no Mundo:
Axiomas estado-sucessor
 Descrição completa de como o mundo evolui (muda e não
muda)
uma coisa é verdade 
[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átil(x))
 (Segurando (x,s) (a  Soltar)]
 É necessário escrever um axioma estado-sucessor para
cada predicado que pode mudar seu valor no tempo
 O que muda no mundo o Wumpus?
• Pegar ouro, e localização/direcionamento do agente
CIn- UFPE
28
Exemplos...
CIn- UFPE
29
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 PróximaLocalização ([x,y ],0) = [x+1,y ]
x,y PróximaLocalização ([x,y ],90) = [x,y+1 ]
x,y PróximaLocalização ([x,y ],180) = [x-1,y ]
x,y PróximaLocalização ([x,y ],270) = [x,y-1 ]
CIn- UFPE
30
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)
CIn- UFPE
31
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 =
Girar(Esquerda))]
CIn- UFPE
32
Deduzindo Propriedades do Mundo
 Agora que o agente sabe onde está, ele pode associar
propriedades aos locais (regra percepção=> modelo):
 l,s Em(Agente,l,s)  Brisa(s)  Ventilado(l)
 l,s Em(Agente,l,s)  Fedor(s)  Fedorento(l)
 Sabendo isto o agente pode deduzir:
• onde estão os buracos e o Wumpus, e
• quais são as cavernas seguras (predicado OK).
 Estas são regras síncronas
• Os predicados Ventilado e Fedorento não necessitam do
argumento de situação
• Elas podem se subdividir em Regras Causais e Regras de
Diagnóstico
CIn- UFPE
33
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
 x choveuEm(x)  molhado(x)
• Sistemas que raciocinam com regras causais são conhecidos
como Sistemas Baseados em Modelos.
CIn- UFPE
34
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.
• Exemplos
– 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
 x molhado(x)  aguadorLigado(x,true)
• Sistemas que raciocinam com regras de diagnóstico são
conhecidos como Sistemas de diagnóstico
 É perigoso misturar esses dois tipos de regras numa
mesma KB!!!
• se choveu é porque o aguador estava ligado
CIn- UFPE
35
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, é preciso
• Programar explicitamente o objetivo corrente
• Conectar ações a objetivos e não diretamente a percepções
• Estabelecer explicitamente a prioridade das ações em função do
objetivo corrente
• Estabelecer explicitamente que as ações de prioridade mais alta
devem ser executadas antes
 Feito isto deixamos a máquina de inferência escolher a
ação mais adequada...
CIn- UFPE
36
Sistema de Ação-Valor
 sistema de ação-valor: Um sistema baseados 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.
CIn- UFPE
37
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
CIn- UFPE
38
Pergunta final
Como implementar esta lógica toda???
CIn- UFPE