Sistemas
Multiagentes
Luis Otavio Alvares (II-UFRGS)
e-mail: [email protected]
prof. Luis Otavio Alvares
Sumário
• Introdução aos SMA
• Conceito de agente e SMA
• Exemplos
• Breve histórico
• Sistemas Multiagentes reativos e cognitivos
• Bibliografia
• SMA reativos
• SMA cognitivos
prof. Luis Otavio Alvares
O que são agentes?
• o termo vem sendo aplicado indistintamente,
tanto na comunidade de computação em
geral como em IA;
• sistemas baseados em agentes estão sendo
propostos como a solução para tudo
(principalmente com o que tenha a ver com a
Internet)
prof. Luis Otavio Alvares
O que é um agente?
•
•
•
•
•
•
é uma entidade real ou virtual
que está inserida em um ambiente
que pode perceber o seu ambiente
que pode agir no ambiente
que pode se comunicar com outros agentes
que tem um comportamento autônomo, conseqüência
de suas observações, de seu conhecimento e de suas
interações com os outros agentes
prof. Luis Otavio Alvares
Outras características possíveis
de agentes
•
•
•
•
•
•
•
Continuidade temporal
Mobilidade
Benevolência
Aprendizagem
Cooperação
Veracidade
...
prof. Luis Otavio Alvares
O que é um sistema
multiagente?
Um conjunto de agentes que interagem
em um ambiente comum
prof. Luis Otavio Alvares
Exemplos
•
•
•
•
•
•
•
•
Jogos de computador
Interpretação de linguagem natural
Simulação
Assistentes pessoais
Comércio eletrônico
Tutores inteligentes
Controle de redes de energia elétrica
...
prof. Luis Otavio Alvares
Mudança de Paradigma
passa-se de uma abordagem global para uma
abordagem baseada em agentes (individual)
prof. Luis Otavio Alvares
Características de domínios típicos
• dados distribuídos
• controle distribuído
• diversidade de conhecimento
• decomponibilidade da tarefa global
• multiplicidade de funções
• certo grau de autonomia
prof. Luis Otavio Alvares
Vantagens
• adaptabilidade
• tolerância a falhas
• modularidade
• eficiência
prof. Luis Otavio Alvares
Problemas
• comunicação
• coordenação
• inexistência de metodologia consagrada
• ...
prof. Luis Otavio Alvares
Breve histórico
Hearsay II (Corkill, Erman, Hayes-Roth, Lesser, 1973)
blackboard architecture
Actors (Hewitt, 1973)e Beings (Lenat, 1975)
estruturas de controle complexas
Contract Net (Smith, 1982)
controle hierárquico descentralizado
DVMT (Lesser 1984)
interpretação distribuída, organização
Robos reativos (Brooks, 1986)
subsumption architecture
MACE (Gasser, 1987)
ambiente multiagente
prof. Luis Otavio Alvares
Tipos de SMA
[Demazeau 94]
Agentes Cognitivos
• representação explícita
• têm histórico
• comunicação direta
• controle deliberativo
• organização social
• poucos agentes
Agentes Reativos
• representação implícita
• não têm histórico
• comunicação indireta
• controle não deliberativo
• organização etológica
• muitos agentes
prof. Luis Otavio Alvares
Exemplo de jogo: GUIMO
• jogo de ação
• um jogo mais interessante por ser menos
repetitivo e mais “real”
• alguns objetivos a serem atingidos:
– resposta rápida por parte dos agentes
artificiais
– independência de um roteiro pré-definido
– maior envolvimento do jogador com os
elementos do sistema
prof. Luis Otavio Alvares
Solução adotada
Definir comportamentos elementares,
possibilitando reações rápidas, que
combinados produzem um
comportamento complexo:
– vaguear
– seguir em determinada direção
– atacar
– defender-se
prof. Luis Otavio Alvares
Exemplo de comportamento
O agente A1 “vê” um inimigo A2. O seu comportamento de
ataque é então ativado, fazendo com que se aproxime de
A2, disparando. Se o agente A2, por sua vez, também atira
em A1, este, ao perceber o projétil, irá saltar para evitar o
ataque que está sofrendo.
O comportamento global do agente A1 seria:
atacar enquanto persegue e desviar-se de um ataque
um comportamento complexo, não previsto inicialmente
prof. Luis Otavio Alvares
Bibliografia
Proceedings ICMAS, AAMAS
Proceedings MAAMAW Workshops (Europa)
Proccedings DAI Workshops (Estados Unidos)
Proceedings IJCAI, AAAI, ECAI, SBIA, ...
Autonomous Agents and Multi-agent Systems (Journal)
Readings in Distributed Artificial Intelligence.
A. Bond e Les Gasser. Morgan Kaufman, 1988
Readings in Agents
M. Huhns e M. Singh. Morgan Kaufman, 1998
Introdução aos Sistemas Multiagentes
L.O.Alvares e J. Sichman, Anais JAI’97
prof. Luis Otavio Alvares
Sistemas
Multiagentes
Sistemas
Multiagentes
Reativos
Reativos
prof. Luis Otavio Alvares
Motivação para o estudo de SMA
Reativos
• Precisamos de agentes complexos para
realizar tarefas complexas ou podemos
realizar uma tarefa complexa através de
interações de muitos agentes simples?
• exemplo clássico: colônia de formigas
prof. Luis Otavio Alvares
Características dos agentes reativos
• não há representação explícita do ambiente
nem de outros agentes
• não há memória das ações (histórico)
• organização etológica
• comportamento simples do tipo estímuloresposta
• comunicação através do ambiente pela
propagação de sinais
prof. Luis Otavio Alvares
Alguns Modelos de SMA Reativos
• Funcionalidade Emergente (Luc Steels)
• Eco-resolução (Jacques Ferber)
• PACO (Yves Demazeau)
prof. Luis Otavio Alvares
Modelo da Funcionalidade
Emergente
- Baseado na arquitetuta de subsunção
(subsumption architecture, Brooks 86)
Módulo superior
Módulo inferior
- Cada módulo é um autômato de estado finito
- Realização de vários robôs reais
prof. Luis Otavio Alvares
Exemplo: robôs mineradores
(L. Steels)
Um conjunto de robôs deve procurar e coletar minerais
e levá-los para a base central.
prof. Luis Otavio Alvares
Comportamento do Robô
1- Evitar obstáculo
2- Se perceber a base central e estiver carregado, descarregar
3- Se perceber um mineral e não estiver carregado, pegá-lo
4- Realizar movimento aleatório
prof. Luis Otavio Alvares
Projeto do robô
prof. Luis Otavio Alvares
Comportamento do robô 2
1- Evitar obstáculo
2- Se perceber a base central e estiver carregado, descarregar
3- Se perceber um mineral e não estiver carregado, pegá-lo
4- Se estiver carregado, seguir maior gradiente
5- Realizar movimento aleatório
prof. Luis Otavio Alvares
Projeto do robô 2
prof. Luis Otavio Alvares
Obervações:
• O robô 2 não apresenta nenhuma forma
de cooperação
• Não permite retornar ao local da jazida de
mineral
• Como melhorar isto?
prof. Luis Otavio Alvares
Robô 3
1- Evitar obstáculo
2- Se perceber a base central e estiver carregado, descarregar
3- Se perceber um mineral e não estiver carregado, pegá-lo
4- Se estiver carregado, seguir maior gradiente, deixando
uma pista
5- Se encontrar uma pista e estiver descarregado, seguir
na direção do menor gradiente
6- Realizar movimento aleatório
prof. Luis Otavio Alvares
[Drogoul 93]
prof. Luis Otavio Alvares
Interpretação dos resultados:
O Robô 3 possui um mecanismo simples de manutenção e
compartilhamento de informação, utilizando o ambiente
oomo memória
64 robôs - melhor resultado (1.113 ciclos)
média - 3.351 ciclos
maior nro. robôs => maior chance de encontrar os minerais
mecanismo de criação de pistas: espécie de catalizador
variações entre populações próximas: pelo que
acontece quando os depósitos ficam esgotados
prof. Luis Otavio Alvares
Robô 4
1- Evitar obstáculo
2- Se perceber a base central e estiver carregado, descarregar
3- Se perceber um mineral e não estiver carregado, pegá-lo
4- Se estiver carregado, seguir maior gradiente deixando
uma pista
5- Se encontrar uma pista e estiver descarregado, seguir
na direção do menor gradiente, retirando a pista
6- Realizar movimento aleatório
prof. Luis Otavio Alvares
[Drogoul 93]
prof. Luis Otavio Alvares
Interpretação dos resultados
• Perda evidente de desempenho para população > 70
robôs
• O que perde em eficiência, ganha em predição (não há
grandes variações entre populações próximas)
• Perda de eficiência: após um robô ter deixado o mineral
na base, há forte probabilidade de outro robô ter
encontrado a pista e a ter seguido, retirando a pista.
• Em vez de um mecanismo de compartilhamento de
informação obtivemos um mecanismo de transferência
de informação
prof. Luis Otavio Alvares
Robô 5
1- Evitar obstáculo
2- Se perceber a base central e estiver carregado, descarregar
3- Se perceber um mineral e não estiver carregado, pegá-lo
4- Se estiver carregado, seguir maior gradiente deixando
duas pistas
5- Se encontrar uma pista e estiver descarregado, seguir
na direção do menor gradiente, retirando uma pista
6- Realizar movimento aleatório
prof. Luis Otavio Alvares
[Drogoul 93]
prof. Luis Otavio Alvares
Interpretação do resultado
média: 3.519 ciclos
mínimo: 1.075 ciclos
melhor solução para população < 85 robôs
problema para mais de 85 robôs:
- deformação das pistas: um robô que retorna se
encontra com outros que vão para o mineral
- verdadeiros bloqueios, engarrafamentos, próximo
à base central
prof. Luis Otavio Alvares
Modelo da Eco-Resolução
(Jacques Ferber)
prof. Luis Otavio Alvares
Eco-Resolução
Técnica de resolução de problemas
Um problema é decomposto em um conjunto de ecoagentes
Cada eco-agente possui um objetivo (atingir um estado de
satisfação) e dois comportamentos gerais:
- de satisfação: procura atingir seu estado de satisfação
- de fuga: de outro agente que o está “agredindo”
prof. Luis Otavio Alvares
Exemplo: PENGI
Agre e Chapman: inviável com algoritmo de planejamento
prof. Luis Otavio Alvares
PENGUI: Comportamento dos agentes
ABELHAS:
- estado de satisfação: matar o pingüim
- comportamento de satisfação: ir em direção ao pingüim
PINGÜIM:
- estado de satisfação: não haver mais diamantes a pegar
- comportamento de satisfação: ir em direção ao diamante
mais próximo
- comportamento de fuga: ir para uma casa o mais longe
possível das abelhas. Ou para a mais próxima, se há um
cubo de gelo adjacente, na direção da abelha
prof. Luis Otavio Alvares
PENGUI (cont.)
Comportamento “inteligente”
- parece que o pingüim é inteligente, pois muitas vezes mata
a abelha com cubos de gelo
- não há nenhuma atividade de “caça às abelhas”
- nós é que consideramos em tudo uma intencionalidade,
que muitas vezes não existe
prof. Luis Otavio Alvares
Exemplo: Quebra-cabeça de 8
prof. Luis Otavio Alvares
Abordagem clássica
...
- abordagem clássica: orientada a estados
(algoritmo A* e variantes)
- limitada
prof. Luis Otavio Alvares
Exemplo: Quebra-cabeça de 8 (cont.)
- mudança de enfoque para abordagem orientada a agentes
- cada peça será um agente
- a escolha do movimento de uma peça (agente)será baseada:
- na distância do seu objetivo
- na distância do “branco”
- ordem de resolução:
prof. Luis Otavio Alvares
Exemplo: Quebra-cabeça de 8 (cont.)
- comportamento de satisfação: ir para a casa mais próxima
do objetivo. Se houver duas casas eqüidistantes, ir para a
mais próxima do branco
- comportamento de fuga: ir para o seu objetivo, se for
adjacente. Senão, ir para a casa mais próxima do branco.
Se houver duas casas eqüidistantes, ir para a mais próxima
do seu objetivo. Restrições: não ir para a casa que é a
do agressor e não ir para a casa que é o objetivo do
antecessor do agressor na ordem de preenchimento.
prof. Luis Otavio Alvares
Problema do canto
E
B
A
C
D
E
N
M
A
B
C
D
N
M
B
C
D
E
A
N
M
F
H
O
G
F
H
O
G
F
H
O
G
J
K
I
L
J
K
I
L
J
K
I
L
B
C
N
D
A
B
C
D
O
M
O
N
M
H
G
A
E
J
F
K
I
L
E
J
F
K
H
I
prof. Luis Otavio Alvares
G
L
Movimento de
Satisfação
Movimento de Fuga
Movimento Inválido
Restrição a um
Movimento Inválido
Exemplo: Quebra-cabeça de 8 (cont.)
- resultados experimentais até 899 peças (30x30)
(Drogoul 93)
- validade para qualquer tamanho de jogo
- validade mesmo para tabuleiro retangular
prof. Luis Otavio Alvares
Modelo PACO (Y. Demazeau)
Em vez de considerar a solução de um problema como
o resultado da minimização de uma função global de
energia
simplesmente expresse o problema como
o estado de equilíbrio de um conjunto de agentes
que interagem entre si e com o ambiente através de
forças
prof. Luis Otavio Alvares
Modelo PACO (cont.)
Técnica de resolução de problemas
Um problema é definido como um conjunto de agentes
que tentam encontrar um estado de equilíbrio
Os agentes são caracterizados por campos:
- de percepção (o que ele percebe do ambiente)
- de comunicação (agentes que o influenciarão na
execução de uma ação )
- de força (agentes sobre os quais ele pode agir)
prof. Luis Otavio Alvares
Modelo PACO (cont.)
O comportamento do agente é baseado num ciclo:
regulagem e aquisição
- definição dos campos de percepção e comunicação
processamento
- cálculo das forças exercidas sobre o agente
regulagem e ação
- cálculo da nova posição do agente
prof. Luis Otavio Alvares
Exemplo: Generalização
Cartográfica
Processo de abstração usado quando a escala do mapa é
reduzida.
Envolve modificação dos dados de modo que
possam ser representados em um espaço menor,
preservando da melhor forma possível os
aspectos geométricos e descritivos.
A maioria dos mapas em pequenas e médias
escalas são obtidos por generalização de
grandes escalas.
prof. Luis Otavio Alvares
Generalização Cartográfica
Processo de abstração usado quando a escala do mapa é reduzida.
Envolve modificação dos dados de modo que possam ser
representados em um espaço menor, preservando da melhor
forma possível os aspectos geométricos e descritivos.
A maioria dos mapas em pequenas e médias escalas são obtidos
por generalização de grandes escalas.
ex: França - mapa básico:
generalizados:
1/25.000
1/50.000
1/100.000
prof. Luis Otavio Alvares
Generalização Cartográfica
• Dificuldade: escolher como representar um número
suficiente de objetos geográficos numa superfície
reduzida, usando símbolos que preservem a
identificabilidade do objeto
• Numerosas modificações nos dados são necessárias.
Exemplo:
prof. Luis Otavio Alvares
Generalização Cartográfica
prof. Luis Otavio Alvares
Generalização Cartográfica
Fatores que influenciam a
generalização:
•Escala
•Objetivo do mapa
•Simbolização
•Meio de saída
prof. Luis Otavio Alvares
Generalização Cartográfica
Automatização
• abordagem algorítmica
• sistemas baseados em conhecimento
problema: independência de contexto
solução:
sistemas multiagentes reativos
prof. Luis Otavio Alvares
O modelo proposto
• entradas:
- dados oriundos de um BD
Geográfico (classe do objeto,
coordenadas, etc…)
-características da saída desejada
• processamento:
baseado num modelo de forças
eletrostáticas de atração e repulsão
• saída: mapa
prof. Luis Otavio Alvares
O Modelo Proposto
Agentes:
cada ponto, representado no BD por suas
coordenadas, corresponde a um agente no modelo
Pré-ordem:
importância do objeto (massa)
Grupo natural:
agentes associados a um mesmo
ponto geográfico
Grupo artificial:
agentes com topologia comum
prof. Luis Otavio Alvares
O Modelo Proposto
Interações: baseadas em forças
• Força de repulsão entre agentes
• Força de acompanhamento integral
• Força de acompanhamento proporcional
• Força de retorno à posição original
• Troca de simbologia
prof. Luis Otavio Alvares
O Modelo Proposto
prof. Luis Otavio Alvares
O Modelo Proposto
prof. Luis Otavio Alvares
Resultados Obtidos
prof. Luis Otavio Alvares
Sistemas Multiagentes
Cognitivos
prof. Luis Otavio Alvares
Características dos agentes
cognitivos
• Representação explícita do ambiente e
de outros agentes
• memória das ações (histórico)
• organização social
• mecanismo de controle deliberativo
• comunicação direta entre os agentes
• poucos agentes
prof. Luis Otavio Alvares
Arquiteturas de agentes
• os modelos clássicos baseiam-se na
corrente simbólica de IA (arquiteturas
deliberativas)
• grande influência da comunidade de
“planning”
prof. Luis Otavio Alvares
Arquitetura de agente cognitivo
Objetivos
Planos
Conhecimento
do domínio
Controle
Raciocínio
Ambiente
Decisão
Percepção
Ação
prof. Luis Otavio Alvares
Arquitetura de agente cognitivo
Conhecimento sobre
si mesmo e os outros
Objetivos
Planos
Conhecimento
do domínio
Controle
Outros agentes
Raciocínio
Ambiente
Decisão
Comunicação
Mensagens
Protocolos
Percepção
Ação
prof. Luis Otavio Alvares
Arquitetura de Agente: Demazeau 90
• CP
• CC
•K
•O
• CR
•P
• CD
•E
• CE
•A
CP
K
O
CE
A
CC
CR
P
CD
E
capacidade de percepção (1st hand)
capacidade de comunicação (2nd hand)
conhecimento
objetivos
capacidade de raciocínio
planos possíveis
capacidade de decisão
escolha de um plano
capacidade de engajamento
ação sobre o ambiente ou outros agentes
prof. Luis Otavio Alvares
Arquitetura BDI : Georgeff 85
Data
Input
Monit or
KAS
(Plans)
Data Base
(Beliefs)
Syst em
Int erfaces
Sensors
Int erpret er
(Reasoner)
Goals
(Desires)
Stack
(Intentions)
Data
Output
Environment
Effect ors
Command
Generat or
prof. Luis Otavio Alvares
Abordagem Mentalista
informações que o agente tem do mundo
(information attitudes):
– conhecimento, crenças
pró-attitudes (orientam, influenciam a ação
do agente):
– desejos, intenções, obrigações, ...
prof. Luis Otavio Alvares
Abordagem Mentalista
Estados mentais necessários (filosofia):
desejos (geral, todos os objetivos e metas do
agente) e crenças
intenções – tem o caráter de comprometimento,
pois os agentes são limitados: tem que tomar
uma decisão e parar de “pensar” e agir para
realizar a decisão
prof. Luis Otavio Alvares
Abordagem mentalista
Intenções:
- estão associadas a ações
- há uma questão temporal envolvida
• orientadas para o presente: causam
comportamentos, ações, para satisfazer a
intenção
• orientadas para o futuro: criam restrições para o
agente; guiam as atividades de planejamento e a
adoção de novas intenções
prof. Luis Otavio Alvares
Interação entre Agentes
prof. Luis Otavio Alvares
Conhecimento sobre outros
agentes
• Representações mútuas:
– as competências: quem sabe como fazer o
que?
– a tarefa sendo executada: quem executa o
que?
– as intenções, os objetivos: quem tem
intenção do que?
– os compromissos: quem está engajado com o
que?
como representar e atualizar este conhecimento?
prof. Luis Otavio Alvares
Teoria dos Atos de Fala [Austin 62]
• comunicar é agir: trata-se de uma
ação regular como qualquer outra,
que deve ser gerada e processada
• categorização de primitivas de
comunicação: inform, ask-todo,answer,promise,propose,…
prof. Luis Otavio Alvares
Atos de Fala
• A maioria dos sistemas multiagentes tem a parte
de comunicação inspirada na Teoria dos Atos
de Fala
• É uma teoria pragmática (teoria do uso da
linguagem): como a linguagem é usada pelas
pessoas no dia a dia para atingir seus planos e
intenções
• A origem da Teoria dos Atos de Fala
normalmente é atribuída a Austin com o livro
How to Do Things with Words (1962)
prof. Luis Otavio Alvares
Atos de Fala
• Austin notou que certas expressões eram
como “ações físicas” que pareciam alterar
o estado do mundo
• Exemplos:
– uma declaração de guerra
– “Eu os declaro marido e mulher”
prof. Luis Otavio Alvares
Teoria dos Atos de Fala (cont.)
Segundo Austin, os atos de fala podem ser
considerados segundo 3 aspectos:
• Locutionary act: ato de emitir sons emissão de palavras e sentenças com
algum significado (expressão oral). Ex.
“está chovendo” x “grablistrod zetagflx dapu”
• Illocutionary act: corresponde à intenção
da emissão: Ex: “vou pagar o que te devo
na próxima semana”. Está sendo realizado
o ato ilocucionário de fazer uma promessa.
prof. Luis Otavio Alvares
Teoria dos Atos de Fala
• Perlocutionary act: corresponde ao resultado
(desejado) da emissão: convince, insult,
frighten.
• Ex: alguém ao contar uma história de fantasmas
para uma criança, à noite, está executando o
ato perlocucionário de assustar a criança.
prof. Luis Otavio Alvares
Teoria dos Atos de Fala
Searle estendeu o trabalho de Austin com o livro Speech
Acts [Searle 69] identificando propriedades e fazendo
uma classificação sistemática dos principais tipos de
atos de fala:
• representatives: comprometem o receptor com a
verdade de uma proposição. Ex: informing
• Diretives: tentativa de levar o receptor a fazer alguma
coisa. Ex: requesting
• Commissives: o emissor se compromete com algo. Ex:
promising
• Expressives: expressa um estado psicológico. Ex:
thanking
• Declarations: efetua alguma mudança em uma situação
institucional. Ex: declaring war
prof. Luis Otavio Alvares
Linguagens de Comunicação
• pressupõem a utilização de um padrão de
linguagem para a comunicação entre
agentes
• o exemplo mais conhecido é o resultado do
projeto “Knowledge Sharing Effort”, KSE,
financiado pelo ARPA, nos anos 90.
– formato para troca de conhecimento (KIF)
– linguagem de consulta e manipulação de
conhecimento (KQML)
• outro padrão: ACL da FIPA
prof. Luis Otavio Alvares
KIF
Usada para estabelecer:
• propriedades de entidades em um
domínio (“Paulo é um gerente”)
• Relações entre entidades em um domínio
(“Pedro é o chefe de Carlos”)
• Propriedades gerais de um domínio
(“Todo estudante deve se matricular em
pelo menos uma disciplina”)
prof. Luis Otavio Alvares
KIF
Knowledge Interchange Format
• versão pré-fixada do cálculo de
primeira ordem, com extensões para
aumentar a expressividade
– noções aritméticas, ex: >, <
– operadores lógicos
– operadores ( tipo LISP)
– procedimentos (tipo Lisp ou Scheme)
prof. Luis Otavio Alvares
KIF: exemplos
• “A temperatura de m1 é de 83 Celsius”:
(= (temperature m1) (scalar 83 Celsius))
• definição de solteiro:
(defrelation bachelor (?x) :=
(and (man ?x) (not (married ?x))))
• “Todo indivíduo com a propriedade de ser
uma pessoa também tem a propriedade
de ser mamífero”:
(defrelation person (?x) :=> (mammal ?x))
prof. Luis Otavio Alvares
KQML
Knowledge Query and Manipulation Language
• uma mensagem é uma lista de
componentes, onde o primeiro indica o tipo
de comunicação e os seguintes são
expressões em KIF
• intuitivamente, uma mensagem é um passo
de diálogo entre um emissor e um receptor,
e a linguagem possibilita vários tipos de
diálogos
prof. Luis Otavio Alvares
KQML
• Cada mensagem contém uma performative (a
classe da mensagem) e um conjunto de
parâmetros. Exemplo:
(ask-one
:content (PRICE IBM ?price)
:receiver stock-server
:language LPROLOG
:ontology NYSE-TICKS
)
prof. Luis Otavio Alvares
KQML (cont.)
Exemplos:
• notificação simples
A to B: (tell (> 3 2 ))
• pedido de execução de uma operação
A to B: (perform (print “Hello!” t))
B to A: (reply done)
• pergunta específica
A to B: (ask-if (> (size c1) (size c2)))
B to A: (reply true)
prof. Luis Otavio Alvares
FIPA
• mais recentemente, a Foundation for
Intelligent Physical Agents (FIPA)
começou a definir padrões para sistemas
multiagentes — a peça central é a ACL
• a estrutura básica é bastante similar a
KQML
prof. Luis Otavio Alvares
Protocolos de Interação
prof. Luis Otavio Alvares
4 : A ask B about why 2
S6
2: B does not want
to answer 1 to A
S1
S2
1: A ask B about X
S3
Answer to a question
next level of dialogue
5 : B inform A about X
3 : B ask A about why 1
S5
Answer to a question
next level of dialogue
prof. Luis Otavio Alvares
S4
Protocolo de Redes de Contrato
gerente
propostas
• anúncio pelo
C
gerente
• propostas pelos
A
B
participantes
• anúncio de um
vencedor
• estabelecimento
de contrato
gerente
C
A
B
participantes
gerente
gerente
decisão
C
A
B
prof. Luis Otavio Alvares
contrato
A
C
B
Protocolo de Resolução de Conflitos [Sian]
• Não há modelos dos outros agentes
• Comunicação de alto nível (assert, propose (nova H),
modify (uma H proposta), agreed (com uma H proposta),
disagree, noopinion, confirm, accept, withdraw)
• Uso de função de avaliação cujos termos são:
count (confirm), count (noopinion), count (modify),count
(disagree) + protocolo de interação para resolver
conflitos
propose
modify
confirm
assert
disagree noopinion
withdraw
agreed
accept
• Executa revisão de crenças + aprendizagem
prof. Luis Otavio Alvares
COORDENAÇÃO DE
AGENTES
prof. Luis Otavio Alvares
Conceito de coordenação
• É o processo de gerenciar dependências
entre atividades [Malone 94]
• É o processo em que agentes se engajam
para garantir que um grupo de agentes
tenha um comportamento coerente
[Nwana e Jennings 96]
prof. Luis Otavio Alvares
Exemplos de coordenação
•
•
•
•
•
•
•
•
•
•
controle de tráfego aéreo
time de futebol
desfile de carnaval
trânsito de automóveis em uma cidade
operação militar
vôo de bando de pássaros
sistema imunológico animal
construção de avião, estrada, etc.
operação cirúrgica
orquestra
prof. Luis Otavio Alvares
Uma taxonomia de
coordenação
• coordenação a priori (pré-definido, decisão
individual, aplicação coletiva)
– reativa - ex: pássaros
– normativa
• incentivo- ex: incentivos fiscais, tarifa telefônica
• punição- ex: código de trânsito
• coordenação a posteriori (pós-definido, decisão
coletiva, aplicação individual: cada agente tem a sua
tarefa específica)
– planejamento centralizado- ex: general no exército
– planejamento distribuído- ex: projeto de avião
prof. Luis Otavio Alvares
Teoria dos Jogos
• A Teoria dos Jogos é construída a partir
da Teoria da Utilidade e da Teoria da
Decisão e se interessa com uma fonte de
incerteza particular: a ação de outros
agentes, igualmente racionais
• Um jogo é caracterizado por uma matriz
de ganhos, onde representa-se nas
células o ganho dos jogadores quando
realizam as ações representadas nas
linhas e colunas
prof. Luis Otavio Alvares
Matriz de Ganhos
• O primeiro jogador
escolhe as ações nas
linhas e o segundo
nas colunas
• Ex: se J1 escolhe a
ação b e J2 escolhe a
ação c, o ganho de J1
é 2 e o de J2 é 5
J2
c
d
1
J1
2
a
3
2
5
1
b
2
0
[Rosenschein e Genesereth 85]
prof. Luis Otavio Alvares
Dilema do Prisioneiro
P2
Delata o
outro
P1
Delata o
outro
Não
delata
3
3
5
0
0
Não
delata
5
[Axelrod 84]
1
1
 Dois suspeitos, depois
que um delito foi
cometido, são
interrogados em salas
separadas
 O problema é que
ofertas que são
individualmente racionais
podem não ser racionais
para o grupo!
prof. Luis Otavio Alvares
Dilema do prisioneiro
• O raciocínio de um prisioneiro:
• Suponha que eu confesse o delate o outro:
se ele não me delatar eu saio livre, mas se ele
também me delatar pegamos 3 anos de prisão
cada um. Então, eu posso pegar 3 anos de
cadeia.
• Suponha que eu não delate o outro: se ele
também não me delatar, eu pego 1 ano de
prisão. Mas se ele me delatar, eu pego 5 anos
de prisão. Então, eu posso pegar 5 anos de
cadeia.
• Com base nisso, é melhor eu delatar o outro
prof. Luis Otavio Alvares
Dilema do prisioneiro
• Portanto o cenário é simétrico (os dois prisioneiros
pensam da mesma maneira) e o que emerge ( se os
dois forem “racionais”) é que os dois agentes vão
confessar o crime e pegarão 3 anos de cadeia cada um.
• Mas intuitivamente esta não é a melhor solução, pois se
nenhum delatasse, eles pegariam apenas 1 ano de
prisão cada um.
• Mas se um não delata, a melhor escolha para o outro
passa a ser delatar e sair livre.
prof. Luis Otavio Alvares
Equilíbrio Nash
• Se o outro jogador jogar x, a minha
melhor jogada é y. E se eu jogar y, a
melhor jogada do outro é x.
• nenhum agente tem qualquer incentivo
para se desviar deste equilíbrio
• nessas condições, a jogada x,y é dita um
ponto de equilíbrio Nash.
prof. Luis Otavio Alvares
Exemplo real
• Suponha que dois países combinem de destruir
suas respectivas armas nucleares.
• O melhor seria os dois realmente destruírem e
não ter o perigo de uma guerra nuclear..
• Mas se um engana o outro e não destrói, fica
em melhor situação.
• O que não destrói, no pior caso, fica na situação
atual, os dois com as bombas.
prof. Luis Otavio Alvares
Teoria dos jogos
• Usada para tomada de decisão com
incerteza causada pelo comportamento de
outros agentes
• Exemplo: escolha de caminho para ir de
casa ao trabalho
prof. Luis Otavio Alvares
Exercício
• Cada aluno deve escolher um número
entre 0 e 100. Ganha quem tiver
escolhido o número que mais se
aproxime da metade da média dos
números.
• Não pode haver comunicação entre os
alunos
prof. Luis Otavio Alvares