Agentes que Trabalham
Juntos


Fechando Negócios...
Coordenando Ações




A Rede de Contratos
Planejamento Parcial Global
E quando não dá certo?
O Resumo da Ópera
Negociando...


Para situações mais complexas, leilões
não bastam...
Qualquer negociação tem 4 componentes:




Conjunto de negociação
Um protocolo
Uma coleção de estratégias
Uma regra que determina quando o consenso
foi atingido
Complicando...

Quantas questões estão sendo discutidas?


Comprar um carro x Pechinchar no preço da cerveja
Quem está envolvido?



Um prá um
Muitos prá um
Muitos prá muitos

Podemos ter até n(n-1)/2 threads de negociação
Dois tipos fundamentais de
domínio


Orientados a Tarefas (DOT)
Representados por uma tupla <T,Ag,C>



T é o conjunto de todas as tarefas
Ag = {1,..,n} é o conjunto de participantes
C é a função de custo para cada subconjunto
de tarefas.

Função monotônica
Acordos... (Deals)


Um acordo é uma alocação de tarefas.
A utilidade do acordo  é a diferença
entre o custo das tarefas que o agente
faria inicialmente (Ti) e as tarefas que
lhe foram atribuídas.


Utilityi() n= c(Ti) –c(i)
Se os agentes não chegarem a um acordo
temos o acordo de conflito.
Mais sobre acordos

Um acordo 1 domina 2 se





1 é tão bom quanto 2 para todos os agentes.
1 é melhor que 2 para algum agente.
1 domina fracamente 2 se a primeira
condição se verifica.
Um acordo que não é dominado por nenhum
outro é chamado de pareto-optimal.
 é individual racional se domina
fracamente o acordo de conflito
Assim...

O conjunto de possibilidades a colocar
em negociação consiste nos conjuntos
de acordos que são


Individual racional
Pareto optimal
Um protocolo...

Protocolo de Concessão Monotônico



Negociação acontece em rounds.
No primeiro, ambos os agentes propõem
acordos no conjunto de negociação
Um acorde é alcançado se




Utility1 (2 )  utility1(1) ou
Utility2 (1 )  utility2(2)
Sem consenso, a negociação continua
Negociação termina com o conflict deal.
Como proceder...


Propor o melhor acordo.
Quem deve ceder?


Depende da “vontade” de um agente
arriscar conflito.
Maior a vontade se a diferença entre a
proposta e o acordo de conflito for
baixa.
Definindo Risco
Riskit= utilidade perdida aceitando a
oferta/ utilidade perdida causando
conflito
1 se
utility (jt) = 0
Riskit=
utility (it) - utility (jt) /
utility (it)
Quanto ceder?




O menos necessário para mudar o
balanço de risco
Protocolo exponencial!
Equilíbrio de Nash
Agentes podem enrolar... Criando
tarefas fantasmas... Ou escondendo
tarefas!
Domínios Orientados a Valor

Um DOV é uma tupla <E, Ag, J, C> onde







E é o conjunto de estados do ambientes
Ag é o conjunto de Agentes participantes do processo
J é a coleção de planos conjuntos
C : JxAg  R é o custo de realização.
Um encontro é o par <e,W>
W é a função de valor que representa o valor do
estado para o agente.
Agentes negociam tanto sobre o estado a que
querem chegar quanto sobre os meios para
atingi-lo.
Algumas Observações
Importantes




“Não há SMA de um só agente...”
Para trabalharem juntos, os agentes
precisam negociar seus papéis...
Cooperação precisa de negociação... Que
precisa de argumentação!
E como coordenar?
Argumentando...


Teoria dos Jogos tem suas desvantagens...
Alguns outros tipos de argumentação...

Lógica


Emocional


Você gostaria que fizessem isto com você?
Visceral


Gera argumentos dedutivos
Envolve o físico – e.g. você bate o pé para enfatizar um
ponto
Místico

Envolve apelos para o místico!
Argumentação Baseada em
Lógica




Base |- (sentença, Justificativas)
Base é um conjunto de sentenças
acordadas pelos agentes.
Argumentos podem ser contra ou a favor
uma determinada proposição.
Dois tipos básicos de argumento


Não trivial
Tautológico
Um exemplo...
Humano(Heracles)
Pai(Heracles, Zeus)
Pai(Apolo, Zeus)
Divino(X) mortal(X)
Pai(X, Zeus)  divino(X)
(Pai(X, Zeus)  divino(X))
Continuando...
Podemos construir ARg1
(mortal(Heracles), {humano(Heracles),
humano(X) mortal(X)})
(mortal(Heracles), {pai(Heracles,Zeus), Pai(X,
Zeus)  divino(X) Divino(X) mortal(X)})
((Pai(X, Zeus)  divino(X)) {(Pai(X, Zeus) 
divino(X))}
Várias Classes de
Argumento...

Por ordem de aceitação





Todos os argumentos a partir da base
Todos os argumentos não triviais
Todos que não podem ser rebatidos
Todos cujas justificativas não podem ser
contestadas
Todos os tautológicos.
Argumentação e Diálogo

Argumentação é um jogo... Vários tipos
identificados







Persuasão
Negociação
Indagação – crescimento do conhecimento geral
Deliberação
Busca de Informação
Conflitos
Misto
Perguntas chaves...


Porque... E Como os agentes cooperam?
Como reconhecem e resolvem conflitos?




De recursos
De alocação de tarefas
De objetivos
Como negociam?

Vários tipos de protocolo... Como vimos
anteriormente!
Critérios para Avaliar o
Sucesso...

Coerência


Mede o quão bem o sistema funciona como uma
unidade. Vários critérios: qualidade da solução,
etc.
Coordenação

Grau em que os agentes precisam se engajar em
atividades “extra-curriculares” para coordenar
suas tarefas.
Tarefas quando Resolvendo
Problemas Cooperativamente




Como decompor o problema em subtarefas?
Como sintetizar as soluções locais?
Como otimizar as atividades?
Que técnicas de Cooperação podem ser
utilizadas para maximizar a eficiência do
sistema?
Compartilhando Tarefas... E
Resultados

Decompondo o problema





Estrutura hierárquica. (Agentes SIFA, Actor)
Decomposição por uma figura central... Ou por
várias...
Requer um conhecimento das habilidades dos
agentes envolvidos.
Solução dos Subproblemas
Síntese das soluções
Compartilhando Tarefas e
Resultados... II

Compartilhando tarefas



Problema de Alocação
Podemos necessitar de negociação!
Compartilhando Resultados...

Proativo


Agentes vão contando seus achados...
Reativo

Agentes contam o que sabem quando solicitados
Então... Coordenar porquê
mesmo?




Porque agentes precisam de informação
que só outros tem;
Recursos são limitados
Queremos otimizar custos...
Objetivos separados podem ser
interdependentes!
Um Protocolo Famoso... A
Contract net


A1 reconhece que tem um problema
A1 anuncia que precisa de um serviço




Pode envolver um broadcast geral... Um
limitado... Ou um contato direto.
Ai,...,Aj respondem, oferecendo seus
préstimos.
A1 contrata o serviço, via award.
Quando o contratado termina, envia um
relatório ao contratante.
Quando recebemos as
mensagens...

Processando um anúncio...



Agente decide se é candidato...
Guarda os detalhes da tarefa, para
poder competir por elas...
Processando a oferta

Gerentes guardam as ofertas até o
deadline. Depois a tarefa é alocada a um
competidor.
Quando recebemos as
mensagens...

Processando o Award


Ganhador começa os procedimentos para
executar a tarefa.
Requerimentos e Informação

O conteúdo que chega é adicionado à
base de conhecimento do agente.
Compartilhando Resultados


Agentes trocam informações à medida
em que os agentes vão solucionando.
Podemos melhorar o desempenho...




Confiança
Completude
Precisão
Pontualidade
Lidando com Inconsistência

Entre os vários agentes



De crença
De objetivos e de intenções
Duas formas de Lidar



Evitando a concorrência
Resolver via negociação
Sistemas que degradam graciosamente.
Coordenando esforços...

Coordenação depende das relações entre as
atividades...

Relações Positivas


Solicitadas
Não solicitadas




Igualdade de Ações
Conseqüências
Favor
Relações Negativas

Recurso e Incompatibilidade
Coordenação via PPG

Consiste em três etapas




Cada agente decide seus objetivos e gera
planos de curto prazo para atingi-los
Agentes trocam informações
Agentes alteram planos locais para
melhor coordenar suas atividades
Várias estruturas envolvidas

Objetivo, Mapa de Atividade e Grafo de
Construção da Solução
PPG Generalizado

Usa cinco técnicas para coordenar
tarefas





Atualizar pontos de vista não locais
Comunicar resultados
Lidar com Redundância Simples
Lidar com Relações negativas entre ações
Lidar com relações positivas entre as
tarefas
Coordenação via Intenções
Conjuntas




Modelos baseados nos times humanos
Ação Coordenada  Ação cooperativa
coordenada
Participar de um time 
responsabilidade
Compromissos e convenções...
A idéia dos Joint Persistent
Goals

O grupo tem a motivação  para atingir o
objetivo .



Todos devem crer que  é possível mas ainda não
aconteceu.
Todos tem o objetivo  até que uma condição se
verifique.
Termina quando...


 é satisfeito
 é impossível ou a motivação não está mais presente
Coordenação baseada em
Times

Consiste em quatro etapas


Reconhecimento
Formação de Times



Solicitação de Ajuda
Formação dos Planos conjuntos
Ação dos Times
Coordenação por Normas e
Leis Sociais


Norma: padrão de comportamento
estabelecido.
Duas abordagens principais:


Design a priori
Emergência de um grupo de agentes
Normas e Leis Emergentes



Como alcançar consensos globais sobre
normas utilizando apenas as
informações locais.
Problema das Camisetas coloridas.
Função de atualização da “estratégia”.
Algumas Estratégias de
atualização de Funções...




Maioria Simples
Maioria Simples com “tipos” de agentes
Maioria Simples com Comunicação
Maior Recompensa
Planejamento Multi-Agentes

Planejamento Centralizado



Há um mestre que distribui planos aos
escravos.
Planejamento distribuído
Planejamento distribuído para planos
distribuídos

Conflitos e negociação em potencial!
E o Resumo da Ópera é...



Vimos o que são SMA...
Suas organizações e formas de
Interação...
Comunicação... E uma Pontinha de
coordenação!