Agentes Baseados na Lógica Proposicional Capítulo 7, AIMA 2ed. Alzennyr Cléa G. Silva

Agentes Baseados na Lógica Proposicional

Capítulo 7, AIMA 2ed.

Alzennyr Cléa G. SilvaAlzennyr Cléa G. Silva

MCI - Prof. Jacques Robin

Base de Conhecimento

Base de Conhecimento = conjunto de sentenças representadas em uma linguagem formal.

Instruções: TELL (construção da BC) ASK (resposta obtida a partir da BC) as vezes também RETRACT (revisão da BC)

Base de conhecimento

Máquina de Inferência

Conteúdo específico do domínio

Algoritmos independente do domínio

Representação de Conhecimento usando a Lógica


Definição Uma sentença lógica não significa nada por si só...

É necessário estabelecer a correspondência entre fatos e sentenças, fixando seu significado através de uma interpretação da sentença.

Exemplo:

“O Papa já está no Rio” mensagem secreta trocada entre dois agentes do FBI que

significa que os documentos sobre as armas atômicas do Iraque (o Papa) foram entregues ao Pentágono (o Rio) a salvo (já está).


Definição Lógica é uma linguagem formal para representação

de informação Sintaxe define as sentenças lógicas Semântica define o significado das sentenças


Interpretação

Interpretação uma sentença é verdadeira sob uma dada interpretação se o

“estado do mundo” (state of affairs) que ela representa se verifica. Valor verdade depende da interpretação da frase e do estado do

mundo real que ela representa (ou modela)

Exemplo “O papa está no Rio” pode ser verdade na interpretação

anteriormente dada se de fato, no mundo do FBI, tais documentos foram recebidos pelo Pentágono a salvo.

“O papa está no Rio” , sob a interpretação “Papa = João Paulo II”, “Rio = Cidade do Rio de Janeiro”, “está = verbo estar”, é falsa pois ele está em Roma.

Nesta ótica, uma sentença pode ser: válida, satisfazível ou insatisfazível.


Validade e Satisfatibilidade

Sentença válida (tautologia) verdadeverdade sob todastodas as possíveis interpretações em todos os

mundos possíveis. Ex. “No mundo Wumpus: existe um buraco em (1,2), ou não

existe um buraco em (1,2)” é sempre verdade, independente da interpretação e do valor-verdade de “existe um buraco em (1,2)” em qualquer mundo possível.

Sentença insatisfazível falsafalsa sob todastodas as possíveis interpretações em todos os mundos

possíveis. Ex: sentenças contraditórias são insatisfazíveis: “existe um

buraco em (1,2), e não existe um buraco em (1,2)” Sentença satisfazível

verdadeverdade para alguma alguma interpretação em algum mundo


Validade e Satisfatibilidade

SentençasSentençasVálidasVálidas

SentençasSentençasSatisfazíveisSatisfazíveis

SentençasSentençasInsatisfazíveisInsatisfazíveis


Derivabilidade (entailment) Derivabilidade significa que uma sentença

segue logicamente de um conjunto de outras sentenças:

Sentença é derivávelé derivável a partir da base de conhecimento KB (conjunção de sentenças) sss é verdadeira em todostodos os mundos possíveis onde KB é verdadeira.


Derivabilidade (entailment)

derivasentenças

Representação sem

ântic

a

sentenças

Mundofatos

sem

ântic

a

segue-sefatos


Raciocínio: Inferência em Computadores

O único conhecimento que o sistema tem sobre o mundo é aquele explicitamente codificado na BC:

não sabem que interpretação foi dada às sentenças na BC, e não sabem nada sobre o mundo, apenas o que existe na BC.

Então, como responder à pergunta “Está OK mover o agente para (2,2)?”

Verificando a partir da BC se a sentença abaixo pode ser derivada “(2,2) está OK”.

O processo de inferência deve mostrar que a sentença abaixo é válida BC ok(2,2) “Se a BC é verdade, então (2,2) está OK”


Regras de Inferência

Modus Ponens:

E-eliminação:

E-introdução:

Ou-introdução:

Eliminação de dupla negação:

Resolução unidade:

Resolução:

,

i

n

...21

n

n

...

,...,,

21

21

n

i

...21

,,

,

diz que a sentença pode ser deduzida da BC constituída pelos


Propriedades da Inferência

A inferência pode ter várias propriedades... Corretude, completude, composicionalidade, monotonicidade e

localidade. Corretude (sound)

gera apenas sentenças válidas Completude

gera todas as sentenças válidas Composicionalidade

o significado de uma sentença é uma função do significado de suas partes.

B1-2 significa: existe um buraco na caverna (1,2) B2-3 significa: existe um buraco na caverna (2,3) B1-2 B2-3 significa composicionalmente: existe um buraco

na caverna (1,2) e um outro na caverna (2,3) Não composicionalmente, B1-2 B2-3 poderia significar: hoje

é feriado e é o dia do funcionário público


Lógica: Inferência Uma Lógica é dita monotônica quando

Tudo que era verdade continua sendo depois de uma inferência se BC1 |= a então (BC1 U BC2) |= a todas as sentenças derivadas da BC original são ainda

derivadas da BC composta pelas novas sentenças inferidas e.g., Lógica Proposicional e de Primeira Ordem. contra-exemplo: Teoria da Probabilidade

Localidade regras como Modus Ponens:

Se é verdade e é verdade, então é verdade são ditas locais porque sua premissa só necessita ser comparada

com uma pequena porção da BC (2 sentenças).


Lógica: Inferência

Localidade e composicionalidade são centrais na construção de sistemas por possibilitar modularidade.

Modularidade favorece a reusabilidade e a extensibilidade do sistema.


Validade de sentenças

A validade pode ser verificada de duas maneiras Tabelas-Verdade Regras de inferência

Tabelas-Verdade ex. Validade de ((P H) H) P ?

P H (P H) ((P H) H) ((P H) H) P

F F F F T

F T T F T

T F T T T

T T T F T


Validade de sentenças Regras de inferência:

uma regra de inferência é sound (preserva a verdade) se a conclusão é verdade em todos os casos onde as premissas são verdadeiras.

((P H) H) P ?

((P H) (H H)) P

((P H) false) P

(P H) P

(P H) P

P H P

True H

True


Complexidade Checar se um conjunto de sentenças é satisfazível é um problema NP-

completo tabela verdade para uma sentença envolvendo n símbolos tem 2n

colunas (exponencial!) Cláusulas de HornCláusulas de Horn

Classe de sentenças úteis que permitem inferência em tempo polinomial

P1 P2 P3 ... Pn Q ou, P1 P2 P3 ... Pn Q é usada em Prolog

2 casos especiais das cláusulas de Horn Fatos,Fatos, quando n = 1 e P1 = true

true Q, ou simplesmente Q Restrições de integridadesRestrições de integridades, quando Q = false

P1 P2 P3 ... Pn F ou, P1 P2 P3 ... Pn não são permitidas em Prolog

Formalização de Agentes Baseados na Lógica Proposicional


BC para o Mundo do Wumpus

A Base de Conhecimento consiste em: sentenças representando as percepções do agente sentenças válidas derivadas a partir das sentenças das percepções regras utilizadas para derivar novas sentenças a partir das sentenças

existentes Símbolos:

Ax-y-t significa que “o agente está na caverna (x,y), no instante t” 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 luz na caverna (x,y)”



Com base nas percepções do estado abaixo, a BC deverá conter as seguintes sentenças:

1

2

3

41 2 3

4

ok

okAf

ok

V Vbok

B!

W!

fbfbfb



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.

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


Modelos Modelos: mundos estruturados formalmente nos quais

sentenças podem ser avaliadas mm é modelo de uma sentença se é verdadeira em mm. M(): conjunto de todos os modelos de .

Então KB sse M(KB) M()

M()


Modelos – Mundo Wumpus

Ex: o Mundo de Wumpus é um modelo da sentença “B1-2” sob a interpretação de que existe um buraco na caverna (1,2).

Podem existir muitos modelos para “B1-2”, basta que eles tenham um buraco em (1,2).


Checagem de Modelo – Mundo Wumpus



KB = regras do mundo wumpus + observações



KB = regras do mundo wumpus + observações 1 = “[1,2] é seguro”, KB 1 , provado pela checagem do modelo



KB = regras do mundo wumpus + observações



KB = regras do mundo wumpus + observações 2 = “[2,2] é seguro”, KB 2


Encadeamento Para Frente e Para Trás Forma Horn

KB = conjunção de cláusulas Horn Cláusula horn =

Símbolo; ou Conjunção de símbolos símbolo

e.g.


Encadeamento Para Frente Idéia: descarte qualquer regra cujas premissas são satisfeitas

na KB, adicione sua conclusão à KB, até que a regra procurada seja encontrada.


Encadeamento Para Frente (exemplo)














Encadeamento Para Trás Idéia: para provar Q por BC,

cheque se Q já é conhecido, ou

prove por BC todas as premissas de alguma

regra concluindo Q.

Cuidados: Evite loops: cheque se novo sub-objetivo já está na pilha de

objetivos Evite trabalho repetido: cheque se novo sub-objetivo

1. Já foi provada como true, ou

2. Já falhou.


Encadeamento Para Trás (exemplo)






















Encadeamento para Frente x Encadeamento para Trás

• EF é dirigida pelos dados, fc. Automático, processamento não consciente. Pode fazer muito trabalho irrelevante para o objetivo procurado

• ET é dirigido pelo objetivo, apropriado para resolução de problemas.e.g. “Onde estão minhas chaves?”Envolve backtracking, pode ser caro, mais muitas vezes bem de complexidade sub-linear no tamanho da BC

• EF pode ser usado para pré-calcular cache de objetivos freqüentes

Adequação depende:• da naturalidade de formalizar o problema a partir de dados ou do objetivo• da necessidade de encontrar apenas uma ou todas as soluções


Considerações Finais

Agentes Lógicos aplicam regras de inferência na BC para derivar novas sentenças;

Encadeamento PF e PT são lineares para cláusulas Horn;

Lógica Proposicional: Não é capaz de atender a questões como: “qual

ação devo tomar?” Pode apenas responder questões como: “devo ir

em frente?”, “devo virar para esquerda?”, etc. Lógica proposicional não possui mecanismos para

generalizar proposições;

Proposições são dependentes do tempo e o tamanho das proposições pode assumir grandes dimensões.

Documents

Agentes Baseados na Lógica Proposicional Capítulo 7, AIMA 2ed. Alzennyr Cléa G. Silva