Fred Freitas - [email protected] -Sistemas Multiagentes
SISTEMAS MULTIAGENTES
Fred Freitas [email protected]
1
Índice





IA e SD
Agentes
Inteligência centralizada x
distribuída
Motivações
Noções fraca e forte de agente









Resolução distribuída de
problemas - RDP
Sistemas Multiagentes - SMAs
SMAs Reativos
SMAs Cognitivos
Teoria dos Atos da Fala
KSE:KQML,KIF e Ontolingua
Sistemas Híbridos
Problemas em IAD
Aplicações
Fred Freitas - [email protected] -Sistemas Multiagentes
2
Sociedade de Objetos

Evolução de Objetos Distribuídos : Objetos
Concorrentes.

Objetos concorrentes = objetos distribuídos +
processador

Inspiração biológica : células de um corpo.

Como manter controle de versões e mudanças
transparentes e robustas para todas as classes de
usuários?
Fred Freitas - [email protected] -Sistemas Multiagentes
3
Sociedade de objetos

Solução: Noção de tempo => Agentes.

Mais atividade e menos passividade.

Sobrevivência ligada à satisfação dos usuários (timeout).

Apertos (91!) : Hosts completamente móveis através de
VIP (Virtual IP) como uma subcamada do IP, migração e
nomeação distribuída, implementados a nível de sistema.
Fred Freitas - [email protected] -Sistemas Multiagentes
4
Modelo de Campo Computacional


Metáfora : Objetos concorrentes
flutuando no mar (Campo
Computacional).
Forças em jogo :
• Gravitação - comunicação
freqüente atrai objetos
• Repulsão - Balanceamento
de carga
• Fricção - Objetos maiores
tendem a não se mover
Novo, atraído pela gravitação
Forças de Repulsão
Fred Freitas - [email protected] -Sistemas Multiagentes
5
Arquiteturas Distribuídas
Arquitetura
Cliente-Servidor
Distribuída
Agentes
Entidade
Mestre
Manda
Peer – Atribui
tarefas
Voltado p/ si
Peer- Cria ou invoca
compromissos
Entidade
Escravo
Obedece
Peer – Satisfaz
pedidos
Autônomo
Peer – Mantém
compromissos
Comunicação
RPC
Msgs assícronas
declarativas
Atos de fala
Fred Freitas - [email protected] -Sistemas Multiagentes
6
IA e SD







Resolução de Problemas
Aprendizado
• Simbólico
• Conexionista
Dedução e inferência
Planejamento
Processamento de Linguagem
Natural
Sistemas Especialistas
Agentes








Interconexão de máquinas,
sistemas, redes, etc
Heterogeneidade
Comunicação
Concorrência
Compartilhamento de recursos
Objetos Distribuídos
Escalabilidade
Transparência
Fred Freitas - [email protected] -Sistemas Multiagentes
7
O que é um agente

Agente é qualquer entidade que:
• percebe seu ambiente através de sensores (ex. cameras,
microfone, teclado,mensagens de outros agentes,...)
• age sobre ele através de efetuadores (ex. video, auto-falante,
impressora, braços, ftp, mensagens para outros agentes,...)
Medida de desempenho: Critério que define o grau de
sucesso das ações
ambiente

sensores
Raciocinador
efetuadores
Agente
modelo do
ambiente
Propriedades

Autonomia (IA)
• raciocínio, comportamento guiado por objetivos
• reatividade

Adaptabilidade & aprendizagem (IA)

Comunicação => Cooperação ou Colaboração
(IA)

Personalidade (IA)

Continuidade temporal

Mobilidade
Inteligência : Centralizada ou
Distribuída ?





Cada um fa(e)z um pouco, e... somos UM!
Não aproveitamos muito o trabalho alheio.
A Internet nos faz trabalhar de forma mais inteligente
(nenhum componente é crítico).
Resolução de problemas : Há alguns cuja solução é
inerentemente distribuída ou fica mais fácil distribuindo!
Somos centralizados ou distribuídos ??
Fred Freitas - [email protected] -Sistemas Multiagentes
10
Histórico

HEARSAY II [Corkill et al.73]
• Arquitetura de quadro-negro.

Sociedade da Mente [Minsky78]
• Distribuição, independência e emergência.

Contract Net [Smith82]
• Leilão de tarefas.

Robôs reativos [Brooks 86]
• Arquitetura de subsunção (taxonomia).
Fred Freitas - [email protected] -Sistemas Multiagentes
11
Sociedade da Mente [Minsky]



Uma porção de agências por mente!
Ações e soluções emergem: conflitos, metas(prazer,dor),
diferentes representações neurais e simbólicas,mecanismos
de controle e vias, garis, ativadores,memória de
agentes,reuso criativo,hierarquias de
sociedades,scripts,habilidades construídas a partir de
somas, teias de RNAs.
Aceitam-se ambiguidades e erros!
Fred Freitas - [email protected] -Sistemas Multiagentes
12
Exemplo







O Quebra-cabeça dos N(8)
números é um NP-completo.
A*-3x3 peças
IDA*-4x4 peças
RTA*-5x5 peças
Sem escalabilidade
RDP-testes c/30x30!
Cd peça:ag.reativo.


H
E
A
B
F
D
C
G
A solução emergiu das interações
entre eles.
Primitivas de satisfação, fuga e
agressão, c/ pontuação por
distância, restrições de
trancamento, loops e pontas.
Fred Freitas - [email protected] -Sistemas Multiagentes
13
Quebra-cabeça dos N(8) números
Fred Freitas - [email protected] -Sistemas Multiagentes
14
Quebra-cabeça dos N(8) números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
Fred Freitas - [email protected] -Sistemas Multiagentes
15
Quebra-cabeça dos N(8) números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
Fred Freitas - [email protected] -Sistemas Multiagentes
16
Quebra-cabeça dos N(8) números
B
C
E
A
H
F
D
G
Ativo
Fred Freitas - [email protected] -Sistemas Multiagentes
17
Quebra-cabeça dos N(8) números
B
C
A
E
H
G
F
D
Ativo
Fred Freitas - [email protected] -Sistemas Multiagentes
18
Quebra-cabeça dos N(8) números
A
E
B
C
G
H
F
D
Bloqueado
Ativo
Fred Freitas - [email protected] -Sistemas Multiagentes
19
IA Clássica


Metáfora psicológica: uma pessoa ou entidade resolve o
problema.
Inteligência atomizada, restrita aos micro aspectos de sua
própria racionalidade.
Fred Freitas - [email protected] -Sistemas Multiagentes
20
IA Distribuída - Sistemas Multiagentes




Complementa a metáfora psicológica com uma
sociológica.
As soluções emergem de ações e interações produtivas
entre agentes autônomos.
Relacionada aos macro aspectos dos agentes :agentes
enquanto sociedade.
Inspirada tb em linguística, sociologia, economia,filosofia,
biologia e ... Redes Neurais!
Fred Freitas - [email protected] -Sistemas Multiagentes
21
IA Distribuída (IAD)





Não é IA paralela, nem Sist.Distribuídos.
Resolução grupal de problemas, através de cooperação (
diferente de colaboração).
Grande interatividade e capacidade de comunicação.
Organização - meios que garantam a convergência:
Estruturas de autoridade e controle divididos.
Divisão de conhecimento e recursos.
Fred Freitas - [email protected] -Sistemas Multiagentes
22
Motivações de Multiagentes

Avanços científicos: grandes redes heterogêneas abertas,
concorrência, sistemas distribuídos, bibliotecas digitais
• Interdependências complexas
• Não há controle global






Limitação de recursos e de racionalidade
Problemas grandes e complexos, experimentação
Domínios distintos
Recuperação de informações(IR), Mineração de Dados e
Mediação de alto nível.
Internet!
Simulação de sistemas naturais e sociais, jogos
Fred Freitas - [email protected] -Sistemas Multiagentes
23
Noção fraca de agente




Racionalidade restrita a si próprio ( egoísmo ou autismo).
Autonomia restrita : controle de seu estado interno.
Sociabilidade autista ou consciente através de uma
Linguagem de Comunicação de Agentes (Ex:KQML,
Arcol).
Reatividade.
Fred Freitas - [email protected] -Sistemas Multiagentes
24
Noção Forte de Agente

Noções mentalísticas : postura intencional, nãomecanicista e útil, pelo emprego de crenças, desejos e
intenções/escolhas (BDI).
 Honestidade e senso de equipe.
 Racionalidade e aprendizado/adaptação social.
 Resolução de problemas complexos e exploração.
 Programação Orientada a Agentes[Shoham]:
• Consistência interna (crenças,obrigações,...)
• Persistência de estado mental
• Capacidade de desincumbir a si e a outros, se não há
capacidade de cumprir as metas.
Fred Freitas - [email protected] -Sistemas Multiagentes
25
Noção Forte de Agente - Lógicas



Difícil formalização : crenças exigem lógicas mais
complexas, porque Acredita(Zé,Melhor-ponta(Garrincha))
e
Mané=Garrincha não quer dizer que
Acredita(Zé,Melhor-ponta(Mané)) !
Lógicas modais normais/ lógicas de conhecimento e
crença.
Mundos possíveis, crenças(KD45), lógicas que combinam
atitudes diferentes.
Fred Freitas - [email protected] -Sistemas Multiagentes
26
Divisão de soluções em IAD


Resolução Distribuída de Problemas - RDP
Sistemas Multiagentes - SMAs
• Reativos
• Cognitivos
Fred Freitas - [email protected] -Sistemas Multiagentes
27
Resolução Distribuída de Problemas RDP





Ênfase no global: modelo,
problema e critérios de sucesso.
Objetivos da sociedade.
Colaboração entre agentes
distribuídos.
E:Tarefas,ambiente.
S:modelo dos agentes e
esquema de resolução das
tarefas.
Fred Freitas - [email protected] -Sistemas Multiagentes
28
Problema
RDP
Concepção
Projeto dos
Agentes
Divisão em
subproblemas
Projeto das
Interações
Projeto das
Organizações
Resolução
Fred Freitas - [email protected] -Sistemas Multiagentes
29
Sistemas Multiagentes - SMA





Ênfase no local: modelo,
problema e critérios de sucesso.
Objetivos dos agentes.
Coordenação entre agentes num
mesmo ambiente.
E:agentes,ambiente.
S:tarefas resolvíveis e esquema
de resolução das tarefas.
Fred Freitas - [email protected] -Sistemas Multiagentes
30
SMA
Concepção
Projeto dos
Agentes
Projeto das
Interações
Projeto das
Organizações
Resolução
Fred Freitas - [email protected] -Sistemas Multiagentes
31
SMAs Reativos X







Conhecimento implícito
Não-histórico
Behaviorista ou positivista
Reativo
Comunicação indireta
Inspirado em coletivos de
animais
Uma porção de agentes
SMAs Cognitivos







Conhecimento explícito
Mentalista e histórico
Subjetivista (BDI)
Deliberativo
Comunicação direta
Inspirado nas sociedades
humanas
Poucos agentes
Fred Freitas - [email protected] -Sistemas Multiagentes
32
SMAs Reativos

R. Brooks 86 - Arquitetura de subsunção (taxonomia)
Controlar robôs físicos (dinamismo e desconhecimento).
• Inteligência pode ser gerada sem conhecimento explícito ou
raciocínio abstrato!
• É uma propriedade emergente de certos sistemas complexos.
• A inteligência real está situada no mundo, e não em sistemas
desincorporados ( especialistas, provadores, etc)!
• Comportamento inteligente emerge das interações com o
ambiente.
• Competição entre camadas hierárquicas.
Fred Freitas - [email protected] -Sistemas Multiagentes
33
SMAs Reativos - Características

Não há representação explícita de conhecimento.
 Não há representação do ambiente.
 Não há memória das ações.
 Os agentes possuem estados internos.
 3 modelos :
• Funcionalidade emergente
• Eco-resolução
• PACO (PAdrões de COordenação)
Fred Freitas - [email protected] -Sistemas Multiagentes
34
Eco-resolução


Solução é um estado estável de comportamentos.
Eco-agentes possuem :
• Objetivo : Estado de satisfação
• Estado interno, baseado em autômato finito:
• Satisfeito
• Em busca de satisfação
• Em fuga
• Ações elementares: comportamentos de satisfação e fuga
• Vontade de estar satisfeito
• Obrigação de fugir, quando atacado
• Percepção : Quem o incomoda
Fred Freitas - [email protected] -Sistemas Multiagentes
35
Tipos de SMAs Cognitivos





Agentes organizados
• Perspectivas múltiplas, leis e regras sociais
Agentes negociantes
• Resolução de conflitos por negociação
Agentes intencionais
• Intenções (ou escolhas), compromissos, planos parciais
Agentes cooperativos
• Representação mútuas, alocação de tarefas
Módulos com comunicação.
Fred Freitas - [email protected] -Sistemas Multiagentes
36
Descrição externa
Raciocínio
Raciocínio Social
Decisão
ED
ER
EC
Revisão
Percepção Recepção
Emissão Ação
Fred Freitas - [email protected] -Sistemas Multiagentes
37
Comunicação entre agentes


Troca de mensagens ou Quadro Negro.
Infra-estrutura de comunicação:
• Com ou sem conexão (email)
• Ponto a ponto, multicast ou broadcast
• Síncrona ou assíncrona

Protocolos:KQML,HTTP,HTML,OLE,CORBA,DSOM.
 Segurança : Selos / autenticações.
 Mediação : Baseada em ontologias ou transacional.
Fred Freitas - [email protected] -Sistemas Multiagentes
38
SMAs Cognitivos - Teoria dos Atos de
Fala





Os SMAs Cognitivos podem basear-se em Teoria da
Decisão, Utilidade, Jogos ou Dependência
Mas devem basear-se na Teoria dos Atos de Fala.
Como uma ação, a comunicação deseja mudar o ambiente.
Atos de fala são assertivos(informativos), diretivos,
comissivos, declarativos ou expressivos (emoções).
KQML e Arcol (FIPA) procuram implementar alguns
destes atos, mas há críticas.
Fred Freitas - [email protected] -Sistemas Multiagentes
39
Knowledge Sharing Effort (KSE)


Desenvolver infra-estrutura para reuso e compartilhamento
de conhecimento.
O KSE é organizado em três grupos de trabalho :
• Interlingua Group - tradução. Linguagem KIF.
• SRKB (Shared, Reuasable Knowledge Bases) Group Construção de Ontologias Compartilháveis.
• External Interfaces Group - Linguagem KQML.
• Ontolingua - Tradução entre formalismos via KIF.
Fred Freitas - [email protected] -Sistemas Multiagentes
40
KQML - Knowledge, Query and
Manipulation Language

KQML é uma linguagem e um conjunto de protocolos que
dão suporte a agentes na identificação, conexão e troca de
informação com outros agentes.
 Mensagens KQML não enxergam o conteúdo das
mensagens que elas transportam;
 É dividida em três camadas :
• camada de comunicação - parâmetros de baixo
nível da comunicação (sender, recipient, id,etc)
• camada de conteúdo - normalmente em KIF;
• camada de mensagem - determina o tipo de
interações da comunicação( linguagem de
conteúdo, ontologia , etc)
Fred Freitas - [email protected] -Sistemas Multiagentes
41
KQML - Executivas (atos de fala)

As executivas podem ser enquadradas nas seguintes
categorias :
• Executivas de Conversação - trocas de informação e
conhecimento na conversação de dois agentes
(askif,ask-all;tell,advertise,insert,subscribe, recruiting)
• Executivas de Intervenção - intervenção do curso
normal da conversação (error,sorry);
• Executivas de Facilitação e Rede - permitem que
agentes achem outros agentes que podem processar
suas consultas (register,unregister,transport-address,
forward,broadcast,broker-one,recommend-one)
Fred Freitas - [email protected] -Sistemas Multiagentes
42
KIF - Knowledge Interchange Format


Codifica o conhecimento a ser transportado em Lógica de
1a. Ordem com cálculo de predicados e teoria dos conjs.
Útil na definição de ontologias.
(defrelation PHYSICAL-DIMENSION
(class PHYSICAL-DIMENSION ))
(defrelation UNIT-OF-MEASURE
(=> (UNIT-OF-MEASURE ?u)
(and (defined (unit.dimension ?u ))
(physical-dimension (unit.dimension ?u )))))
(defunction QUANTITY.DIMENSION
(=> (physical-quantity ?q)
(and (defined (QUANTITY.DIMENSION ?q ))
(physical-dimension (QUANTITY.DIMENSION ?q )))))
Fred Freitas - [email protected] -Sistemas Multiagentes
43
Comunicação via KQML e KIF
Exemplo : O facilitador recebe a seguinte mensagem :
(broker-one :sender
C
:receiver
facilitador
:reply-with id3
:language KQML
:ontology kqml-ontology
:content
(ask-all :sender
C
:reply-with id4
:language
Prolog
:ontology
Campeonato
Brasileiro
:content
“Campeao(Flamengo,Y)”))
Fred Freitas - [email protected] -Sistemas Multiagentes
44
Comunicação via KQML e KIF


Exemplo (cont.) :
Então, o agente facilitador depois de procurar pelas mensagens
“advertise”que tem sido recebidas por ele, decide enviar a seguinte
mensagem para o agente A :
(ask-all
:sender
facilitador
:receiver
A
:in-reply-to
id1
:reply-with
id4
:language
Prolog
:ontology
Campeonato Brasileiro
:content
“Campeao(Flamengo,Y)”))
Fred Freitas - [email protected] -Sistemas Multiagentes
45
Comunicação via KQML e KIF


Exemplo (cont.) :
E o agente A responde com a seguinte mensagem :
(tell
:sender
A
:receiver
facilitador
:in-reply-to
id4
:reply-with
id5
:language
Prolog
:ontology
Campeonato Brasileiro
:content
“Campeao(Flamengo, 1980), ... ,
Campeao(Flamengo, 1992)”)
Fred Freitas - [email protected] -Sistemas Multiagentes
46
Comunicação via KQML e KIF

Exemplo (cont.) :E então, o agente facilitador envia para o agente C :
(forward
:from
A
:sender
facilitador
:receiver
C
:in-reply-to
id3
:reply-with
id6
:language
KQML
:ontology
kqml-ontology
:content
(tell
:receiver C
:language Prolog
:ontology C. Brasileiro
:content
“Campeao(Flamengo, 1980),
... ,
Campeao(Flamengo,1992)”)
Fred Freitas - [email protected] -Sistemas Multiagentes
47
Ontolingua
Ontologias
“de prateleira”
Ontolingua
LOOM
Ontol.
“T-box”
Epikit
Axiomas
Express
Modelo
Inform.
Prolog
Regras
backwar
chaining”
CLIPS
Regras
forward
chaining
CORBA
IDL
Fred Freitas - [email protected] -Sistemas Multiagentes
KIF
Lógica
predic.1ª
ordem
48
Colaboradores remotos
Ontolingua
Servidor / Editor de Ontologias
Editor
Escritores
HTT
P
Leitores
Aplicações remotas
NGF
P
Bibl
NGF
P
Aplic.
GUI
Servidor
DB
Tradutores:
LOOM,IDL,CLIPS...
Aplicações stand-alone
Aplic.
Transferência de arquivos (Batch)
Fred Freitas - [email protected] -Sistemas Multiagentes
KQ
ML
BC
49
Sistemas Híbridos



As camadas superiores são deliberativas e as inferiores são
reativas, com maior precedência.
Problema: como gerenciar interações clean entre camadas.
InteRRaP - hierárquico :
•
•
•
•
Interação com o mundo.
Padrões de comportamento ativados com pré-condições
Planos e cooperação
Orientado por dados e metas
Fred Freitas - [email protected] -Sistemas Multiagentes
50
Problemas em IAD

Ausência de metodologias de projeto claras.
 Incerteza e conflito.
 Interação e linguagens ainda não sedimentadas.
 Modelagem de outros agentes.
 Chaveamento cognitivo/ reativo.
 Quais informações devem ser globais e quais locais.
 Quando executar, planejar e coordenar.
 Principais : coerência e cooperação, através da
coordenação (forte ligação com planejamento e
escalonamentos).
Fred Freitas - [email protected] -Sistemas Multiagentes
51
Dilema do Prisioneiro
Jogador
2
Coopera
Jogador
1
Coopera
Denuncia
Denuncia
Classificação social de agentes
SMA
Independente
Discreto
Cooperativo
Cooperação
emergente
Comunicativo
Deliberativo
Ñ-comunicativo
Negociador
Fred Freitas - [email protected] -Sistemas Multiagentes
53
Aplicações












Interpretação de dados e
planejamento distribuídos
BDs distribuídos e SDs
Roteamento, equilíbrio de carga
CSCW e PDAs
CAD/CAM/CAE
Recuperação de informações
PLN
Tomada de decisão distribuída
Escalonamento
Diagnóstico e monitoração
Robótica : visão e trajetória
Produtos: General Magic, IBM,
etc.











Transportes
• Tráfego urbano e aéreo
Controle de aceleração de
partículas
Distribuição de eletricidade
Alocação de recursos em
fábricas distribuídas
Sistemas de Telecomunicação
Assistência a pacientes
Controle de espaçonaves
Fabricação de aço
Simulação de comportamentos
Cinema
Mineração, cartografia, imagens
Fred Freitas - [email protected] -Sistemas Multiagentes
54