CIn- UFPE

1

Agentes Baseados em Lógica

Agentes em lógica proposicionalAgentes 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:

V - caverna visitada

1

2

3

41 2 3

4

ok

okAf

ok

V Vbok

B!

W!

fbfbfb

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 ambienteR1: fWWWR2: fWWWWR3: fWWWW

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: fWWWW

CIn- UFPE

6

Como Encontrar o Wumpus - Inferência!

Como mostrar que BC W é 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 Tabela-

Verdade terá 12 colunas => 212 = 4096

(2) usando regras de inferência!

CIn- UFPE

7

Lógica Proposicional: Regras de Inferência

Modus Ponens:

E-eliminação:

E-introdução:

Ou-introdução:

Eliminação de dupla negação:

Resolução unitária:

Resolução:

,

i

n

...21

n

n

...

,...,,

21

21

n

i

...21

,,

,

diz que a sentença pode ser derivada de por inferência.

CIn- UFPE

8

Como Encontrar o Wumpus - Inferência!

1. Aplicando Modus Ponens a feR1obtemosWWW

2. Aplicando E-eliminação a (1), obtemos três sentenças isoladas:WWW

3. Aplicando Modus Ponens a feR2e em seguida aplicando E-eliminaçãoobtemosWWWW

4. Aplicando Modus Ponens a feR4obtemosWWW2-W

CIn- UFPE

9

Como Encontrar o Wumpus - Inferência!

5. Aplicando Resolução Unitária, onde é WWWe é Wobtemos (do passo 2, temos WWWW

6. Aplicando Resolução Unitária, onde é WWe é WobtemosWW

7. Aplicando Resolução Unitária, onde é We é WobtemosW

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

11Problemas 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 verdadesobre 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çã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,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

Descrição completa de como o mundo evolui (muda e não muda)

uma coisa é verdade [uma ação acabou de torná-la verdadeela 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

Representando Mudanças no Mundo: Axiomas estado-sucessor

CIn- UFPE

28

Exemplos...

CIn- UFPE

29

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

30

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

31

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

32

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

Deduzindo Propriedades do Mundo

CIn- UFPE

33

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.

Tipos de regras

CIn- UFPE

34

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

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

Modularidade das Regras

CIn- UFPE

36

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

37

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

Modularidade: Adequação das Regras

CIn- UFPE

38

Pergunta final

Como implementar esta lógica toda???