1
Agentes Baseados em Conhecimento
DI/UFPE
Experimento “Robô humano”
 Partes:
• 1 Cérebro (1 pessoa)
• 2 Braços (1 por pessoa = 2 pessoas)
• 1 Sistema de visão (1 pessoa)
 Objetivo:
• Os braços devem localizar e segurar um determinado objeto
 Cérebro:
• não pode ver
• pode fazer perguntas e dar ordens aos braços e à visão:
- controla os braços indicando
– deslocamento em uma direção (ângulo no sentido horário ou antihorário) e distância dadas
– ângulos de giro na vertical e na horizontal
– força a aplicar para segurar o objeto
- controla o sistema de visão
– pedindo que se desloque para obter outros ângulos de visão
DI/UFPE
2
Experimento “robô humano”
 Braços
•
•
•
•
não podem ver
não devem ouvir (obedecer) o que diz o sistema de visão
têm tato pouco refinado
podem responder apenas “sim” ou “não” ao cérebro
- ex. estão tocando algo?
• seguem comandos do cérebro
 Sistema de visão
• não pode fornecer informação sem ter sido perguntado pelo
cérebro
• pode distinguir diferentes objetos e estimar distâncias
• pode mover-se de forma a obter informações visuais a partir
de diferentes ângulos
DI/UFPE
3
Experimento “Robô humano”
 Voluntários?
• Braços e olhos (sistema de visão) saem da sala...
• Cérebro recebe a tarefa
 Conclusões?
•
•
•
•
Um modelo do mundo é imprescindível
Conhecimento prévio do mundo é importante
Coordenar diferentes sistemas é complicado
Feedback visual e de força são imprescindíveis
- A maioria dos sistemas de visão não é móvel
• É difícil construir um plano sem conhecer as pré-condições
DI/UFPE
4
De volta ao exemplo de West...
 West é criminoso ou não?
• “A lei americana diz que é proibido vender armas a uma nação
hostil. Cuba possui alguns mísseis, e todos eles foram vendidos
pelo Capitão West, que é americano”
 Como resolver automaticamente este problema de
classificação?
 Segundo a IA (simbólica), é preciso:
• Identificar o conhecimento do domínio (modelo do problema)
• Representá-lo utilizando uma linguagem formal de
representação
• Implementar um mecanismo de inferência para utilizar esse
conhecimento
DI/UFPE
5
A) Todo americano que vende uma arma a uma nação hostil é criminoso
B) Todo país em guerra com uma nação X é hostil a X
C) Todo país inimigo político de uma nação X é hostil a X
D) Todo míssil é um arma
E) Toda bomba é um arma
F) Cuba é uma nação
G) USA é uma nação
H) Cuba é inimigo político dos USA
I) Irã é inimigo político dos USA
novo
conhecimento
J) West é americano
K) Existe um mísseis em cuba
L) Os mísseis de cuba foram vendidos por West
M) Cuba possui um míssel M1
O) M1 é uma arma
P) Cuba é hostil aos USA
Q) M1 foi vendido a Cuba por West
R) West é crimonoso
- de K
- de D e N
- de F, G, H e C
- de L, M e N
- de A, J, O, F, P e Q
conhecimento
do problema
conhecimento prévio
Solucionando o caso do cap. West (linguagem natural)
7
Questões levantadas pelo exemplo
 Seria possível resolver esse problema com busca?
 Por que?
DI/UFPE
Limitações da resolução de
problemas por Busca
 Agentes de Busca são muito eficientes na solução de
problemas que podem ser formalizados por:
• 1. um estado inicial;
• 2. ações (operadores);
• 3. um conjunto de estados finais.
 Porém, não são capazes de resolver problemas que
exigem raciocínio baseado em conhecimento sobre o
mundo:
• porque seu modelo do mundo é pobre e o raciocínio é limitado
• e.g., diagnóstico médico, controle aero-espacial, prova de
teoremas, sistemas especialistas em geral,...
• mesmo em casos aparentemente solucionáveis por busca
(planejamento), pode ser preciso adicionar conhecimento
explícito
DI/UFPE
8
9
Comprar banana, leite e um liqüidificador
Ir ao banco
Pagar contas
Ir à escola
Pegar dinheiro
Ir dormir
Assistir aula
Levantar
começo
Ler um livro
Ler um livro
Sentar na cadeira
Ir ao supermercado
Etc...
Comprar queijo
Comprar banana
...
Fim
Comprar atum
 Como representar que “é no supermercado que se vende banana”?
 A função heurística apenas escolhe o estado mais próximo do objetivo.
• Não permite descartar ações a priori ( adivinhação)
DI/UFPE
10
Plano de aula
 Agentes Baseados em Conhecimento (BC)
• definição geral
 Categorias de conhecimento e de raciocínio
 Linguagens de representação de conhecimento
 Mecanismos de raciocínio
 Arquitetura e algoritmo básico do Agente BC (caso
dedutivo)
 Sistemas baseados em conhecimento
DI/UFPE
11
Agentes Baseados em Conhecimento
 São agentes que
• conhecem seu mundo, e
• raciocinam sobre suas possíveis ações
 Sabem:
•
•
•
•
•
•
DI/UFPE
o estado atual do mundo (propriedades relevantes)
como o mundo evolui
como identificar estados desejáveis do mundo
como avaliar o resultado das ações
conhecimento sobre conhecimento (meta-conhecimento)
etc.
12
Categorias de Conhecimento
 Procedimental:
• fatos e seqüências de instruções para manipular esses fatos
- ex.: como desmontar uma bicicleta
 Declarativo:
• representação descritiva dos fatos, relacionamentos e regras
- as partes de uma bicicleta e seus relacionamentos
- o pai do pai é o avô
 Episódico:
• fatos vividos, casos, exemplos...
- ex. D. Maria tem dor de cabeça e dengue
 Meta-conhecimento:
• conhecimento sobre o conhecimento disponível
- ex. eu não sei Astronomia
DI/UFPE
13
Categorias de Raciocínio (Inferência)
 Dedução: fatos + regras de inferência => novos fatos.
• ex. Em todo lugar que há fogo, há fumaça. Aqui tem fogo,
logo...
 Abdução: inverso da dedução.
• ex. Se há fumaça, há fogo.
 Indução: parte-se dos fatos para gerar regras.
• ex. Se Sr. Antônio, assim como D. Maria, tem dor de cabeça
e dengue, então todo mundo que tem dengue, tem dor de
cabeça.
 Analógico: casos + regras de adaptação
• ex.: Para construir este hospital, vou me basear no projeto
daquele outro
DI/UFPE
14
Agentes Baseados em Conhecimento (dedutivo)
 Principais componentes:
• Base de Conhecimento
• Mecanismo de Inferência
 Base de Conhecimento:
• contém sentenças
- representações de fatos e regras expressas em uma Linguagem
de Representação de Conhecimento
• conhecimento em forma “tratável” pelo computador
- ex. míssil é uma arma, M1 é um míssil
 Mecanismo (motor) de Inferência:
• responsável por inferir, a partir do conhecimento da base,
novos fatos ou hipóteses intermediárias/temporárias
- ex. M1 é uma arma
DI/UFPE
15
Linguagens de Representação do Conhecimento
 Linguagens de programação:
• são precisas, porém não são suficientemente expressivas
 Linguagens naturais:
• são muito expressivas, porém são ambíguas
 Linguagens de representação de conhecimento (LRC):
• estão entre as anteriores...
• existem 3 grandes classes:
- linguagens (predominantemente) declarativas
- linguagens procedimentais
- linguagens híbridas
DI/UFPE
Ciclo de vida dos sistemas baseados em
conhecimento
Nível de
Conhecimento
Nível Lógico
Nível de
Implementação
AQUISIÇÃO
linguagem natural
FORMALIZAÇÃO
linguagem de
representação de
conhecimento
linguagens de
implementação
IMPLEMENTAÇÃO
BC
REFINAMENTO
DI/UFPE
16
Tipos de Linguagens de Representação do
Conhecimento (LRC)
 Linguagens procedimentais: dizem como
• representam fatos (através de constantes ou variáveis
instanciadas) e seqüências de instruções para manipular
esses fatos
• representação e implementação estão intrinsecamente ligados
- ex. C, Pascal, Lisp, ...
 Linguagens declarativas: dizem o que
• representam fatos, seus relacionamentos e regras
(conhecimento puro)
- necessita ser processado por algum código!)
• Linguagens Lógicas (ex. Lógica de 1a ordem)
• baseadas em Regras (ex. regras se-então)
• baseadas em Objetos (ex. frames, ontologias, etc.)
DI/UFPE
17
Tipos de Linguagens de Representação do
Conhecimento
 Linguagens híbridas
•
•
•
•
•
DI/UFPE
objetos + regras
lógica + objetos
lógica + objetos + regras
etc...
Vocês estudam em IA Simbólica (eletiva)
18
19
Linguagens de Representação do Conhecimento
 Uma Linguagem de Representação do Conhecimento é
definida por:
1) uma sintaxe, que descreve as configurações que podem
constituir sentenças daquela linguagem;
2) uma semântica, que liga cada sentença aos fatos no mundo
que ela representa
- cada sentença faz uma afirmação a respeito do mundo;
- o agente acredita nas sentenças que correspondem a sua
configuração interna.
 E geralmente ...
• tem um mecanismo de inferência associado
DI/UFPE
20
Representação & Raciocínio
 Raciocínio é um processo de construção de novas sentenças
a partir de sentenças existentes.
 Raciocínio plausível (sound):
• garante que as novas sentenças representam fatos que se
seguem dos fatos representados pelas sentenças existentes na
BC.
• implementa a relação de “implicação” entre sentenças
fatos
segue-se
fatos
Mundo
Representação
sentenças
DI/UFPE
implica
sentenças
A) " x,y,z Americano(x) Arma(y) Nação(z) Hostil(z) Vende(x,z,y)
 Criminoso(x)
B) " x Guerra(x,USA) Hostil(x)
C) " x InimigoPolítico(x,USA) Hostil(x)
D) " x Míssil(x) Arma(x)
E) " x Bomba(x) Arma(x)
F) Nação(Cuba)
G) Nação(USA)
H) InimigoPolítico(Cuba,USA)
I) InimigoPolítico(Irã,USA)
novo
conhecimento
J) Americano(West)
K) $ x Possui(Cuba,x) Míssil(x)
L) " x Possui(Cuba,x) Míssil(x)  Vende(West, Cuba,x)
M) Possui(Cuba,M1)
N) Míssil(M1)
O) Arma(M1)
P) Hostil(Cuba)
Q) Vende(West,Cuba,M1)
R) Criminoso(West)
conhecimento
do problema
conhecimento prévio
Solucionando o caso do cap. West (Lógica de primeira ordem)
- Eliminação: quantificador existencial e
conjunção de K
- Modus Ponens a partir de D e N
- Modus Ponens a partir de C e H
- Modus Ponens a partir de L, M e N
- Modus Ponens a partir de A, J, O, F, P e Q
22
Implementando raciocínio (dedutivo): Arquitetura
Agente
ambiente
sensores
Tell
Base de Conhecimento
Máquina de Inferência (Raciocínio)
Mecanismo de Aprendizagem - opcional
Ask
Tell
efetuadores
Ask - consulta a BC
Tell - adiciona novas sentenças à BC
Retract - retira sentenças da BC
DI/UFPE
Implementando raciocínio (dedutivo):
laço principal de TODO agente
 Programa Agente Baseado em Conhecimento
t := 0
//contador de tempo
enquanto Agente-BC vivo, faça
Tell(BC, Percepções-Sentença(percepção,t))
ação <- Ask(BC, Pergunta-Ação(t))
Executa(ação)
Tell(BC, Ação-Sentença(ação,t))
t <- t + 1
Mas este laço não é geral demais?
Aguardem os próximos capítulos...
DI/UFPE
23
24
Direções do raciocínio dedutivo
 Raciocínio progressivo
• dos dados à conclusão - data-driven inference
• as regras da BC são usadas para gerar informação nova
(novos fatos) a partir de um conjunto inicial de dados
• os fatos gerados passam a fazer parte da BC
- ex.: criminoso(West).
 Raciocínio regressivo
• da hipótese aos dados - goal-directed inference
• usa as regras da BC para responder a perguntas
• busca provar se uma asserção é verdadeira
- ex.: criminoso(West)?
• só processa as regras relevantes para a pergunta (asserção)
DI/UFPE
Tipologia de sistemas baseados em
conhecimento
25
 Cada LRC (predominantemente declarativa) tem, pelo menos, um
sistema de raciocínio associado
Principais sistemas de
raciocínio declarativos/dedutivos
lógica
Provadores de teorema
Programação em lógica
regras
objetos
Sistemas Redes Semânticas
Sistemas Frames
Sistemas de Lógica descritiva
Sistemas OO
Sistemas de produção
Sistemas de manutenção da verdade
DI/UFPE
híbridos
regras+objetos
lógica+objetos
lógica+objetos+funções
Sistemas baseados em conhecimento:
implementando regras
 Provadores de teoremas
• Muito expressivos e completamente declarativos
• Pouco intuitivos e ineficientes com grandes BC
 Linguagens de Programação Lógica
• Restringem a lógica, não permitindo o tratamento completo
da negação, da disjunção e/ou da igualdade.
• ASK0 decompõe-se em ASK1 & ... & ASKN
• Geralmente usam Encadeamento Regressivo.
- Exemplos: Prolog, Datalog, XSB, MRS
DI/UFPE
26
Sistemas baseados em conhecimento:
implementando regras
 Sistemas de Produção
•
•
•
•
•
Restringem a lógica mais ainda, sem objetos complexos
permitem raciocínio não monótono,
SE ASK1 & ... & ASKN ENTÃO TELL | RETRACT | FAZ
mais intuitivo, porém sem semântica lógica clara,
Geralmente usam Encadeamento Progressivo.
- Exemplos: OPS-5, CLIPS, SOLAR.
 Sistemas de manutenção da verdade
• Truth-maintenance systems (TMS)
• Garante base de conhecimento consistente com raciocínio
não monótono
DI/UFPE
27
Sistemas baseados em conhecimento:
implementando objetos
 Sistemas de Redes Semânticas
• BC: nós (representando objetos) conectados por arcos
(representando a relação binária entre eles).
• Raciocínio baseado apenas na herança, não na dedução lógica
- Exemplos: KRL, SNEPS, NETL, Conceptual Graphs.
 Sistemas Frames
• Consistem em uma hierarquia de frames (quadros) conectados
por atributos, onde os frames representam objetos do mundo e
atributos usualmente a relação entre eles.
• ~ Redes Semanticas + Procedimentos dirigidos pelos dados
• Muito expressivo, sem semântica clara
- Exemplos: KRIPTON, OWL, FRAIL, KODIAK.
DI/UFPE
28
Sistemas baseados em conhecimento:
implementando objetos
 Linguagens de classes
• hierarquia de objetos encapsulando comportamento e
estrutura e com comunicação via envio de mensagens
• sem motor de inferência built-in, nem semântica clara
- Exemplos: Smalltalk, Lisp-CLOS, Java, ...
 Sistemas de Lógica Descritiva
• Expressam e raciocinam com definições complexas de
objetos e classes, e relações entre eles, utilizando redes
semânticas como princípio de organização.
• ~ Redes semântica com semântica lógica bem definida +
classificação automático de conceitos e instâncias
- Exemplos: KL-ONE, CLASSIC, LOOM.
DI/UFPE
29
Sistemas baseados em conhecimento:
abordagem híbrida
 Sistemas híbridos
• combina as vantagens de cada sistema e ainda mais
algumas de engenharia de software
 Exemplos
• eoops: objetos + regras (C++/Clips, Smalltalk/NéOpus,
Java/Jeops,...)
• lógica + objetos (ObjLog),
• lógica + objetos + funções (LIFE), etc...
DI/UFPE
30
Principais critérios de avaliação de uma
Linguagem de Representação de Conhecimento
 Expressividade: o que é possível dizer facilmente na linguagem?
 Inferência disponível: que tipo de inferência é possível fazer na
linguagem?
 Corretude: a inferência é plausível (sound)? A semântica é bem
definida?
 Completude: a inferência é completa?
 Eficiência inferencial: a inferência se realiza em um tempo razoável?
 Modularidade: é fácil identificar e reutilizar partes do conhecimento?
 Legibilidade: é fácil de ler e entender o que está escrito?
 Eficiência aquisicional: é fácil adicionar conhecimento?
 Abertura: é um sistema fechado o pode ser conectado com outros
serviços (BD, Internet, GUI, etc..)
DI/UFPE
31