Aprendizado por Reforço
Acelerado por Heurística para
um Sistema Multi-Agentes
Luiz Antonio Celiberto Junior
Reinaldo Augusto da Costa Bianchi
Mestrado em Engenharia Elétrica
Centro Universitário da FEI
Sumário
Objetivo
Aprendizado por Reforço
Aprendizado por Reforço Acelerado por
Heurísticas.
HAQ(λ) e HMMQ.
Proposta.
Resultados.
Conclusão.
WTDIA 2006
2
Objetivo
Utilizar o Aprendizado por Reforço acelerado por
Heurísticas no domínio da robótica móvel, utilizando a
plataforma multi-agentes do RoboCup 2D:
Para realizar o aprendizado.
Para avaliação de seu funcionamento.
Estudo de como sistemas multi-agentes podem trabalhar com
o aprendizado.
As Heurísticas serão criadas com base em regras bem
conhecidas e utilizadas tradicionalmente no domínio do
RoboCup 2D.
Serão realizadas comparações do funcionamento do
sistema com e sem o uso de Heurísticas.
WTDIA 2006
3
Aprendizado por Reforço
Agente sem conhecimentos prévios
Aprende através de interações com o ambiente.
Recebendo recompensas por suas ações e assim
descobrindo a política ótima.
Alguns dos principais algoritmos de AR:
Q-Learning.
Q(λ).
Minimax-Q
WTDIA 2006
4
Algoritmo Q-Learning
A função de estimação Q (calculada através da
Exploração on-line do agente) é computada
através da equação:
WTDIA 2006
5
Algoritmo Q-Learning
Na escolha das ações:
Exploração aleatória Є-Greedy
WTDIA 2006
6
Algoritmo Q(λ)
Combina a eligibilidade e o Q-Learning.
Na eligibilidade, a recompensa dada a uma ação
é distribuída para os passos anteriores.
Imagem retirada do trabalho: Pegoraro, 2001 - Aprendizado por Reforço em Robótica Móvel Através do Uso de
conhecimento sobre o Domínio.
WTDIA 2006
7
Algoritmo Q(λ)
Escolhe uma ação at e recebe uma recompensa rt
δ←r+argmaxQ(st+1,at+1)-Q(st,at)
e(st,at)=e(st,at)+1
Q(st,at) = Q(st,at)+α.δ.e(st,at)
Caso at+1=a*, então e(st, at)=γλe(st,at)
Caso contrario e(st,at) = 0
WTDIA 2006
8
Minimax-Q
Combina Minimax e o Q-Learning para um caso
particular do jogos de Markov entre dois
jogadores que competem entre sí.
Funciona de maneira semelhante ao Q–Learning:
A função valor-ação, será uma ação at em um estado st
quando o oponente toma um ação ot.
WTDIA 2006
9
Aprendizado por Reforço
Problema do aprendizado
Aprendizado demorado.
Lento para convergência
Necessidade de milhares de interações para aprender.
O uso de alguma forma de aceleração do
aprendizado é necessário.
WTDIA 2006
10
Aprendizado por Reforço Acelerado
por Heurísticas
Acelerar a convergência ao se utilizar funções
heurísticas para guiar a exploração do espaço de
estados-ações (Bianchi, 2004).
Heurística definida por Ht(st,at) que irá indicar a
importância de executar em um estado st uma
ação at.
WTDIA 2006
11
Aprendizado por Reforço
Acelerado por Heurísticas
Uma Heurística adequada causa uma aceleração
do aprendizado por reforço.
Uma Heurística inadequada pode causar um
atraso no sistema que não impede de convergir
para uma politíca ótima.
WTDIA 2006
12
HAQ(λ) e HMMQ
HAQ(λ)= Q(λ) acelerado por Heuristicas.
HMMQ= Minimax-Q acelerado por Heuristicas.
Heuristicas como uma somatória simples ao
valor da função valor–ação e definidas como:
Ação considerada “boa” : H=1.
Outras ações: H=0.
WTDIA 2006
13
Proposta
Utilizar o Aprendizado por Reforço acelerado por
Heurísticas na Plataforma RoboCup Simulação 2D.
Comparar o aprendizado com e sem Heurísticas.
Estado:
Posição do agente , ângulo do agente e posição da bola.
Definição e implementação do algoritmo HAQ(λ) Heuristically Accelerated Q(λ).
WTDIA 2006
14
Proposta
Para um único agente:
Aprendizado em forma tabular (matriz Q)
Criação de um goleiro com aprendizado sem
Heurística, comparado com um com Heurística
Ações:
Correr para a bola.
chutar a bola.
pegar a bola.
Heurística: Chute a bola quando estiver perto.
WTDIA 2006
15
Proposta
Goleiro + Zagueiro com aprendizado vs. 2 Atacantes
Aprendizado usando abstrações dos estados.
Apenas a informação que distingui estados (Mausberg,2005)
,2005 .
Comparar o aprendizado com e sem Heurísticas.
Heuristica : Tire a bola da área de defesa.
Ações:
Parado.
Correr para a bola.
Chutar a bola.
Pegar a bola (goleiro).
Fazer passe para outro jogador.
Driblar.
Conduzir a bola .
WTDIA 2006
16
Proposta
2 Atacantes com Aprendizado vs. Goleiro + Zagueiro
Aprendizado usando abstrações dos estados.
Comparar o aprendizado com e sem Heurísticas.
Heuristica : Leve a bola para o gol.
Ações:
Parado.
Correr para a bola.
Chutar a bola para o Gol.
Fazer passe para outro jogador.
Driblar.
Conduzir a bola .
WTDIA 2006
17
Proposta
Para um time (multi-agentes)
Aprendizado usando abstrações dos estados.
Criação de um time com aprendizado sem Heurística, comparado com um com
Heurística.
Time deve trocar informações entre os agentes.
Aonde está a bola ? Alguém pode me ajudar ?
Troca de aprendizado (Aprendizado de um agente será a Heurística de outro)
Ações:
Parado.
Correr para a bola.
chutar a bola.
pegar a bola (goleiro).
Fazer passe para outro jogador.
Conduzir a bola .
Driblar.
WTDIA 2006
18
Resultados
Três experiências iniciais.
Uso do Minimax-Q acelerado por Heurísticas
Uso do Q-Learning em aprendizado
Uso do Q(λ) em um Goleiro, acelerado por
Heurísticas.
WTDIA 2006
19
Experiência 1
Experiência de como a Heurística influência no
aprendizado, usando Minimax-Q acelerado por Heurística,
2 jogadores (aprendizado x aleatório), grade de 10x10
células.
Heurística: Se estiver com a bola, vá para o gol do
adversário.
Aprendizado foi utilizado os valores:
α de 1.0 com decaimento uniforme por ação
taxa de exploração/explotação de 0.2.
fator de desconto γ de 0,9.
O reforço de 1000 quando o agente chega ao gol e -1000 por
gol marcado pelo adversário.
WTDIA 2006
20
Experiência 1
WTDIA 2006
21
Experiência 2
Aprendizado com funções de baixo nível
(correr, chutar)
Reforço: olhar para a bola (+100), olhar para o gol
(+100) e fazer gol (+1000)
α de 0.1.
taxa de exploração/explotação de 0.2.
fator de desconto γ de 0,9.
WTDIA 2006
22
Experiência 2
WTDIA 2006
23
Experiência 3
Um único agente usando Aprendizado por Reforço (Q(λ)).
Reforço:
- 1000 para cada gol recebido,
+1000 quando pegar a bola ou chutar a bola.
γ=0.9; α=0.1; λ =0.5; exploração= 5%
Sistema executado em Linux sobre VMware, simulando
sempre a mesma máquina com as mesmas características.
Partida : 3.000 ciclos.
WTDIA 2006
24
Experiência 3
Aprendizado sem
Heurísticas.
WTDIA 2006
Aprendizado com
Heurísticas.
25
Experiência 3
Gráfico com e sem Heurísticas para um jogador
WTDIA 2006
26
Conclusão
Um sistema com AR+H é mais eficiente na
realização do aprendizado que sistemas com
somente AR.
As recompensas devem ser formuladas para os
objetivos secundários e não somente para o
objetivo principal (fazer o gol/ganhar partida).
WTDIA 2006
27
Obrigado.