Interações SMAOu... 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 AulaRecordar é Viver... Interação – definições

ComponentesTipos

Formas de CooperaçãoMétodos

E quando não tem conversa? ConflitosAlguns 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 tarefasTem conflitos...ou junta esforçosPode se reorganizar....

Como isso acontece??Interação é a chave...

QUAL É MESMO A IMPORTÂNCIA DA INTERAÇÃO??

Parte I

Um Sistema Multiagente

Ambiente

Esfera de Influência

Organização

Agentes

Interação

Recurso

Definindo SMA

Um SMA é um sistema que possui os seguintes elementos: Um ambiente, E Um conjunto de objetos O Um conjunto de Agentes, A (AO) 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çãoPressupõ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íveisHabilidades de cada agente

O que cada um sabe fazer?

ENTÃO... COMO ESCOLHER O QUE FAZER?

Um conceito importante... UtilidadeAgentes 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 anti-simétrica)

E daí?Se os agentes i e j atuam no

ambiente simultaneamenteO 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 ambosResponder às ações de um dos doisNão responder a nenhum

20

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) = 4O que você faria no lugar de i?

E de j?

21

Matriz de Recompensa

ij

D C

D 44

14

C 41

11

22

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.

23

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.

24

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

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çãoCooperaçãoIndiferençaAntagonismo – ou Conflito

Região de Conflito

Agente A

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

AmarelaColaboraçã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çãoInteraçã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 objetivoMas 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 IntencionalAgentes 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 ConflitosAlguns 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 verificaA adição de um novo agente melhora o

desempenho do grupoA 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... IIFormaçã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 sozinhoSolução cooperativa melhor que

a individualExiste 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 PlanosNegociaçã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

LembrandoAgentes querem suas preferênciasO grupo deve monitorar o processo

Como saber se funcionou?

Três indicadores básicosAumento 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çãoIndispensável...Via troca de mensagensVia 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ítulosComo chegar a consensos?

De tarefasDe recursos