MultiStage
Um Protocolo para Resolução
de Conflitos em Negociação
Multiagente
Emerson Luís dos Santos
Fabiano Mitsuo Hasegawa
Márcio Roberto Starke
Introdução
●
●
IAD
●
Sistemas Distribuídos  IA
●
Resolução Distribuída de Problemas
●
Sistemas Multiagentes
●
Melhor utilização de recursos
●
Visão local das partes de um problema
●
Diversos problemas reais são distribuídos
Sistemas Multiagentes
●
Alto nível de autonomia
●
Flexibilidade e Escalabilidade
Sistemas Multiagentes
 Ambiente
●

Recursos

Influências
Unidade básica: Agente

Simples
– Monolítico
– Modular
 Composto
Sistemas Multiagentes
 Organizações

comunidade vivendo em prol dos mesmos
interesses
 Sociedade

Conjunto de organizações que compõem um
sistema

Regras

Homogêneas/Heterogêneas
Características de uma Sociedade
 Colaboração
 Cooperação
 Competição
 Evolução

Adaptação

Aprendizado
 Ciclo de vida
 Migração
 Comportamentos Sócio-naturais
Composição de um Agente
 Reativo

Mapeamento estado/ação

Percepção

Baixo nível de autonomia
Composição de um Agente
 Cognitivo
 Self-Model
 Acquaintance-Model
 Comunicação
 Coordenação
 Planejamento
 Aprendizado
 Negociação
 Competências (Controle de recursos)
 Raciocínio
 Emoção
 Objetivos
 Percepção
 Alto nível de autonomia
Tipos de Coordenação
 Padronização

Regras

Arquitetura
 Supervisão

Hierarquia
 Ajuste Mútuo

Consenso
Negociação
 Tipos
que se
mundo real

Contrato

Acordo

Troca

Oferta

Híbridos
poderia
identificar
 Problemas

Conflitos por escassez de recursos

Causas externas (Falhas)
no
Protocolo Contract-Net
 Recebimento de tarefa
 Decomposição da tarefa em sub-tarefas *
 Anúncio de sub-tarefa
 Ofertas dos candidatos
 Premiação da melhor oferta
 Confirmação da oferta
Protocolo Contract-Net
 Delegação da sub-tarefa ao contratado
 Execução ou repasse da sub-tarefa
 Devolução
do
Sub-resultado
contratante
 Recomposição dos sub-resultados
ao
O Protocolo Multistage

Generalização do protocolo contractnet
• Primitivas adicionais
• Restabelecimento de contrato

Comunicação e recursos limitados

A satisfação de um objetivo pode impedir
a
satisfação
de
outro
ou
ser
inalcançável por si

Capacidades preemptivas na alocação de
recursos para conexões de diferentes
O Protocolo Multistage

Através da troca de informações, os
agentes tratam os conflitos de
recursos
modificando
seu
comportamento

Decisões sobre o impacto de escolhas
locais na satisfação de objetivos
globais

Informações incompletas ou inválidas
atualizadas dinamicamente
 Geração e manutenção de planos
Domínio das Telecomunicações
 Recursos limitados
 Cada agente detém o controle de uma
área e seus respectivos recursos
interconectados por links de dados
 Agentes trocam informações através de
links de comunicação exclusivos com
baixa largura de banda
 A conexão entre dois recursos exige a
reserva de banda nos links pertencentes
ao caminho
 Uma falha em qualquer equipamento de
comunicação pode causar a instanciação
de vários objetivos que devem ser
satisfeitos em tempo real
Domínio das Telecomunicações
Conexões
Instanciadas independentemente e ao
mesmo tempo em cada um dos agentes das
extremidades
 Cada agente sabe quais são os agentes
da extremidade de cada conexão
 Constituição

•
•
•
•

Recurso Inicial
Recurso Final
Identificador
Prioridade
Exemplo
• p-1:s-3:5:1 (AgenteI-RecursoI:AgenteF-RecursoF:ID:Prioridade)
Geração de Planos





A instanciação de um objetivo dispara um
processo de geração de planos
A escolha do melhor plano é baseada em
informações extremamente locais
Planos
sobressalentes
são
armazenados
para
eventuais
necessidades
posterior
com
identificadores apropriados
Um plano consiste de fragmentos locais
de um caminho que são armazenados
localmente nos respectivos agentes
Algoritmo exaustivo de busca em
Satisfação de Objetivos
 Nem todos os agentes necessariamente
têm conhecimento da satisfação de um
objetivo
 Agentes
conhecem
apenas
seus
fragmentos de plano e objetivos locais
 Conflitos são propagados através de
mensagens
 Conflitos
surgem por escassez de
recursos locais ou por negação de
serviços
 Agentes
armazenam
informações
Visão Geral da Negociação
Instanciação
do
objetivo
nas
extremidades
 Geração de planos
 Requisição
de
estabelecimento
de
conexão aos vizinhos apropriados para
satisfação do maior número de objetivos
possíveis
 Análise de requisições recebidas

• Pedidos de estabelecimento de conexão
• Confirmações de estabelecimento de conexão
• Negação de pedidos e informação dos devidos
conflitos


Atualização de informações internas
Reavaliação dos objetivos locais e novas
Particularidades de
Nomenclatura

Primary Goal
• Objetivo que possui ao menos uma das
extremidades no agente

Secondary Goal
• Objetivo que não possui extremidade no
agente

Task Announcement¹
• Pedido de complementação de plano

Response¹
• Resposta a um task announcement
– Bid: resposta positiva
– Reject: resposta negativa
Particularidades de
Nomenclatura

Tentative Commitment
• Pedido de estabelecimento de conexão com
reserva de recursos locais

Conflict
• Conflito local ao transmissor

Cancellation
• Conflito não-local ao transmissor

Commitment
• Confirmação de estabelecimento de conexão

Feasibility Tree
• Base de conhecimento mantida no agente
Complexidade
Os membros da organização não possuem
recursos suficientes para manterem
visões globais consistentes
 Devido ao dinamismo do mundo, o
conjunto de soluções ótimo em um
determinado instante pode não ser mais
o conjunto ótimo do instante seguinte

Limitações

Novos objetivos primários só são
considerados se não houver nenhum
outro objetivo primário sendo resolvido

Não converge para otimização

Planos são subutilizados

Não é claro quando se descartar planos

Não há adaptação
Aprendizado por Reforço

Domínios em que o aprendizado deve ser
realizado em tempo real

Adaptação rápida mesmo com poucos
exemplos

A cada ação tomada, recebe-se um prêmio
positivo/negativo correspondente aos
efeitos dessa ação no mundo

Maximização
recebidos

Aprendizado de uma política de atuação
da
soma
dos
prêmios
Motivação

Estimativas de custo de planos podem
proporcionar melhoria na performance
global

Melhores
iterações

Potencial Memória para Capitalização de
Conhecimento
práticas
ao
longo
das
TPOT-RL (Team-Partitioned, OpaqueTransition Reinforcement Learning)
 Aprender uma função que associa pares
estado-ação a prêmios esperados
 Os
resultados são armazenados em
tabelas para a sua posterior utilização
 Introduz três principais adaptações ao
paradigma de aprendizado por reforço

A função de valor é particionada entre a
organização, com cada agente aprendendo
apenas para estados em quais ele pode atuar.
Todos
os
agentes
são
treinados
simultaneamente
TPOT-RL (Team-Partitioned, OpaqueTransition Reinforcement Learning)

O espaço de estados do ambiente é
agressivamente generalizado, de forma que o
agente percebe o ambiente em função de
características
discretas
referentes
a
estados

Ao invés de se atualizar a tabela de
aprendizado segundo estimativas de prêmio
geradas por simulações, as atualizações são
feitas segundo prêmios recolhidos algum
tempo no futuro
Módulo de Aprendizado
 Escolha de ação

para
cada
par
(recurso_local_inicial,
recurso_destino_objetivo), há uma tabela com
tantas entradas quantos forem os planos que
tenham sidos gerados durante a fase de
geração de planos
Módulo de Aprendizado
 Propagação de prêmio e atualização de
tabela

quando uma conexão é estabelecida, o agente
destino envia mensagens aos agentes que
fazem parte do circuito informando-lhes o
custo total da conexão. Quando um agente
recebe esta mensagem, ele decrementa do
custo total o valor de custo acumulado até
seu recurso inicial
Módulo de Aprendizado
 Geração de planos

periodicamente são gerados novos planos
para cada conexão estabelecida; em eventuais
falhas, o tempo de restauração será menor

buscas para satisfação de requisições de
estabelecimento
de
conexão
só
são
realizadas numa eventual não existência de
planos pré-construídos

na geração de planos, contabiliza-se as
estimativas de planos gerados no passado

Planos com estimativas
podem ser podados

para cada plano gerado, seu custo associado
históricas
ruins
Vantagens do Módulo de
Aprendizado
 Redução das gerações de planos

Planos com estimativas úteis para um
determinado objetivo podem existir a priori

a geração de planos é periódica e pode ser
congruente com a carga da rede ou o desejo
do administrador
 Coerência com o estado global

a escolha de um plano para a satisfação de um
objetivo não é executada apenas conforme
estimativas de custo local, mas segundo
estimativas que refletem a atividade global da
rede coletadas como prêmios que são
propagados em intervalos periódicos
Vantagens do Módulo de
Aprendizado
 Redução do tempo de resposta

o tempo de restauração e estabelecimento de
conexões é sensivelmente reduzido, uma vez
que os planos podem já estar prontos e com
estimativas
de
custo
atualizados
e
consistentes
Desvantagens do Módulo de
Aprendizado

Memória
• O número de tabelas mantido em memória
segundo esta abordagem é superior ao
necessário em [Sto98]
• Na aplicação de Stone, só uma tabela de
tamanho | U | x | A | x | M | é mantida em cada
agente
– U: janela de atividade {baixa, alta}
– A: conjuntos de links que partem de um nó
– M: número total de nós da rede
• na abordagem proposta, existem | U | x | A | x |
O|
– U: janela de atividade {baixa, alta}
– A: número de planos existentes para cada conexão
estabelecida
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

Qual seria o rendimento de uma empresa
que tivesse que treinar seu funcionário
toda vez que ele fosse requerido em uma
tarefa?

Pessoas nos diversos cenários do dia-adia aprendem a atuar adequadamente
tentando executar suas tarefas da
forma mais eficaz possível

No mundo real, pessoas
aptidões natas (dons)
possuem
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

Habilidade está diretamente relacionado
a atividade e seu aumento é gradativo

A habilidade também pode ser obtida
através da observação, da escuta, da
leitura, do estudo, do erro, por
analogia, entre outros

A memória é utilizada nos processos de
raciocínio desenvolvidos ao longo da
vida
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

Uma vez que seus integrantes possuem
tamanhas capacidades, as organizações
existentes nas sociedade tendem a
apresentar
comportamentos
semelhantes, pois são gerenciadas por
seres inteligentes e sua mão-de-obra
também é constituída de indivíduos com
inteligência

Dentro deste ambiente, pode-se concluir
que a sobrevivência é bastante difícil

Paradoxalmente, a sobrevivência está
sendo alcançada de forma relativamente
satisfatória pelos seres do mundo real
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

Em uma sociedade de agentes de
software, as mesmas características e
comportamentos são desejáveis

Habilidade
• A única maneira de se conseguir boas práticas
é pelo aprendizado, o que implica esforço
computacional na manutenção de uma memória
e na criação de métodos de inferência que
permitam a extração de conhecimento dos
fatos observáveis
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

A utilização do Reinforcement Learning
para
a
melhoria
do
protocolo
Multistage garante as capacidades de se
adaptar dinamicamente às transições de
estados do mundo e de se manter uma
memória organizacional

Executando
segundo
as
melhores
políticas de atuação, a otimização surge
conseguida naturalmente
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento

A memória poderia ser utilizada por
processos mais de auxílio à tomada de
decisão que indicassem, por exemplo, a
necessidade de se aumentar a banda de
um link, de se construírem novos
caminhos físicos ou de se reestruturar a
rede

Pode-se aplicar o Multistage em outros
domínios, utilizando os mesmos métodos
e alcançando as mesmas vantagens do
domínio das telecomunicações
Reflexões sobre a Relevância da
Proposta na Gestão do
Conhecimento
 Os agentes aprendem a atuar em prol da
organização
• sem a necessidade de perceber em todo o
mundo
• observando apenas os efeitos a longo prazo
de suas ações
 O
conhecimento de cada agente é
coerente com o conhecimento da
organização e com as transições de
estado de um domínio estocástico
Relevância da Abordagem na
Gestão do Conhecimento

Aplicações em
• WorkFlow
• Telecomunicações
• Trânsito
• Planejamento de Rotas para Robôs
• Reutilização do Conhecimento