Interações SMA
Ou... Como tratar com muita gente influenciando o
mesmo espaço?
Ao final desta aula a gente deve...
Entender o conceito de interação e sua
influência no projeto de SMA
 Conhecer os vários tipos de interação
existentes
 Entender como agentes devem raciocinar
frente a diferentes situações de
interação - i.e. como tomar a melhor
decisão possível?

Plano de Aula
Recordar é Viver... 
 Interação – definições

◦ Componentes
◦ Tipos

Formas de Cooperação
◦ Métodos

E quando não tem conversa? Conflitos
◦ Alguns Exemplos famosos...
RECORDAR É VIVER...
Recordar é viver...

Até agora vimos...
◦ SMA = metáfora da Inteligência Social
◦ Implica em...
 Comunicação, com infraestrutura e linguagem comuns
 Organização,
 Agentes tem papeis, direitos e deveres
 Interação
 Que depende diretamente da Comunicação
 É regulada pela Organização
 Negociação
 De tarefas e recursos
 Coordenação
 De esforços.
Assim...

SMA...
◦ Realiza a decomposição das tarefas
◦ Tem conflitos...ou junta esforços
◦ Pode se reorganizar....
Como isso acontece??
Interação é a chave...
Parte I
QUAL É MESMO A
IMPORTÂNCIA DA
INTERAÇÃO??
Um Sistema Multiagente
Interação
Organização
Agentes
Recurso
Esfera de
Influência
Ambiente
Definindo SMA

Um SMA é um sistema que possui os seguintes
elementos:
◦
◦
◦
◦
◦
◦
Um ambiente, E
Um conjunto de objetos O
Um conjunto de Agentes, A (AO)
Um conjunto de relações R, que liga objetos
Um conjunto de operações Op
Operadores que representam os resultados das operações
em Op e as reações do ambiente a eles.
Trocando em miúdos...

Um Sistema Multiagentes ...
◦ Consiste de uma coleção de componentes
autônomos, com objetivos particulares
◦ Que se interrelacionam
 De acordo com uma Organização
 Interagindo, negociando e coordenando esforços para
resolver tarefas
Podemos também concluir...

Que agentes podem ter esferas de
influência que se sobrepõem...
◦ O que implica em relações de dependência
entre eles!





Independência
Dependência Unilateral
Dependência Mútua
Dependência Recíproca...
E mais algumas que a gente vai ver na seqüência 
Um Cenário...
Imagine que você vai construir uma casa em
Porto de Galinhas... Contrata arquiteto,
engenheiro, peões (agentes variados)... A
casa construída resulta da integração do
comportamento de todos, agindo conforme
seus objetivos e habilidades, respeitando os
recursos disponíveis.
Interação

Acontece
◦ Quando agentes se vêem em uma relação dinâmica, trocando
ações que influenciam reciprocamente seus
comportamentos.

Possui...
◦ Uma série de eventos
 Os encontros
◦ Contato (direto ou indireto)

Gera/é regulada por
◦ Organizações Sociais.
O conceito de Interação

Pressupõe:
◦
◦
◦
◦

A presença de agentes que se comunicam
Situações de “encontro” deste agentes
Elementos dinâmicos – e.g. comunicação
Uma certa flexibilidade nas relações
Gera/Resulta de
◦ Organizações

“Um grupo é mais que a soma de seus
componentes”
Situações de Interação
Uma situação de Interação então é...
Um conjunto de comportamentos que
resulta do agrupamento de agentes que
devem atuar no ambiente para atingir
seus objetivos, e que dependem de
recursos limitados.

Comparando Interações

Uma interação depende de...
◦ Objetivos
 Os agentes têm objetivos compatíveis?
◦ Recursos Disponíveis
◦ Habilidades de cada agente
 O que cada um sabe fazer?
ENTÃO... COMO
ESCOLHER O QUE
FAZER?
Um conceito importante... Utilidade
Agentes terão preferências sobre estados
do mundo, representadas por um número.
 Assim... Seja Ω= {w1, w2, ...} o conjunto de
estados do mundo, podemos definir uma
função de utilidade assim...
µi : Ω
ℝ
 A função de utilidade é uma função de
ordem (reflexiva, transitiva e antisimétrica)

E daí?
Se os agentes i e j atuam no ambiente
simultaneamente
 O comportamento do ambiente, então é
o produto cartesiano das ações possíveis
de i e j
 O ambiente pode:

◦ Responder às ações de ambos
◦ Responder às ações de um dos dois
◦ Não responder a nenhum
Vamos então supor o seguinte
cenário...

Suponha que agentes i e j (capazes de duas ações
C ou D) têm a seguinte função de utilidade:
i(D,D) = 1 i(D,C) = 1 i(C,D) = 4 i(C,C) = 4
j(D,D) = 1 j(D,C) = 4 j(C,D) = 1 j(C,C) = 4
O que você faria no lugar de i?
E de j?
20
Matriz de Recompensa
i
D
C
j
D
4
4
C
1
4
4
1
1
1
21
Estratégias Dominantes

Que ações tomar?
◦ Uma estratégia s1 domina s2 para o agente i se todo o
elemento de s1 é preferido a todos os elementos de s2.
 Ou seja, não importa o que j faça, a recompensa de i vai ser sempre
maior ou igual do que com as outras ações.
22
Equilíbrio de Nash

Duas estratégias estão em EN se:
◦ Considerando que agente i executa S1 agente j não
pode fazer melhor que executar S2.
◦ Considerando que o agente j vai executar S2 i não
pode fazer melhor que S1
◦ No equilíbrio, os agentes não têm incentivo de se
desviar... O problema é que nem todas as situações
tem EN. Ou tem mais de um...
◦ Mas sempre há equilibrio qdo há aleatoriedade.
23
Pensando mais um pouco...

Interações Competitivas...
◦ Suponha que temos dois agentes i e j, onde um i
prefere um estado 1 sss j prefere 2.
◦ Interações de soma Zero.
 Quando a i (1) + j (1) = 0
 Ex. um jogo de xadrez
24
Em resumo...
O segredo é encontrar quais os melhores
resultados (de maior utilidade)
 Viável de calcular com poucos agentes – e
também na tomada de decisões
hierárquicas

QUE TIPOS DE
INTERAÇÕES POSSO
ENFRENTAR?
Uma primeira Classificação
Cooperação
 Indiferença
 Antagonismo – ou Conflito

Agente
A
Região de
Conflito
Agente
B
Tipos de Interação (I)

Independência
◦ Objetivos Compatíveis
◦ Cada agente tem recursos e habilidades Suficientes
◦ Ex. Duas pessoas pegando o Ceasa/Casa Amarela

Colaboração Simples
◦ Objetivos compatíveis e Recursos Suficientes
◦ Habilidades Insuficientes
◦ Ex. eu chamo Aline para fazer um bolo para o povo
de Agentes Autônomos
Tipos de Interação (II)

Obstrução
◦ Objetivos Compatíveis e Habilidades Suficientes
◦ Recursos Insuficientes
 Um corredor derruba outro na maratona
 Situação de Comércio

Colaboração Coordenada
◦ Objetivos Compatíveis
◦ Recursos e Habilidades Insuficientes
 Controle de Redes
Tipos de Interação (III)

Competição Individual
◦ Objetivos Incompatíveis
◦ Recursos e habilidades Suficientes
◦ Maratona

Competição Coletiva
◦ Objetivos Incompatíveis
◦ Recursos Suficientes
◦ Habilidades Insuficientes
 pode causar a formação de Coalisões
◦ Ex. Jogo de Futebol
 Competição entre fornecedores
Tipos de Interação (IV)

Conflitos Individuais sobre Recursos
◦ Objetivos incompatíveis e recursos insuficientes
◦ Habilidades Suficientes
◦ Ex. Dois agentes querendo o “prato de lasagna”

Conflitos Coletivos
◦ Objetivos Incompatíveis
◦ Recursos e Habilidades Insuficientes
 Formação de Coalisões para se apossar dos recursos necessários.
◦ Ex. quem já jogou “War”?
Ainda mais Interação...

Comensalismo
◦ Interação beneficia apenas um dos agentes,
sem prejudicar o outro.

Proto-Cooperação
◦ Interação otimiza a obtenção das metas.

Simbiose
◦ A interação entre os agentes é obrigatória,
cada um cedendo serviços ao outro.
Explorando mares nunca dantes
navegados...
Uma forma mais explícita de interação...
Resolução cooperativa de problemas
 Ocorrem quando um grupo de agentes se
junta para atingir um objetivo comum.

◦ Negociação em dois níveis
 Qual o objetivo?
 Como coordenar ações?
Cooperar = Colaborar?

Cooperar
◦ Agentes tem mesmo objetivo
◦ Mas tem sub-objetivos diferentes em um
instante no tempo.

Colaborar
◦ Mesmos objetivos e sub-objetivos todo o
tempo.
 “A gente faz junto”
Formas de Cooperação

Como Postura Intencional
◦ Agentes estão engajados em um plano, após ter
adotado um objetivo comum.
 E quando o cooperador só atrapalha?
 1000 pessoas tentando ajudar na minha mudança
◦ Pode também ser vista como o benefício que advém
da cooperação entre agentes
 As formigas não planejam a cooperação
Como avaliar a Cooperação?

Do ponto de Vista do Observador:
◦ Coordenação de Ações
 O plano parece coerente?
◦ Grau de Paralelismo das ações
 Como foi a distribuição? E a execução?
◦ Robustez do Sistema
Alguns Critérios de Cooperação
◦ Compartilhamento de Recursos
 Bom uso de recursos e habilidades
◦ Não Redundância de Ações
 Devido a qualidade da cooperação
◦ Não Persistência de Conflitos
Alguns destes critérios podem ser conflitantes...
O que fazer?
Definindo Cooperação...
Diz-se que um grupo de agentes coopera,
quando uma das duas condições se verifica
◦ A adição de um novo agente melhora o
desempenho do grupo
◦ A ação dos agentes serve para evitar (ou resolver)
conflitos.
Modelando o processo...

Uma situação de cooperação pode ser
analisada em 4 estágios:
◦ Reconhecimento
 Agente não consegue fazer a tarefa sozinho
 Prefere fazer acompanhado
◦ Formação de Times
 Agente pede ajuda
Modelando o Processo... II
◦ Formação de um plano de ação
 Agentes negociam um plano que deve...
 Ser coerente e eficiente!
◦ Execução do plano
 Agentes então executam as tarefas alocadas
 Mantendo-se em contato durante o processo.
Mas... Como reconhecer?
Não pode resolver sozinho
 Solução cooperativa melhor que a
individual
 Existe alguém que pode ajudar...

Formando Times...

Duas etapas básicas...
◦ O agente deve convencer o grupo de que
aquele objetivo é válido
◦ E que o grupo é capaz de fazê-lo
 Envolve necessariamente um processo de
negociação!
Formando Planos

Negociação fundamental
◦ Grupo se compromete a agir conforme
acordado; ou
◦ Pelo menos 1 agente propôs uma ação e o
grupo explora aquela possibilidade

Lembrando
◦ Agentes querem suas preferências
◦ O grupo deve monitorar o processo
Como saber se funcionou?

Três indicadores básicos
◦ Aumento da capacidade de sobrevivência
 Sobrevivência individual vs Sobrevivência de grupo
◦ Melhoria da Performance
◦ Aumentos Quantitativos e/ou Qualitativos
Como Possibilitar a Cooperação ?

Agrupamento e Multiplicação
◦ Arranjo dos agentes e aumento de seu
número.

Comunicação
◦ Indispensável...
◦ Via troca de mensagens
◦ Via difusão de um sinal
Como Possibilitar a Cooperação
?(II)

Especialização
◦ Compromete a capacidade de resolução geral
◦ Não é necessariamente determinada a priori

Divisão de Tarefas e Recursos
◦ Quem faz o que quando?
◦ Sistemas cognitivos
 Mecanismos de fornecimento e demanda

Coordenação de Ações
◦ Resolução de Conflitos via arbitração e negociação
Vantagens da Cooperação
Realização de Tarefas impossíveis previamente
 Melhoria da relação

no de tarefas/tempo de execução

Melhoria na organização dos recursos.
Recordando...
Interação
Objetivos
Recursos
Habilidades
Independência
Compatíveis
Suficientes
Suficientes
Colab. Simples
Compatíveis
Suficientes
Insuficientes
Colab. Coordenada Compatíveis
Insuficientes
Insuficientes
Obstrução
Compatíveis
Insuficientes
Suficientes
Compet. Indiv.
Incompatíveis
Suficientes
Suficientes
Compet. Coletiva
Incompatíveis
Suficientes
Insuficientes
Conflito Recursos
Incompatíveis
Insuficientes
Suficientes
Conflito Coletivo
Incompatíveis
Insuficientes
Insuficientes
Cenas dos Próximos Capítulos

Como chegar a consensos?
◦ De tarefas
◦ De recursos