Cooperação e
Coordenação em SMA
Agentes Autônomos
CIn – Centro de Informática
Universidades Federal de Pernambuco
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
Coordenação Reativa

Baseado na idéia de que é mais fácil agir diretamente, sem planejar
antes !

Solução baseada em agentes reativos:

Agentes simples, situados, trabalham no “presente”

Não possuem representação do ambiente

Reação depende da apenas da sua percepção do ambiente!

Solução aparentemente simplista, porém muitos agentes reativos
trabalhando juntos possuem grande capacidade

Exemplos de técnicas para coordenação reativa:

Campos Vetoriais para determinar movimentação de agentes móveis

Marcas no ambiente para coordenar ações dos agentes
Ex.: Movimentação de Grupo de
Agentes Reativos

Craig Reynolds (1987) propôs:

Comportamento baseado em regras de posicionamento observadas por
todos os membros da sociedade


Gera comportamento similar a de pássaros migratórios


Comportamento coletivo emergente !
Facilmente extensível para outras situações !


Especificam distância mínima, direção e velocidade dos agentes
Seguir líder, dispersão, distribuição sobre território, etc.
Steering behaviours:

Fórmulas matemática determinam movimentação dos agentes

http://www.red3d.com/cwr/steer/
Marcação do Ambiente

Idéia é utilizar o ambiente como uma forma de comunicação
flexível, robusta e simples

Uma Marca é um sinal ou “impressão” no ambiente


Podem ser adicionadas, removidas ou lidas pelos agentes

Também podem “desaparecer” com o passar do tempo
Importante:

Em coordenação reativa, adicionar agentes aleatoriamente não
necessariamente aumenta a performance do sistema!
Exemplo: Montagem de uma Moto
R1
R2
Roda Traseira
Motor
Quadro
Roda Dianteira
Exemplo: Montagem de uma Moto
Regra pegarPeça
se não estou carregando nada
e estou em frente de um depósito de peças
pegar o que está na minha frente
então ir para ponto de montagem
Regra buscarMotor
se não estou carregando nada
e estou no ponto de montagem
e percebo a roda dianteira no ponto de montagem
então ir para depósito de motor
Exemplo: Montagem de uma Moto

Solução com um único agente é bastante simples

Com mais de um agente pode ocorrer o caso da mesma peça ser
adicionada duas vezes

Solução?

Fazer com que agentes possam ver o que os demais estão fazendo!

Funciona? Mais ou menos ...

Agente R1 teria que saber se Agente R2 tem realmente a intenção de levar
a peça para o ponto de montagem

Não é facilmente extensível, se houver n agentes, deve-se saber o que os
outros n-1 agentes estão fazendo !
Exemplo: Montagem de uma Moto

Solução 2:

Marcar no ambiente aquilo que agentes estão fazendo no ponto de montagem

Necessita apenas pequena alteração nas regras !
Regra buscarMotor
se não estou carregando nada
e estou no ponto de montagem
e percebo a roda dianteira no ponto de montagem ou uma
marca buscarRodaDianteira
então ir para depósito de motor e colocar marca buscarMotor
Outros Tipos de Mecanismos de
Coordenação


Intenções Conjuntas

Conhecer as intenções dos demais agentes ajuda a coordenar ações

Agentes em uma tarefa cooperativa assumem um compromisso com o
grupo

Devem também existir convenções sociais (guias) associadas

Especificam quando um compromisso pode ser quebrado

Como um agente deve se comportar perante os demais
Modelagem Mútua

Mecanismo de coordenação onde comunicação não é necessária

Agentes possuem um modelo dos demais agentes (crenças, intenções,
etc.)
Outros Tipos de Mecanismos de
Coordenação

Normas e Leis Sociais

Convenções sobre as quais o agente pode regular seu comportamento

Uma norma especifica um padrão de comportamento a ser seguido.
Ex.: fazer fila para entrar no cinema (Não furar fila !)

Leis Sociais são normas, mas as quais estão associadas punições. Ex.:
uma pessoa pode ir para cadeia por assalto a banco !

Simplifica processo de tomada de decisão


Dita curso de ações a serem seguidas em determinadas situações
Podem ser especificadas em tempo de projeto ou emergir a partir do
próprio sistema
Seleção Dinâmica de Mecanismos
de Coordenação

Mecanismos de coordenação vistos possuem propriedades e
características distintas sendo adequados para diferentes situações

Diferem principalmente quanto:

Nível de coordenação a ser preestabelecida em tempo de
desenvolvimento

Tempo e esforço necessários para estabelecer coordenação em tempo
de execução

Grau de sucesso e surgimento de comportamento coordenado em
determina situação
Seleção Dinâmica de Mecanismos
de Coordenação

Não há um mecanismo de coordenação universalmente melhor !

Seria importente permitir que agentes fossem capaz de selecionar
qual mecanismo usar em determinada situação:


Para tarefas importantes, melhor adotar mecanismo que tem alta
possibilidade de sucesso mesmo custando caro

Para tarefas não muito importante, pode-se fazer o contrário !
Existem estudos que visam permitir a seleção de mecanismos de
coordenação em tempo de execução

Excelente-Toledo e Jennings

Bastante útil quando lida-se com ambientes dinâmicos, abertos e
heterogêneos
Bibliografia

Jacques Ferber, Multi-Agent Systems – An Introduction to
Distributed Artificial Intelligence

Michael Wooldridge, Na Introduction to MultiAgent Systems

Excelent-Toledo, Jennings, The Dynamic Selection of Coordination
Mechanisms