Aprendizado Multiagente
Gustavo Danzi de Andrade
[email protected]
Agentes Autônomos
Patrícia Tedesco
Lembrando

Aprendizado


Envolve




Um sistema que aprende melhora seu
comportamento futuro com base na experiência do
passado
Aquisição de conhecimento
Melhoria da performance
Processo conduzido pelo próprio agente
Aplicação


Ambientes complexo, grandes e dinâmicos
O aprendizado pode ser off-line ou on-line
Mestrado em Ciência da Computação
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 manual de conhecimento é difícil
(manutenção, adaptação e tratamento de
incerteza)
Mas a inteligência pode não depender apenas de
um único agente
Mestrado em Ciência da Computação
Motivação

Portanto... vamos estudar o melhor
dos mundos!
SMA
Aprendizado
Aprendizado
Multiagente
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Alguns Conceitos

Inteligência em SMA:


Por que pensar a inteligência como propriedade de
um único indivíduo?
Não existe inteligência em:




Um time de futebol?
Um formigueiro?
Na sociedade?
O conceito de inteligência em SMA é muito mais
abrangente...
Mestrado em Ciência da Computação
Alguns Conceitos

Aprendizado em um SMA não é
apenas uma ampliação do
aprendizado em sistemas single agent

Aprendizado em um SMA é mais do
que a soma dos aprendizados isolados
de cada agente!
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Categorias de Aprendizado em SMA

Generalizando, existem duas
categorias de aprendizado em SMA:



Centralizado (ou isolado): o processo de
aprendizado é totalmente executado por um
agente, sem interação com demais agentes.
Descentralizado (ou iterativo): vários agentes
estão engajados em um mesmo processo de
aprendizado. Pode haver ou não troca de
informação
Em um SMA, um agente pode estar
envolvido em vários processos
centralizados/descentralizados
Mestrado em Ciência da Computação
Outras caracterizações

Grau de Descentralização:


Nível da Interação:


Observação por um curto período de tempo, ou
longas negociações
Grau de Envolvimento:


Um único agente seqüencial, ou vários agentes
atuando paralelamente
Algumas atividades só podem ser realizadas por
um dado agente, ou há substitutos
Objetivo:

Agentes têm objetivos complementares ou
conflitantes
Mestrado em Ciência da Computação
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, ...
Estudaremos algumas delas...
Mestrado em Ciência da Computação
Mas antes...



Existem vários métodos de
aprendizado single-agente que podem
ser aplicados em SMA
Mas aprendizagem por reforço (RL) é
o método mais usado
Lembrando:



Aprendizado Supervisionado: um professor
especifica as ações desejadas
Aprendizado por Reforço: um crítico indica a
utilidade de cada ação
Aprendizado Não-supervisionado: o agente
procura similaridades nas suas ações
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Aprendizagem por Reforço

“Aprender o que fazer (mapear
situações em ações) de forma a
maximizar um sinal numérico”
[Sutton e Barto, 1998]
Mestrado em Ciência da Computação
Aprendizagem por Reforço
Oponente sem
defesa...
Agente
Ambiente
Percepções (s)
Ações (a)
Reforço (+/-) R(s,a)
Mestrado em Ciência da Computação
Aprendizagem por Reforço



O agente percebe um estado s, e
escolhe uma ação a, que leva a um
novo estado s’
Cada par (s,a) possui um reforço
R(s,a) transmitido ao agente quando
executa a no estado s
O agente pratica uma política (s)  a
Mestrado em Ciência da Computação
Aprendizagem por Reforço


Queremos encontrar a política ótima
*(s)  a, que maximiza a soma
esperada de recompensas futuras
Podemos definir uma função
Q(s,a)  , que indica o retorno
esperado quando, a partir de s, o
agente executa a ação a e segue a
política  a partir de então
Mestrado em Ciência da Computação
Q-Learning

Q-Learning é um algoritmo que
computa iterativamente a função
Q: S x A  
Usa a regra de atualização:
Q(s,a)  Q(s,a) +  [r + V(s’) – Q(s,a)]
onde
V(s’) = maxaQ(s’,a)

Converge para a função Q* ótima

Mestrado em Ciência da Computação
Voltando a Aprendizado em SMA

Estudaremos três tópicos:



Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Aprendizado e Coordenação

Problemas de Coordenação:





Interesse coletivo e maximização da performance
global
Abordagens tradicionais tratam a coordenação em
tempo de projeto (off-line), especificando regras
de comportamento, protocolos de negociação, etc.
Mas SMAs 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
Mestrado em Ciência da Computação
Exemplos

Robocup:


Grupo de jogadores cuja medida de performance pode
ser dada por #GolsPro - #GolsContra
Patrulha:


Grupo de robôs, em que cada
um patrulha uma parte do terreno
Medida da performance dada pela ociosidade média do
terreno
Mestrado em Ciência da Computação
Aprendizado e Coordenação

Correntes de estudo:

Aprendizado Isolado: agentes não se comunicam
no processo de aprendizado: parte do princípio de
que a comunicação consome tempo, recursos, é
suscetível a falhas...



Pode ser centralizado ou distribuído
Aprendizado Interativo: agentes cooperam no
aprendizado, coordenando suas atividades
conjuntamente
Ambas utilizam aprendizagem por
reforço
Mestrado em Ciência da Computação
Aprendizado Isolado Centralizado

Características:



RL tradicional, em um único agente (coordenador)
O estado é o estado global
Uma ação, para n agentes, é dada por uma tupla:



<a1, a2,..., an>
A recompensa é a medida de performance global
do sistema
Problemas:



Tamanho do conjunto de ações exponencial no
tamanho de agentes (intratável!)
Acessibilidade total nem sempre é possível
Enfim: só funciona em ambientes pequenos...
Mestrado em Ciência da Computação
Exemplo: Futebol de barrinha

Ambiente:



S = (Pj1, Pj2, Pb, Po1, Po2)



onde Pi é a posição do jogador i
A = (aj1, aj2)


Barra pequena
Cada time com 2 jogadores
onde aji Є {tocar, chutar, marcarOponente1,
marcarOponente2, atacar}
R = #GolsPro - #GolsPro
Problema:

Mais e no futebol de campo, com 11 jogadores?
Mestrado em Ciência da Computação
Aprendizado Isolado Descentralizado

Características:


Cada agente aprende individualmente (RL)
Ambiente deve possuir:






Pouco acoplamento entre os agentes
O feedback dado em um tempo curto
Muitas possibilidades de comportamento ótimo
Resumindo: o ambiente deve dar “muito” reforço
Os agentes podem alcançar especialização, e não
aprenderem o mesmo comportamento
Problema:

Atribuição de crédito: como dar uma recompensa
pela performance individual de cada agente?
Mestrado em Ciência da Computação
Uma solução: Modelo de Recompensa

Selfish Utility (SU)


Team Game Utility (TG)


Cada agente recebe como recompensa uma
medida da sua performance
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
Mestrado em Ciência da Computação
Aprendizado Interativo

Características:


Aprendizagem dos agente envolve comunicação e
coordenação explícita
Dois algoritmos:



Action Estimation Algorithm (ACE)
Action Group Estimation Algorithm (AGE)
Cada agente aprende individualmente (RL)
Mestrado em Ciência da Computação
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ãoconflitante com o contexto de atividades existente
(inicialmente, vazio) e a insere no conjunto
Repete-se esses passos até que todos os agentes
tenham determinado suas ações
O contexto de atividade é então executado
Mestrado em Ciência da Computação
Aprendizado Interativo - AGE

Action Group Estimation Algorithm
(AGE):




Para um dado estado, cada agente divulga, em
broadcast, todas as ações possíveis e suas
relevâncias
Os agentes criam todos os contextos de atividades
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 ações
Escolhe-se o melhor contexto de atividades e o
executa
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
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
Estuda como o aprendizado conduzido
por um agente pode ser influenciado
por outros agentes
Adivinhar o comportamento dos
outros agentes:

Preferência, Estratégias, Intenções, ...
Mestrado em Ciência da Computação
Explorando o Oponente

Características:




Utilizado em two player zero-sum games
Procura aprender a estratégia do oponente
observando o seu comportamento
A partir daí, adota uma estratégia mais inteligente
Abordagem com RL tradicional funciona em alguns
casos:



Gamão (trabalho de Tesauro, 1995)
Damas
Mas fracassa em outras


Jogos Estocásticos
Xadrez
Mestrado em Ciência da Computação
Explorando o Oponente

Min-Max Q-Learning:




Inclui as ações possíveis do oponente
Q(s,aagente, aoponente)
Bom contra oponente ótimo; não explora
comportamento estocástico do oponente
Exemplo: em um dado estado s
a1
Ações do
oponente
a1
a2
a3
a2
0
1
4
a3
5
2
3
Mestrado em Ciência da Computação
7
0
1
Ações do
agente
Explorando o Oponente

Opponent Modeling



Utiliza um modelo explícito do oponente
Computa a freqüência de cada ação executada
Calcula a recompensa esperada como uma média
ponderada pelas probabilidades
Mestrado em Ciência da Computação
Aprendizado sobre e a partir de outros agentes

Outras possibilidades de aplicação:


Aprender papéis organizacionais
Aprender em ambientes de mercado (leilão...)
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Aprendizado e Comunicação

Aprender a ser comunicar:


Comunicação como aprendizado:


Nesse caso, o processo de aprendizagem objetiva
a diminuição da carga de comunicação entre os
agentes
Nesse caso, a comunicação é vista como um
método de troca de informações que permite aos
agentes refinarem suas tarefas de aprendizado
Nas duas abordagens:


Deixar claro o que, quando, como e com quem se
comunicar
Definir uma ontologia comum (consenso no
significado dos símbolos)
Mestrado em Ciência da Computação
Aprendendo a se Comunicar

Contract-net


Geralmente é implementado com broadcast:
satura a rede em grandes sistemas
Solução: Addressee Learning


Agentes adquirem e refinam conhecimento sobre
as habilidades de resolução de tarefas de outros
agentes
Implementação: CBR (case-based reasoning):


Cada agente possui uma base da casos, contendo,
para cada caso:
A especificação, os agentes que já resolveram, e
o quanto boa ou ruim foi a solução
Tarefas alocadas diretamente e dinamicamente
Mestrado em Ciência da Computação
Comunicação como Aprendizado

Abordagem 1: 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


Exemplo: Caçada





Caçadores caçam no tabuleiro
Têm visão limitada
Cada um tem uma Q-Table
Trocam informações do tipo onde
estou, o que vejo e o que aprendi
Resultado: os sensores e atuadores dos caçadores são
unidos (centralizados)
Mestrado em Ciência da Computação
Comunicação como Aprendizado

Abordagem 2: alto-nível
Interações complexas, como negociações ou explicação
mútua sobre o objetivo da combinação das informações
 Resulta em entendimento compartilhado e não apenas
em informação compartilhada

A1: proponho X

Exemplo: Blackboard
Em um quadro negro, agentes
propõem, contra-propõem,
aceitam e negam hipóteses
 Uma hipótese proposta por um
agente é uma generalização do
conhecimento desse agente

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)
Mestrado em Ciência da Computação
Roteiro




Alguns Conceitos
Características: aprendizado em SMA
Aprendizagem por reforço
Aprendizado em SMA




Aprendizado e coordenação de atividades
Aprendizado sobre e a partir de outros agentes
Aprendizado e comunicação
Conclusões
Mestrado em Ciência da Computação
Conclusões

Aprendizado multiagente é um tema
vasto, em que muitas e diferentes
abordagens existem



Muitas questões ainda em aberto...
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
Mestrado em Ciência da Computação
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
Sutton, R., Barto, A. Reinforcement Learning: An
Introduction. Cambridge, MA, 1998.
Mestrado em Ciência da Computação