CIn- UFPE

1

Agentes que raciocinam com base na lógica de primeira ordem (LPO)

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

CIn- UFPE

2

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

3

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, 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.

CIn- UFPE

4

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

5

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

Para tratar incerteza• Outras lógicas (de n-valoradas, fuzzy, para-consistente, etc.) • Probabilidade

CIn- UFPE

6

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 verdadesobre fatos,

objetos, relações

Grau de crença:0-1

Sistema Formal

Cálculo Teoria

Linguagem Regras de derivação

sintaxe + semântica

Teoremas Axiomas

axiomas + regras de derivação => teoremas

CIn- UFPE

8

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 | ...

CIn- UFPE

9

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.

Predicados denotam Propriedades e Relações:• uma interpretação especifica a que propriedade (predicados

unários) ou relação no mundo o predicado se refere:– ex. o irmão = predicado binário que se refere à relação de

irmandade: Irmão(Caetano, Betânia )– ex. Feio(Maguila) - faz referência à propriedade ser feio

CIn- UFPE

10

LPO: Semântica

Funções denotam Relações Funcionais: • uma interpretação especifica que relação funcional no mundo é

referida pelo símbolo da função, e que objetos são referidos pelos termos que são seus argumentos.

• ligam um objeto (ou mais) a um único objeto no mundo.

• Exemplos: 1) Mãe(Roberto Carlos) -> LadyLaura– função que devolve o nome da mãe do seu argumento.

2) Nota (Zezinho) = 9– devolve a nota do argumento (aluno) Zezinho

Termos denotam Objetos: • são constantes, variáveis ou funções.

CIn- UFPE

11

LPO: Semântica

Sentenças Atômicas: predicados + termos• o valor-verdade de uma sentença depende da interpretação e

do mundo.– Irmão(Caetano, Betânia); - termos simples

casados(PaiDe(Caetano),MãeDe(Betânia)) - termos complexos

Sentenças Complexas:• usa conectivos e quantificadores

• a semântica dessas sentenças é atribuída da mesma maneira que na lógica proposicional:

– semântica dos conectivos + valor-verdade das sentenças individuais.

– Irmão(Caetano, Betânia) Filho(Zeca,Caetano) => Tia(Betânia,Zeca)

CIn- UFPE

12

LPO: Semântica

Igualdade:• declara que dois termos se referem ao mesmo objeto:

– Mãe(Roberto Carlos) = Lady Laura• pode ser visto como a relação identidade...

Exemplo• Para dizer que Huguinho tem pelo menos dois irmãos (Luizinho

e Zezinho), escreve-se: • x, y irmão(Huguinho,x) irmão(Huguinho,y) (x =

y)

CIn- UFPE

13

LPO: semântica dos quantificadores

Universal (• conjunção sobre o universo de objetos:

(x) P(x) é verdade sse P é verdade para todos os objetos no mundo.

• Ex. (x) Gato(x) Mamífero(x)– o valor-verdade é dado pela semântica do quantificador universal e do

conectivo

Existencial ():• disjunção sobre o universo de objetos:

(x) P(x) é verdade sse P é verdade para algum objeto no mundo.• Ex. (x) (y) pessoa(x) mãe(y,x)

Conexão entre os dois• (x) Gosta(x,Banana) (x) Gosta(x,Banana)

CIn- UFPE

14

Leis de De Morgan: Equivalência entre sentenças quantificadas e entre sentenças não quantificadasx)P(x)P P Q P Q )(x)P(x)P P Q) P Q (x)P(x)P P Q P Q)(x)P(x)P P Q P Q)

Moral da história:• Não precisamos de ambos os quantificadores e nem de

ambos os conectivos e ao mesmo tempo!

• Útil para melhorar a eficiência da inferência – ex. cláusulas de Horn (PROLOG)

Lógica de Primeira Ordem: Leis de De Morgan

Sistema Formal em LPO

Cálculo = Cálculo de Predicados

Teoria

Linguagem= LPO

Regras de derivação= regras de inferência

sintaxe + semântica

Teoremas = fatos derivados(axiomas + regras de derivação)

Axiomas= fatos + regras

DiacrônicasSíncronas

causais de diagnóstico

BC = fatos e regras básicos (só axiomas!)MT = fatos particulares à instância do problema e fatos derivadosMI = regras de inferência

CIn- UFPE

16Uso de LPO em agentes baseados em

conhecimento

função Agente-BC(percepção) retorna uma açãoTellTell(BC, Percepções-SentençaPercepções-Sentença(percepção,t))

ação AskAsk(BC Pergunta-AçãoPergunta-Ação(t))

TellTell(BC, Ação-SentençaAção-Sentença(ação,t))

t t + 1

retorna ação

Onde...• função Pergunta-Ação Pergunta-Ação cria uma query tal como: a Ação(a,6)

• função ASKASK devolve uma lista de instanciações:{a / Pegar} - Pegar é atribuída à variável ação.

• TELLTELL gravar a ação escolhida na BC.

CIn- UFPE

17

LPO em agentes baseados em conhecimento

No mundo :Pedro possui um cachorro.Todo dono de cachorro é um protetor dos animais.Nenhum protetor dos animais mata um animal.

Na Lógica:A. x cachorro(x) possui(Pedro,x)B. x (y cachorro(y) possui(x,y)) protetorAnimais(x)C. x protetorAnimais(x) y animal(y) mata(x,y)

Representação

do mundoRepresentação

lógica inicial

Representação

lógica atualizada

Mecanismo Mecanismo

de inferênciade inferênciaConhecimento de Conhecimento de

lógicalógica

CIn- UFPE

18

LPO em agentes baseados em conhecimento

Axiomas = fatos e regras básicos e fatos do problema• exs. Pai(Caetano,Zeca), Mãe(Canô, Caetano)• (x,z) Avó(x,z) (y) Mãe(x,y) (Mãe(y,z) Pai(y,z))

Teoremas = fatos derivados• ex. Avó(Canô, Zeca)

Pesquisa = ASK • Quantificador : a resposta é booleana

– ASK(BC, Irmã(Betânia,Caetano)) -> true– ASK(BC, x (Irmã(x,Caetano) Cantora(x))) -> false

• 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}

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, 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

CIn- UFPE

20

Agente 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,Luz,c,g], t) Ação(Pegar, t)

Essas regras dividem-se entre • Regras de (interpretação) da percepçãob,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)

CIn- UFPE

21

Limitações do agente reativo

um agente ótimo deveria:• recuperar o ouro ou• determinar que é muito perigoso pegar o ouro e• em qualquer dos casos acima, voltar para (1,1) e sair da

caverna.

Um agente reativo nunca sabe quando sair,• 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.

CIn- UFPE

22

Agentes LPO com Modelo do Mundo

Nossos agentes podem ter um comportamento ótimo se:• todas as percepções são gravadas na BC, e• existem regras para lidar com percepções passadas e

presentes.• Porém, escrever essas regras dá trabalho... e é ineficiente

Solução: • modelo interno do mundo = sentenças sobre o mundo atual, em

vez de percepções passadas– “às 4h30 pegou o ouro” ===> “está com o ouro”

• as sentenças serão atualizadas quando:– receber novas percepções e realizar ações– ex. chaves no bolso, pegou o ouro,..

• Regras diacrônicas: descrevem como o mundo muda através do tempo.

CIn- UFPE

23Representando Mudanças no Mundo: abordagens

“Como representar as mudanças realmente?• O agente foi de [1,1] para [1,2]

“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.

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)?”

Solução: Cálculo situacional• uma maneira de escrever mudanças no tempo em LPO.• representação de diferentes situações na mesma BC

CIn- UFPE

24

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

25

Exemplo de cálculo situacional

Result(Forward,S0) = S1

Result(Turn(Right),S1) = S2

Result(Forward,S2) = S3

CIn- UFPE

26

Representando Mudanças no Mundo

As ações são descritas pelos seus efeitos• especificando-se as propriedades da situação resultante da

realização da ação• por meio dos axiomas de efeito e dos axiomas frames.

Axiomas de efeito: descrevem como o mundo muda• O agente estará segurando algo se ele acabou de pegá-lo

x,s Presente(x,s) Portável(x) Segurando(x,Resultado(Pegar,s))

• o agente não estará segurando nada depois de realizar uma ação de Soltar:

x,s Segurando(x,Resultado(Soltar,s))

CIn- UFPE

27

Axiomas de Frames: descrevem como o mundo permanece igual.• Se o agente está segurando algo e ele não o soltou, então ele

continua segurando-o a,x,s Segurando(x,s) (aSoltar)

Segurando(x,Resultado(a,s))

• Se o agente não está segurando algo e ele não pegou nada, então ele continua com as mãos vazias

a,x,s Segurando(x,s) (a Pegar Presente (x,s) Portável(x))

Segurando(x,Resultado (a,s))

Como Saber se o Agente está com o Ouro?

CIn- UFPE

28

Axioma de efeito + axioma de frames = axioma 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.

Axiomas estado-sucessor

CIn- UFPE

29

O ‘Frame Problem’ e outros

Problema representacional dos axiomas de frame: • proliferação de axiomas de frames• foi tema de calorosos debates durante anos...• solução: uso de axiomas estado-sucessor

Problema inferencial dos axiomas de frame: • excesso de inferências (para atualizar todo o mundo)• solução: usar planejamento (só atualiza o estrito necessário)

Problema de Qualificação: • dificuldade em enumerar todas as pré-condições de sucessor

de uma ação

Problema da Ramificação: • dificuldade em enumerar todos os efeitos de uma ação

CIn- UFPE

30

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 ]

Guardando localizações

CIn- UFPE

31

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)

Guardando localizações

CIn- UFPE

32

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 agentea,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))]

Guardando localizações

CIn- UFPE

33

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)

Sabendo isto o agente pode deduzir:• onde estão os buracos e o Wumpus, e• quais são as cavernas seguras (predicado OK).

Os predicados Ventilado e Fedorento não necessitam do argumento de situação

Deduzindo Propriedades do Mundo

CIn- UFPE

34

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)• axiomas que possibilitam deduzir propriedades escondidas no

mundo

Existem dois tipos principais de regras síncronas:• Regras Causais• Regras de Diagnóstico.

Tipos de regras

CIn- UFPE

35

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.

Modularidade das Regras

CIn- UFPE

36

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.

Modularidade: Adequação das Regras

CIn- UFPE

37

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.

Sistema de Ação-Valor

CIn- UFPE

38

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.

Agentes Baseados em Objetivos

CIn- UFPE

39

(1) 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)?

(2) 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.

Como encontrar seqüências de ações

CIn- UFPE

40

(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üênciasações e conseqüências ações e conseqüênciasações e conseqüências

sair das cavernas

Agentes Baseados em Objetivos