Aprendizado Multiagente
Gustavo Danzi de Andrade
Geber Ramalho
Patrícia Tedesco
Objetivo
Apresentar as características, limitações,
vantagens e conseqüências da utilização de
mecanismos de aprendizado em
sistemas multiagente
Roteiro
Motivação
Alguns conceitos
Características do
Aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Motivação
 Por que SMA?
– Muitos problemas do mundo real são melhor
modelados/resolvidos através de um conjunto
de agentes
– Mas SMAs estão tipicamente inseridos em
ambientes complexos – grandes, dinâmicos, e
imprevisíveis.
 Por que aprendizado?
– A aquisição de conhecimento é difícil: envolve
dificuldades de desenvolvimento, manutenção,
adaptação e tratamento de incerteza.
– Mas a inteligência pode não depender apenas
de um único agente
Motivação
Portanto... por que não construir
o “melhor dos mundos”?
SMA
Aprendizado
Multiagente
Aprendizado
Roteiro
Motivação
Alguns conceitos
Características do
Aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Alguns Conceitos
Interação agente/ambiente:
Ambiente
Percepções
Ações
Alguns Conceitos
Agente que aprende (off-line):
Algoritmo de
Aprendizado
Exemplos
Inteligência!
Conhecimento
Percepções
Sensores
Ambiente
Ações
Efetuadores
Agente
Módulo de
Execução
Alguns Conceitos
Agente que aprende (on-line):
Percepções
Sensores
Seleciona as ações
externas a serem
executadas pelo
agente
Ambiente
Crítico
Melhora o
comportamento
futuro do agente
Módulo de
Execução
Módulo de
Aprendizagem
Inteligência!
Ações
Efetuadores
Agente
Gerador de
Problemas
Sugere ações para
promover
experiências novas e
informativas
Alguns Conceitos
Inteligência em SMA:
Por quê pensar a inteligência/racionalidade
como propriedade de um único indivíduo?
Não existe inteligência em...
Um time de futebol?
Um formigueiro?
Uma empresa (correios, ...) ?
Na sociedade?
O conceito de inteligência em SMA é muito
mais abrangente, portanto...
Alguns Conceitos
Aprendizado em um SMA não é
apenas uma ampliação do aprendizado
em sistemas “single agent”!
Aprendizado em um SMA não é a
soma dos aprendizados isolados de
cada agente!
Roteiro
Motivação
Alguns Conceitos
Características do
aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Categorias do Aprendizado em SMA
Generalizando, existem duas
categorias de aprendizado em SMA:
Aprendizado centralizado (ou isolado): o
processo é totalmente executado por um
agente, sem interação com demais agentes.
Aprendizado descentralizado (ou interativo):
vários agentes estão engajados em um mesmo
processo de aprendizagem. Pode haver ou não
troca de informação.
Em um SMA, um agente pode estar
envolvido em vários processos
centralizados/descentralizados
Características do Aprendizado em SMA
Grau de descentralização:
Distributividade
Paralelismo
Características do Aprendizado em SMA
Interação
Nível da interação: de observação a troca de informações
Persistência da interação: de curto a longo prazo
Freqüência da interação: de alta a baixa
Padrão da interação: de não-estruturado a
hierárquico
Variação: de fixa a mutável
Envolvimento
Relevância do envolvimento
Papel estabelecido durante o envolvimento
Características do Aprendizado em SMA
Objetivo
Tipo de aperfeiçoamento: individual ou global?
Compatibilidade dos objetivos: complementares ou
conflitantes?
Conclusão acerca das características
do aprendizado SMA:
A possibilidade de
combinações é enorme!
Roteiro
Motivação
Alguns Conceitos
Características do
aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Principais Correntes de Pesquisa
Não existe uma metodologia de
ensino bem-definida para
aprendizado em SMA
Existem tendências, focos em
diferentes áreas, aplicações, ...
As correntes de pesquisa
apresentadas a seguir:
São abordagens concretas de aprendizado em SMA
Ilustram a aplicação de alguns conceitos de
aprendizado (RL, CBR, etc.) em sistemas
multiagente
Aprendizado e Coordenação de Atividades
Problemas de Coordenação:
Abordagens tradicionais tratam a coordenação em
tempo de projeto (off-line), especificando regras de
comportamento, protocolos de negociação, etc.
Mas SMA’s são utilizados em ambientes abertos e
dinâmicos, com agentes que têm objetivos e
habilidades variáveis
Logo, torna-se necessário que os agentes se
adaptem a novas demandas e oportunidades
Solução:
Agentes devem aprender como coordenar suas
atividades dinamicamente
Aprendizado e Coordenação de Atividades
Correntes de Estudo:
Aprendizado Isolado: um agente não considera
outros agentes em seu processo de aprendizado
Aprendizado Interativo: agentes cooperam no
aprendizado, coordenando suas atividades
conjuntamente
Ambas abordagens usam aprendizado por reforço (RL)
Aprendizado Isolado Concorrente
Características:
Agentes não se comunicam no processo de
aprendizado: parte do princípo de que a comunicação
consome tempo, recursos, é suscetível a falhas...
Características relevantes do ambiente:
Pouco acoplamento entre os agentes
Forma de relacionamento: cooperação, indiferença, ou
competição
Tempo para obter feedback do ambiente curto
Grande quantidade de comportamentos ótimos
Exemplo: corrida de Fórmula 1
Coordenar para não colidir…
CIRL – Modelos de Recompensa
 Selfish Utility (SU)
– Cada agente recebe como recompensa uma
medida da sua performance
 Team Game Utility (TG)
– Cada agente recebe como recompensa uma
medida da performance global
 Wonderful Life Utility (WLU)
– Recompensa calculada como:
• Recompensa global – Recompensa se o
agente não existisse
– Penaliza conflitos por recompensas
Aprendizado Isolado Concorrente
Resultados:
Limitações em ambientes fortemente acoplados,
com feedback demorado e poucas combinações
ótimas
Agentes precisam do reforço, mas o ambiente não dá...
Solução: intercalar o aprendizado dos agentes
Agentes podem alcançar especialização, e não
aprenderem o mesmo comportamento
Conclusão: fácil de implementar, e leva a bons
resultados
Aprendizado Interativo
Características:
A aprendizagem dos agentes envolve comunicação
explícita
Agentes agem para otimizar um objetivo global:
aplicável apenas em ambientes cooperativos
Dois algoritmos:
Action Estimation Algorithm (ACE)
Action Group Estimation Algorithm (AGE)
Aprendizado Interativo - ACE
Action Estimation Algorithm (ACE):
Para um dado estado, cada agente divulga, em
broadcast, suas melhores ações e suas relevâncias
Os agentes escolhem a melhor ação não-conflitante
com o contexto de atividade (activity context)
existente e a insere no conjunto
Repete-se esses passos até que todos os agentes
tenham determinado suas ações
O contexto de atividades é então executado
Exemplo: Jantar
Um agente para cada tarefa: entrada,
prato principal, e sobremesa
Aprendizado Interativo - AGE
Action Group Estimation Algorithm (AGE):
Para um dado estado, cada agente divulga, em
broadcast, suas melhores ações/reforços
Os agentes criam todos os contextos de atividade
(activity context) não-conflitantes possíveis com as
ações existentes e as novas ações do agente
Repete-se esses passos até que todos os agentes
tenham informado suas melhores ações
Escolhe-se o melhor contexto de atividades
Conclusão: apresenta melhor resultado do que o
ACE, mas a um custo computacional maior
Roteiro
Motivação
Alguns Conceitos
Características do
aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Aprendizado sobre e a partir de outros agentes
Ao contrário da coordenação, agora o
aprendizado objetiva uma melhoria
individual da performance do agente
Explica como o aprendizado conduzido
por um agente pode ser influenciado
por outros agentes
Adivinhar o comportamento do outros
agentes:
Preferências;
Estratégias;
Intenções, etc.
Aprendizado sobre e a partir de outros agentes
Apresentaremos três
abordagens:
Aprender papéis organizacionais
Aprender em ambientes de mercado
Aprender a explorar um oponente
Abordagem 1: Aprender papéis organizacionais
Capacitar cada membro do grupo a
identificar seu papel na organização
de uma forma adaptável
Exemplo: Se “dando bem” na noite...
Observando os outros agentes, qual
papel escolher? Exigente, moderado
ou desesperado?
Abordagem 2: Aprendendo em ambientes de mercado
Agentes compram e vendem
informações em um mercado
O ambiente é dinâmico por natureza
A qualidade da informação vendida por
diferentes agentes pode não ser a
mesma
Só é possível verificar a qualidade da
informação após comprá-la
Abordagem 3: Aprendendo a aproveitar-se do oponente
Abordado em two player zero-sum
games
Procura aprender a estratégia do
oponente observado o seu
comportamento
A partir daí, adota uma estratégia mais
inteligente
Exemplo: Jogos...
Roteiro
Motivação
Alguns Conceitos
Características do
aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Aprendizado e Comunicação
Aprender a se comunicar:
Nesse caso, o processo de aprendizagem objetiva a
diminuição da carga de comunicação entre os
agentes
Comunicação como aprendizado:
Nesse caso, a comunicação é vista como um método
de troca de informações que permite aos agentes
refinarem suas tarefas de aprendizado
As duas abordagens acima:
Devem deixar claro o que, quando, como e com
quem se comunicar
Necessitam da definição de uma ontologia comum
(consenso no significado dos símbolos)
Abordagem 1: Aprender a se Comunicar
Objetivo: evitar desperdício de
recursos causado pela comunicação
Exemplo: Contract-net
Geralmente implementado com broadcast satura a
rede para sistemas grandes...
Simplesmente mudar a solicitação de tarefas de
broadcast para ponto-a-ponto não resolve:
Caminhos de comunicação diretos precisariam ser
conhecidos previamente pelo projetista
Ambientes dinâmicos seriam complexos demais
para projetar
Habilidades podem estar sendo desperdiçadas...
Como solucionar isso?
Abordagem 1: Aprender a se Comunicar
Proposta de solução: Addressee
Learning
Agentes adquirem e refinam conhecimento sobre as
habilidades de resolução de tarefas de outros agentes
Com esse conhecimento, tarefas são alocadas
diretamente e dinamicamente, sem broadcast
Implementação: CBR (case-based reasoning)  cada
agente tem uma base de casos, contendo, para cada
caso:
A especificação do caso
Que agentes já solucionaram o caso
O quanto boa ou ruim foi a solução
Abordagem 2: Comunicação como Aprendizado
Objetivo: prover suporte ao
aprendizado através de comunicação
Duas possibilidades:
Aprendizado baseado em comunicação de baixo-nível
Aprendizado baseado em comunicação de alto-nível
Apenas para não nos desorientarmos:
Principais correntes em aprendizado em SMA
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e Comunicação
Estamos
aqui!
Comunicação como aprendizado
Baixo-nível
Aprender a se comunicar
Alto-nível
Abordagem 2: Comunicação como Aprendizado
Aprendizado baseado em comunicação
de baixo-nível:
Interações simples, do tipo pergunta e resposta
Realiza troca de informações que estão faltando
Resulta em informação compartilhada
Abordagem 2: Comunicação como Aprendizado
Exemplo de aprendizado baseado em
comunicação de baixo-nível: Let’s Hunt
Together
Caçadores caçam presas em um tabuleiro
Caçadores tem visão limitada
Cada caçador pode ter uma Q-Table
Caçadores trocam informações do tipo
onde estou, o que vejo e o que aprendi.
Essa cooperação é interessante: os
sensores e efetuadores dos caçadores são
unidos (centralizados)
Abordagem 2: Comunicação como Aprendizado
Aprendizado baseado em comunicação
de alto-nível:
Interações complexas, como negociação ou explicação
mútua sobre o objetivo da combinação das informações
Semelhante à comunicação humana (complexa...)
Resulta em entendimento compartilhado e não apenas
em informação compartilhada
Abordagem 2: Comunicação como Aprendizado
Exemplo de aprendizado baseado em
comunicação de alto-nível: Blackboard
A1: proponho X
A2: concordo com X
A3: por que não
usamos Y no lugar
de X?
A1: concordo com Y
A2: concordo com Y
A1: ASSERT(Y)
A2: ASSERT(Y)
A3: ASSERT(Y)
Em um quadro negro, agentes
propõem, contra-propõem, aceitam e
negam hipóteses
Uma hipótese proposta por um agente
é uma generalizações do conhecimento
desse agente
Ex.: Um agente A sabe que todo
pernambucano é brasileiro e que todo
paraibano é brasileiro  A propõe que
todo nordestino seja brasileiro
Roteiro
Motivação
Alguns Conceitos
Características do
aprendizado em SMA
Principais correntes de pesquisa em
aprendizado SMA:
Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Conclusões
Aprendizado multiagente é um tema
vasto, em que muitas e diferentes
abordagens existem
O tema herda as complexidades
inerentes de SMA: comunicação,
coordenação, negociação, ...
O projeto mais complexo da
aprendizagem pode ser compensado
pela qualidade dos resultados
Referências
Sen S., Weiss G., Multiagent systems: A modern
approach to Distributed Artificial Intelligence., Cap.
06, The MIT Press, 1999.
Stone, P., Veloso, M., Multiagent Systems: A Survey
from a Machine Learning Perspective, Carnegie
Mellon University, 1997
Veloso, M. Uther, W. (1997) Adversarial
Reinforcement Learning
http://citeseer.nj.nec.com/uther97adversarial.html
Figueiredo, K., Aprendizado e Coordenação
de Sistemas Multi-Agentes, PUC-Rio,
junho de 2000