Raciocínio Não Monotônico e Abdução
Gustavo Lacerda
Jacques Robin
CIn-UFPE
Agente baseado em conhecimento
dedutivo ou abdutivo
Sensores
Base de Conhecimento Intencional (BCI):
regras, classes,
formulas lógicas
universalmente quantificadas
Não
Monotônica
Ask
Ambiente
Máquina de inferência
dedutiva ou abdutiva
Tell
Ask
Retract
Base de Conhecimento Extensional (BCE):
fatos, objetos
formulas lógicas instanciadas
Atuadores
Tipologia de raciocínio não monotônico
 Raciocínio sobre ações e mudanças em ambientes não estacionários
 Axiomatização em lógica monotônica de raciocínio não monotônico
temporal:
 Cálculo situacional
 Cálculo de eventos
 Revisão não monotônica via retract de base de conhecimento
extensional armazenando apenas fatos presentemente verdadeiros
 Manutenção da verdade da base de conhecimento depois de um retract
 Raciocínio hipotético com informação parcial em ambientes
inacessíveis





Negação por falha em programação em lógica
Herança com sobrescrita em hierarquias de classes
Abdução
Revisão das crenças hipotéticas
Causas da necessidade de tal revisão:
 Recepção sensorial ou comunicativa de novos fatos confirmados, e que contradiz
hipótese default ou abduzida
 Tal contradição pode ser direta ou indireta via dedução
Ações, Situações e Eventos
Cálculo de Situações
denota estados resultantes de ações
Ontologia: tudo são termos lógicos
* situações: A função Result(a,s) denota a situação que resulta
quando a ação a é executada na situação s.
* fluentes: funções e predicados que variam de uma situação para
outra. e.g. ~Holding(G1, S0) quer dizer que o agente não está com
o ouro na situação inicial S0.
* predicados eternos: e.g. Gold(G1) (não se escreve a situação)
Ações, Situações e Eventos
Cálculo de Situações
Além de ações individuais, nós podemos falar sobre
seqüências de ações.
Executar uma seqüência vazia não muda a situação:
Result([],s) = s.
Executar outras seqüências: executar a primeira ação e
depois executar o resto na situação resultante:
Result([a|seq],s) = Result(seq, Result(a,s)).
Ações, Situações e Eventos
Cálculo de Situações
Duas coisinhas a lembrar:
Toda situação, exceto S0, é o resultado de uma
ação ou sequência de ações a partir de S0.
Na nossa notação, a situação é sempre o último
argumento
Ações, Situações e Eventos
Cálculo de Situações
Projeção: dado um estado inicial e uma seqüência de ações,
deduzir o estado final.
Planejamento: dado um estado inicial e um estado final
desejado, responder a pergunta: “que sequência de ações
vai resultar no estado desejado?”.
ou seja, quais valores de seq satisfazem
At(G1, [1,1], Result(seq,S0))?
(o objetivo sendo que o ouro G1 esteja na posição [1,1])
Ações, Situações e Eventos
Cálculo de Situações
Axiomas de Possibilidade: que ações são possíveis numa
dada situação.
e.g. “o agente pode se mover entre locais adjacentes”
At(Agent,x,s) /\ Adjacent(x,y)
=> Poss(Go(x,y),s).
e.g. “se o agente está segurando alguma coisa, ele pode
soltar”
Holding(g,s) => Poss(Release(g),s).
Ações, Situações e Eventos
Cálculo de Situações
Axiomas de Consequências: quais propriedades (fluentes)
vão ser “setadas” como resultado de executar a ação.
e.g. Poss(Go(x,y),s) =>
At(Agent,y,Result(Go(x,y),s)).
e.g. Poss(Grab(g),s) =>
Holding(g,Result(Grab(g),s)).
Ações, Situações e Eventos
Cálculo de Situações
Agora vamos tentar usar um plano no mundo Wumpus:
digamos que o objetivo é pegar o ouro G1, que está em
[1,2], com o agente começando em [1,1].
A ação Go([1,1],[1,2]) funciona, e podemos dizer
que o agente chegou lá:
At(Agent[1,2],Result(Go([1,1],[1,2]),S0))
Agora, precisamos mostrar que é possível o agente pegar
o ouro, ou seja…
Ações, Situações e Eventos
Cálculo de Situações
• Queremos mostrar que é possível o agente pegar o ouro.
• Já sabemos que o agente está em [1,2]
• Só resta confirmar que o ouro também está lá…
“o ouro está em [1,2] na nova situação”
At(G1,[1,2],Result(Go([1,1],[1,2]),S0))
• Infelizmente, nada no nosso KB justifica essa conclusão.
• O problema é que os axiomas de consequências dizem o
que muda, mas não dizem o que fica igual.
• Neste caso, a posição do ouro (antes de pegá-lo)
• Este é o famoso frame problem.
Ações, Situações e Eventos
Frame Problem:
Como representar as coisas que não mudam?
Possíveis Soluções:
Axiomas de Frame: para cada ação, para cada fluente, nós
dizemos se/quando a ação não influencia o fluente.
Desvantagem: o número de axiomas vai ser O(AF).
Axiomas de Estado Sucessor:
Ação é possível =>
(fluente é verdadeiro no estado resultante
 (a ação tornou o fluente verdadeiro
\/ o fluente já era verdadeiro )
Os problemas das ramificações
e da qualificação
 Ramificação:
Se o agente está segurando uma mala, e o agente move,
então a mala move com ele.
Se dentro da mala tem uma banana, ela também move.
E assim por diante...
e.g.: em cima da p.333
 Qualificação:
para modelar o mundo real, uma regra precisa de muitas
condições. Sempre vão existir os casos imprevisíveis,
aonde as regras vão estar erradas ou incompletas.
e.g.: Se a gosma do Wumpus melar o ouro, a ação “Grab”
pode não funcionar.
 Exemplificar os dois no Wumpus com lógica (pegar
exemplo do AIMA)
Limitações do cálculo situacional
 Assume que o agente é o único causador de mudança do
mundo
 Representa tempo de maneira pontual e não intervalar,
indiretamente via situações.
 Representa a topologia do tempo, mas não a geometria, ou
seja a ordem “antes e depois” é preservada, porém
situações não diferenciam entre um intervalo de 1s e de 1
semana.
 “Cálculo de Eventos” supera essas limitações.
Cálculo situacional x de eventos
Regras do Mundo Wumpus
Situation Calculus
Event Calculus
At(o,x,S0) 
((o = Agent  x = [1,1])
 (o = G1  x = [1,2])).
T = holds
holds(at(Agent,[1,1],T0).
holds(at(G1,[1,2],T0).
Agent  G1.
Holding(o,SO).
Gold(G1) 
Adjacent([1,1],[1,2]) 
Adjacent([1,2],[1,1]).
Initiates(Go(x,y),At(Agent,y
),t).
Initiates(Grab(g),Holding(g)
,t).

AIMA pp.330-334
Cálculo de eventos
Ontologia
No Cálculo de Eventos, os predicados não são do domínio. Ver abaixo.
Eventos Discretos: como ações, mas não precisam ser causadas por
um agente
Initiates(e,f,t) indica que o evento e no tempo t causa o
fluente f a ser verdade.
Terminates(w,f,t) indica que o evento e no tempo t causa o
fluente f a não ser verdade.
Happens(e,t) indica que o evento e acontece no tempo t.
Clipped(f,t,t2) diz que f é terminado por algum evento entre
t e t2.
Ontologia do cálculo de eventos
 Eventos Líquidos: Eventos que não acontecem imediatamente.
E(e,i) quer dizer que um evento tipo e ocorreu dentro do intervalo i.
T(e,i) quer dizer que um evento tipo e ocorreu exatamente no intervalo i.
 Estados: Além de descrever processos de mudança contínua, eventos
líquidos podem descrever processos de constância contínua.
T(In(Shankar,NewYork),Today) quer dizer que Shankar passou o dia
inteiro em NewYork.
 Intervalos: Podemos falar sobre as possíveis relações entre dois intervalos
de tempo: Meet, Before, After, During, Overlap.
 Fluentes e objetos: O objeto “USA” é um evento que começou em 1776.
Sua propriedade “President” é um fluente, que representamos assim:
T(President(USA) = GeorgeWashington, AD1790).
Limitações do cálculo de eventos
 Eficiência: para cada situação, você calcula o mundo
inteiro novamente. Alto custo de memória e de
processamento.
Solução: sistemas de planejamento especializados.
Raciocinar sobre crenças e conhecimento
 Seção 10.4 do AIMA
 Quando o agente raciocina sobre suas ações, ele pode:
 usar proposições sobre crenças e proposições, tanto de outros
agente quanto dele mesmo.
 Ações podem ter precondições e efeitos de
conhecimento.
 Por exemplo:
 a ação “discar o telefone de alguém” tem o conhecimento desse
número como precondição;
 enquanto que a ação “procurar um número na lista telefônica” tem
o efeito de saber o número.
Raciocinar sobre crenças e conhecimento
 Seção 10.4 do AIMA
Problema ao representar crenças: transparência
referencial, ou seja, a gente sempre pode substituir um
termo por outro que tenha o mesmo valor.
(Superman = Clark) |=
Believes(Lois,Flies(Superman)) 
Believes(Lois, Flies(Clark))
Raciocinar sobre crenças e conhecimento
 Uma solução é usar a lógica modal epistêmica / doxástica,
que usa operadores referencialmente “opacos”.
 Num agente com um mínimo de racionalidade,
(K(A  B), K(A))  K(B)
 (A, K(A  B)) ou (K(A), A  B) são suficientes
para concluir B, mas não para concluir K(B).
Nós temos
BLois(Flies(Superman)), mas não temos
BLois (Superman = Clark)
 Então não podemos concluir que BLois(Flies(Clark))
(que bom!)
Raciocinar sobre crenças e conhecimento
 Outra solução é usar aspas, com o unique string axiom e
uma função de denotação: então temos
den(“Superman”) = den(“Clark”) = Objeto4892,
enquanto que “Superman”  “Clark”.
Refletir mudanças do ambiente em base de
conhecimento instantânea com retract
 Codificar atualização do modelo do agente de um ambiente não
estacionário usando:
 retract(old fact) e tell(new fact), no lugar de tell(new fact, new
situation)
Porém, surge o problema da manutenção da verdade
 O que foi deduzido a partir do fato retirado, tem que ser por sua
vez retirado
Executamos uma regra tipo Go(x,y):
Com esse tipo de sistema, acontece o seguinte:
 tell(At(Agent,y))
 retract(At(Agent,x))
 simultaneamente
 Regra de ramificação do ouro andando junto ao agente quando está
segurando o ouro permitiu prova a partir de At(Agent,x),
Holding(G1).
 Precisamos retrair também At(G1,y).
Exemplo do problema da manutenção da
verdade no Mundo do Wumpus
 Parece ser eficiente em relação ao cálculo de eventos, já que não faz
cópia de toda base para cada modificação do ambiente.
 Porém pode levar a um processo em cadeia, no qual se desfaz a
maioria das deduções passadas. Repô-las pode ter um custo
equivalente.
 Abordagem ingênua para manutenção de verdade:
 retrair tudo o que foi deduzido após a inclusão do fato que foi retraído
 recomeçar dedução de tudo que foi deduzido depois desse ponto (via
resolução ou encadeamento de regras para frente)
 isto é INEFICIENTE
Manutenção da verdade
baseada em justificativa
 Abordagem JTMS (Justification-Based Truth Maintenance System):
 cada frase na KB é anotada com uma justificação (as frases a partir da
qual ela foi inferida)
 Quando o Retract é executado, todas as frases que usavam a frase
retraída como justificativa são re-avaliadas: se não passarem, elas serão
retraídas também, recursivamente...
 E tudo o que não é mais justificável vai ser retraído nessa reação em
cadeia.
 Porém as frases retraídas não são deletadas, pois elas podem voltar
a ser consideradas no futuro. Desta maneira a cadeia de inferências
é mantida caso a frase volte a ser considerada True.
 Vantagem: mais rápido que o sistema ingênuo quando há hipóteses
que são consideradas True e False alternadamente.
 Limitações: mudança de contexto é ineficiente
 Além de permitir a retração de informação incorreta, TMSs em
geral podem acelerar a análise de múltiplas hipóteses. Por exemplo,
se a cidade das olimpíadas de 2048 mudar de Bucharest para Sibil, a
cadeia pode ser re-usada.
Manutenção da verdade
baseada em suposição
 Cada frase é rotulada com o conjunto de assunções que a torna
verdade. Desta maneira é fácil verificar se uma frase é deduzível ou
não: é equivalente a testar “set containment”.
Circunscrição
Seção 10.7 do AIMA
 Versão mais poderosa da hipótese do mundo fechado
Bird(x)  Abnormal(x)  Flies(x)
Se Abnormal for circunscrito, um raciocinador circunscritivo pode
assumir Abnormal(x) a menos que Abnormal(x) seja sabido.
Republican(Nixon)  Quaker(Nixon).
Republican(x)  Abnormal2(x)  Pacifist(x).
Quaker(x) Abnormal(x)  Pacifist(x).
Como o sistema resolve isso?
* Dois modelos preferidos: Abnormal1(Nixon) e Abnormal2(x). O
sistema fica corretamente indeciso sobre esta frase.
* Porém, podemos usar circunscrição priorizada, aonde uma regra é
dada mais importância que a outra.
Lógica default
Seção 10.7 do AIMA
 Usa regras default para gerar conclusões não-monotônicas.
Bird(x) : Flies(x)/Flies(x).
quer dizer se x é um pássaro, e “x voa” é consistente com a KB, então
“x voa” pode ser concluído por default.
 Obviamente, a conclusão default estará sujeita a revisão.
Abdução
Conhecimento
Prévio Causal
em Intenção
X co(X)  ca(X)  e(X)
Conhecimento
Prévio em Extensão:
• Efeitos Observados
e(a), e(b), ...
• Causais Observadas
Incompletas
co(a), co(b), ...
Abdução
CPCI  CPEC  NCEC |= CPEE
Viés sobre Hipóteses:
X ca(X)
Novo Conhecimento
em Extensão:
Causas Hipotéticas
ca(a), ca(b) ...
Abdução: exemplo
 A partir de:
 Conhecimento prévio causal em intenção:
 X,Y,T loc(agent,X,Y,T)  orientation(0,T)  do(forward,T)  loc(wall,X+1,Y)
 loc(agent,X,Y,T+1)
 Conhecimento prévio em extensão incompleto de causas:
 loc(agent,4,1,1)  orientation(0,1)  do(forward,1)
 Conhecimento prévio em extensão de efeitos observados:
 loc(agent,4,1,2)
 Abduzir:
 Novo conhecimento em extensão de causa hipotética:
 loc(wall,5,1)
Aplicações práticas da abdução em IA

Tirado de p. 1 e 13-14 de Kakas-Denecker (KD), Seção 1.3 de Kakas-Kowalski-Toni (KKT)
 Diagnóstico de Falha (Diagnóstico médico): aqui a teoria descreve o
comportamento “normal” do sistema. Quando se tem a observação
que o comportamento está anormal, busca-se o componente anormal
que explica esse comportamento anormal do sistema.
 Visão de Alto Nível: as hipóteses abduzíveis são os objetos a serem
reconhecidos, e observações são descrições parciais dos objetos.
 Raciocínio Legal: para encontrar casos similares.
 Engenharia de Software: para resolver inconsistências em
requirementos de sistemas
 Constraint Solving Problems: Quebra-cabeças lógicos, N-Queens,
problemas de planejamento no mundo dos blocos, etc.
Formulações lógicas da abdução


Seções 1-3 de KD
Seções 1.2-1.3 de KKT
 Dada uma teoria conhecida P, uma explicação abdutiva para
um query Q é um conjunto  de átomos abduzíveis tal que:
 Visão de derivação:
(P    Q)  (P   | False)  (P    IC)
 Visão de consistência:
(P    Q)  (P    IC | False)
 Esta escolha vai depender do que você quer fazer
Viés sobre hipóteses abdutivas: objetivos

pp. 4-6 de KKT
 Encontrar conjunto de hipótese mais conciso e mais geral
 Encontrar causas explicando os efeitos observados, no
lugar de encontrar co-efeitos das mesmas causas subjacentes
 Encontrar causas mais profundas (básicas), no lugar de
causas intermediárias, efeitos dessas causas profundas
 Encontrar um número mínimo que causas que expliquem o
máximo de observações
 Considerar apenas instâncias de um conjunto prédefinido de predicados chamado de abduzíveis.
 Geralmente escolhidos dentro dos predicados sem definição intencional
na base de conhecimento
 Podem ser estratificados em níveis de preferências
Viés sobre hipóteses: predicados abduzíveis

Exemplo:
grass-is-wet  rained-last-night
grass-is-wet  sprinkler-was-on
shoes-are-wet  grass-is-wet
 Para a observação shoes-are-wet:
A explicação {grass-is-wet} não é básica
enquanto {rained-last-night} e {sprinkler-was-on} são.
 A explicação {rained-last-night, sprinkler-was-on} não é
mínima.
Viés sobre hipóteses abdutivas:
restrições de integridade
 Excluir hipóteses que:
 Violam diretamente um conjunto pré-definido de restrições de
integridades
 Cuja inclusão na base de conhecimento permite deduzir fatos que violam
uma dessas restrições
 Logicamente:
 Exemplo:
At(Wumpus(x))  At(Wumpus(y)  x = y
sprinkler  choveu  false
Viés sobre hipóteses abdutivas: minimização
 Excluir conjunto de hipóteses que podem ser explicadas em termos
de (i.e., deduzidas a partir de) outras hipóteses igualmente válidas
 Exemplo: grassIsWet, quando sabemos sprinkler-was-on
 Preferir conjunto de hipóteses com maior número de efeitos
observados (corroboração)
 Exemplo: formigasDeAsas corrobora chuva e não sprinkler
 Preferir conjunto de hipóteses mais geral
 Exemplo:
 Preferir conjunto de hipóteses mais conciso: quanto menos prerequisitos, mais plausível é que as hipóteses sejam verdade.
 Exemplo:
Dedução
Conhecimento
Prévio Causal
em Intenção
X c(X)  e(X)
Conhecimento
Prévio em Extensão:
Causas Observadas
c(a), c(b), ...
Dedução
CPEC  CPCI |= NCEE
Novo Conhecimento
em Extensão:
Efeitos Previstos
e(a), e(b) ...
Conhecimento
Prévio Diagnóstico
em Intenção
X e(X)  c(X)
Conhecimento
Prévio em Extensão:
Efeitos Observados
e(a), e(b), ...
Dedução
CPDI  CPEE |= NCEC
Novo Conhecimento
em Extensão:
Causas
c(a), c(b) ...
Dedução: exemplos
 A partir de:
 Conhecimento prévio causal
em intenção:
 X,Y,T loc(agent,X,Y,T)
 orientation(0,T)  forward(T)
  loc(wall,X+1,Y)
 loc(agent,X+1,Y,T+1)
 Conhecimento prévio em extensão
de causas observadas:
 loc(agent,1,1,1)  orientation(0,1)
 forward(1)   loc(wall,2,1)
 Deduzir:
 Novo conhecimento em extensão de
efeito previsto:
loc(agent,2,1,2).
 A partir de:
 Conhecimento prévio diagnóstico
em intenção:
 X,Y,T loc(agent,X,Y,T) 
smell(stench,T)  smelly(X,Y).
 X,Y smelly(X,Y) 
loc(wumpus,X+1,Y) 
loc(wumpus,X-1,Y) 
loc(wumpus,X,Y+1) 
loc(wumpus,X,Y-1)).
 Conhecimento prévio em
extensão de efeito observado
 smell(stench,3)  loc(agent,2,2,3)
 Deduzir:
 Novo conhecimento em extensão de
causa hipotética:
 loc(wumpus,3,2)  loc(wumpus,1,2) 
loc(wumpus,2,3)  loc(wumpus,2,1)).
Indução
Conhecimento Prévio
Causal em Intenção
Incompleto
X c(X)  i(X)
Conhecimento
Prévio em Extensão:
• Efeitos Observados
e(a), e(b), ...
• Causais Observadas
c(a), c(b), ...
Indução
CPCI  NCCI  CPEC |= CPEE
Viés sobre Hipóteses:
X,Y i(X)  Y(X)
Novo Conhecimento
Causal Hipotético
em Intenção
X i(X)  e(X)
Indução: exemplo
 A partir de:
 Conhecimento prévio em extensão:
loc(wall,1,1)  loc(wall,0,1)  loc(wall,1,2)  loc(0,2)  ...
loc(wall,4,5)  loc(wall,4,4)  loc(wall,3,5)  loc(wall,3,4)  ...
 Viés sobre hipótese:
 P1,P2,P3,P4  {>,<,=}, C  {, }, Q1,Q2,Q3  {,}:
Q1U1,U2,U3,U4 Q2V1,V2,V3,V4 Q3W
P1(U,V1)  P2(U,V2)  P3(U,V3)  P4(U,V4)  loc(W,U,V)
 Induzir:
 Novo conhecimento em intenção:
 X,Y X<1  X>4  Y<1  Y>4  loc(wall,X,Y)
 Variação:
 Conhecimento prévio em intenção:
 X,Y,H,W X<1  X>H  Y<1  Y>W  loc(wall,X,Y)