Roteiro


Agentes Trabalhando Juntos

Resolução Cooperativa de Problemas Distribuídos

Compartilhamento de Tarefas e Resultados

Compartilhamento de Tarefas Usando Contract-Net

Funcionamento do Contract-Net
Coordenação em SMA

O Que é Coordenação

Quando Ações Devem Ser Coordenadas

Relações Entre Ações

Algumas Formas de Coordenação
Agentes Trabalhando Juntos

Como desenvolver agentes que podem trabalhar juntos de maneira
eficiente?

O conceito de cooperação de SD é suficiente?


Não !

Agentes devem agir de maneira “estratégica”: agentes heterogêneos,
interesses próprios (diferentes objetivos), etc.

Autonomia dos agentes !
Agentes que trabalham juntos devem compartilhar Tarefas,
Informações e Coordenar Atividades
Resolução Cooperativa de
Problemas Distribuídos

Agentes com diferentes habilidades trabalhando juntos de maneira
a resolver problemas que estão além das suas capacidades
individuais

Assume existência de agentes benevolentes:


Sempre compartilham mesmos objetivos (não há espaço para conflitos)

Ajudam sempre que necessário
No entanto, a área de sistemas multi-agentes estuda sociedade de
agentes autônomos, com interesses próprios !

Pergunta chave: por que e como agentes cooperam?
Resolução Cooperativa de
Problemas Distribuídos



Decomposição do problema

Decomposição hierárquica até atingir granularidade desejada

Escolher mecanismo de decomposição

Capacidade dos agentes deve ser conhecida
Solução do sub-problema

Sub-problemas resolvidos individualmente

Agentes podem compartilhar informações
Síntese da solução

Soluções individuais integradas hierarquicamente em apenas uma
Compartilhamento de Tarefas e
Resultados

Problema decomposto em sub-problemas menores alocados para
agentes diferentes


Alocação das tarefas depende da arquitetura dos agentes:

Caso mais simples: agentes com mesmas habilidades e sem autonomia

Estabelecimento de acordos: agentes com habilidades distintas e
autônomos
Agentes compartilhando informações relevantes para resolução de
sub-problemas

Pró-ativa: Agente envia informação por acreditar que essa informação
auxiliará outro agente

Reativa:Agente envia informação como resposta a uma solicitação
Exemplo: Construção de Edifício
Construtor
Analisador de solo
Solicita análise de solo
para construção
apropriada das fundações
Carregador de material
Exemplo: Construção de Edifício
Construtor
Analisador de solo
Resultado da análise de
solo
Carregador de material
Exemplo: Construção de Edifício
Construtor
Solicita material
Carregador de material
Analisador de solo
Exemplo: Construção de Edifício
Construtor
Entrega material
Carregador de material
Analisador de solo
Compartilhamento de Tarefas
Usando Contract-Net


Protocolo de alto nível voltado para obtenção de uma estratégia de
cooperação eficiente

Desenvolvido por R. G. Smith em 1979 e baseado em protocolos de
mercado público

Visa o compartilhamento de tarefas entre vários agentes
Composto por 4 etapas:

Anuncio da tarefa, encaminhamento de proposta, análise das propostas
e emissão do “contrato”
Funcionamento do Contract-Net
(1) Agente reconhece
existência de tarefa
que não pode
desempenhar sozinho
Funcionamento do Contract-Net
(2) Agente anuncia a
tarefa para os demais
agentes
Funcionamento do Contract-Net
(2) Agentes enviam
suas propostas
Funcionamento do Contract-Net
(3) Propostas
recebidas são
analisadas e a melhor
é escolhida
(4) Uma proposta é
escolhida e o contrato é
emitido
Coordenação em SMA

O que acontece quando agentes possuem ações interdependentes?

Necessário gerenciar inter-dependências !

Mecanismos de coordenação são essenciais quando agente
possuem atividades que interagem entre si

Exemplos de atividades:

Duas pessoas tentando sair de uma sala por uma porta estreita

Funcionário precisa de assinatura de gerente para enviar um
documento

Aluno A encontra artigo de interesse de B e encaminha-o (atividade
pró-ativa)
Então, O Que é Coordenação?

Quando agentes trabalham juntos é necessário gerenciar algumas
tarefas complementares

Tarefas de coordenação:


Fazem parte do sistema organizacional e possibilitam a execução das
tarefas produtivas
Então, coordenação é o conjunto de tarefas suplementares que
devem ser executadas em um SMA, as quais não seriam
necessárias caso existisse apenas um único agente
Quando Ações Devem Ser
Coordenadas?

Informações e resultados disponíveis apenas através de outros
agentes


Recursos limitados


Tempo, espaço, dinheiro, ferramentas ...
Otimização de custos


Ex.: Agente construtor precisa que alguém lhe forneça material
Eliminação de tarefas desnecessárias e redundantes
Agentes com objetivos inter-dependentes cooperando entre si

Ex.: Dois agentes trabalhando no mundo dos blocos (sem competição!)
Relações Entre Ações

Algumas ações quando executadas simultaneamente podem levar
a conflitos ou aumento da performance

Relações negativas: impossibilitam a execução de algumas ações


Relações positivas: favorecem ações fazendo com que uma se
beneficie de outra


Incompatibilidade de objetivos, limitação de recursos
Maior eficiências do que se ações fossem executadas
independentemente
Em SMA, coordenação acontece em tempo de execução

Agentes devem reconhecer relações e tratá-las quando elas ocorrem
Relações Entre Ações
Relações
Entre Ações
Relações
Negativas
Conflito de
Recursos
Recursos
Consumíveis
Incompatibilidade
de Objetivos
Recursos Não
Consumíveis
Relações
Positivas
Relação de
Igualdade
Relação de
Favor
Relações de
Conseqüência
Algumas Formas de Coordenação



Coordenação via Sincronização

Maneira mais simples e limitada de coordenação (originária de SD)

Descreve precisamente a seqüência de ações concorrentes
Coordenação via Planejamento

Fases de elaboração de planos e execução do plano escolhido

Limitados com relação a eventos não previstos e situações muito
complexas
Coordenação Reativa

Não existe fase de planejamento, fazem uso do ciclo percepção-ação
do agente

Adequadas para situações onde é difícil prever o que irá acontecer
Sincronização de Ações

Definir a relação de tempo existente entre as ações de modo que:

Sejam executadas na ordem correta

Produzam o resultado esperado

Deve ser aplicada quando o objetivo é prover coerência e evitar
interferência entre ações

Situações típicas:

Sincronização de movimentos


Ex.: dois agentes andando de bicicleta
Sincronização para acesso a recurso

Ex.: controle de acesso a uma máquina
Coordenação via Planejamento


Problema de planejamento em SMA é mais complexo do que o
caso tradicional

Ações de vários agentes devem ser levadas em consideração

Maior necessidade de replanejamento

Maior interdependência entre ações, dificultando ordenamento das
ações, etc...
Em SMA, planejamento pode se quebrado em 3 fases:

Elaboração de planos, sincronização/coordenação e execução de
planos
Modos de Planejamento

Planejamento centralizado para múltiplos agentes



Único agente responsável por elaborar plano
Coordenação centralizada para planos parciais

Tarefa de elaboração de plano distribuída

Único agente responsável for sincronizar/coordenar sub-planos
Coordenação distribuída para planos parciais

Tarefa de elaboração de plano distribuída

Cada agente deverá ter a iniciativa de sincronizar seu sub-plano com
os demais agentes
Planejamento Centralizado Para
Múltiplos Agentes

Apenas um agente capaz de planejar e organizar ações para todos
os agentes

Demais agentes são simplesmente executores de planos

Construção do plano composta por 3 etapas:

Encontrar um plano parcial geral

Determinar pontos do plano que podem ser executados em paralelo
(Identificação de sub-planos)

Incluir pontos de sincronização

Alocar os sub-planos para os demais agentes
Planejamento Centralizado Para
Múltiplos Agentes
Coordenador do plano
Plano
Plano
Plano
Plano
Executor
Executor
Executor
Executor
Coordenação Centralizada Para
Planos Parciais

Apenas a etapa de coordenação é centralizada

Cada agente desenvolve seu próprio plano parcial e o encaminha
para o coordenador

Coordenador tenta sintetizar todos os sub-planos em um único
plano coerente


Identificar conflitos e eliminá-los via ordenação de ações ou inclusão
pontos de sincronização
Coordenador capaz de identificar tanto relações positivas quando
negativas
Coordenação Centralizada Para
Planos Parciais
Coordenador
Plano coordenado
Obj. A
Obj. D
Plano parcial
Obj. B
Planejador/
Executor
Planejador/
Executor
Obj. C
Planejador/
Executor
Planejador/
Executor
Coordenação Distribuída Para
Planos Parciais

Não existe o papel de coordenador em nenhuma das etapas

Cada agente planeja individualmente as ações que deseja executar de
acordo com seus objetivos

Maior dificuldade é identificar relações entre as ações que compõem os
diversos sub-planos

Agentes devem trocar informações sobre os seus planos e objetivos
Coordenação Distribuída Para
Planos Parciais

V. Lesser e E. Durfee desenvolveram o modelo Partial Global
Planning (PGP)

PGP é uma estrutura contendo informações sobre os planos do
agente, seu objetivos, custos associados, resultados esperados,
etc.

Agentes trocam PGP e tentam identificar:

Agentes cujos objetivos façam parte de um objetivo de grupo

Planos que possam ser combinados
Coordenação Distribuída Para
Planos Parciais
Obj. A
Pedidos, informações e
planos parciais
Executor/
Planejador
Obj. B
Executor/
Planejador
Obj. C
Executor/
Planejador