Agentes que Trabalham
Juntos


Fechando Negócios...
Coordenando Ações



Planejamento Parcial Global
E quando não dá certo?
O Resumo da Ópera
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 derivados da base
Todos os argumentos não triviais




Derivados de um conjunto consistente
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 – uma combinação dos anteriores
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
Exemplo 1: Figuras
Escondidas

Problema:


Encontrar figuras escondidas em uma
determinada área
Tarefa simples de busca:

Como você pode trabalhar como parte de
um time para resolvê-la?
Exemplo 1: Discussão




Decomposição: dividir a área ou as figuras
para a busca
Alocação: distribuir as sub-tarefas entre
os agentes
Execução: cada agente deve procurar as
figuras atribuídas a ele, ou fazer uma
busca na área destinada a ele.
Síntese: cada agente apresenta as
figuras encontradas.
Compartilhamento no problema
do ToH
1) Decomposição: se
preocupa em sempre
mover o maior disco
para o seu destino;
2) Alocação: escolha randômica dos agentes;
3) Execução: As tarefas são decompostas até que
o estado inicial e final sejam o mesmo;
4) Síntese dos Resultados: Quando um agente
resolve um problema, ele passa a solução para o
de cima, e assim sucessivamente.
Compartilhamento em Sistemas
Heterogêneos

Aplica-se quando atribuições de
subproblemas para agentes não são simples





agentes podem ter diferentes capacidades;
subproblemas precisam de diferentes
capacidades
As decisões precisam ser baseadas em
informações mais dinâmicas.
Contract Net Protocol
E quando os agentes não estiverem
disponíveis para executar sub-tarefas?
Compartilhamento em Sistemas
Heterogêneos

Adaptações do Contract Net




Contratação publicada
Tentar novamente
Revisão de anúncio
Decomposições alternativas
Compartilhamento de
Resultados


Uma mesma tarefa pode ter resultados
diferentes se executada por agentes
diferentes.
Solucionadores de problemas podem
aumentar o desempenho do grupo se
combinarem as seguintes características:




Confiança
Completude
Precisão
Conveniência
Compartilhamento de
Resultados

Complicações:



os agentes precisam conhecer o que fazer com
os resultados compartilhados
a comunicação de um grande volume de
resultados pode ser custoso.
Técnicas:



Cooperação funcionalmente precisa
Repositórios compartilhados e busca negociada
Estruturação organizacional
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!
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
Planejamento distribuído

Existem três classes de planejamento
distribuído:



Planejamento centralizado de planos
distribuídos
Planejamento distribuído de planos
centralizados
Planejamento distribuído de planos
distribuídos
Planejamento centralizado de
planos distribuídos

Contexto:



Um problema a ser resolvido e vários agentes
disponíveis
Agente coordenador
Objetivo:

Encontrar, no espaço de planos o que pode ser
decomposto e distribuído mais rapidamente.
Planejamento centralizado
de planos distribuídos

Dado o objetivo, um conjunto de operadores
e um estado inicial, o coordenador:


Gera um plano parcialmente ordenado
Decompõe este plano em sub-planos



Restrições de ordenação devem ficar dentro e não
entre os sub-planos
Insere sincronização
Atribui sub-planos a agentes
Planejamento distribuído de
planos centralizados

Contexto:


Tarefa muito complexa que requer o
auxílio de especialistas em cada subtarefa
Objetivo

Utilizar a expertise de cada agente para
formular sub-planos especializados
Planejamento distribuído de
planos centralizados


Feito de forma síncrona ou assíncrona
Síncrona:


A ordenação é feita durante o processo
de planejamento
Assíncrona

Somente durante o compartilhamento de
resultados os conflitos com relação à
ordem são resolvidos
Exemplos

Manufatura:


Logística:


especialistas em geometria, encaixe, pintura,
etc.
especialistas em planejamento de caminho,
carregamento de veículos e despache
Comunicação fim-a-fim:

especialistas no roteamento de mensagens
Planejamento distribuído de
planos distribuídos



Há apenas planos parciais de relevância
local
Compatibilidade global entre esses planos
parciais deve ser mantida

evitar conflitos durante a execução

fomentar ajuda mútua
Troca de mensagens e/ou temporização são
usados para resolver interações negativas
Planejamento distribuído de
planos distribuídos



Fusão de planos
Construção iterativa de planos
Negociação de planejadores
distribuídos
Fusão de Planos



Cada agente formula planos que podem ser
executados separadamente
Um agente coleta os planos individuais e
analisa para descobrir que seqüências de
ações podem causar conflitos
Três etapas



Análise de interação
Análise de segurança
Resolução de interação
Negociação de planejadores
distribuídos

Principais ferramentas:



A linguagem utilizada pelos participantes
O protocolo seguido durante a
negociação
O processo de decisão usado para
determinar suas posições, concessões e
critérios
Atributos Ideais do Mecanismo
de Negociação





Eficiência
Estabilidade
Simplicidade
Distribuição
Simetria
Planejamento Distribuído
Contínuo


Planejamento e execução intercalados
Um agente deve planejar continuamente
quando:




Aspectos do mundo podem mudar
dinamicamente
Aspectos do mundo são revelados
incrementalmente
Pressão do tempo faz com que a execução
comece antes do plano ter sido totalmente
gerado
Os objetivos podem evoluir com o tempo
Planejamento, coordenação e
execução intercalados







Decomposição de tarefas
Formulação de planos locais
Abstração de planos locais
Identificação de objetivos globais
parciais
Ação em planos globais parciais
Modificação em andamento
Re-alocação de tarefas
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
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!