Modelos Baseados em Agentes

CoordenaçãoCoordenação

Coordenação

Coordenação = Coordenar açõesdistribuição + planejamento

Resolução Distribuída de ProblemasProblemas que requerem “esforço coletivo”Distribuição de tarefasDistribuição de conhecimento (resultados)

PlanejamentoPlanejamento centralizado, distribuído, parcial...

Resolução Distribuída de Problemas

MotivaçãoVelocidade da resolução do problema

Ex.: distribuição de uma aplicação em várias máquinasEspecialização inerente ao problema

Ex.: monitoramento de uma grande área geográficaNecessidade de apenas uma “visão local”

Ex.: controle de tráfegoNecessidade dos resultados serem distribuídos

Ex.: Entrega distribuídaVisão otimista de sistemas multi-agentes

Todos são benevolentes (pró-social)Diferente de agentes centrados em si (self-interested)

RDP: QuestõesComo um problema pode ser dividido em menores para serem distribuídos?Como a solução de um problema pode ser sintetizada a partir de resultados de sub-problemas?Como a resolução dos sub-problemas pode ser otimizada de forma a maximizar a solução global?Que técnicas podem ser utilizadas para coordenar de forma eficiente as ações dos agentes?

Etapas e atividadesEtapas da RDP

Decomposição do problemaResolução dos sub-problemasSíntese das soluções

Atividades (provavelmente) envolvidasDistribuição de tarefasDistribuição de resultados

Pró-ativamenteRe-ativamente

Distribuição de tarefasExemplo: Contract Net

Olá !!! Preciso

resolver A

Faço por Y

Faço por X

Contrato feito

Meu problema P pode ser

dividido em A, B, C e D,

mas não sei como resolver

A

Identificaçãodo problema

Lançamento de propostas

Anúncio Contrato

Contract NetTipos de anúncios

Geral (broadcast)Restrito (focalizado em um grupo de agentes)Direto (a um ou mais agente que o solicitante conhece)

E se não houver proposta que atenda as necessidades?

Revisão do anúncioAnúncio periódicoInverter protocolo de interação

Proponentes fazer o anúncio (Feira Livre)

Tarefas interdependentesAo distribuir tarefas a diferentes agentes, nem sempre é possível resolvê-las de maneira independente.

Ex.: Engenharia de produtosInterdependência simples

O gerente solicita novas sub-tarefas a medida que suas dependências são resolvidas.

Interdependência mais complexaDistribuição de resultados

Distribuição de resultados

Retorno em relação ao desempenho do grupo:Confiança

Diferentes agentes chegando ao mesmo resultado reforça a confiança que aquele resultado está correto

CompletudeResultados de sub-problemas cobrem o problema como um todo

PrecisãoPara refinar sua solução, um agente precisa saber mais sobre a solução de outros agentes

RapidezMesmo se um agente é capaz de resolver um problema sozinho, a resolução em paralelo pode agilizar a solução.

Gerenciando inconsistênciasCooperação simples distribui tarefas

Todos agentes conhecem todas as informações necessárias e as especificações de suas sub-tarefasExemplo: Rede de contrato

Gerente possui visão global e solicita serviçosCooperação mais complexa

Os agentes possuem uma visão parcialSolução 1: negociação

Custo na troca de mensagensSolução 2: reduzir inconsistências “passo-a-passo”

Functionally Accurate / Cooperative (FA/C)

Functionally Accurate/CooperativeFA/C

Functionnaly Accurate (vários inícios “falsos”)Cooperativo (requer troca iterativa)

CaracterísticasResolução adaptativaAgentes trocam resultados intermediários em alto nível de abstraçãoInconsistência é resolvida por resultados parciaisNão existe apenas uma única solução possível

Solução iterativaGrande número de informações sendo trocadas

Limitando a comunicação na distribuição de resultados

Reduzir o número de mensagens trocadas entre os agentes

Se mensagens assíncronas “distração”Repositório compartilhado

Ex.: BlackboardDefinição de estruturas organizacionais

Agentes trocam mensagens no seio de gruposProcura heurística distribuída com restrições

Agenda de recursos disponíveis

DIMAp 14

Arquitetura de Blackboard (1)

• Principais componentes• O blackboard – espaço de dados global• Um conjunto de agentes (chamados

fontes de conhecimento) que atuam sobre o blackboard

• Um mecanismo de controleblackboard

DIMAp 15

Arquitetura de blackboard (2)

Nível 1

Nível 2

...

...

Nível nSolução

Hipóteses

Dados

Procura heurística c/ restriçõesInconsistência no uso de recursosUm agente associado a cada recurso

C

C

C

R

R

Tentativade demanda

C

C

C

R

R

Demandaagregada

C

C

C

R

R

Solicitaçãode reserva

C

C

C

R

R

Aceitação/rejeição

r

a

a

Técnicas de coordenaçãoProblema

Gerenciamento de interdependências entre as atividades dos agentes

TécnicasEstruturas organizacionaisPlanejamento Global Parcial (PGP)Coordenação baseada em trabalho em equipe

Intenções conjuntasModelagem mútua

Normas e leis sociaisPlanejamento multi-agente

Estruturas organizacionaisDefine um padrão de tomada de decisão e comunicação entre agentes

Ex: Indústria projetistas, engenheiros, vendas etc.

Responsável por modelar os tipos de interações entre agentesAjuda a coordenação especificando quais ações um agente em capaz de tomarEstruturas organizacionais podem ser

EspaciaisFuncionaisCentralizadasDescentralizadas

Estruturas Organizacionais (1)Hierarquia Espacial (do problema)

Designer

Gerente do produto A

VendasEngenheiro Designer

Gerente do produto B

VendasEngenheiro

Estruturas Organizacionais (2)Hierarquia funcional

Gerente de projetos

Designers

Gerente de designers

Vendas

Gerente de vendas

Engenheiros

Gerente de engenharia

Gerentes funcionais

Estrutura Organizacional (3)Mercado centralizado

Gerente de projeto A

Designers

Gerente de designers

Vendas

Gerente de vendas

Engenheiros

Gerente de engenharia

Gerente de projeto B Gerente de projeto C

Estrutura Organizacional (4)Mercado descentralizado

Gerente de projeto A

Designers VendasEngenheiros

Gerente de projeto B Gerente de projeto C

Discussão sobre as estruturasCusto da coordenação

Hierarquia espacial: +Hierarquia funcional: ++Mercado centralizado: +++Mercado descentralizado: ++++

Útil quando há uma relação de “mestre/escravo” entre os agentesPressupõe que, no mínimo, um agente possui uma visão geral do problema

Nem sempre ocorre isso em SMA

Planejamento Global ParcialAgentes cooperativos trocam informação de forma a chegarem a conclusões comuns sobre o processo de resolução do problemaPorque é “parcial”?

O sistema não gera um plano para o problema geral

Porque é “global”?Agentes expandem seus planos a partir da troca de planos locais com outros agentes

PGPAssume que

As tarefas são passíveis de serem decompostasUm agente com uma tarefa a ser planejada pode não ter conhecimento das tarefas que outros agentes estão planejando, nem como elas se relacionam com a suaAgentes não possuem necessariamente conhecimento de tarefas globais

Objetivo dessa técnica de coordenaçãoExpandir a visão dos agentes

Estágios do PGPEstágios

1) Cada agente decide por si mesmo quais são seus objetivos e gera planos de curto-prazo para alcançá-los2) Agentes trocam informação entre si para determinar se planos e objetivos interagem3) Agentes alteram planos locais de forma a melhor coordenar suas atividades

Para evitar incoerência no processo (estágios)Definição de uma “meta-estrutura” especifica quais agentes um agente deve trocar informações e em quais situações ele o fará

Representação de um PGPPGP

Uma estrutura de dados gerada cooperativamente contendo as ações e interações de um grupo de agentes

A estrutura possuiObjetivo

O objetivo global do grupoMapa de atividades

O que cada agente está fazendo e seus resultadosGrafo de construção da solução

Representação da interação dos agentes

Coordenação baseada em trabalho em equipe

Modelos baseados em equipes humanasModelagem de estados mentais intenções

Como uma intenção individual para alcançar determinado objetivo se distingue de uma equipe (uma intenção coletiva)?

Responsabilidade em relação a outros membros da equipeAcordo entre as partes antes de mudar uma açãoEx.: Duas pessoas carregando um objeto pesado

Objetivo/visão individual responsabilidade de equipe

Coordenação através de Intenções conjuntas

Em uma atividade cooperativa, os agentes devem possuir um engajamento conjunto, bem como engajamentos individuais.Engajamento

“Promessa” junto ao grupoPersistência de açõesPodem mudar ao longo do tempo (o grupo como um todo)Convenção maneira de monitorar engajamentos

Especifica em que circunstâncias um engajamento pode ser revisto ou abandonado

ConvençõesRazões para terminar um engajamento

Objetivo alcançadoCrença (coletiva) que o objetivo é impossívelMotivação/justificativa (coletiva) para alcançar o objetivo não mais existe

Convenções sociaisEspecifica como agir em relação aos outros membros da equipe

Coordenação através de modelagem mútua

Cada agente modela os demais agentes – suas crenças e intenções

Se coloca no “lugar do outro”Coordenação das atividades de um agente baseado no que ele acredita sobre os objetivos e intenções dos demaisCooperação sem comunicação

Teoria dos jogos pode ser utilizada (Dilema do prisioneiro)

Normas e leis sociaisNorma

Padrão de comportamento esperadoLei social

Similar a normas, porém estabelecido de forma autoritáriaPode ser especificado através de um conjunto de restrições (E’, a)

E’ E (conjunto de possíveis estados do ambiente)a A (conjunto finito de ações do agente)Se o ambiente se encontre em algum estado E’, então ação a é proibida

Construção de normas e leisPré-definidas

Autoritariamente definidas por quem projeta o sistemaEmergentes

Surgem a partir do comportamento do grupoMemória do grupo

Ex.: PrimatasGeração de normas emergentes

Como um grupo de agentes convergem para uma norma social usando apenas visões locais?

“Jogo da camisa”: cada agente possui duas camisas, cada uma com uma cor diferente todos devem vestir a mesma cor.

Estratégias para normas emergentes

Maioria simplesAgentes mudam para determinado comportamento se eles perceberem que a maioria age daquela maneira

Maioria simples por tipo de agenteAgentes se comunicam entre si para estabelecer categorias (em geral duas), onde eles se enquadram e adotam a maioria da categoria

Maioria simples com comunicação de sucessoAgentes só compartilham suas estratégias quando há algo “interessante” a ser compartilhado

Maior prêmio cumulativoAgentes adotam um comportamento quando o retorno de tal para o grupo de agentes é o melhor até o momento.

Coordenação através de planejamento multi-agente

DistribuiçãoPlanejamentoExecução dos planos

Planejamento centralizado para execução de planos de forma distribuída

Similar à distribuição de tarefasNem sempre planos centralizados encaixam na disponibilidade de execução dos demais agentes

Planejamento distribuído para execução de planos de forma centraliza

Agentes planejadores especialistas em diferentes áreasPlanejamento distribuído para execução de planos de forma distribuída

Complexo a gerenciar e interligar planos e ações

Combinação de planosProblemas de interdependência das ações de planos de diferentes agentesAlgoritmo de Georgeff (1983)

A partir de um conjunto de planos iniciais gerar planos para vários agentes de forma que não haja conflitos entre eles.1) Análise de interação2) Análise de segurança3) Resolução das interaçõesUtiliza o formalismo STRIPS aumentado

Formalismo STRIPSUtilizado para definir planos

Plano = seqüência de açõesCada ação definida a partir de:

NomeLista de pré-condições (pre)Lista de fatos que não serão mais válidos após a execução da açãoLista de fatos que serão verdadeiros após a execução da ação

Georgeff + Lista de fatos que devem ser verdadeiros durante a execução da ação

Etapas do algoritmoAnálise de interação

Detecta as interdependências de açõesSatisfatórioComutativoPrecedência

Análise de segurançaDetecta que situações (ações em paralelo) não devem existir

Resolução de interaçãoResolve as situações problemáticas

Exemplo do algoritmoPlano de X = {a, b, c} e Plano de Y = {k, l, m, n}Análise de interação

(a,k) = comutativo; (b,m) = b precede m; etc.Análise de segurança

Remove todas ações comutativas (global)Teorema da comutatividade

A situação de iniciar a e b é problemática se um dos seus sucessores for problemáticoA situação de iniciar a e terminar b é problemática se a situação de terminar a e b é problemáticaA situação de terminar a e b é problemática se ambos sucessores são problemáticos

Resolução de interaçãoUso de semáforos para resolução de conflitos