Cooperação e Coordenação em SMA Agentes Autônomos CIn – Centro de Informática Universidades Federal de Pernambuco

Cooperação e Cooperação e Coordenação em SMACoordenação em SMA

Agentes AutônomosCIn – Centro de Informática

Universidades Federal de Pernambuco

RoteiroRoteiro

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 JuntosAgentes 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 Resolução Cooperativa de Problemas DistribuídosProblemas 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 Resolução Cooperativa de Problemas DistribuídosProblemas 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 Compartilhamento de Tarefas e ResultadosResultados

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ícioExemplo: Construção de Edifício

Analisador de solo

Carregador de material

Construtor

Solicita análise de solo para construção apropriada das fundações


Analisador de solo


Construtor

Resultado da análise de solo


Analisador de solo


Construtor

Solicita material


Analisador de solo


Construtor

Entrega material

Compartilhamento de Tarefas Compartilhamento de Tarefas Usando Contract-NetUsando 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”

(1) Agente reconhece existência de tarefa que não pode desempenhar sozinho

Funcionamento do Contract-NetFuncionamento do Contract-Net


(2) Agente anuncia a tarefa para os demais agentes


(2) Agentes enviam suas propostas


(4) Uma proposta é escolhida e o contrato é emitido

(3) Propostas recebidas são analisadas e a melhor é escolhida

Coordenação em SMACoordenação em SMA

O que acontece quando agentes possuem ações inter-dependentes?

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?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 Quando Ações Devem Ser Coordenadas?Coordenadas?

Informações e resultados disponíveis apenas através de outros agentes

Ex.: Agente construtor precisa que alguém lhe forneça material

Recursos limitados

Tempo, espaço, dinheiro, ferramentas ...

Otimização de custos

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çõesRelaçõ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

Incompatibilidade de objetivos, limitação de recursos

Relações positivas: favorecem ações fazendo com que uma se beneficie de outra

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çõesRelações Entre Ações

Incompatibilidade de Objetivos

Conflito de Recursos

Recursos Consumíveis

Recursos Não Consumíveis

Relação de Favor

Relações de Conseqüência

Relação de Igualdade

Relações Entre Ações

Relações Positivas

Relações Negativas

Algumas Formas de CoordenaçãoAlgumas Formas de Coordenação

Coordenação via SincronizaçãoCoordenaçã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 PlanejamentoCoordenaçã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 ReativaCoordenaçã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çõesSincronizaçã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 PlanejamentoCoordenaçã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 PlanejamentoModos de Planejamento

Planejamento centralizado para múltiplos agentesPlanejamento centralizado para múltiplos agentes

Único agente responsável por elaborar plano

Coordenação centralizada para planos parciaisCoordenaçã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 parciaisCoordenaçã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 Planejamento Centralizado Para Múltiplos AgentesMú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 Planejamento Centralizado Para Múltiplos AgentesMúltiplos Agentes

Coordenador do plano

Executor

ExecutorExecutor

Executor

Plano

PlanoPlano

Plano

Coordenação Centralizada Para Coordenação Centralizada Para Planos ParciaisPlanos 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 Coordenação Centralizada Para Planos ParciaisPlanos ParciaisCoordenador

Plano parcial

Obj. A

Obj. B

Obj. C

Obj. D

Plano coordenado

Planejador/Executor

Planejador/Executor

Planejador/Executor

Planejador/Executor

Coordenação Distribuída Para Coordenação Distribuída Para Planos ParciaisPlanos 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


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


Executor/Planejador

Executor/Planejador

Executor/Planejador

Obj. A

Obj. B

Obj. CPedidos, informações e planos parciais

Coordenação ReativaCoordenaçã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 Ex.: Movimentação de Grupo de Agentes ReativosAgentes Reativos

Craig Reynolds (1987) propôs:

Comportamento baseado em regras de posicionamento observadas por todos os membros da sociedade

Especificam distância mínima, direção e velocidade dos agentes

Gera comportamento similar a de pássaros migratórios

Comportamento coletivo emergente !

Facilmente extensível para outras situações !

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 AmbienteMarcaçã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 MotoExemplo: Montagem de uma Moto

Quadro

Roda Traseira

Roda Dianteira

Motor

R1 R2


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


e estou no ponto de montagem

e percebo a roda dianteira no ponto de montagem

então ir para depósito de motor


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 !

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


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 Outros Tipos de Mecanismos de CoordenaçãoCoordenação

Intenções ConjuntasIntençõ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útuaModelagem 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 Outros Tipos de Mecanismos de CoordenaçãoCoordenação

Normas e Leis SociaisNormas 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 Seleção Dinâmica de Mecanismos de Coordenaçãode 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 Seleção Dinâmica de Mecanismos de Coordenaçãode 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

BibliografiaBibliografia

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

Documents

Cooperação e Coordenação em SMA Agentes Autônomos CIn – Centro de Informática Universidades Federal de Pernambuco