Fred Freitas - [email protected] - Sistemas Multiagentes
SISTEMAS MULTIAGENTES
Prof. Fred Freitas - fred. @cin.ufpe.br
1
Índice





Inteligência centralizada x
distribuída
Motivações
Classificações
Resolução distribuída de
problemas - RDP
Sistemas Multiagentes - SMAs







SMAs Reativos
SMAs Cognitivos
Comunicação entre agentes
cognitivos
Noções fraca e forte de agente
Sistemas Híbridos
Problemas em IAD
Aplicações
Fred Freitas - [email protected] - Sistemas Multiagentes
2
Inteligência : Centralizada ou
Distribuída ?






Visão de Inteligência: Coletiva ou individual?
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!
Agentes sem inteligência podem em conjunto gerar algo
inteligente?
A inteligência de cada ser humano é centralizada ou
distribuída ??
Fred Freitas - [email protected] - Sistemas Multiagentes
3
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 [Smith 82]
• Leilão de tarefas.

Robôs reativos [Brooks 86]
• Arquitetura de subsunção (taxonomia).
Fred Freitas - [email protected] - Sistemas Multiagentes
4
Sociedade da Mente [Minsky]



Uma porção de agências por mente!
Ações/soluções emergem das interações entre as agências:
• 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
5
Sociedade da Mente [Minsky]
Fred Freitas - [email protected] - Sistemas Multiagentes
6
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
7
Quebra-cabeça dos N números
Fred Freitas - [email protected] - Sistemas Multiagentes
8
Quebra-cabeça dos N números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
Fred Freitas - [email protected] - Sistemas Multiagentes
9
Quebra-cabeça dos N números
E
B
A
F
C
H
D
G
Bloqueado
Ativo
Fred Freitas - [email protected] - Sistemas Multiagentes
10
Quebra-cabeça dos N números
B
C
E
A
H
F
D
G
Ativo
Fred Freitas - [email protected] - Sistemas Multiagentes
11
Quebra-cabeça dos N números
B
C
A
E
H
G
F
D
Ativo
Fred Freitas - [email protected] - Sistemas Multiagentes
12
Quebra-cabeça dos N números
A
E
B
C
G
H
F
D
Bloqueado
Ativo
Fred Freitas - [email protected] - Sistemas Multiagentes
13
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
14
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 também em linguística, sociologia, economia,
filosofia, biologia ...
Fred Freitas - [email protected] - Sistemas Multiagentes
15
IA e SD






Resolução de Problemas
Aprendizado
• Simbólico
• Conexionista
Dedução e inferência
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
16
IA Distribuída (IAD)

Não é IA paralela, nem Sistemas 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
17
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
18
Classificações em IAD

Divisão de tarefas
• Resolução Distribuída de Problemas - RDP
• Sistemas Multiagentes - SMAs

Inteligência de cada agente
• Reativos
• Cognitivos

Cooperação
• Cooperativos
• Competitivos
Fred Freitas - [email protected] - Sistemas Multiagentes
19
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
20
Problema
RDP
Divisão em
subproblemas
Concepção
Projeto dos
Agentes
Projeto das
Interações
Projeto das
Organizações
Resolução
Fred Freitas - [email protected] - Sistemas Multiagentes
21
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
22
SMA
Concepção
Projeto dos
Agentes
Projeto das
Interações
Projeto das
Organizações
Resolução
Fred Freitas - [email protected] - Sistemas Multiagentes
23
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
24
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
25
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.
 Exemplos de modelos :
• Funcionalidade emergente
• Eco-resolução
Fred Freitas - [email protected] - Sistemas Multiagentes
26
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
27
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
28
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
29
Comunicação entre agentes

Troca de mensagens ou Quadro Negro.
 Protocolos:KQML,HTTP,HTML,OLE,CORBA,DcOM.
 Segurança : Selos / autenticações.
 Mediação : Baseada em ontologias ou transacional.
Fred Freitas - [email protected] - Sistemas Multiagentes
30
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
31
SMAs Cognitivos –
Teoria dos Atos de Fala

Os SMAs Cognitivos podem basear-se em Teoria da
Decisão, Utilidade, Jogos ou Dependência
 A comunicação 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) implementam alguns destes atos
 O vocabulário de comunicação entre os agentes é
desempenhado por uma ontologia
Fred Freitas - [email protected] - Sistemas Multiagentes
32
Ontologias

Conceitualização acerca de uma área de conhecimento [Gruber 95]
• Conjuntos de conceitos, definições, relações, axiomas e
restrições sobre a área
 As ontologias garantem, através de um vocabulário comum de
termos e seus respectivos conceitos, a comunicação em nível de
conhecimento entre agentes cognitivos
[é-um 777]
777
Ont. de Meios de Transporte
Trem
Meu agente
Avião
Transporte Carreira
Barco
Caça
Agente da
Cia. Aérea
Avião
Id
Modelo
Fred Freitas - [email protected] - Sistemas Multiagentes
Xy
33
777
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
34
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.
Passa a existir o problema de revisão de teoria (ou revisão
de crenças)
Fred Freitas - [email protected] - Sistemas Multiagentes
35
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
36
Agentes não-estritamente cooperativos: o
Dilema do Prisioneiro
Jogador
2
Coopera
Jogador
1
Denuncia
Coopera
Denuncia
Fred Freitas - [email protected] - Sistemas Multiagentes
37
Classificação social de agentes
SMA
Independente
Discreto
Cooperativo
Cooperação
emergente
Comunicativo
Deliberativo
Ñ-comunicativo
Negociador
Fred Freitas - [email protected] - Sistemas Multiagentes
38
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
39
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
40