Pós-Graduação em Ciência da Computação · Paulemir Campos, Paulo Gonçalves e Rubens Bernante, ... d e f são jogadores, g é o goleiro e b é a bola. Os objetos são vistos

Pós-Graduação em Ciência da Computação

APLICAÇÃO DE MINERAÇÃO DE DADOS PARA

REDUZIR A DIMENSÃO DO ESPAÇO DE

CARACTERÍSTICAS E AÇÕES EM

APRENDIZAGEM POR REFORÇO: CENÁRIO DO

DRIBLE DA ROBOCUP

Por

DAVI CARNAÚBA DE LIMA VIEIRA

Dissertação de Mestrado

Universidade Federal de Pernambuco

[email protected]

www.cin.ufpe.br/~posgraduacao

RECIFE, 09/2010

UNIVERSIDADE FEDERAL DE PERNAMBUCO

CENTRO DE INFORMÁTICA

PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO

DAVI CARNAÚBA DE LIMA VIEIRA

APLICAÇÃO DE MINERAÇÃO DE DADOS PARA REDUZIR A DIMENSÃO DO ESPAÇO DE CARACTERÍSTICAS E AÇÕES EM APRENDIZAGEM POR REFORÇO: CENÁRIO DO DRIBLE DA

ROBOCUP

ESTE TRABALHO FOI APRESENTADO À PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO DO CENTRO DE INFORMÁTICA DA UNIVERSIDADE FEDERAL DE PERNAMBUCO COMO REQUISITO PARCIAL PARA OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIA DA COMPUTAÇÃO.

ORIENTADOR(A): Paulo Jorge Leitão Adeodato

Recife, SETEMBRO/2010

Vieira, Davi Carnaúba de Lima

Aplicação de mineração de dados para reduzir a dimensão do espaço de características e ações em aprendizagem por reforço: cenário do drible da RoboCup / Davi Carnaúba de Lima Vieira - Recife: O Autor, 2010.

xix, 125 folhas : il., fig., tab.

Dissertação (mestrado) Universidade Federal de Pernambuco. CIn. Ciência da computação, 2010.

Inclui bibliografia e apêndice.

1. Inteligência artificial. 2. Mineração de dados. 3. Aprendizagem por reforço. I. Título.

006.3 CDD (22. ed.) MEI2010 – 0172

Aos meus pais, José Antonio Cruz Vieira e

Maria Nazaré Carnaúba de Lima Vieira

Agradecimentos

Primeiramente a Deus por ter me concedido inteligência suficiente para finalizar es-

se trabalho.

A todos os membros da banca. É uma grande honra poder contar com a con-

tribuição de todos.

Aos professores Aluízio Araújo, Flávia Barros, Francisco Carvalho, Patrícia

Tedesco, Paulo Adeodato e Teresa Ludermir. Foi muito prazeroso estar em contato

com professores tão dedicados.

Novamente ao professor Paulo Adeodato pela orientação e confiança deposi-

tada no meu trabalho de dissertação.

Aos meus pais pelo apoio incondicional e pelo exemplo de força e determina-

ção.

A minha esposa Carine, companheira de todas as horas, por tudo que tem fei-

to por mim.

Aos meus amigos Antonio Zarth, Daniel Melo, Eric Rommel, Orivaldo Vieira,

Paulemir Campos, Paulo Gonçalves e Rubens Bernante, por me fazerem sentir em

casa mesmo estando longe dela. Sentirei saudades dos nossos debates intelectuais

que aconteciam nos botecos da Várzea.

Ao meu professor e agora amigo, Ulisses Dias, pelo incentivo e orientação pa-

ra continuar minha vida acadêmica.

Ao Centro de Informática pela ótima estrutura e a FACEPE pelo apoio finan-

ceiro.

“History has proven that human predictive

powers have never been good beyond a decade. A

few examples are in place here. On the 17th of De-

cember 1903, Orville Wright made the first man-

carrying powered flight in an aircraft built by himself

and his brother Wilbur Wright. The flight covered

about 120 feet and lasted for 12 seconds. If at that

point someone would have claimed that roughly 66

years later the first man would set foot on the moon,

he would surely have been diagnosed as mentally

insane. However, on the 20th of July 1969, Neil

Armstrong stepped out of the Apollo-11 Lunar Mod-

ule and onto the surface of the moon.”

(Boer & Kok, 2002)

Resumo A aprendizagem por reforço é usada em cenários nos quais não se dispõe de um

resultado associado a cada estado nem a cada ação tomada por um agente

inteligente. Essa forma de aprendizagem; portanto, mantém uma forte dependência

da exploração dos espaços de estados e de ações que produz uma explosão de

dados cujo armazenamento se torna um problema em muitas situações. Por outro

lado, tem-se a mineração de dados como uma área da inteligência artificial que

busca extrair informações ou padrões de grandes quantidades de dados, ou

armazenados em um banco de dados ou trafegando em um fluxo contínuo de dados.

A principal contribuição deste trabalho é mostrar como as técnicas de

mineração de dados podem ser utilizadas para selecionar as variáveis e ações mais

relevantes dos ambientes da aprendizagem por reforço. O objetivo desta seleção é

reduzir a complexidade do problema e a quantidade de memória usada pelo agente,

que podem acelerar a convergência da aprendizagem. A dificuldade em utilizar as

técnicas de mineração de dados em ambientes da aprendizagem por reforço deve-

se ao não armazenamento dos dados provenientes da exploração dos espaços de

estados e de ações em um banco de dados. Este trabalho também contribui

propondo um esquema de armazenamento para os estados visitados e as ações

executadas pelo agente.

Neste estudo, o método de seleção de atributos e de ações foi validado

experimentalmente em um problema no qual a aprendizagem por reforço é a

abordagem mais adequada; o drible no futebol de robôs – RoboCup-2D. Este

problema é composto de 23 variáveis contínuas e 113 ações disponíveis para o

agente que consome cerca de 18MB de memória quando utilizado o algoritmo

combinado com a técnica de tile-coding. Os resultados dos experimentos

mostraram que a quantidade de variáveis do ambiente pode ser reduzida em até

56% e a quantidade de ações em até 85%, com uma redução do uso da memória de

95% e um aumento no desempenho de aproximadamente 10% de acordo com a

distribuição da freqüência relativa de sucesso do agente. A abordagem proposta é

simples de usar e eficiente.

Palavras-chave: Aprendizagem por Reforço, Agentes Inteligentes, RoboCup, Mine-

ração de Dados, Seleção de Atributos e Ações.

Abstract Reinforcement learning is used in scenarios when there is no outcome associated

with the states or actions taken by an intelligent agent. Therefore, this form of learn-

ing keeps it as a strong dependence of the operation of state spaces and actions that

produce an explosion on data which becomes a problem in many situations. On the

other hand, we have the Data mining which can be seen as an area of artificial intel-

ligence that seeks to extract information or patterns from large amounts of data either

stored in databases or flowing in streams.

The main contribution of this work is to show how the techniques of data min-

ing can be used to select the most relevant features and actions from reinforcement

learning environments. The objective of this selection is to reduce the complexity of

the problem and the amount of memory used by the agent thus leading to faster con-

vergence. The difficulty in using data mining techniques in reinforcement learning

environments is due to the lack of states and actions explored by the agent stored in

a database. This work also contributes by proposing a storage schema for the visited

states and actions performed by the agent.

In this study, the method of selection of attributes and actions was validated

experimentally on an issue where the reinforcement learning is the most appropriate

approach; the dribble in robot soccer - RoboCup 2D. This problem is composed of 23

continuous variables and 113 actions available to the agent which results in a memo-

ry consumption of approximately 18MB when the traditional is used com-

bined with the tile-coding technique. The experiments’ results show that the amount

of variables in the environment were reduced by 56% and the amount of actions by

85%, which resulted in a reduction in memory consumption of 95% and an increase

in performance of up to 10% according to the relative frequency distribution of

agents’ success. The approach proposed here is both easy to use and efficient.

Keywords: Reinforcement Learning, Intelligent Agents, RoboCup, Data Mining, Fea-

ture and Action Selection.

xi

Sumário

CAPÍTULO 1 INTRODUÇÃO ............................................................................................................................... 1

1.1 APRENDIZAGEM POR REFORÇO E A ROBOCUP............................................................................... 1

1.2 MOTIVAÇÃO ................................................................................................................................... 3

1.3 CONTEXTUALIZAÇÃO ...................................................................................................................... 5

1.4 OBJETIVOS..................................................................................................................................... 7

1.5 CONTRIBUIÇÕES ............................................................................................................................ 8

1.6 DESCRIÇÃO DA DISSERTAÇÃO ....................................................................................................... 9

1.7 ORGANIZAÇÃO DA DISSERTAÇÃO ................................................................................................... 9

CAPÍTULO 2 MODELO COMPUTACIONAL ........................................................................................................11

2.1 APRENDIZADO POR DIFERENÇA TEMPORAL...................................................................................12

2.1.1 Rastro de Elegibilidade ..........................................................................................................13

2.1.1.1 Sarsa( ) .............................................................................................................................................. 14

2.1.1.2 Método Q( )........................................................................................................................................ 16

2.2 CONTROLE COM APROXIMADOR DE FUNÇÕES ...............................................................................17

2.3 TILE CODING (CMAC) ..................................................................................................................19

CAPÍTULO 3 AMBIENTE DE TESTE ....................................................................................................................23

3.1 VISÃO GERAL DO SIMULADOR .......................................................................................................23

3.2 VISÃO GERAL DO AGENTE.............................................................................................................25

3.2.1 Sensor Visual .........................................................................................................................26

3.2.2 Sensores Auditivos ................................................................................................................28

3.2.3 Sensores Corporais ...............................................................................................................29

3.3 MODELAGEM DO AMBIENTE DO DRIBLE .........................................................................................30

3.3.1 Treinador ................................................................................................................................34

3.3.2 Comportamento dos Oponentes ...........................................................................................34

3.3.2.1 Time UvA Trilearn .............................................................................................................................. 35

3.3.3 Implementação do Agente ....................................................................................................36

xii

CAPÍTULO 4 MINERAÇÃO DE DADOS NA APRENDIZAGEM POR REFORÇO .......................................................39

4.1 SELEÇÃO DE ATRIBUTOS ...............................................................................................................40

4.1.1 LVF - Las Vegas Filter ...........................................................................................................42

4.1.2 Taxa de Ganho.......................................................................................................................45

4.1.3 Regressão Linear e o Coeficiente de Correlação................................................................46

4.2 SELEÇÃO DE AÇÕES .....................................................................................................................47

4.3 APRENDIZAGEM POR REFORÇO E A MINERAÇÃO DE DADOS ..........................................................48

4.3.1 Armazenamento e Seleção dos dados ................................................................................50

CAPÍTULO 5 EXPERIMENTOS E ANÁLISE ESTATÍSTICA DOS DADOS ..................................................................52

5.1 TREINAMENTO DO AGENTE ...........................................................................................................52

5.2 SELEÇÃO DE ATRIBUTOS ...............................................................................................................55

5.2.1 Treinamento com Todos os Atributos...................................................................................56

5.2.1.1 Análise da Correlação dos Atributos ................................................................................................. 61

5.2.2 Taxa de Ganho.......................................................................................................................63

5.2.3 Las Vegas Filter .....................................................................................................................68

5.3 SELEÇÃO DE AÇÕES .....................................................................................................................72

5.3.1 Análise das Ações com Todos os Atributos .........................................................................73

5.3.2 Análise das Ações com Atributos Eliminados por Taxa de Ganho ....................................75

5.3.3 Análise das Ações com Atributos Eliminados por LVF .......................................................76

5.3.4 Remoção das Ações nos Modelos Discutidos .....................................................................77

5.4 COMPARAÇÃO DOS MODELOS .......................................................................................................80

5.4.1 Teste do Desempenho ..........................................................................................................80

5.4.2 Uso da Memória .....................................................................................................................82

5.5 QUALIDADE DO DRIBLE .................................................................................................................84

CAPÍTULO 6 CONCLUSÃO ................................................................................................................................86

6.1 RESULTADOS E DISCUSSÕES ........................................................................................................87

6.2 CONTRIBUIÇÕES E RELEVÂNCIA ....................................................................................................90

6.3 TRABALHOS FUTUROS ..................................................................................................................91

APÊNDICE A APRENDIZAGEM POR REFORÇO ..................................................................................................93

A.1 INTRODUÇÃO .................................................................................................................................93

A.1.1 Política Ótima .........................................................................................................................96

A.2 PROGRAMAÇÃO DINÂMICA ............................................................................................................97

A.2.1 Processo de Aprendizagem ..................................................................................................98

A.2.1.1 Policy Evaluation ....................................................................................................................98

A.2.1.2 Policy Improvement ................................................................................................................99

A.2.1.3 Policy Iteration ...................................................................................................................... 100

xiii

A.2.1.4 Value Iteration ....................................................................................................................... 102

A.3 ALGORITMOS DA APRENDIZAGEM POR REFORÇO ........................................................................ 103

A.3.1 Monte Carlo .......................................................................................................................... 104

A.3.1.1 Monte Carlo On-Policy ......................................................................................................... 105

A.3.1.2 Monte Carlo Off-Policy ......................................................................................................... 107

APÊNDICE B MODELOS BASEADOS NO GRADIENTE DESCENDENTE ............................................................... 110

B.1 INTRODUÇÃO ............................................................................................................................... 110

B.1.1 Algoritmo do Mínimo Quadrado Médio ............................................................................... 112

B.2 REDES NEURAIS MULTILAYER PERCEPTRON .............................................................................. 114

REFERÊNCIAS BIBLIOGRÁFICAS ..................................................................................................................... 118

xiv

Lista de Figuras

Visão mecânica da técnica de elegibility traces. Fonte: (Sutton & Barto, 1998) .................... 14

Alguns tilings sobrepostos. Nesta figura cada tile é endereçado por duas variáveis, e . A

generalização é obtida entre as regiões sobrepostas. A sobreposição dos tiles torna possível

a experiência obtida em uma região ser compartilhada entre seus vizinhos. ....................... 21

Monitor. .............................................................................................................................. 24

Estrutura do Agente. ............................................................................................................ 25

Posições de todas as linhas e bandeiras do campo. .............................................................. 25

Campo de visão do agente. Os objetos são representados pelos círculos pretos, onde a, e, c,

d e f são jogadores, g é o goleiro e b é a bola. Os objetos são vistos pelo agente se estiverem

dentro do seu ângulo de visão determinado por view_angle, o jogador a, no entanto, pode

ser sentido pelo agente. O goleiro g e a bola b não são vistos pelo agente. Unum_far_length,

unum_too_far_length, team_far_length e team_too_far_length são constantes que

representam a distância de um objeto e, por padrão, são definidos como 20, 30, 40 e 60

(metros), respectivamente. Fonte: (Stone, 1998). ................................................................ 27

Estados finais de um episódio. (a) Agente passou o oponente, mas o estado final não

aparenta ser um drible. (b) Agente passou o oponente deixando-o atrás do seu corpo. Neste

caso, o estado final aparenta mais ser um drible. ................................................................. 31

Ambiente de treinamento .................................................................................................... 32

Busca exaustiva pelo espaço de atributos. O ponto de partida pode iniciar sem nenhum

atributo (visualização top-down) ou com todos atributos (visualização bottom-up). ............ 40

Esquema Snowflake de armazenamento do treinamento do agente. Os Dados de

treinamento estão armazenados em duas tabelas principais: Resultado e ResultadoTemAção.

............................................................................................................................................ 51

xv

Decaimento exponencial da taxa de aprendizado. ............................................................... 56

Curvas de desempenho (média de dez execuções) do agente com todas as variáveis,

mudando apenas o parâmetro alpha (taxa de aprendizado). ............................................... 57


mudando apenas o parâmetro E. ......................................................................................... 58


mudando apenas o parâmetro lambda (elegibility traces).................................................... 59


mudando apenas a quantidade de tilings. ............................................................................ 59

Curvas de desempenho (média de dez execuções) do agente com todas as variáveis e com a

combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e

quantidade de tilings. .......................................................................................................... 60

Correlação entre as variáveis com coeficiente maior que sete décimos. Dados retirados do

treinamento com todas as variáveis. .................................................................................... 62

Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro

Alpha após a remoção das variáveis segundo a taxa de ganho. ............................................ 65


E após a remoção das variáveis segundo a taxa de ganho. ................................................... 65


Lambda após a remoção das variáveis segundo a taxa de ganho.......................................... 66


Tilings após a remoção das variáveis segundo a taxa de ganho. ........................................... 66

Curvas de desempenho (média de dez execuções) do agente com a combinação dos

melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das

variáveis irrelevantes de acordo com a taxa de ganho e a redundância (correlação). ........... 67


alpha após a remoção das variáveis irrelevantes pelo algoritmo LVF.................................... 69

xvi


E após a remoção das variáveis irrelevantes pelo algoritmo LVF. ......................................... 70


Lambda após a remoção das variáveis irrelevantes pelo algoritmo LVF. ............................... 71


Tilings após a remoção das variáveis irrelevantes pelo algoritmo LVF. ................................. 71

Curvas de desempenho (média de dez execuções) do agente com a combinação dos

melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das

variáveis irrelevantes pelo algoritmo LVF. ............................................................................ 72

Confiança das ações extraídas do treinamento do agente com todas as variáveis para dois

níveis de exploração............................................................................................................. 74

Suporte das ações extraídas do treinamento do agente com todas as variáveis para dois

níveis de exploração............................................................................................................. 74

Confiança das ações extraídas do treinamento do agente após remoção das variáveis

segundo a taxa de ganho para dois níveis de exploração...................................................... 75

Suporte das ações extraídas do treinamento do agente após remoção das variáveis segundo

a taxa de ganho. ................................................................................................................... 75

Confiança das ações extraídas do treinamento do agente após a remoção das variáveis

irrelevantes pelo algoritmo LVF para dois níveis de exploração. ........................................... 76

Suporte das ações extraídas do treinamento do agente após a remoção das variáveis

irrelevantes pelo algoritmo LVF para dois níveis de exploração. ........................................... 76

Curvas de desempenho (média de dez execuções) de todas as abordagens relativas as

seleções de ações variando o parâmetro . ........................................................................ 78

Comparação do desempenho no teste dos modelos (média de dez execuções) com todas as

variáveis. .............................................................................................................................. 80

Comparação do desempenho dos modelos (média de dez execuções) no teste com as

variáveis selecionadas segundo a Taxa de Ganho e a Redundância. ..................................... 81

xvii

Comparação do desempenho dos modelos (média de dez execuções) no teste com as

variáveis selecionadas pelo algoritmo LVF. ........................................................................... 82

Comparação do uso da memória dos modelos (média de dez execuções) com todas as

variáveis. .............................................................................................................................. 83

Comparação do uso da memória dos modelos (média de dez execuções) com as variáveis

selecionadas pelo algoritmo Taxa de Ganho. ....................................................................... 83

Comparação do uso da memória dos modelos com as variáveis selecionadas pelo algoritmo

LVF (média de dez execuções). ............................................................................................. 84

Interação agente-ambiente. Traduzido da fonte: (Sutton & Barto, 1998) ............................. 94

Modelo linear. ................................................................................................................... 113

Rede Neural Multilayer Perceptron. ................................................................................... 114

xviii

Lista de Tabelas Possíveis valores para os parâmetros view_width_factor e view_quality_factor. ................. 27

Descrição dos sensores corporais do agente. ....................................................................... 29

Ações realizáveis pelo agente............................................................................................... 32

Representação do ambiente em 23 variáveis contínuas ....................................................... 33

Resultado das competições German Open e RoboCup realizadas entre 2001 e 2004. O time

UvA Trilearn obteve 3 vitórias no torneio German Open e uma vitória no torneio da

RoboCup. ............................................................................................................................. 35

Valores iniciais para os parâmetro do modelo. ..................................................................... 54

Espaço de busca. .................................................................................................................. 54

Variação inicial dos parâmetros do modelo. ......................................................................... 54

Taxa de ganho para as variáveis do ambiente. ..................................................................... 64

Quantidade de variáveis removidas. .................................................................................... 77

xix

Lista de Algoritmos Sarsa( )................................................................................................................................ 15

Q( ) ..................................................................................................................................... 17

Versão adaptada do algoritmo para o gradiente descendente linear. .................. 22

Interceptação da bola .......................................................................................................... 35

Implementação do Agente: Função startEpisode(). .............................................................. 37

Implementação do Agente: Função step(). ........................................................................... 38

Implementação do Agente: Função endEpisode(). ................................................................ 38

LVF (Las Vegas Filter) ........................................................................................................... 44

Algoritmo policy iteration. .................................................................................................. 101

Algoritmo value iteration. .................................................................................................. 102

Monte Carlo on-policy ........................................................................................................ 106

Monte Carlo off-policy ....................................................................................................... 108

Combinação do algoritmo Q-Learning com as redes neurais artificiais multilayer perceptron.

.......................................................................................................................................... 117

xx

Lista de Siglas

instante de tempo discreto

instante de tempo final de um episódio

recompensa recebida no instante de tempo

estado sucessor

estado no instante de tempo

próxima ação

ação executada no instante de tempo

ação ótima

política ótima

probabilidade de transição do estado para o estado se executado a

ação

recompensa imediata esperada com a transição do estado para o esta-

do se executado a ação

quantidade de tillings

desconto

taxa de aprendizado

taxa de decaimento do rastro

probabilidade de executar uma ação aleatória em uma política

-ésimo retorno recebido no estado

xxi

probabilidade de executar uma ação quando o estado é

ação executada com probabilidade no estado

eligibility trace de um estado

eligibility trace do par estado-ação

função valor estado de uma política

função valor estado ótima

função valor estado-ação de uma política

função valor estado-ação ótima

1

Capítulo 1

Introdução

By mid-21st century, a team of fully autonomous humanoid robot soccer

players shall win a soccer game, complying with the official rules of the

FIFA, against the winner of the most recent world cup for human players.

-H. KITANO

1.1 Aprendizagem por Reforço e a RoboCup

A aprendizagem por reforço (Sutton & Barto, 1998) tem sido amplamente utilizada

em problemas nos quais outras abordagens de aprendizado não podem ser aplica-

das; problemas cujas tarefas não oferecem o suporte de um professor que possa

disponibilizar as respostas desejadas ou comportamentos esperados. Modelos que

necessitam de um professor são conhecidos como modelos supervisionados e utili-

zam a aprendizagem supervisionada como base de seu treinamento (Haykin, 1994).

Os modelos baseados neste tipo de aprendizagem dispõem de um conjunto de en-

trada e respostas desejadas na sua amostra de dados para treinamento. O objetivo

dos modelos supervisionados é aproximar a saída estimada - gerada pelo modelo -

da resposta desejada. Sucessivas passagens da amostra de treinamento pelo mo-

delo são feitas até que algum critério de parada seja satisfeito. Normalmente os cri-

térios de parada dos métodos iterativos estão associados ao erro gerado pelo mode-

lo e são satisfeitos quando o erro é menor que algum valor especificado previamente

ou se este erro não se reduz ao longo das iterações.

Outro tipo de aprendizado é conhecido como aprendizagem não-

supervisionada. Neste tipo de aprendizagem os modelos não dispõem de um pro-

fessor para disponibilizar as respostas desejadas. O processo de aprendizagem

consiste em encontrar semelhanças entre os dados, agrupando-os em grupos para

posteriormente serem rotulados.

1.1 Aprendizagem por Reforço e a RoboCup 2

O termo aprendizagem por reforço consiste em programar modelos para que

possam ser treinados por interação com o ambiente, e tem como objetivo aumentar

sua recompensa ao longo do tempo (Sutton & Barto, 1998). Este tipo de aprendiza-

do foi inspirado principalmente no comportamento do aprendizado animal, cujo trei-

namento tem como base tentativa e erro. Explicitamente, este tipo de aprendizado

não possui um professor, mas existem informações sobre a relevância de suas a-

ções codificadas em um sinal numérico1 chamado recompensa.

O conceito de aprendizado por reforço pode ser aplicado em tudo que possa

monitorar e atuar no ambiente, tais como um agente. A área de Inteligência Artificial

define um agente como uma entidade que funciona de forma contínua e autônoma,

que seja capaz de sentir e atuar no ambiente em que se situam, por meio de atuado-

res e sensores (Russell & Norvig, 2003). Em um robô pode-se, por exemplo, consi-

derar como atuador um motor de passo que permite realizar o movimento de um

braço mecânico e, como sensor, uma câmera de vídeo que permite a visualização

do ambiente.

Widrow e colegas (1973) utilizaram o termo “aprendendo com um crítico” (le-

arning with a critical) para diferenciar o processo de aprendizagem por reforço dos

modelos que aprendem com um professor. É de responsabilidade do crítico avaliar e

codificar o efeito das ações realizadas pelo agente em um sinal numérico que indica

o quanto é “promissor” realizar uma ação particular em um estado. O agente deve

selecionar as ações que maximizem o acumulado do sinal de recompensa que rece-

be ao longo do tempo, pois ações que o levam para estados que aparentemente dão

a maior recompensa em um dado momento podem levar a outros que não dão

(Sutton & Barto, 1998).

Dentre todas as tarefas em que a aprendizagem por reforço é utilizada pode-

se destacar o campeonato de futebol de robôs. De acordo com Kitano e colegas

(1995), a iniciativa do campeonato de futebol de robôs ou RoboCup é uma tentativa

criada com o intuito de prover um ambiente complexo e padronizado, onde pesqui-

sadores da área de inteligência artificial e áreas relacionadas possam avaliar e exa-

minar novas tecnologias. Seu objetivo final é desenvolver, até o ano de 2050, um

time de futebol completo composto por robôs humanóides (Kitano & Asada, 1998).

1 O sinal numérico deve ser um número que represente a satisfação do agente em um estado. Normalmente este número assume valores negativos para punição e positivos para recompensa.

1.2 Motivação 3

O campeonato de futebol de robôs cobre diversas áreas da Inteligência Artifi-

cial e robótica, tais como, projeto de agentes autônomos, colaboração entre agentes,

raciocínio em tempo real, sensores em tempo real, aprendizado, visão, controle mo-

tor, controle inteligente de robô e outras (Kitano et al., 1997). O escopo do presente

trabalho, no entanto, está restrito ao ambiente de um simulador 2D que abstrai ques-

tões mais complexas ligadas à robótica, como movimentação de membros e visão

computacional. Formalmente, o ambiente proporcionado pelo simulador de futebol

de robôs (RoboCup) é definido como: Parcialmente Observável, Estocástico, Episó-

dico2, Dinâmico, Contínuo e Multi-Agente (Russell & Norvig, 2003).

Como apresentado em detalhes por Stone (1998), o simulador de futebol de

robôs é um ambiente totalmente distribuído, multi-agente que possui os jogadores

de um time e os oponentes do outro. O simulador opera em tempos discretos, em

que cada passo de tempo representa 100ms e, se o agente não realizar uma ação

neste intervalo de tempo, o agente perde a chance de executar a ação, tornando o

ciclo perdido (Cheny et al., 2003).

Ainda no simulador de futebol de robôs, estados ocultos são incluídos. Cada

agente tem uma visão parcial do mundo a todo momento: por padrão, a visão de

cada agente é limitada em um ângulo de 90 graus, e a precisão dos objetos vistos

pelo agente diminui com o aumento da distância. Os agentes tem ruído nos senso-

res e atuadores; o que não permite que eles percebam o mundo exatamente como

ele é (sim como eles vêem), como também não permite que possam afetar o mundo

exatamente como queiram. Adicionalmente, os ciclos de percepção e ações são as-

síncronos, proibindo o uso de paradigmas tradicionais da IA clássica que utilizam a

percepção como entrada para a ativação de determinadas ações. As oportunidades

de comunicação entre os agentes são limitadas e o agente deve tomar suas deci-

sões em tempo real, o que impede a utilização de algoritmos de busca exaustiva.

Estas características tornam o simulador de futebol de robôs realístico e desafiador.

1.2 Motivação

O simulador de futebol de robôs apresenta desafios para modelos de aprendizagem,

disponibilizando um ambiente estocástico com variáveis de estado contínuas, que

2 Seqüência finita de percepção-ação do agente.

1.2 Motivação 4

inclui a ação do vento, incerteza, ruídos nos sensores e outras que justificam e moti-

vam a utilização do ambiente proporcionado pelo futebol de robôs no teste de novas

abordagens de aprendizado. Estas e outras complexidades tornam o futebol de ro-

bôs um simulador de tempo real capaz de prover um ambiente desafiador, ideal para

o teste de novos modelos computacionais.

De posse da bola, um jogador da linha tem fundamentalmente quatro opções:

chutar a gol, conduzir a bola, dar um passe para um companheiro ou dar um drible

no adversário. O chute a gol é um problema tipicamente supervisionado (Oliveira et

al., 2009) enquanto os outros três não produzem resultados diretamente associados

às ações. O interesse pela habilidade do drible deve-se ao fato de que, em uma par-

tida real de futebol, a habilidade de driblar é considerada uma das mais difíceis de

executar e uma das mais eficientes em um movimento de ataque. Com esta habili-

dade, os jogadores serão capazes de aumentar o desempenho do ataque, permitin-

do jogadas individuais que podem aumentar as chances de gol.

A aprendizagem por reforço tem sido aplicada com sucesso em ambientes

com grandes quantidades de estados (Tesauro,1994; Crites & Barto, 1996; Bagnell

& Schneider, 2001; Braga & Araújo, 2002; Barto et al., 1990; Stone et al., 2005). Sua

tolerância a ruídos e sua capacidade de generalização em ambientes estocásticos

tornam os modelos de aprendizado por reforço atrativos em ambientes como o pro-

porcionado pelo futebol de robôs (Stone et al., 2005; Riedmiller et al., 2001). Assim

como na aprendizagem supervisionada e não-supervisionada, a qualidade dos da-

dos é de grande importância para a convergência e generalização destes modelos

(Coons et al., 2008).

A Mineração de Dados é uma das aplicações de inteligência artificial que bus-

ca extrair informações ou padrões de grandes quantidades de dados armazenados

em bancos de dados, ou trafegando em um fluxo contínuo de dados (Han & Kamber,

2006). Pesquisas recentes mostram que algumas técnicas da mineração de dados

podem ser aplicadas com sucesso na aprendizagem por reforço para (Alhajj & Kaya,

2003; Kheradmandian & Rahmati, 2009), mas estas técnicas não têm sido utilizadas

para determinar quais atributos e ações são relevantes para que o agente consiga

atingir seu objetivo. Contudo, existem casos de sucesso para esta finalidade em ou-

tros paradigmas da aprendizagem que incentivam pesquisas nesta área (Matoušek

& Aubrecht, 2006; Lu et al., 1996).

1.3 Contextualização 5

1.3 Contextualização

Recentemente, grande parte das pesquisas, relacionadas com a aprendiza-

gem por reforço, procuram desenvolver algoritmos mais eficientes, porém isso re-

quer o pré-processamento dos dados antes da aplicação dos algoritmos (Lu et al.,

1996; Han & Kamber, 2006). O pré-processamento dos dados é uma etapa da mine-

ração de dados que consiste em tratar os dados contidos em uma base de dados

para que seja alcançado um ganho na eficiência do aprendizado, entre outros as-

pectos. Na aprendizagem por reforço, a inexistência de bases de dados representa

uma dificuldade para a aplicação de técnicas de mineração de dados.

Apesar das pesquisas com mineração de dados estarem mais relacionadas

na literatura com os paradigmas da aprendizagem supervisionada e não-

supervisionada, Cohen e Maimon (2005) mostram que existem relações entre a a-

prendizagem por reforço e a mineração de dados. Vieira e colegas (2010) mostra-

ram que é possível a utilização das técnicas de mineração de dados para seleção de

atributos e ações em ambientes da aprendizagem por reforço. A seleção de atributos

e ações permitiu a redução da dimensionalidade do problema, redução no tempo de

convergência e no uso da memória.

Dentre as técnicas de pré-processamento encontradas na mineração de da-

dos, a seleção de atributos feature selection (Han & Kamber, 2006) é uma das mais

importantes. Com a seleção de atributos é possível reduzir a complexidade do pro-

blema, aumentar a capacidade de generalização, acelerar o processo de aprendiza-

do, melhorar a interpretabilidade do modelo e reduzir a quantidade de memória e

processamento utilizados. De acordo com a lógica da navalha de Occam (Occam’s

Razor) (Liu & Motoda, 1998), modelos complexos tendem a ser menos eficiente que

os de menor complexidade. Esta lógica expõe a importância em realizar uma análise

qualitativa dos atributos.

Na mineração de dados, a qualidade dos atributos pode ser medida calculan-

do-se o ganho de informação de cada variável. O ganho de informação é uma medi-

da que mede a capacidade de um atributo em classificar os dados de treinamento

(Mitchell, 1997). Outras técnicas de mineração de dados para esta finalidade já fo-

ram descritas na literatura (Hall, 1999; Liu & Setiono, 1996).

Na aprendizagem por reforço, a escolha dos atributos do ambiente e ações do

agente é de fundamental importância para seu aprendizado, pois atributos desne-

1.3 Contextualização 6

cessários aumentam o espaço de busca, tornando difícil encontrar uma solução óti-

ma (Coons et al., 2008). Com a remoção das variáveis de menor relevância, de a-

cordo com alguma métrica usada pelas técnicas de seleção de atributos, é possível

obter um ganho significativo no desempenho do modelo (Han & Kamber, 2006).

Na literatura há trabalhos (Cavazos & Moss, 2004; 2006; Stepheson et al.,

2002) que utilizam especialistas no problema para auxiliarem na tarefa de seleção

de atributos. Porém, vale ressaltar que a disponibilidade de um especialista nem

sempre é possível, e em alguns casos o especialista pode não ajudar. Hipotetica-

mente, se fosse perguntado a um jogador de futebol em quais características do

campo, da bola e do oponente ele está preocupado no momento de um drible, entre

outras, possivelmente a distância do oponente seria uma das principais característi-

cas. Entretanto, para um robô, a distância da bola poderia ser sua principal caracte-

rística, pois sem esta variável o robô seria incapaz de realizar um chute já que, no

futebol de robôs, existe uma margem que define uma distância máxima entre o a-

gente e a bola para que seja possível realizar um chute. Se neste ponto as variáveis

mais relevantes do ambiente recebessem um peso maior no treinamento do agente,

os modelos construídos provavelmente teriam desempenhos diferentes.

Outro aspecto de suma importância nos ambientes da aprendizagem por re-

forço é o espaço de ações disponíveis para o agente. Agentes que possuem gran-

des quantidades de ações, não necessariamente redundantes, podem prejudicar o

aprendizado tornando a convergência do modelo mais lenta (Riedmiller, 1999). Uma

das soluções para este tipo de problema consiste na transformação das ações de

forma a reduzir o espaço de ações do agente (Stone & Sutton, 2001). Basicamente

esta técnica baseia-se na abstração de um conjunto de ações, geralmente de baixo

nível, em uma única ação de alto nível. No entanto, a desvantagem desta técnica é a

necessidade de um especialista com conhecimentos avançados do problema. Uma

alternativa, naturalmente, seria avaliar todas as ações realizáveis pelo agente, para,

então, remover as ações que não contribuem para o agente alcançar seu objetivo.

A seleção de atributos e ações são apenas algumas das melhorias que po-

dem ser alcançadas com a aplicação de técnicas de mineração de dados em ambi-

entes da aprendizagem por reforço. Outras que podem ser realizadas são:

Transformação das variáveis - Estas também fazem parte da etapa

de pré-processamento, e são intensamente utilizadas em problemas da a-

1.4 Objetivos 7

prendizagem supervisionada e não-supervisionada. As técnicas para trans-

formação das variáveis buscam meios para modificar (transformar) as variá-

veis de entrada de um modelo, com o objetivo de obter atributos de melhor

qualidade (Han & Kamber, 2006).

Eliminação de atributos correlacionados (Agakov et al., 2006; Cava-

zos & Moss, 2006) - Esta técnica evita a utilização de atributos redundantes

no aprendizado do modelo. Na aprendizagem por reforço, atributos redundan-

tes podem prejudicar a generalização, aumentar o tempo de convergência e o

consumo de memória e processamento.

A maior dificuldade da seleção automática de atributos, sem o uso das técni-

cas de mineração de dados, é o crescimento exponencial do tempo necessário para

encontrar um conjunto ótimo de atributos, uma vez que não seria possível encontrar

a seleção ótima sem o teste de todas as possíveis combinações dos atributos re-

levantes escolhidos de todos os atributos, i.e., aplicando o critério

vezes. Se a quantidade dos atributos relevantes não é conhecida, o tempo total

necessário para encontrar a melhor combinação de atributos será proporcional a

.

1.4 Objetivos

O principal objetivo deste trabalho é propor a utilização de técnicas de mineração de

dados para a seleção de atributos e ações dos ambientes da aprendizagem por re-

forço, visando a melhorar o desempenho dos modelos utilizados e reduzir o consu-

mo de memória e processamento.

Outro objetivo considerado é a utilização da aprendizagem por reforço no fu-

tebol de robôs para a realização do drible. Como forma de incorporar conhecimento,

os agentes utilizam as ações de nível intermediário disponíveis pelo time CMUnited-

99 (Boer & Kok, 2002), ao invés das ações primitivas do simulador. As ações utiliza-

das são:

Hold_BALL() - Posiciona a bola em um ângulo em relação ao corpo do

agente que mantenha a bola o mais distante possível do oponente.

1.5 Contribuições 8

Conduzir(ângulo, velocidade) - Conduz a bola com um ângulo entre

graus em 3 possíveis velocidades: devagar, normal e rápido. O

ângulo de condução deve ser múltiplo de 5 graus para diminuir a complexida-

de do problema.

Intercept() - Procura e intercepta a bola. Esta função é chamada

quando a bola está a uma distância maior que a permitida para realizar um

chute.

Através destas ações deseja-se criar uma nova ação de alto-nível chamada

drible() que possibilite o agente driblar o oponente.

1.5 Contribuições

Este trabalho contribui demonstrando que a aprendizagem por reforço pode ser apli-

cada com sucesso na realização do drible, um problema de grande complexidade e

pouco abordado na literatura. A complexidade citada diz respeito ao tamanho do es-

paço de busca que é aumentado proporcionalmente em função da quantidade de

ações e estados do ambiente. Por exemplo, em um ambiente episódico de esta-

dos e ações, considerando-se que um estado não seja revisitado no mesmo epi-

sódio, o tempo necessário para o agente encontrar a melhor solução no pior caso é

. Riedmiller (1999) investigou a utilização das redes neurais em ambientes da

aprendizagem por reforço, constatando um aumento no tempo de convergência des-

tes modelos, cerca de 400% (144.000s), devido ao aumento da quantidade de a-

ções. Os experimentos realizados acerca desta etapa investigarão a capacidade de

convergência do modelo utilizado por este trabalho em ambientes complexos com

grande quantidade de ações e estados. O ambiente do drible é composto de 23 va-

riáveis de estado contínuas e, 113 ações realizáveis, o que torna o espaço de busca

do agente alto e desafiador.

A principal contribuição mostra que as técnicas de mineração de dados po-

dem, também, ser utilizadas com sucesso em problemas da aprendizagem por refor-

ço. Uma das vantagens da utilização das técnicas de mineração de dados para a

identificação dos atributos e ações mais relevantes de um determinado problema é a

realização de uma análise estatística das variáveis de forma independente do espe-

1.6 Descrição da Dissertação 9

cialista no domínio. Identificando e selecionando as melhores variáveis e ações de

acordo com alguma métrica estabelecida previamente, é possível melhorar a capa-

cidade de generalização, diminuindo o tempo de convergência, aumentando a inter-

pretabilidade e reduzindo o consumo de processamento e memória.

1.6 Descrição da Dissertação

Neste trabalho será apresentado o desenvolvimento de um modelo baseado na a-

prendizagem por reforço para o controle de um agente inserido no ambiente provido

pelo simulador de futebol de robôs (RoboCup). Este modelo será utilizado no trei-

namento do agente para aprender a realizar o drible.

O modelo utilizado possui características temporais e foi combinado com um

aproximador linear, conhecido como tile-coding (Sutton & Barto, 1998), para permitir

a sua utilização em ambientes de estados infinitos. O treinamento do modelo ocorre

mediante o cálculo das estimativas de recompensa para cada estado visitado, e tem

convergência garantida para uma política ótima, se o agente visitar os estados infini-

tamente (Sutton & Barto, 1998). Terminado o treinamento, as estimativas de recom-

pensa de cada estado estarão armazenadas na memória do agente e, portanto, as

próximas ações do agente serão determinadas por uma busca gulosa (Mitchell,

1997) pelas entradas da tabela de estimativas (Sutton & Barto, 1998).

O agente será treinado contra o oponente do time UvA Trilearn (Boer & Kok,

2002). Este time foi escolhido devido a sua reputação, e disponibilização do código

fonte e do código binário.

O presente trabalho avaliará 3 métodos para identificar e selecionar os atribu-

tos mais relevantes e 2 medidas, confiança e suporte, normalmente utilizadas na

avaliação de regras de associação, para identificar e selecionar as ações mais rele-

vantes.

1.7 Organização da Dissertação

Esta dissertação está organizada em seis capítulos, incluindo esta introdução.

1.7 Organização da Dissertação 10

O Capítulo 2 está relacionado ao desenvolvimento do modelo utilizando o mé-

todo de aprendizagem temporal combinado com a técnica de tile-coding para permi-

tir a generalização.

O Capítulo 3 mostra como o ambiente de teste foi modelado para um proble-

ma da aprendizagem por reforço e como o modelo criado foi estruturado para solu-

cioná-lo. Ainda neste capítulo serão mostradas informações importantes para a

construção do ambiente de treinamento, tais como as características técnicas dos

jogadores, do campo, do técnico e da bola.

O Capítulo 4 descreve as técnicas de mineração de dados, e como estas po-

dem ser utilizadas em ambientes da aprendizagem por reforço.

O Capítulo 5 mostra os experimentos, seus resultados e sua interpretação

baseada em análise estatística do modelo utilizando o problema do drible como es-

tudo de caso.

O Capítulo 6 apresenta as conclusões da dissertação, suas limitações e res-

salta as perspectivas de trabalhos futuros.

O Apêndice A revisa o conceito de programação dinâmica, enfatizando aspec-

tos importantes para a consolidação dos principais métodos da aprendizagem por

reforço.

O Apêndice B revisa os modelos baseados no gradiente descendente e como

podem ser combinados com os algoritmos da aprendizagem por reforço.

11

Capítulo 2

Modelo Computacional

Os tradicionais modelos da aprendizagem por reforço baseados em tabelas são in-

capazes de generalizar (Sutton & Barto, 1998). Algumas técnicas vêm sendo combi-

nadas em problemas de domínios de larga escala para possibilitar a generalização.

O jogo de gamão (Tesauro, 1994), controle de elevadores (Crites & Barto, 1996),

controle de helicóptero (Bagnell & Schneider, 2001), balanceamento da polia (Barto

et al., 1990), navegação de robôs (Braga & Araújo, 2002) e o KeepAway da Robo-

Cup (Stone et al., 2005) são exemplos de combinações.

Este trabalho utilizou um aproximador linear, conhecido como Tile Coding

(CMAC) (Albus, 1975), construído com base no funcionamento do cerebelo, para

obter a generalização desejada. A motivação do uso deste aproximador deve-se à

teoria que o cerebelo é responsável pelo controle de membros. O funcionamento do

cerebelo tem características semelhantes ao aproximador linear chamado Percep-

tron (Albus, 1975) que é a base para o funcionamento do CMAC.

Este capítulo divide-se em quatro seções com os conceitos colocados de for-

ma seqüencial: A Seção 2.1 apresenta dois dos principais algoritmos da aprendiza-

gem por reforço. A Seção 2.2 realiza uma revisão na literatura e introduz o conceito

de aproximação de funções. A Seção 2.3 mostra a variante do algoritmo LMS para

construir o modelo linear utilizado.

2.1 Aprendizado por Diferença Temporal 12

2.1 Aprendizado por Diferença Temporal

O método de aprendizagem por Diferença Temporal, também chamado de TD

(Temporal Difference) (Sutton, 1988), surgiu com a combinação de idéias retiradas

de dois métodos da aprendizagem por reforço: Monte Carlo e a programação di-

nâmica (Sutton & Barto, 1998).

A vantagem dos métodos temporais deve-se ao seu processo de aprendiza-

gem incremental. Diferente do método Monte Carlo, neste tipo de aprendizagem o

valor de um estado, ou de um par estado-ação, é atualizado imediatamente após a

ação do agente. Da mesma forma que a programação dinâmica, o aprendizado por

diferença temporal atualiza o valor de um estado utilizando o valor do seu estado

sucessor e da recompensa imediata. Sendo assim, não é preciso esperar até o fim

do episódio para que a aprendizagem aconteça. Esta característica possibilita utilizar

os métodos temporais em ambientes que não sejam episódicos. Isto traz uma gran-

de vantagem em relação ao método Monte Carlo, pois em alguns problemas os epi-

sódios podem ser longos tornando a aprendizagem lenta. Em outras palavras a a-

tualização da função valor-estado para um estado pode ser definida como:

( 2.1)

onde e são respectivamente o valor dos estados e , é a taxa de a-

prendizado, é o estado sucessor a e é o desconto. O valor do parâmetro de-

ve ser maior que zero e menor que um. De acordo com Sutton & Barto (1998), de-

ve diminuir com o tempo para impedir que as estimativas continuem variando em

resposta as recompensas mais recentes recebidas.

O termo desconto apresentado na Equação 2.1 refere-se a um termo que de-

termina a importância das recompensas futuras (Sutton & Barto, 1998). Se for igual

a zero tornará o agente mais oportunista, considerando apenas as recompensas i-

mediatas. Desta forma o agente aprenderá a escolher para maximizar apenas

o que pode diminuir o retorno. À medida que se aproxima de um, o agente dará

mais importância às recompensas futuras de forma a maximizar o retorno.

A Equação 2.1 tem uma semelhança com a Equação A.14 como mostrado a

seguir:


( 2.2)

Uma possível forma de interpretar a Equação A.17 é dada a seguir:

( 2.3)

onde para o método Monte Carlo é enquanto que para o método TD é

. Para e a convergência é garantida pela lei dos

grandes números, mas não para o caso em que é uma constante e

. No entanto, Dayan (1992) provou que para qualquer política fixa , o mé-

todo TD também converge para com probabilidade se o parâmetro decair

com o tempo.

Antes de apresentar a variação do algoritmo TD para os métodos on-policy e

off-policy, a Subsubseção 2.1.1 apresenta um mecanismo chamado de eligibility tra-

ces que se combinado com os algoritmos TD pode proporcionar um aumento na efi-

ciência do aprendizado.

2.1.1 Rastro de Elegibilidade

A técnica eligibility trace (rastro de elegibilidade) torna possível retornar para os es-

tados passados uma parcela da recompensa recebida em um estado sucessor. A

Figura 2.1 ilustra a mecânica da técnica.


Figura 2.1 Visão mecânica da técnica de elegibility traces. Fonte: (Sutton & Barto, 1998)

Este método utiliza uma memória adicional associada a cada estado deno-

tado por , onde em cada interação seu valor é diminuído, em função de dois pa-

râmetros e e, incrementado em (accumulating traces) ou substituído por (re-

placing traces) quando é o estado sucessor de . Em outros termos, pode-se defi-

nir a atualização de em um instante de tempo , como segue:

(accumulating traces)

( 2.4)

ou (replacing traces)

( 2.5)

onde é o fator de desconto e é o parâmetro para redução gradual de . O

parâmetro determina a contribuição dos estados passados para que ao agente

resultar-se em um estado .

2.1.1.1 Sarsa( )

Nesta seção é apresentado o método on-policy combinado com a técnica de elegibi-

lity traces, chamado Sarsa( ) (Rummery, 1995). Conforme visto nas seções anterio-

res os métodos on-policy seguem uma política flexível e a atualização da política é a

mesma utilizada para o controle do agente. A política utilizada pode ser qualquer

uma, mas deve garantir que todos os estados sejam visitados infinitamente.


Algoritmo 2.1 Sarsa( )

O Algoritmo 2.1 segue uma política (Seção A.3) para garantir que

os estados não greedy tenham probabilidade de serem selecionados. Um exemplo

de política para o Algoritmo 2.1 é selecionar uma ação greedy com pro-

babilidade e com probabilidade uma ação qualquer. O Algoritmo 2.1 mostra o

pseudocódigo do algoritmo modificado. Conforme apresentado, a estimativa

passa a ser atualizada por:

( 2.6)

onde

( 2.7)

e (accumulating traces)

início:

para cada faça

;

;

fim

para cada faça

inicialize ;

repita

realize a ação e observe e ;

escolha uma ação seguindo uma política derivada de Q;

;

; // Para accumulating traces ou

; // Para replacing traces

para todo faça

;

;

fim

;

;

até ;

fim

fim


( 2.8)

ou (replacing traces)

( 2.9)

O algoritmo Sarsa( ) segue a mesma propriedade do algoritmo TD( ), ou se-

ja, fixando uma política é possível estimar o valor de e, garantindo que o

agente siga uma política assegura a convergência para uma política óti-

ma .

2.1.1.2 Método Q( )

Q-Learning (Watkins, 1989) é um algoritmo off-policy, baseado na aprendizagem por

diferença temporal, normalmente utilizado em tarefas de controle. Este algoritmo

trabalha com uma matriz de estado-ação que armazena as estimativas de recom-

pensa em se realizar uma ação em um estado .

Seguindo o conceito da aprendizagem por diferença temporal, a atualização

da estimativa de recompensa de um par estado-ação, dá-se por:

( 2.10)

onde é a estimativa de recompensa de realizar uma ação em um estado ,

é um parâmetro que define a taxa de aprendizado, é o fator de desconto e

é a estimativa de recompensa de realizar uma ação em um estado suces-

sor a .

2.2 Controle com Aproximador de Funções 17

Algoritmo 2.2 Q( )

O Algoritmo 2.2 mostra o método Q-Learning com a técnica de eligibility traces. Este

método segue uma política de comportamento flexível (e.g. ) enquanto

que a política de estimação continua gulosa ( ).

2.2 Controle com Aproximador de Funções

Nas tarefas de controle em ambientes da aprendizagem por reforço, obter a genera-

lização desejada pode ser problemático, pois em grande parte das tarefas alguns

estados nunca serão vivenciados exatamente como antes. Estas tarefas incluem

sensores complexos, como os de uma imagem visual. A solução para este tipo de

problema é a generalização de estados já visitados pelo agente, para estados nunca

vistos anteriormente.

A generalização a partir de exemplos é largamente utilizada em outros para-

digmas da aprendizagem, como, por exemplo, a aprendizagem supervisionada. Este

início:

para cada faça

;

;

fim

para cada faça

inicialize ;

repita

realize a ação e observe e ;

escolha uma ação seguindo uma política derivada de Q;

;

;

; // Para accumulating traces ou

; // Para replacing traces

para todo faça

;

se então ;

senão ;

fim

;

;

até

fim

fim

2.2 Controle com Aproximador de Funções 18

tipo de aprendizagem é freqüentemente chamado de aproximação por função, pois

são utilizados exemplos de uma função desconhecida para construir um aproxima-

dor de toda função.

Os tradicionais algoritmos da aprendizagem por reforço (Apêndice A) são re-

presentados como uma tabela na qual cada entrada representa o valor de estimativa

do par estado-ação. Este tipo de abordagem é limitado em tarefas com pequenos

números de estados e ações devido ao alto consumo de memória e tempo de pro-

cessamento para preencher a tabela de estimativas. Cada entrada da tabela manti-

da por estes modelos não compartilha o conhecimento com seus vizinhos, o que não

permite a generalização.

A generalização em ambientes da aprendizagem por reforço é de grande vali-

a, pois em ambientes com variáveis de estado contínuo a quantidade de estados

torna-se infinita, tornando o treinamento dos agentes impraticável devido ao alto

consumo de memória e tempo de processamento para preencher a tabela de esti-

mativas, visto que o agente deve revisitar cada estado infinitamente (ver Apêndice

A). A principal característica da generalização em ambientes da aprendizagem por

reforço é possibilitar que os agentes possam se basear em experiências passadas

para realizar determinadas ações em estados nunca vistos anteriormente pelo agen-

te.

Basicamente, os modelos utilizados na aprendizagem supervisionada e não-

supervisionada, tais como uma rede neural artificial, podem ser combinados com a

aprendizagem por reforço para obter a generalização desejada. Como exemplo des-

ta combinação pode-se citar o trabalho de Tesauro (1994) que consistiu na combi-

nação de uma Rede Neural Artificial Multilayer Perceptron (Rumelhart et al., 1986)

com o algoritmo para estimar os valores de . A grande vantagem deste

modelo consiste na capacidade das Redes Neurais Multilayer Perceptron aproxima-

rem qualquer função computável. No entanto, segundo Haykin (1994), a aplicação

das redes neurais artificiais em ambientes da aprendizagem por reforço é problemá-

tica devido à facilidade de este aproximador cair em ótimos locais. Boyan & Moore

(1995) e Riedmiller (2005) propõem estratégias para o treinamento da rede neural

em ambientes da aprendizagem por reforço para diminuir as chances de a rede neu-

ral cair em ótimos locais.

Barto e colegas (1990) utilizaram elementos adaptativos baseados no funcio-

namento do neurônio biológico (Perceptron). Neste trabalho o sistema de aprendiza-

2.3 Tile Coding (CMAC) 19

do consiste em dois elementos principais, são eles: ASE (Associative Search Ele-

ment) e ACE (Adaptive Critic Element). Este modelo possibilita a generalização em

ambientes complexos. Entretanto, assume a existência de um decodificador para

dividir o espaço de estados em regiões (Boxes) representadas por um vetor binário

de componentes. A desvantagem destes modelos deve-se ao número de regiões

obtidas em problemas de grande complexidade, o que ocasiona um uso excessivo

de memória para armazenar as estimativas de cada região. Outra desvantagem é

que as regiões não compartilham sua experiência com as regiões vizinhas, impedin-

do a generalização.

Uma alternativa para o modelo de Barto e colegas (1990) é a integração da

técnica CMAC (Cerebellar Model Articulation Controller) proposta por Lin e Kim

(1991). A técnica CMAC (Albus, 1975) distribui o aprendizado entre células de me-

mória ao invés de manter o aprendizado limitado em uma região. Esta técnica utiliza

as variáveis de estado como endereços para células de memórias, o que possibilita

o compartilhamento do aprendizado entre as regiões visitadas.

O trabalho realizado por Stone e colegas (2005) tornou possível verificar a

combinação do algoritmo com o modelo descrito por Lin e Kim (1991). As

células de memória neste modelo são organizadas em grades (tilings) de dimensão

e tamanho , sobrepostas com um deslocamento entre cada, onde é um

parâmetro que define a quantidade de grades existentes. Stone e colegas (2005)

validaram o modelo experimentalmente aplicando-o no ambiente do futebol de robôs

em um problema específico chamado Keepaway. Neste problema, os jogadores de-

vem manter a posse de bola pelo maior tempo possível sem perder a bola para os

oponentes. Os resultados dos experimentos apresentados foram satisfatórios, já que

em média, os jogadores permaneceram com a posse de bola por 15 segundos con-

tra 8 segundos de uma solução hand-coded.

2.3 Tile Coding (CMAC)

Uma parte do cérebro que parece ser intimamente envolvida nos processos de con-

trole de membros é o cerebelo (Brindley, 1964). A anatomia e os estudos neuro-

físicos desta parte do cérebro têm sustentado esta teoria (Albus, 1971; Grossman,

1967).


Segundo Albus (1971), a ativação do cerebelo chega sob a forma de um fe-

edback sensorial e proprioceptiva3 dos músculos, articulações e pele junto com os

comandos de nível superior dos centros do motor que indicam o movimento que é

para ser realizado. De acordo com a teoria, esta entrada consiste em um endereço

no qual o conteúdo contido nestes endereços contém sinais apropriados para os

músculos realizarem o movimento desejado.

O resultado do movimento gera uma nova entrada (estado) e o processo é

repetido, resultando em uma trajetória de um membro pelo espaço. A cada ponto

desta trajetória, o estado do membro é enviado para o cerebelo como entrada e a

memória cerebelar respondem com sinais atuadores para os músculos que movi-

mentam o membro para o próximo ponto da trajetória (Albus, 1975).

O CMAC é um sistema adaptativo utilizado em tarefas de controle. Inspirado

no funcionamento do cerebelo, a aproximação para uma política ótima é computada

pela referência a uma tabela ao invés de soluções matemáticas, tais como as redes

neurais artificiais (Albus, 1975). Este sistema combina as ações com as variáveis de

estado em um vetor de entrada utilizado para endereçar fisicamente posições na

memória onde serão armazenados os valores de estimativa de cada par estado-

ação.

A vantagem da combinação deste aproximador linear com os tradicionais mé-

todos da aprendizagem por reforço deve-se à possibilidade de este aproximador

permitir o compartilhamento do conhecimento de uma região entre suas vizinhas,

possibilitando a generalização. Determinada a região em que um estado se encon-

tra, as estimativas de suas regiões vizinhas são combinadas por meio de uma soma,

de forma similar ao perceptron.

3 Termo utilizado para nomear a capacidade em reconhecer a localização de um membro no espaço que inclui

sua posição e orientação, a força exercida pelos músculos e a posição de cada parte do corpo às demais, sem utilizar a visão.


Figura 2.2 Alguns tilings sobrepostos. Nesta figura cada tile é endereçado por duas

variáveis, e . A generalização é obtida entre as regiões sobrepostas. A sobrepo-sição dos tiles torna possível a experiência obtida em uma região ser compartilhada entre seus vizinhos.

A técnica de tile-coding consiste em separar o espaço de entrada em regiões

chamadas de tiles. Basicamente, um conjunto de vários tiles é chamado de tiling e

pode haver vários tilings sobrepostos com um deslocamento de entre si, onde

é a quantidade utilizada. A Figura 2.2 ilustra este conceito.

Cada tile contém uma estimativa daquela região. O valor da estimativa pas-

sa a ser obtido pela Equação 2.11.

( 2.11)

onde corresponde à estimativa contida no tile dos tilings de no qual o estado se

limita, e é a quantidade de tilings. A atualização de cada tile é dada pela Equação

2.1 com apenas uma alteração no valor de que passa a ser . A ação a ser

realizada pelo agente em um estado é definida por:

( 2.12)

A Equação 2.12 garante que o agente sempre realize as ações que aparen-

temente o levam a uma melhor recompensa ao longo do tempo. Para garantir que o

agente explore uma maior quantidade de estados, uma ação aleatória deve ser se-

lecionada com probabilidade e uma ação gulosa com probabilidade , desta

forma é possível diminuir a probabilidade de o agente cair em máximos locais (Se-

ção A.3 na página 103). O Algoritmo A.1 mostra o pseudo-código do CMAC combi-

nado com o algoritmo .


Algoritmo 2.3 Versão adaptada do algoritmo para o gradiente descenden-

te linear.

início:

;

;

para cada faça

;

para cada faça

;

fim

escolha uma ação seguindo uma política ;

repita

;

para cada faça

fim

realize a ação , observe a recompensa, , e o próximo estado, ;

;

para cada faça

;

fim

escolha uma ação seguindo uma política ;

;

;

;

até ;

fim

fim

23

Capítulo 3

Ambiente de Teste

O ambiente de teste utilizado nos experimentos deste trabalho é descrito neste capí-

tulo. Antes da apresentação do ambiente de teste as características mais elementa-

res do simulador e do agente são apresentadas nas Seções 3.1 e 3.2, respectiva-

mente.

A Seção 3.3 mostra como o ambiente de teste foi modelado. Ainda nesta se-

ção, será apresentado o comportamento dos oponentes utilizados no treinamento e

como o agente foi implementado para treinar o drible. Também é mostrada a impor-

tância do treinador (agente responsável em coordenar o time) no treinamento da ha-

bilidade de driblar.

3.1 Visão Geral do Simulador

O simulador da RoboCup-2D4 consiste em três componentes principais, são elas

(Boer & Kok, 2002): servidor, logplayer e monitor. O servidor tem papel principal em

uma partida de futebol da RoboCup. Esta componente proporciona um campo de

futebol virtual e é responsável pela simulação de todos os movimentos dos objetos

contidos no campo, que incluem os jogadores, treinadores, bola e ainda um juiz que

controla a partida de acordo com as regras do jogo.

Os jogadores são controlados por programas cliente (cérebro dos jogadores)

que se conectam ao servidor via protocolo UDP/IP5. Estas conexões são individuais

e estão associadas a um único jogador. Usando esta conexão é possível enviar soli-

citações ao servidor para executar uma ação específica (e.g. chutar a bola), como

também receber informações do estado do ambiente. Contudo, a comunicação dire-

4 Disponível em: http://sourceforge.net/projects/sserver/develop

5 Protocolo de comunicação não orientado para conexão. Este protocolo não garante a entrega dos dados para

o destino.

3.1 Visão Geral do Simulador 24

ta entre os jogadores não é permitida. Para isto, o agente deve se comunicar com os

outros agentes através dos comandos say (falar) e hear (escutar) enviados direta-

mente para o servidor que restringe esta comunicação. O servidor controla a partida

em instantes de tempo discreto. Cada instante de tempo, ou ciclo, possui 100ms e,

devido à característica de comunicação assíncrona, o servidor não espera pela ação

de um cliente para passar para o próximo instante de tempo. Sendo assim, se neste

intervalo de tempo o cliente não executar nenhuma ação, o ciclo será perdido.

O simulador também inclui um monitor para visualizar a partida de futebol. O

monitor e o servidor são conectados via protocolo UDP/IP. Depois de realizada a

conexão, o monitor passa a atualizar graficamente as informações do estado do am-

biente enviadas pelo servidor. A Figura 3.1 mostra a execução do monitor.

Figura 3.1 Monitor.

A última componente do simulador da RoboCup é o logplayer. O logplayer é

responsável em reproduzir uma partida de futebol da RoboCup armazenada em dis-

co. Esta ferramenta é útil para analisar as jogadas de um time em questão. Entre as

funções disponíveis pela ferramenta pode-se destacar a redução e o aumento da

3.2 Visão Geral do Agente 25

velocidade de reprodução, avanço na reprodução para uma jogada específica e re-

petição.

Figura 3.2 Estrutura do Agente.

Figura 3.3 Posições de todas as linhas e bandeiras do campo.

3.2 Visão Geral do Agente

Cada jogador é composto de um corpo e um pescoço, e são controlados de forma

independente pelo programa cliente. A representação gráfica de um jogador é mos-

trada na Figura 3.2. O pescoço determina para onde o agente está olhando em um

dado momento e a posição do corpo é a orientação do agente.

Os sensores dos agentes estão divididos em sensores visuais, corporais e

auditivos (Boer & Kok, 2002). Estes sensores são detalhados nos tópicos a seguir.


3.2.1 Sensor Visual

O sensor visual detecta as informações visuais do campo como distância e direção

dos objetos. Estas informações são enviadas pelo servidor automaticamente a cada

send_step ms. Send_step é um parâmetro do servidor que determina a freqüência

com que o servidor envia as informações dos objetos (jogadores e bola) ao agente.

O sensor visual também funciona como um sensor de proximidade, vendo os objetos

que estão atrás do agente, mas só se estiverem a uma distância máxima visi-

ble_distance. Visible_distance é uma constante definida antes do inicio da partida.

Por padrão, visible_distance tem valor 3 (metros).

A informação sensorial enviada para o agente, como distância e ângulo, são

relativas ao agente. A informação relativa deve ser convertida em informação global

pelo agente. Para facilitar esta conversão, foram colocadas bandeiras e linhas den-

tro e nos limites do campo. A Figura 3.3 mostra o campo com todas as bandeiras e

linhas. Combinando a posição global das bandeiras no campo com a posição relati-

va dos objetos, o agente pode determinar sua posição global e a dos outros objetos

no campo.

É permitido para o agente controlar a freqüência de atualização, qualidade e

limite de visão do seu sensor visual. A freqüência de atualização é obtida em função

dos parâmetros view_width_factor, send_step e view_quality_factor. O cálculo reali-

zado para determinar a nova freqüência é (Boer & Kok, 2002):

( 3.1)

onde é o novo intervalo de tempo no qual o servidor envia as infor-

mações visuais do agente, é o intervalo de tempo normal,

determina a largura do campo de visão do agente e

indica a qualidade da visão do agente.

Os parâmetros e devem assumir va-

lores pré-determinados pelo simulador. Estes valores são apresentados na tabela a

seguir:


Tabela 3.1 Possíveis valores para os parâmetros view_width_factor e vi-

ew_quality_factor.

Parâmetro Valor Descrição

view_width_factor

0.5 Visão estreita (45o)

1 Visão normal (90o)

2 Visão larga (180o)

view_quality_factor 0.5 Qualidade baixa

1 Qualidade alta

Figura 3.4 Campo de visão do agente. Os objetos são representados pelos círculos pretos, onde a, e, c, d e f são jogadores, g é o goleiro e b é a bola. Os objetos são vistos pelo agente se estiverem dentro do seu ângulo de visão determinado por vi-ew_angle, o jogador a, no entanto, pode ser sentido pelo agente. O goleiro g e a bo-la b não são vistos pelo agente. Unum_far_length, unum_too_far_length, te-am_far_length e team_too_far_length são constantes que representam a distância de um objeto e, por padrão, são definidos como 20, 30, 40 e 60 (metros), respecti-vamente. Fonte: (Stone, 1998).

Modificando o parâmetro afeta diretamente a sensibilidade

da visão do agente da seguinte forma:

Se for 0.5, o agente consegue somente enxergar, inde-

pendente da distância, apenas o nome do objeto e a direção do objeto.

Se for 1, o agente consegue enxergar mais detalhes dos

objetos, mas com a seguinte restrição: com o aumento da distância entre o

agente e um dado objeto, a quantidade de detalhes vistos pelo agente é re-


duzida. Seja a distância entre o agente e um objeto e ,

, , constantes que

discretizam a distância entre os objetos e o agente conforme ilustrado na Fi-

gura 3.4, os detalhes enxergados pelo agente são determinados como segue:

- Se , então o agente é capaz de visualizar o

número do uniforme do jogador e o nome do time ao qual pertence o

jogador. Ainda é possível visualizar: distância, direção, variação da di-

reção do corpo e pescoço e, a direção do corpo e pescoço.

- Se , então o agente é

capaz de saber a distância e direção do jogador com probabilidade 1.

No entanto, a probabilidade com que o agente consegue notar a varia-

ção da direção do corpo e pescoço diminui linearmente de 1 até 0 a

medida que aumenta.

- Se , então o agente não pode determinar

a variação da direção do corpo e pescoço do jogador, mas pode de-

terminar a distância e direção do jogador.

3.2.2 Sensores Auditivos

O sensor auditivo do agente detecta mensagens enviadas pelo treinador ou pelos

outros jogadores do mesmo time ou do time adversário. As mensagens são limitadas

por padrão em 512 bytes, e é o único meio de comunicação entre os agentes. O si-

mulador restringe a capacidade auditiva de cada agente. Agentes não conseguem

escutar mensagens originadas de jogadores que estão a uma distância máxima indi-

cada pela constante audio_cut_distance.

Outra restrição deste sensor limita a quantidade de mensagens que um agen-

te pode escutar em um intervalo de tempo. Cada vez que o agente recebe uma

mensagem, sua capacidade auditiva é diminuída pela constante hear_decay. O ser-

vidor mantém uma variável que conta a quantidade de mensagens recebidas pelo

agente. Inicialmente é igual ao seu valor máximo (hear_max). Esta variável indica

sua capacidade auditiva e quando atinge seu valor mínimo (zero) o agente fica

impossibilitado de receber novas mensagens. A cada ciclo de tempo, a variável é


incrementada hear_inc vezes e o agente pode voltar a receber mensagens quando

.

3.2.3 Sensores Corporais

Os sensores corporais detectam a informação física do agente, tais como energia,

velocidade do agente, ângulo do pescoço e outros. Uma descrição de todas as in-

formações obtidas através dos sensores corporais é resumida na Tabela 3.2. As in-

formações dos sensores corporais são enviadas ao agente a cada sense_body_step

ms (por padrão sense_body_step é igual a 100 ms).

Tabela 3.2 Descrição dos sensores corporais do agente.

Sensor Descrição Valor Padrão

view_quality Qualidade da visão do agente. Pode assu-

mir os valores high (alta) ou low (baixa). high

view_width

Largura do cone que representa a visão do

agente. Pode assumir valores narrow (es-

treito), normal ou wide (largo)

normal

stamina Número real positivo representando a ener-

gia atual do agente. -

effort Número real positivo representando o esfor-

ço atual do agente. -

amountOfSpeed Representa a velocidade atual do agente. -

directionOfSpeed Representa a direção do agente. -

neckAngle Representa o ângulo do pescoço em rela-

ção ao seu corpo. -

Dois sensores apresentados na Tabela 3.2 merecem atenção, são eles: sta-

mina e effort. O simulador impede que os jogadores fiquem correndo constantemen-

te no campo na sua velocidade máxima. Para controlar o quanto um jogador pode

correr, o servidor implementa o conceito de stamina (energia) e effort (esforço). A-

gentes que correm o tempo todo gastam sua energia (stamina) mais rapidamente do

que aqueles que correm somente quando necessário.

3.3 Modelagem do Ambiente do Drible 30

No inicio da partida o valor de stamina é igual à stamina_max. A cada ciclo de

tempo o valor de stamina é recuperado de acordo com a seguinte equação:

( 3.2)

onde stamina_inc_max é uma constante que determina a taxa de recuperação da

energia (stamina) e recovery é uma variável que diminui quando o valor de stamina

é menor que , onde recover_dec_thr é uma cons-

tante do simulador. É importante citar que o valor de recovery não é recuperado du-

rante a partida. Se recovery é decrementada, o tempo de recuperação de stamina

será maior.

Apesar de a variável stamina representar a energia do agente, é a variável

effort que determinará o esforço que o agente pode aplicar em uma corrida. As vari-

áveis stamina e effort estão relacionados como segue:

1. effort somente será decrementado quando stamina for menor que

, onde é uma constante do si-

mulador.

2. effort somente será incrementado quando stamina for maior que

, onde é uma constante do si-

mulador.

3.3 Modelagem do Ambiente do Drible

Neste trabalho o drible é definido como a habilidade de o jogador conduzir a bola

entre os oponentes sem perder a posse até um ponto específico do campo. Durante

o processo de drible o agente deve aprender a selecionar entre as possíveis ações,

as com maior probabilidade de sucesso, cujo objetivo é induzir o oponente a uma

determinada posição que favoreça a realização do drible.

Em alguns artigos encontrados na literatura o drible é tratado como a habili-

dade do jogador apenas conduzir a bola o que não é verdade. Em outras palavras

um movimento é considerado como sendo um drible se:

( 3.3)

e


( 3.4)

onde é a posição em metros do jogador no eixo ,

é a posição em metros no

eixo do oponente, é o instante de tempo, e entre e deve existir uma se-

quência de ações que torne possível o agente realizar o drible.

O agente deve iniciar um episódio em uma posição onde

. Será

considerado um drible, se em um instante de tempo , o agente conseguir pas-

sar seu oponente, i.e., se sua posição no eixo for maior (

). A constante (50cm) define uma distância mínima que o agente deve manter

do seu oponente após o drible.

Figura 3.5 Estados finais de um episódio. (a) Agente passou o oponente, mas o es-

tado final não aparenta ser um drible. (b) Agente passou o oponente deixando-o a-trás do seu corpo. Neste caso, o estado final aparenta mais ser um drible.

A Figura 3.5a mostra o estado final de um episódio que satisfaz apenas a E-

quação 3.3. Neste caso, a figura dá a impressão de que o agente correu do oponen-

te passando-o sem driblar. A Equação 3.4 garante que casos como este não ocor-

ram freqüentemente. Assim, para ser recompensado, é necessário que o agente en-

frente o oponente “encarando a marcação”. A Figura 3.5b mostra o estado final de

um episódio que satisfaz as Equações 3.3 e 3.4.

As seguintes equações asseguram a posse de bola do agente:

( 3.5)

onde é a norma euclidiana, é a margem de chute e , e são vetores

com as coordenadas relativas ao campo em metros da bola, do agente e do oponen-

te, respectivamente.

O ambiente de treinamento é modelado conforme apresentado na Figura 3.6.


Figura 3.6 Ambiente de treinamento

O objetivo do agente é satisfazer as Equações 3.3 e 3.4 sem que o mesmo ul-

trapasse os limites da região de drible, representados pelas linhas mais claras na

Figura 3.6. A linha mais escura é considerada como o fim da região de drible e se o

agente ultrapassá-la deverá ser recompensado mesmo não satisfazendo as Equa-

ções 3.3 e 3.4 do drible. A localização da região de drible é escolhida aleatoriamente

no inicio do drible. Isto garante que o agente não se limite apenas a uma região do

campo para realizar o drible.

O episódio é reiniciado e o agente é punido se exceder os limites da região

representada pelas linhas brancas ou, se a Equação 3.5 for . A posição do o-

ponente é aleatorizada a cada episódio, e a posição do agente é fixa no inicio da

região do drible.

A representação do ambiente para o agente é dado através de 23 variáveis

descritas na Tabela 3.4. As 110 ações realizáveis pelo agente são descritas na Ta-

bela 3.3.

Tabela 3.3 Ações realizáveis pelo agente.

Ação Descrição

Conduzir(ângulo,

velocidade)

Conduz a bola com um ângulo entre -90 e 90 em 3 possíveis

velocidades: lento, normal e rápido. O ângulo de condução

deve ser múltiplo de 5 incluindo o zero.

Hold_BALL( ) Coloca a bola próximo ao corpo do agente em um ângulo que

mantenha a bola o mais distante do oponente.

Intercept( ) Intercepta a bola.


Tabela 3.4 Representação do ambiente em 23 variáveis contínuas

Variável Descrição

aVelX Velocidade do agente em relação ao eixo x.

aVelY Velocidade do agente em relação ao eixo y.

bVel Velocidade relativa da bola.

oVelX Velocidade do oponente em relação ao eixo x.

oVelY Velocidade do oponente em relação ao eixo y.

bDist Distância entre o agente e a bola em metros.

oDist Distância entre o agente e o oponente em metros.

oBDist Distância entre o oponente e a bola em metros.

aSD Distância entre a posição inicial do agente e o agente em metros.

oSD Distância entre a posição inicial do agente e o oponente em metros.

bAngle Ângulo da bola em relação ao corpo do agente.

oBAngle Ângulo da bola em relação ao corpo do oponente.

oAngle Ângulo do oponente em relação ao corpo do agente.

aSA Ângulo da posição inicial do agente em relação ao agente.

oSA Ângulo da posição inicial do agente em relação ao oponente

aBodyA Ângulo da posição inicial do agente em relação ao corpo do agente.

ballDir Ângulo que indica a direção da bola.

bPosX Posição da bola no eixo x.

bPosY Posição da bola no eixo y.

oPosX Posição do oponente no eixo x.

oPosY Posição do oponente no eixo y.

aPosX Posição do agente no eixo x.

aPosY Posição do agente no eixo y.

O espaço de ações do agente para um estado foi definido como segue:

( 3.6)

onde é a margem de chute definido nos parâmetros do servidor da RoboCup.

Neste trabalho, a cada passo de tempo, o agente foi recompensado por e

no fim de cada episódio por se o agente realizou o drible e por se o agente não

conseguiu realizar o drible.


3.3.1 Treinador

O simulador da RoboCup permite a utilização de um agente especial chamado de

treinador. O treinador possui habilidades especiais, como movimentação de jogado-

res, visualização do campo e objetos sem ruído em seus sensores, capacidade em

parar e iniciar a partida, substituição dos jogadores e outras.

Existem dois tipos de treinadores, on-line e o off-line. Os treinadores do tipo

on-line são os únicos permitidos em uma partida real da RoboCup. Este tipo de trei-

nador possui algumas limitações se comparado com o treinador off-line. O treinador

on-line tem como única finalidade a coordenação do time com a realização de subs-

tituições e no envio de mensagens com instruções para os jogadores. O treinador

ainda pode manter estatísticas do jogo para uma mudança rápida na estratégia do

time.

O treinador off-line é utilizado no treinamento de jogadas ensaiadas do time

ou no treinamento de alguma habilidade específica, como o drible. Neste trabalho o

treinador off-line faz o papel do crítico. É ele o responsável em informar ao agente se

o episódio terminou ou não em sucesso. Ao fim de cada episódio o treinador é res-

ponsável em mover os jogadores para suas posições iniciais, conforme descrito na

Seção 3.3.

3.3.2 Comportamento dos Oponentes

Os dois times utilizados como oponentes, no treinamento do agente, são descritos

nos próximos tópicos. O time UvA Trilearn contém uma detalhada documentação da

implementação de suas funcionalidades básicas. Esta documentação é apresentada

na dissertação de mestrado de Boer & Kok (2002).

A Tabela 3.5 mostra o resultado classificatório do times UvA Trilearn nas compe-

tições German Open e Robocup.Os resultados apresentados mostram que os times

utilizados possuem uma boa estratégia de jogo, se comparado com os outros times

existentes.


Tabela 3.5 Resultado das competições German Open e RoboCup realizadas entre

2001 e 2004. O time UvA Trilearn obteve 3 vitórias no torneio German Open e uma vitória no torneio da RoboCup.

Torneio Classificação Ano

German Open 5o 2001

RoboCup 4o 2001

German Open 1o 2002

RoboCup 4o 2002

German Open 1o 2003

RoboCup 1o 2003

German Open 1o 2004

RoboCup 7o 2004

3.3.2.1 Time UvA Trilearn

A habilidade de interceptar a bola do time UvA Trilearn baseia-se no método analíti-

co apresentado em (Stone, 1998).

Algoritmo 3.1 Interceptação da bola

intercept( )

inicio

;

se então retorne ;

;

repita

;

;

;

até ou ;

se então

retorne

;

senão retorne ;

fim


O Algoritmo 3.1 mostra o pseudocódigo da habilidade de interceptar a bola

implementada pelo time UvA Trilearn.

No método analítico a estimativa da velocidade da bola é realizada através de

métodos preditivos que utilizam as posições passadas da bola. Os futuros movimen-

tos da bola são previstos baseando-se em sua velocidade estimada. Os métodos

preditivos utilizados no Algoritmo 3.1 (predictGlobPosAfterNrCycles e predictNrCy-

clesToPoint) são utilizados para prever o futuro estado dos objetos dinâmicos conti-

dos no campo, estes objetos incluem a bola e os oponentes. O time UvA Trilearn

não utiliza a previsão para determinar as futuras ações dos oponentes, concentran-

do apenas na previsão da posição da bola.

Os métodos preditivos utilizados no Algoritmo 3.1 são: predictGlobPosAf-

terNrCycles e predictNrCyclesToPoint. O primeiro método, predictGlobPosAf-

terNrCycles, realiza a predição da posição de um objeto após uma determinada

quantidade de ciclos. O segundo método preditivo, predictNrCyclesToPoint, realiza

a previsão de quantos ciclos serão necessário para o agente mover-se para a posi-

ção especificada.

3.3.3 Implementação do Agente

Os algoritmos da aprendizagem por reforço apresentados no Apêndice A assumem

que a interação entre o agente e o ambiente é síncrona. Em interações síncronas, o

agente e o ambiente estão em perfeita sincronia, tanto que o ambiente somente é

atualizado após a ação do agente. Enquanto esta ação não é realizada nada acon-

tece, o tempo para. Por exemplo, se a interação entre os jogadores e o simulador de

futebol de robôs fosse síncrona, o simulador só iria avançar para o próximo instante

de tempo após a ação de todos os jogadores.

Em uma interação assíncrona, o agente e o ambiente não estão em perfeita

sincronia, o tempo nunca é parado como acontece na interação síncrona. Neste tipo

de interação o simulador é quem dá o tempo e o agente deve acompanhar. Este tipo

de interação é problemático em problemas multiagentes ou onde a dinâmica do am-

biente depende do tempo. Isto porque o ambiente sofre constantes modificações

devido à ação dos outros agentes, ou da existência de objetos que variam com o

tempo (e.g. aceleração da bola).


Como descrito na Seção 3.1 o simulador recebe as ações do agente de forma

assíncrona operando em instantes de tempo discretos de 100ms, onde a cada ins-

tante de tempo o agente pode realizar uma ação. Se neste intervalo de tempo o a-

gente não executar nenhuma ação, o ciclo é perdido e o agente perderá a chance de

executar sua ação. Devido a estas características a implementação do modelo foi

dividido em 3 funções principais: startEpisode(), step() e endEpisode().

A função startEpisode() é chamada no inicio do episódio. Esta função apenas

seleciona a primeira ação do episódio seguindo uma política . A imple-

mentação desta função é apresentada a seguir:

Após o primeiro instante de tempo do episódio, a função step() é chamada a

cada ciclo do simulador. Esta função recebe a recompensa da última ação, escolhe

a próxima ação seguindo uma política e atualiza a política que está sen-

do seguida. O Algoritmo 3.3 apresenta a implementação da função step().

O último instante de tempo do episódio não deve ser executado na função

step(), pois o agente não deve selecionar uma próxima ação (característica da fun-

ção step()). Sendo assim, a função endEpisode() é chamada ao invés da função

step(). Na função endEpisode() o agente recebe a recompensa da última ação reali-

zada e atualiza a política seguida. Esta última função é apresentada no Algoritmo

3.4.

Algoritmo 3.2 Implementação do Agente: Função startEpisode().

startEpisode( )

;

;

para toda faça

;

fim

;

;

fim


Algoritmo 3.3 Implementação do Agente: Função step().

Algoritmo 3.4 Implementação do Agente: Função endEpisode().

endEpisode( )

se então

;

senão ;

;

para todo tile faça

;

fim

fim

step( )

;

;

;

para toda faça

;

fim

;


;

fim

;


;

;

fim

;

;

;

fim

39

Capítulo 4

Mineração de Dados na Aprendizagem por Reforço

A seleção de atributos é um processo para identificar e remover atributos irrelevan-

tes e/ou redundantes. Este processo reduz a dimensionalidade do problema fazendo

com que os algoritmos de aprendizagem possam operar de maneira eficiente e rápi-

da. Em alguns casos, a precisão dos algoritmos de aprendizagem pode ser aumen-

tada; em outros casos, o modelo torna-se mais compacto e, portanto, são mais rápi-

dos e fáceis de interpretar.

Pesquisas mostram que o desempenho da maioria dos algoritmos de apren-

dizagem de máquina são afetados por informações irrelevantes e redundantes du-

rante o treinamento. Por exemplo, o algoritmo do vizinho mais próximo (nearest nei-

ghbour) é sensível a atributos irrelevantes – o número de exemplos necessários pa-

ra que o algoritmo alcance uma precisão especificada aumenta exponencialmente

com o aumento de atributos irrelevantes (Langley & Sage, 1994b; Aha et al., 1991).

Outros algoritmos como as árvores de decisão e o C4.5 (Quinlan, 1993; Quin-

lan,1986) também são sensíveis a atributos irrelevantes e redundantes. Em muitos

casos, removendo os atributos redundantes e irrelevantes é possível aumentar signi-

ficativamente a eficiência destes algoritmos (Kohavi & John, 1996).

Na aprendizagem por reforço os atributos irrelevantes e redundantes aumen-

tam a dimensionalidade dos dados e o espaço de busca do agente. Se o espaço de

busca do agente é muito grande é possível que o algoritmo nunca6 convirja para

uma solução. Desta forma, fica evidente a importância da seleção de atributos em

ambientes da aprendizagem por reforço. Sendo assim, deseja-se explorar a política

do agente através do comportamento do agente armazenado em um banco de da-

dos para encontrar as variáveis mais relevantes. Espera-se que as variáveis mais

6 Em um espaço de busca muito grande pode levar anos para encontrar uma solução. Neste caso é considerado

que o algoritmo não converge para uma solução.

4.1 Seleção de Atributos 40

relevantes para uma política ( ) também sejam relevantes para outra política ( ), tal

que .

Neste capítulo são apresentados os princípios de funcionamento dos algorit-

mos de seleção de atributos considerados neste trabalho (Seção 4.1 e as Subse-

ções 4.1.1, 4.1.2 e 4.1.3). A abordagem proposta para a seleção de ações é apre-

sentada na Seção 4.2. A Seção 4.3 mostra a correlação existente entre a aprendiza-

gem por reforço e a mineração de dados. Nesta última seção também é mostrado

como o armazenamento e as transformações dos dados de treinamento do agente

são realizados.

Figura 4.1 Busca exaustiva pelo espaço de atributos. O ponto de partida pode inici-

ar sem nenhum atributo (visualização top-down) ou com todos atributos (visualiza-ção bottom-up).

4.1 Seleção de Atributos

De acordo com Genari et al. (1989), os atributos serão relevantes se seus valores

variam sistematicamente de acordo com o atributo que determina a classe. Em ou-

tras palavras, um atributo será útil ou relevante se estiver correlacionado com o atri-

buto que determina a classe das instâncias; caso contrário o atributo é considerado

irrelevante.


Evidências experimentais encontradas na literatura mostram que é preciso e-

liminar atributos irrelevantes e redundantes (Langley & Sage, 1994a; Kohavi & John,

1996; Kohavi & Sommerfield, 1995). Desta forma, é possível obter uma melhora na

eficiência dos algoritmos de aprendizagem. Um atributo é dito redundante se exis-

tem um ou mais atributos que possuem alto grau de similaridade com ele (inter-

correlação). Um conjunto de atributos ideal é aquele cujos atributos possuem um

alto grau de correlação com o atributo classe e uma inter-correlação baixa (Hall,

1999). Deve-se, portanto, maximizar a correlação dos atributos com o atributo classe

e minimizar a inter-correlação entre eles:

( 4.1)

e

( 4.2)

onde é um operador que mede a correlação entre dois atributos, é um atributo

qualquer e é o atributo classe.

Os algoritmos para a seleção de atributos buscam identificar no conjunto de

atributos um subconjunto de atributos relevantes e não-redundantes. Segundo Lan-

gley (1994c), existem quatro operações básicas que afetam a natureza desta busca:

1. Ponto de partida (ver Figura 4.1). A Seleção de um subconjunto inicial de atri-

butos como ponto de partida pode afetar a eficiência da pesquisa. Uma opção

é começar com nenhum atributo e sucessivamente adicioná-los. Neste caso,

a pesquisa segue naturalmente através do espaço de busca (forward through

the search space) (Langley, 1994c). Por outro lado, a pesquisa pode começar

com todos os atributos e, sucessivamente, removê-los. Neste caso, a pesqui-

sa é dita ser retrógrada através do espaço de busca (backward through the

search space) (Langley, 1994c). Outra alternativa é começar em algum lugar

no meio do espaço de busca e passar para o exterior a partir deste ponto.

2. Organização da pesquisa (Langley, 1994c). Uma busca exaustiva pelo espa-

ço de atributos é computacionalmente caro (ver Figura 4.1). Se inicialmente

existir atributos, então existem subconjuntos possíveis. Estratégias de

busca heurística são mais viáveis computacionalmente do que os exaustivos,

embora eles não garantam encontrar sempre um subconjunto ótimo de atribu-

tos.


3. Estratégia de avaliação. Como os subconjuntos de atributos são avaliados é o

principal fator dos algoritmos de seleção de atributos. Um paradigma chama-

do de filtro (Kohavi & John, 1996; Kohavi, 1995) funciona independente de

qualquer algoritmo de aprendizado; atributos indesejáveis são filtrados antes

do inicio da aprendizagem. Estes algoritmos usam heurísticas baseadas em

características gerais dos dados - ao invés de algoritmos de aprendizagem -

para avaliar os subconjuntos de atributos (Hall, 1999).

4. Critério de parada. Dependendo da estratégia de avaliação, um algoritmo que

seleciona atributos pode parar de adicionar ou remover atributos quando ne-

nhuma das alternativas melhora o desempenho do algoritmo de aprendiza-

gem. Alternativamente, o algoritmo poderá continuar a rever os subconjuntos

de atributos, enquanto não for alcançado um desempenho estabelecido pre-

viamente. Outra opção poderia ser a de continuar gerando subconjuntos de

atributos até atingir o extremo oposto do espaço de busca e em seguida, es-

colher o melhor (Langley, 1994c).

4.1.1 LVF - Las Vegas Filter

Las Vegas é um algoritmo aleatório que sempre retorna os resultados corretos, ou

informa sobre uma possível falha (Liu & Setiono, 1996). Em outras palavras, o algo-

ritmo Las Vegas não se arrisca com a veracidade dos resultados; ele só arrisca nos

recursos utilizados para a computação dos resultados (a casa sempre vence). Os

algoritmos Las Vegas usam a aleatoriedade para guiar sua busca de tal forma que a

solução correta é sempre garantida mesmo quando as piores escolhas são feitas

(Brassard & Bratley, 1996).

O algoritmo LVF (Las Vegas Filter) é uma variação do algoritmo Las Vegas

para a seleção de atributos (Liu & Setiono, 1996). Seu funcionamento é descrito a

seguir: considerando um conjunto de dados que possuam atributos, o algoritmo

LVF deve gerar um subconjunto aleatório de atributos, , a cada ciclo de execução

do algoritmo. Se o número de atributos ( ) do subconjunto de atributos, , é menor

que a quantidade de atributos do subconjunto ( ), então os dados ( ) que

possuem os atributos selecionados em são checados de acordo com o critério de

inconsistência. Se a taxa de inconsistência é menor que , então .


O critério de inconsistência é a principal componente do algoritmo LVF (Liu &

Setiono, 1996). O critério indica se o conjunto de atributos reduzidos pode ser aceito.

Isto é, quando a taxa de inconsistência está abaixo de um valor especificado previ-

amente. A taxa de inconsistência é calculada em um processo de três passos. Pri-

meiro, uma contagem dos padrões inconsistentes é realizada. Se dois padrões com-

binam, exceto pelo rótulo da classe, estes padrões são considerados inconsistentes.

Os padrões inconsistentes devem ser agrupados por suas respectivas clas-

ses. Após o agrupamento, deve-se contar separadamente a quantidade de padrões

inconsistentes em cada grupo. O total de padrões inconsistentes será a soma de

todas as instâncias inconsistentes. Por exemplo, para um subconjunto de atributos

selecionados aleatoriamente de um conjunto de treinamento que possui 3 classes,

onde a classe 1 tem padrões inconsistentes, a classe 2 tem padrões inconsis-

tentes e a classe 3 tem padrões inconsistentes, o total de padrões inconsistentes

( ) será .

No segundo passo determina-se a inconsistência do subconjunto de atributos

escolhido. Esta inconsistência é calculada da seguinte forma. Subtrai do total de pa-

drões inconsistentes ( ) o grupo de classe que obteve o maior número de padrões

inconsistentes, i.e., . No terceiro passo deve-se calcular a taxa

de inconsistência definida por:

Liu e Setiono (1996) utilizaram o algoritmo LVF em dois problemas de alta di-

mensionalidade – o primeiro tinha 65.000 instâncias descritas por 59 atributos; o se-

gundo tinha 5.909 instâncias descritas por 81 atributos. Segundo os autores, o algo-

ritmo LVF foi capaz de reduzir o número de atributos em ambos os problemas em

mais que a metade. Os autores também relatam que, devido à natureza aleatória do

algoritmo, quanto maior o valor do parâmetro MAX melhor serão os resultados obti-

dos.

As três principais vantagens do algoritmo LVF, são:

1. Simples de implementar;

2. Eficiente, isto é, rápido em obter o resultado;

3. Resultado não é afetado por algoritmos de aprendizagem;


O Algoritmo 4.1 mostra a implementação do algoritmo LVF.

Algoritmo 4.1 LVF (Las Vegas Filter)

A principal desvantagem do algoritmo LVF é a impossibilidade do seu uso em

problemas que apresentem variáveis contínuas. No entanto, esta desvantagem pode

ser eliminada aplicando algoritmos que discretizem as variáveis contínuas (Fayyad &

Irani, 1993; Kononenko, 1995).

Um problema em potencial a respeito da utilização da inconsistência como cri-

tério para selecionar atributos é que apenas um atributo sozinho pode garantir que

não exista inconsistência nos dados. Um exemplo deste tipo de atributo é o CPF.

Segundo Liu e Setiono (1996), este problema pode ser resolvido deixando este atri-

buto fora do processo de seleção de atributos.

Entrada: – Número de tentativas,

– Conjunto de instâncias,

– Número de atributos,

– Taxa de inconsistência mínima permitida

Saída: conjunto de atributos que satisfazem o critério de inconsistência

inicio:

para até faça

;

;

se então

se então

;

;

;

senão ( ) e ( ) então

;

fim

fim


4.1.2 Taxa de Ganho

Para selecionar as variáveis mais relevantes é possível utilizar a taxa de ganho (Ga-

in Ratio) de cada variável, mas para isto antes é necessário calcular o ganho de in-

formação. O uso do ganho de informação como medida para estimar a qualidade

dos atributos foi primeiramente proposto por Hunt e colegas (1966) e depois por

Quinlan (1986) para construir árvores de decisão. Esta medida é baseada no traba-

lho pioneiro de Claude Shannon (1948) sobre a teoria da informação que estuda o

valor, ou o “conteúdo da informação”, das mensagens (Han & Kamber, 2006). A E-

quação 4.3 mostra como calcular o ganho de informação de um atributo do conjun-

to de instâncias .

( 4.3)

onde é a quantidade de informação necessária para identificar a classe de

uma instância em , é o conjunto de todos os possíveis valores para o

atributo , é um subconjunto de cujo atributo possui valor , é a

quantidade de instâncias. A entropia é calculada pela equação definida por:

( 4.4)

onde é a quantidade de classes em , é a probabilidade de uma instância em

pertencer a classe e é estimada por

.

A taxa de ganho aplica uma normalização ao ganho de informação utilizando

a informação de separação (SplitInfo) similar a Equação 4.4 da entropia:

( 4.5)

onde a única diferença entre as Equações 4.4 e 4.5 é o somatório. A taxa de ganho

finalmente é calculada por:

( 4.6)


O calculo da taxa de ganho não elimina as variáveis menos relevantes, ao

invés disto, apenas associa um valor que representa a capacidade da variável em

particionar as instâncias de segundo suas respectivas classes. Fica a cargo do

usuário decidir quais variáveis devem ser eliminadas. Geralmente as variáveis elimi-

nadas são as que possuem o menor ganho de informação. Nesta técnica, assim

como no algoritmo LVF, não é possível utilizá-la em problemas que possuam atribu-

tos contínuos. No entanto, esta limitação pode ser eliminada aplicando algoritmos

que discretizem as variáveis contínuas. Outra desvantagem desta medida é a im-

possibilidade de detectar atributos redundantes.

4.1.3 Regressão Linear e o Coeficiente de Correlação

A regressão linear é um método para se estimar um valor esperado de uma variável

y, dados os valores de outra variável x (Han & Kamber, 2006). A regressão é cha-

mada de linear por considerar que a relação entre as variáveis é dada por uma fun-

ção linear. Se a distribuição dos valores de x e y puder ser representada por uma

função linear, diz-se que estas duas variáveis estão correlacionadas ou que existe

uma relação entre elas. A função linear que descreve o comportamento dos dados

pode ser obtida através das seguintes equações:

( 4.7)

e

( 4.8)

onde é o tamanho da amostra que consiste no par , e são os coeficientes

da reta e, e são as médias das variáveis e , respectivamente. Finalmente, a

reta pode ser obtida substituindo os valores obtidos de e em:

( 4.9)

Determinar a correlação existente entre duas variáveis pode ser útil para de-

terminar e avaliar a relação existente entre duas variáveis. A correlação pode ser

positiva ou negativa. Na correlação positiva as variáveis x e y crescem no mesmo

sentido, i.e., se x cresce, y também tende a crescer. Já na correlação negativa as

variáveis x e y crescem em sentido contrário, i.e., se x cresce, y decresce. Quanto

4.2 Seleção de Ações 47

maior o valor absoluto da correlação entre as variáveis maior é a redundância exis-

tente entre elas. O coeficiente de correlação é uma medida que quantifica a similari-

dade entre duas grandezas não determinísticas e pode ser calculado pela equação

abaixo:

( 4.10)

onde é o coeficiente de correlação, é o tamanho da amostra e, e são as

grandezas entre as quais se deseja calcular o coeficiente de correlação.

4.2 Seleção de Ações

A técnica de mineração de dados proposta para a seleção de ações se baseia em

duas medidas conhecidas como: suporte e confiança. Estas medidas são normal-

mente utilizadas para minerar padrões freqüentes de um banco de dados, com o

objetivo de criar regras de associação ou de classificação (Han & Kamber, 2006).

Neste trabalho estas duas medidas são utilizadas para medir o grau de utilização e

importância de cada ação para o sucesso do agente em realizar o drible: se uma

ação é freqüentemente utilizada e a ocorrência desta ação nos episódios de sucesso

é baixa então esta ação é removida. O cálculo do suporte mede a freqüência de uso

de uma ação . A Equação 4.11 mostra como calculá-lo.

( 4.11)

onde é frequência em que a ação é realizada pelo agente e

é a contagem de todas as ações realizadas pelo agente.

A segunda medida, confiança, informa o quanto uma ação é importante para

o sucesso do drible e é definida por:

( 4.12)

onde é a freqüência em que a ação acontece quando o drible é reali-

zado com sucesso ( ) pelo agente e é a frequência em que a ação é rea-

4.3 Aprendizagem por Reforço e a Mineração de Dados 48

lizada pelo agente. Então, se e então a

ação é removida.

O uso do suporte evita eliminar ações nos casos em que a medida de confi-

ança não é conclusiva. Por exemplo, sem o uso do suporte, uma ação que foi utili-

zada uma única vez e que participou de um episódio de insucesso teria confiança de

0%. No entanto, tirar conclusões da relevância de uma ação com apenas um exem-

plo do seu uso não é confiável. O suporte evita que casos como estes ocorram.

4.3 Aprendizagem por Reforço e a Mineração de Dados

É comum distinguir três categorias de métodos de aprendizagem, são eles: aprendi-

zagem supervisionada, aprendizagem não-supervisionada e aprendizagem por re-

forço. Normalmente os métodos da aprendizagem supervisionada são os mais utili-

zados na mineração de dados (Cohen & Maimon, 2005), portanto, a relação entre a

aprendizagem supervisionada e a aprendizagem por reforço é exemplificada a se-

guir. Por exemplo, considere um algoritmo de aprendizagem que precise extrair um

modelo de resposta para diversas situações diferentes. No aprendizado supervisio-

nado o algoritmo contará com um conjunto de observações rotuladas por um profes-

sor (ou oráculo). O rótulo de cada observação é considerado pelo agente como a

resposta desejada da situação, que é dada pelas variáveis desta observação.

Na aprendizagem por reforço, o privilégio de se ter um professor não é possí-

vel. Em vez disto, o algoritmo vê as situações (estados), escolhe as respostas (a-

ções) de forma autônoma e obtém recompensas de um crítico que indica o quão boa

foram as ações escolhidas (Cohen & Maimon, 2005). As variáveis que compõem a

observação do ambiente são as mesmas em ambas as abordagens (Cohen &

Maimon, 2005).

De acordo com Cohen e Maimon (2005), as ações tomadas pelo agente po-

dem ser consideradas as respostas desejadas utilizadas na aprendizagem supervi-

sionada. No entanto, estas respostas somente são conhecidas após a interação do

agente com o ambiente. Contudo, se o treinamento do agente for armazenado em

um banco de dados, na forma estado-ação, é possível utilizar estes dados para o

treinamento de um modelo da aprendizagem supervisionada.


O problema desta abordagem é que nem sempre todas as ações tomadas pe-

lo agente são desejáveis - alguma ação pode ter ocasionado ao agente não atingir

seus objetivos. Ainda é desconhecido um meio para identificar as ações, realizadas

em um episódio, que não contribuíram para o agente alcançar seus objetivos. Neste

trabalho, o foco é propor um meio para selecionar as ações mais relevantes (Seção

4.2).

Para a seleção das variáveis mais relevantes pretende-se rotular cada estado

com a respectiva ação realizada pelo agente. Desta forma é obtido o mapeamento

de toda a política do agente. A seleção realizada desta forma permite a identificação

das variáveis que influenciam na decisão do agente (ações realizadas). Esta sele-

ção, porém, é problemática em ambientes da aprendizagem por reforço, pois no iní-

cio do aprendizado as ações têm a mesma probabilidade de serem selecionadas.

Outra característica que torna difícil a aplicação desta seleção é a possibilidade de o

agente executar ações aleatórias durante todo o treinamento. Para solucionar estes

problemas as ações aleatórias não devem ser armazenadas no banco de dados e os

dados de treinamento utilizados devem originar-se dos episódios em que o treina-

mento do agente começa a convergir.

O objetivo desta seleção é saber quais variáveis variam sistematicamente de

acordo com o atributo classe. De acordo com Gennari et al. (1989), em ambientes

da aprendizagem supervisionada uma variável é considerada relevante se varia sis-

tematicamente de acordo com o atributo classe. Esta afirmação leva às seguintes

hipóteses nos ambientes da aprendizagem por reforço:

Se uma variável tem alto grau de correlação com o atributo classe, então esta variá-

vel é uma boa candidata para determinar a ação do agente.

e

Se uma variável tem baixo grau de correlação com o atributo classe, então

esta variável é uma boa candidata para ser removida.

Espera-se que se uma variável não é relevante para um política , também

seja irrelevante para uma outra política , onde é melhor que . Caso isto não

seja verdade, o desempenho do agente não irá aumentar.


O esquema da Figura 4.2 sugere como o armazenamento dos dados do trei-

namento do agente deve ser feito. As tabelas Resultado e ResultadoTemAções

são as que armazenam os dados de treinamento e que possibilitam o agrupamento

destas ações em episódios. A Subseção 4.3.1 dá uma breve descrição das tabelas e

campos do esquema de armazenamento. A Subseção 4.3.1 mostra como a etapa de

armazenamento e seleção dos dados no esquema deve ser realizada.

4.3.1 Armazenamento e Seleção dos dados

Esta seção apresenta uma sugestão para o armazenamento do treinamento do a-

gente. As tabelas e os principais campos do esquema de armazenamento represen-

tados pela Figura 4.2 são descritos a seguir:

1. Tabela Resultado: tabela que armazena os dados gerais de um episódio. Esta

tabela tem relacionamento de muitos para um com a tabela Experimento e

de um para muitos com a tabela ResultadoTemAções. Neste caso, um resul-

tado faz parte de somente um único experimento e para cada resultado há

uma seqüência de ações armazenada na tabela ResultadoTemAções.

campo episódio: número do episódio.

campo execução: número da repetição do experimento.

campo sucesso: indica se o agente conseguiu realizar o drible. Este cam-

po deve possuir os valores “S” ou “N” correspondendo a sucesso e falha

na realização do drible, respectivamente.

campo janela: indica os episódios que fazem parte da mesma janela de

tempo.

2. Tabela ResultadoTemAções: tabela que armazena todas as variáveis do am-

biente e as ações realizadas pelo agente a cada instante de tempo. Esta ta-

bela tem relacionamento de muitos para um com a tabela Resultado e de

muitos para um com a tabela Ação.

campo número: instante do tempo.


3. Tabela ação: tabela que armazena todas as possíveis ações do agente. Esta

tabela mantém uma descrição do código de todas ações.

4. Tabela experimento: tabela que armazena os dados gerais de um experimen-

to.

campo tamModelo: quantidade de memória utilizada pelo modelo.

Figura 4.2 Esquema Snowflake de armazenamento do treinamento do agen-

te. Os Dados de treinamento estão armazenados em duas tabelas principais:

Resultado e ResultadoTemAção.

52

Capítulo 5

Experimentos e Análise Estatística dos Dados

Os experimentos apresentados neste capítulo foram divididos em cinco etapas. A

primeira etapa (Seção 5.1) realiza uma busca experimental pelos parâmetros do

modelo de aprendizado.

Determinado os melhores parâmetros de acordo com a distribuição da fre-

qüência relativa de sucesso no drible, a segunda etapa (Seção 5.2) identifica e sele-

ciona os atributos mais relevantes utilizando os algoritmos apresentados nas Seções

4.1.1, 4.1.2 e 4.1.3 do Capítulo 4. O armazenamento e seleção destes dados foram

realizadas conforme descrito na Seção 4.3.

Os experimentos realizados na terceira etapa (Seção 5.3) identificam e sele-

cionam as melhores ações utilizando a métrica apresentada na Seção 4.2 do Capítu-

lo 4. Após determinar os melhores atributos e ações do problema, a quarta etapa

(Seção 5.4) combina as melhores ações e variáveis identificadas e um novo treina-

mento é realizado. A última etapa (Seção 5.5) avalia a qualidade do drible e valida o

modelo com o teste do agente.

5.1 Treinamento do Agente

O treinamento do agente foi realizado utilizando o algoritmo combinado

com a técnica de tile-coding. O algoritmo de aprendizado direciona o agen-

te para que obtenha uma maior recompensa ao longo do tempo enquanto que a téc-

nica de tile-coding permite manter as estimativas de recompensas como uma função

parametrizada. A técnica de tile-coding também permitirá ao agente generalização

que é importante em ambientes como o do futebol de robôs onde não é possível visi-

tar todos os possíveis estados do ambiente.

Para o problema abordado, cada variável possuiu tilings de uma dimensão.

O tamanho definido para cada tile foi determinado de acordo com o tipo da variável.

5.1 Treinamento do Agente 53

Para as variáveis que representam velocidade, ângulo ou a distância os tiles tiveram

tamanhos 0.2, 5 e 2, respectivamente. Estes valores foram retirados do trabalho de

Stone e Sutton (2001).

Uma das tarefas do projetista de um modelo computacional é definir quais se-

rão os valores dos parâmetros. Estes valores devem ser escolhidos cuidadosamen-

te, pois influenciam no desempenho do modelo na fase de aprendizagem. O modelo

utilizado possui cinco parâmetros que afetam no desempenho do aprendizado do

agente, são eles:

1. Taxa de aprendizado (alpha) – Este parâmetro deve ter valores pequenos pa-

ra que o modelo possa captar variações temporais. Segundo Sutton e Barto

(1998), é garantido convergência para uma política ótima se este parâmetro

decair com o tempo.

2. Desconto (gamma) – O desconto determina o interesse do agente pelas re-

compensas futuras. Quanto mais gamma se aproxima de zero o agente torna-

se mais oportunista interessando-se mais pelas recompensas imediatas.

3. E – Parâmetro que define a probabilidade de o agente explorar ao invés de

seguir uma política determinística.

4. Elegibility Trace (lambda) – Permite recompensar ou punir todo o percurso

que o agente seguiu até o fim do episódio. Uma parcela da recompensa rece-

bida no fim do episódio é retropropagada para seus estados antecessores. A

retropropagação do sinal de recompensa diminui à medida que o estado an-

tecessor se afasta do estado final. Este parâmetro determina o quanto o sinal

de recompensa deve diminuir em função do tempo.

5. Quantidade de Tilings – Este parâmetro determina como a experiência de um

estado deve ser compartilhada com seus vizinhos. A resolução deste compar-

tilhamento é determinada por este parâmetro.

Como não há formas teóricas de determinar qual o melhor ajuste para estes

parâmetros, o projetista do modelo deve ajustar estes valores experimentalmente,

por meio de um projeto experimental (Jain, 1991). Para acelerar este processo, op-

tou-se pelo projeto experimental linear, iniciando a busca com os valores de parâme-

tros que são freqüentemente encontrados na literatura. Os parâmetros iniciais utili-

zados como ponto de partida são apresentados na Tabela 5.1.

5.1 Treinamento do Agente 54

Tabela 5.1 Valores iniciais para os parâmetro do modelo.

Alpha Gamma E Lambda Tilings

0.007812 0.95 0.01 0.75 8

Tabela 5.2 Espaço de busca.

Parâmetro Valores

Alpha

(frações de potência de 2)

Gamma 0.95 (constante)

E 0, 0.01, 0.1

Lambda 0.5, 0.75, 0.90, 0.95

Tilings 2, 4, 8, 16, 32 (potências de 2)

Tabela 5.3 Variação inicial dos parâmetros do modelo.

Parâmetro Primeira Variação Segunda Variação

Alpha 0.015625 0.00390625

Gamma - -

E 0 0.1

Lambda 0.5 0.9

Tilings 4 16

A condução dos experimentos desta etapa se deu da seguinte forma. Com o

objetivo de determinar os melhores valores para os parâmetros do modelo, os parâ-

metros alpha, E, lambda e tilings foram fixados em seus valores iniciais e cada pa-

râmetro foi variado individualmente. Inicialmente foram determinadas duas variações

para cada um dos parâmetros do modelo (Tabela 5.3). Se em uma das variações for

possível notar um ganho no desempenho do aprendizado, então o parâmetro que

proporcionou este ganho deverá continuar variando em direção ao melhor resultado.

A busca conduzida desta forma pode falhar se os parâmetros tiverem uma forte re-

lação entre eles. Se isto for verdade, o ideal será fazer um projeto -fatorial ou -

fatorial no espaço de busca dos parâmetros, a custos bem mais elevados.

Para limitar o espaço de busca o parâmetro Alpha foi variado à potência ne-

gativa de dois e o parâmetro Tiling foi variado seguindo a recomendação de Albus


(1975) sendo atribuídos valores múltiplos de dois. Para o restante dos parâmetros os

valores atribuídos basearam-se nos mais comuns encontrados na literatura. A Tabe-

la 5.2 mostra o espaço de busca. O desempenho de uma execução será calculado a

cada 300 episódios utilizando a freqüência relativa de sucesso do agente no drible.

Para determinar o melhor parâmetro será levado em consideração o tempo de con-

vergência e o desempenho obtido pela área abaixo da curva.

5.2 Seleção de Atributos

Esta seção trata da construção do modelo no que se diz respeito à representação do

ambiente e escolha dos parâmetros do modelo de aprendizado. Todas as subseções

desta seção, exceto a Subseção 5.2.1, utilizam abordagens estatísticas para sele-

cionar quais variáveis devem ser escolhidas para representar o ambiente. Assume-

se que estas variáveis são as mais relevantes para o problema abordado. As variá-

veis que não fazem parte desta seleção são consideradas irrelevantes e devem ser

descartadas. Espera-se que, ao treinar o modelo sem estas variáveis, seja possível

observar um aumento ou uma variação irrelevante no desempenho do drible.

As subseções desta seção estão organizadas como segue. Na Subseção

5.2.1 o agente foi treinado com todas as variáveis descritas na Tabela 3.4. Os expe-

rimentos desta etapa devem ser armazenados em um banco de dados para que os

algoritmos de seleção utilizados nas subseções 5.2.1, 5.2.2 e 5.2.3 possam utilizá-

los para identificar as variáveis mais relevantes.

Algumas considerações sobre o modelo utilizado nas próximas seções são

feitas a seguir. Primeiro, o método de exploração é o mais utilizado na

literatura e foi utilizado para a construção dos modelos. Foi decido não utilizar o mé-

todo softmax, pois não havia motivos suficientes que justificassem a sua utilização

(ver Seção A.3 na página 103). A técnica de elegibility traces foi utilizada com repla-

cing traces. Segundo Sutton e Barto (1998), a utilização da técnica com accumula-

ting traces tem desempenho pior do que com replacing traces.

A segunda consideração a ser feita é com relação ao decaimento do valor do

parâmetro alpha. Para garantir a convergência do modelo é preciso que o parâmetro

alpha decaia com o tempo, sendo assim, optou-se por utilizar um decaimento expo-

nencial dado como segue:


( 5.1)

onde é o valor inicial de alpha, é número atual do episódio,

é a quantidade total de episódios e é uma constante que possibilita

determinar a velocidade de decaimento do parâmetro alpha. A Figura 5.1 mostra as

curvas de decaimento de alpha de acordo com a variação da constante para

e . Nos experimentos realizados utili-

zou-se .

Figura 5.1 Decaimento exponencial da taxa de aprendizado.

Para tornar os resultados mais confiáveis cada treinamento foi repetido dez

vezes. Em todos os casos um único treinamento com 4200 episódios durou cerca de

1 hora para concluir. O treinamento do agente ocorre em tempo real, portanto, a ca-

pacidade de processamento da CPU utilizada não tem influência no tempo de exe-

cução dos experimentos.

5.2.1 Treinamento com Todos os Atributos

As curvas de aprendizagem para as variações apresentadas na Tabela 5.3 são a-

presentadas nas Figuras 5.2, 5.3, 5.4, 5.5 e 5.6. Cada curva representa a média do


desempenho em 10 execuções. O objetivo da construção destes modelos foi unica-

mente para determinar os melhores valores dos parâmetros alpha, E, lambda e til-

lings.

A Figura 5.2 mostra os desempenhos do agente com a variação do parâmetro

alpha (taxa de aprendizado). Note que a figura mostra uma curva a mais além das

três já esperadas. Isto foi devido ao fato de o máximo desempenho do sistema ter

sido observado para o valor superior ao limite originalmente planejado para este pa-

râmetro nos experimentos sobre o aprendizado. A variação deste parâmetro termi-

nou com o valor 0.03125 em que foi observada uma redução no desempenho do

modelo se comparado com o aprendizado no qual alpha teve valor 0.015625. Apesar

de os resultados apresentados na Figura 5.2 não possibilitarem determinar a melhor

variação com confiança, porém, escolheu-se alpha = 0.015625, pois este valor apre-

sentou o melhor desempenho na maior parte do treinamento. Nota-se que quando

Alpha teve valor muito alto (0.03125) o desempenho do agente foi melhor no inicio,

mas devido às grandes alterações nos tiles, o desempenho do agente não teve a

mesma tendência que obteve no inicio do treinamento.

Figura 5.2 Curvas de desempenho (média de dez execuções) do agente com todas as variáveis, mudando apenas o parâmetro alpha (taxa de aprendizado).

As curvas de aprendizado para a variação do parâmetro E são apresentadas

na Figura 5.3. As curvas mostram que o agente obteve um melhor desempenho

quando E foi igual a zero, no entanto, a curva de aprendizado para E igual a 0.1 ob-


teve um resultado satisfatório com relação à curva anterior. Nota-se que no inicio do

aprendizado a exploração proporcionou uma aceleração no inicio do aprendizado,

mas após o episódio 2000 o treinamento aparenta convergir com apenas 30% de

sucesso. Contudo, tornar o agente guloso em relação à política (E = 0) pode fazer

com que apresente um desempenho pior em treinamentos com mais de 4200 episó-

dios, nestes casos o agente pode estar preso em alguma política sub-ótima o que

poderá resultar em uma convergência prematura. Neste caso optou-se em realizar

dois treinamentos, um para E igual a 0 e o outro para E igual a 0.01.

Figura 5.3 Curvas de desempenho (média de dez execuções) do agente com todas as variáveis, mudando apenas o parâmetro E.

A Figura 5.4 mostra as curvas de aprendizado de acordo com a variação do

parâmetro lambda. O aprendizado foi iniciado com lambda = 0.75 e, seguindo a es-

tratégia dos experimentos (ver Seção 5.1), o agente também foi treinado para 0.5 e

0.9. Foi notado um aumento no desempenho do agente quando o valor de lambda

aumentou para 0.9 sugerindo a variação deste parâmetro mais uma vez nesta dire-

ção. Sendo assim, o agente foi treinado com lambda = 0.95 e mais uma vez foi no-

tado um aumento no desempenho do drible. O agente foi treinado uma última vez

sendo lambda = 1 onde foi observada uma redução do desempenho. Esta redução

no desempenho deve-se ao retorno total da recompensa recebida, no fim do episó-

dio, para as ações passadas (ver Subseção 2.1.1). Neste caso, ainda que o algorit-


mo tenha características temporais, a aproximação de é idêntica ao algoritmo

Monte Carlo (Sutton & Barto, 1998).

Figura 5.4 Curvas de desempenho (média de dez execuções) do agente com todas as variáveis, mudando apenas o parâmetro lambda (elegibility traces).

Figura 5.5 Curvas de desempenho (média de dez execuções) do agente com todas as variáveis, mudando apenas a quantidade de tilings.

A Figura 5.5 mostra as curvas de aprendizado para a variação do parâmetro

tiling. As duas variações iniciais (ver Tabela 5.3) para o parâmetro tilings não permiti-

ram identificar com certeza a curva que apresentou o melhor desempenho. Sendo

assim, decidiu-se variar este parâmetro mais uma vez em ambas as direções do es-

paço de busca, com tilings igual a 2 e 16. Analisando as duas curvas adicionais, po-


de-se notar que o desempenho com tilings igual a 2 foi superior aos demais. Isto a-

conteceu devido a baixa resolução obtida com apenas 2 tiles (ver Seção 2.3). Desta

forma, o desempenho do agente não foi afetado pelas variações estocásticas do

ambiente.

Figura 5.6 Curvas de desempenho (média de dez execuções) do agente com todas

as variáveis e com a combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e quantidade de tilings.

De acordo com as Figuras 5.2, 5.3, 5.4 e 5.5 os melhores valores para os pa-

râmetros alpha, E, lambda e tilings foram respectivamente, 0.015625, 0, 0.95 e 2. A

Figura 5.6 mostra o treinamento do agente com a combinação dos melhores valores

para os parâmetros retirados dos treinamentos anteriores.

O modelo treinado com utilizou em média 17.7MB de espaço em memória.

Com o desempenho do agente é pior até o episódio 8000, o desempenho

do agente nos episódios seguintes tem desempenho similar ao do treinamento com

. O modelo treinado com utilizou em média 18.1MB de espaço em

memória. Este último modelo consumiu 409KB a mais que o modelo construído com

. Em termos de tempo de convergência, o modelo com foi superior ao

modelo construído com .

Treinamento do Agente(Melhores Variações)

E=0

E=0.010 2000 4000 6000 8000 10000 12000

Episódio

0

10

20

30

40

50

De

se

mp

enho


5.2.1.1 Análise da Correlação dos Atributos

Para facilitar a análise da correlação entre as variáveis do problema, o treinamento

da Figura 5.6 foi armazenado em um banco de dados na forma do esquema apre-

sentado na Figura 4.2 (pagina 51). A quantidade de registros existentes no banco de

dados foi de 670826 para o treinamento com todas as variáveis e .

A Figura 5.7 mostra a correlação das variáveis que obtiveram o coeficiente de

correlação maior que sete décimos. No inicio do treinamento o agente ainda não tem

consciência de suas ações podendo perder o controle da bola chutando-a para lon-

ge. Este comportamento explica a linha vertical formada nas Figura 5.7c-f.

De acordo com a Figura 5.7 as variáveis oBDist, bDist, oSD, aSD, aPosX,

bPosX, oPosX, aPosY, bPosY e oPosY tiveram grau de correlação maior que oito

décimos. As demais variáveis não apresentadas na Figura 5.7 tiveram correlação

menor que 0.65. A correlação entre oBDist e bDist (Figura 5.7a) sugere que uma das

variáveis seja removida, também é sugerido o mesmo entre oSD e aSD (Figura

5.7b). Entre as variáveis aPosX, bPosX, oPosX, aPosY, bPosY e oPosY (Figura

5.7c-h) foi possível observar o maior coeficiente de correlação com aproximadamen-

te 0.99.

Medir a correlação das variáveis é uma técnica útil para verificar se existe re-

dundância entre as mesmas, quando elas são de natureza numérica. Variáveis re-

dundantes podem aumentar a complexidade do modelo e até reduzir o seu desem-

penho. No entanto, deve-se ter cuidado com a remoção de uma variável correlacio-

nada. Apesar de oBDist e bDist terem um alto grau de correlação entre si, o contexto

destas duas variáveis são diferentes. A variável oBDist é a distância na qual o opo-

nente se encontra da bola e, bDist é a distância na qual o agente se encontra da

bola.

Note que no inicio da reta de regressão linear da Figura 5.7a a distribuição

dos dados não é linear. No inicio de todo episódio o oponente inicia distante da bola

e o agente com a bola junto ao seu corpo (ver Seção 3.3 na página 30). Neste ponto

estas duas variáveis têm valores e funções totalmente diferentes. Naturalmente, a-

pós alguns instantes de tempo os valores destas duas variáveis estarão bem próxi-

mos, pois o agente se aproxima com a bola do oponente para realizar o drible e o

oponente se aproxima da bola para tomá-la, ambos têm o mesmo objetivo que é ter

a posse de bola.


Figura 5.7 Correlação entre as variáveis com coeficiente maior que sete décimos. Dados retirados do treinamento com todas as variáveis.

Variável bDist x oBDistcorr = 0,874527

-2 0 2 4 6 8 10 12 14 16 18 20 22 24 26

oBDist

-2

0

2

4

6

8

10

12

14

16

18

20

22

24

26

bD

ist

(a) Variável aSD x oSDcorr = 0,985993

-5 0 5 10 15 20 25 30 35 40 45

oSD

-5

0

5

10

15

20

25

30

35

40

45

aS

D

(b)

Variável aPosX x bPosXcorr = 0,981928

-60 -40 -20 0 20 40 60

bPosX

-50

-40

-30

-20

-10

0

10

20

30

40

50

aP

osX

(c) Variável oPosX x bPosXcorr = 0,974656

-60 -40 -20 0 20 40 60

bPosX

-50

-40

-30

-20

-10

0

10

20

30

40

50

oP

osX

(d)

Variável aPosY x bPosYcorr = 0,993429

-40 -30 -20 -10 0 10 20 30 40

bPosY

-40

-30

-20

-10

0

10

20

30

40

aP

osY

(e) Variável oPosY x bPosYcorr = 0,977967

-40 -30 -20 -10 0 10 20 30 40

bPosY

-40

-30

-20

-10

0

10

20

30

40

oP

osY

(f)

Variável aPosX x oPosXcorr = 0,993429

-50 -40 -30 -20 -10 0 10 20 30 40 50

oPosX

-50

-40

-30

-20

-10

0

10

20

30

40

50

aP

osX

(g) Variável aPosY x oPosYcorr = 0,994257

-40 -30 -20 -10 0 10 20 30 40

oPosY

-40

-30

-20

-10

0

10

20

30

40

aP

osY

(h)


A importância da variável bDist é clara: o agente a todo o momento utiliza es-

ta variável para saber se está a uma distância mínima para realizar um chute, caso

não esteja, o agente deve se aproximar da bola. Mas nada se sabe da importância

do restante das variáveis correlacionadas. A utilização das abordagens estatísticas

para a seleção de atributos descritas na próxima seção pode ajudar a decidir quais

variáveis redundantes devem ser removidas e se realmente devem ser removidas.

5.2.2 Taxa de Ganho

O primeiro algoritmo utilizado para identificar as variáveis mais relevantes é a taxa

de ganho (ver Seção 4.1.2).

A Tabela 5.4 mostra as variáveis ordenadas pelo seu respectivo ganho. As

variáveis do topo da tabela são consideradas as mais relevantes, pois possuíram a

maior taxa de ganho. Conseqüentemente as que estão nas últimas linhas da tabela

são consideradas as menos relevantes.

As variáveis bPosX, bPosY, oPosY, aPosX, aPosY e oPosX obtiveram as

menores taxa de ganho e portanto foram removidas do aprendizado do agente. Visto

que a Figura 5.7 já sugeria sua remoção pela alta correlação existente entre elas.

Utilizando a taxa de ganho apenas confirmou-se a sua remoção.

É importante lembrar que a taxa de ganho não tem nenhuma relação com a

correlação entre as variáveis. Não é possível verificar a redundância existente entre

as variáveis utilizando a taxa de ganho. Isto pode ser notado comparando o ganho

das variáveis bDist, oBDist, aSA e oSA e o coeficiente de correlação da Figura 5.7.

É recomendável que apenas uma das duas variáveis correlacionadas permaneça

para a construção do modelo. Como não se sabe a importância das variáveis oB-

Dist, aSD e oSD decidiu-se remover as variáveis que tivessem a menor taxa de ga-

nho, neste caso as variáveis aSA e oBDist. Se o desempenho do agente no treina-

mento for menor do que o com todas as variáveis, então estas variáveis podem ter

alguma relevância e devem voltar a fazer parte do modelo.

Após a remoção das variáveis bPosX, bPosY, oPosY, aPosX, aPosY, oPosX,

aSD e oBDist restaram apenas 15 variáveis de um total de 23. Isto é, uma redução

de aproximadamente 35%.

O mesmo procedimento realizado na Seção 5.2.1 para encontrar os melhores

parâmetros será realizado novamente após a seleção de atributos. As Figuras 5.8,


5.9, 5.10 e 5.11 mostram o desempenho do agente de acordo com a variação dos

parâmetros alpha, E, lambda e tilings, respectivamente.

Tabela 5.4 Taxa de ganho para as variáveis do ambiente.

Variável Ganho

bDist 0,48

oBAngle 0,13

bVel 0,13

oDist 0,12

oVelY 0,11

bDir 0,11

oVelX 0,11

aVelY 0,11

oBDist 0,09

aVelX 0,09

oAngle 0,07

oSD 0,06

aSD 0,05

bAngle 0,05

aBodyA 0,05

oSA 0,05

aSA 0,04

bPosX 0,01

bPosY 0,01

oPosY 0,01

aPosX 0,01

aPosY 0,01

oPosX 0,00

O desempenho do agente variando o parâmetro alpha (ver Figura 5.8) apre-

sentou comportamento semelhante ao modelo com todas as variáveis. Com alpha

igual a 0.015625 foi possível observar o melhor desempenho entre as variações. O


valor deste parâmetro coincidentemente é o mesmo que o modelo com todas as va-

riáveis.

Figura 5.8 Curvas de desempenho (média de dez execuções) do agente mudando

apenas o parâmetro Alpha após a remoção das variáveis segundo a taxa de ganho.

Figura 5.9 Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro E após a remoção das variáveis segundo a taxa de ganho.

A Figura 5.9 mostra que o incentivo da exploração no modelo construído com

as variáveis relevantes selecionadas segundo a taxa de ganho e o grau de correla-

ção passou a proporcionar um aumento no desempenho do agente. Isto aconteceu

devido às variáveis irrelevantes já proporcionarem uma exploração natural, mas de


forma inadequada. Quando as variáveis irrelevantes foram removidas, o incentivo da

exploração permitiu ao agente explorar com mais consciência. Com foi

possível observar o melhor desempenho. No treinamento com todas as variáveis a

exploração não apresentou nenhum aumento no desempenho ou no tempo de con-

vergência do modelo.

A Figura 5.10 mostra as curvas de desempenho quando variado o parâmetro

lambda. Para este parâmetro o melhor desempenho do agente foi obtido quando

lambda foi igual a 0.75.


apenas o parâmetro Lambda após a remoção das variáveis segundo a taxa de ga-nho.

Figura 5.11 Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro Tilings após a remoção das variáveis segundo a taxa de ganho.


Com a variação do parâmetro tiling não foi possível observar nenhuma dife-

rença significativa no desempenho dos modelos apresentado na Figura 5.11. No en-

tanto, a curva de desempenho com tiling igual a 4 tem área maior que as outras cur-

vas no decorrer do aprendizado, sendo assim, optou-se em utilizar este valor para o

parâmetro tiling.

A Figura 5.12 mostra a curva de desempenho do agente na realização do dri-

ble. Os parâmetros alpha, E, lambda e tilings escolhidos para treinar o agente foram

0.015625, 0.01, 0.75 e 4, respectivamente. A remoção das variáveis irrelevantes

proporcionou uma estabilidade no treinamento do modelo fazendo com que o de-

sempenho do agente não oscilasse tanto quanto o modelo com todas as variáveis.

Figura 5.12 Curvas de desempenho (média de dez execuções) do agente com a

combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das variáveis irrelevantes de acordo com a taxa de ganho e a redundância (correlação).

Comparando a curva de aprendizado com as apresentadas na Subseção

5.2.1 percebe-se que o modelo construído com as variáveis selecionadas segundo a

taxa de ganho e a redundância converge com desempenho superior ao construído

com todas as variáveis (Figura 5.6). O modelo também apresentou uma aceleração

no aprendizado do agente. Se o treinamento fosse interrompido na metade do tem-


E=0

E=0.010 2000 4000 6000 8000 10000 12000

Episódio

0

10

20

30

40

50

60

De

se

mp

enh

o


po, i.e., quando completado 6000 episódios, seu desempenho ainda seria superior

ao desempenho do modelo com todas variáveis construído em 12000 episódios.

O modelo com utilizou em média 2.15MB de espaço em memória. Com

o desempenho do agente até o episódio 1700 é muito próximo ao modelo

com , mas após o episódio 1700 o desempenho é pior. No final o modelo con-

verge com aproximadamente 50% de sucesso contra 57% do modelo com . O

modelo treinado com utilizou em média 1.7MB de espaço em memória. Es-

te último modelo consumiu 460KB a menos que o modelo construído com .

5.2.3 Las Vegas Filter

Uma vantagem clara do algoritmo LVF em relação à taxa de ganho é a remoção au-

tomática das variáveis irrelevantes. A taxa de ganho apenas avalia a capacidade de

uma única variável em particionar os dados. No entanto, tem-se uma quantidade

muito maior de subconjuntos de atributos para avaliar. Ao invés de analisar individu-

almente todas as variáveis de um problema o algoritmo LVF analisa os possíveis

subconjuntos que as variáveis podem formar. É claro que este tipo de análise tem

um custo, mas o algoritmo tem-se mostrado eficiente em termos de tempo de pro-

cessamento e resultados (Liu & Setiono, 1996).

As variáveis bPosX, bPosY, oPosY, aPosX, aPosY e oPosX foram eliminadas

antes da execução do algoritmo, pois possuem um alto grau de correlacionamento e

uma baixa taxa de ganho. Teoricamente estas variáveis não devem trazer nenhuma

informação útil para o agente. Deixá-las no processo de aprendizado do agente só

limitaria a realizar o drible em uma pequena região do campo. As variáveis oBAngle,

oSD e aSD não foram eliminadas antes da execução do algoritmo, foi deixado a car-

go do algoritmo determinar a relevância destas variáveis.

O algoritmo foi iniciado com um subconjunto de variáveis selecionadas aleato-

riamente e com MAX igual a 1310 (1% do espaço de busca). Foram observadas as

taxas de inconsistência e escolhido o subconjunto de atributos no qual foi possível

observar a menor taxa de inconsistência. Após a execução do algoritmo, o conjunto

de variáveis selecionado foi: oVelY, bDist, oDist, oBDist, aSD, oSD, bAngle, oAngle,

oSA e aBodyA. As seguintes variáveis foram removidas: aVelX, aVelY, bVel, oVelX,

oBAngle, aSA, bDir. A inconsistência das variáveis selecionadas foi de 0.00929. O


algoritmo LVF não removeu nenhuma das 4 variáveis (bDist, oBDist, aSD, oSD) cor-

relacionadas no momento de sua execução. Apesar de estas variáveis apresenta-

rem um grau de correlação alto, em certas regiões do espaço de estados elas apre-

sentam funções totalmente diferentes.

As figuras abaixo mostram as curvas de aprendizado do agente de acordo

com a variação dos valores dos parâmetros alpha, E, lambda e tilings. As curvas de

desempenho para a variação do parâmetro alpha é apresentado na Figura 5.13. Pa-

ra determinar o valor deste parâmetro foram necessárias mais duas variações além

das três planejadas inicialmente. Isto foi devido ao desempenho do modelo ter au-

mentado quando o valor do parâmetro alpha também aumentou. A variação termi-

nou quando observado uma redução no desempenho do aprendizado quando alpha

teve valor igual a 0.0625.

Figura 5.13 Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro alpha após a remoção das variáveis irrelevantes pelo algoritmo LVF.

A Figura 5.14 mostra o desempenho do modelo quando variado o parâmetro

E. Percebe-se que com o desempenho do modelo é superior aos demais

modelos até o episódio 3300. O modelo construído com é superior a partir do

episódio 3200. A exploração permitiu ao agente encontrar uma sub-política ótima

mais rápido que o modelo com E=0, mas o agente continua a explorar o que impede

que desempenho continue a aumentar. Valores muito altos para o parâmetro E im-


possibilitaram ao agente permanecer em uma política provocando uma convergência

prematura.


apenas o parâmetro E após a remoção das variáveis irrelevantes pelo algoritmo LVF.

Com a variação do parâmetro lambda percebe-se uma influência maior no

desempenho do modelo. A Figura 5.15 mostra as variações do parâmetro lambda.

Nenhuma das três variações iniciais (0.5, 0.75 e 0.9) apresentou diferença no de-

sempenho. Portanto, foi preciso variar este parâmetro mais duas vezes com lambda

igual a 0.95 e 1. O modelo com lambda igual a 0.95 apresentou desempenho melhor

que as demais variações. Com lambda igual a 0.95 permitiu acelerar o aprendizado

culpado ações passadas pelo insucesso do agente no fim dos episódios. Isto possi-

bilitou que o agente não insistisse em executar estas ações com freqüência, pas-

sando a tentar o restante das ações.

A Figura 5.16 mostra as variações do parâmetro tiling. Nenhuma das três va-

riações iniciais (4, 8 e 16) apresentou diferença no desempenho. Sendo assim, o

parâmetro tiling foi variado em ambas às direções do espaço de busca (tiling=2 e

tiling=32).


Figura 5.15 Curvas de desempenho (média de dez execuções) do agente mudando apenas o parâmetro Lambda após a remoção das variáveis irrelevantes pelo algo-ritmo LVF.


apenas o parâmetro Tilings após a remoção das variáveis irrelevantes pelo algoritmo LVF.

A Figura 5.17 mostra o desempenho do agente na realização do drible. Se-

guindo a mesma estratégia dos experimentos anteriores, os parâmetros utilizados

para o modelo foram , , e . De acor-

do com a figura o desempenho do agente atinge convergência com 52% de suces-

so. Este modelo utilizou em média 882KB de espaço em memória. O desempenho


do modelo com está bem próximo ao com . O uso de memória do

modelo com foi de apenas 12KB a menos que o modelo com . A ace-

leração do aprendizado e o aumento do desempenho foram alcançados no modelo

construído com as variáveis selecionadas segundo o algoritmo LVF. Note que após

o episódio 6500 o desempenho do agente é superior ao do modelo construído com

todas as variáveis.

Figura 5.17 Curvas de desempenho (média de dez execuções) do agente com a

combinação dos melhores valores para os parâmetros gamma, alpha, E, lambda e tilings após a remoção das variáveis irrelevantes pelo algoritmo LVF.

5.3 Seleção de Ações

Nesta seção será apresentada a segunda etapa dos experimentos. Nas seções an-

teriores foram apresentadas algumas técnicas para a identificação das variáveis irre-

levantes e redundantes em ambientes da aprendizagem por reforço, agora pretende-

se estudar outro ponto importante da aprendizagem por reforço: o espaço de ações

do agente. Há varias razões que incentivam a seleção de ações. Assim como as va-

riáveis irrelevantes, as ações irrelevantes podem atrasar e até mesmo atrapalhar a

convergência do agente. Nesta seção será apresentado como as ações irrelevantes

para o agente podem ser identificadas e removidas para reduzir a complexidade do


E=0

E=0.010 2000 4000 6000 8000 10000 12000

Episódio

0

10

20

30

40

50

60

De

se

mp

enh

o


modelo, acelerar o tempo de convergência e possivelmente obter um ganho no de-

sempenho do modelo.

Os experimentos desta seção iniciam analisando o suporte e confiança (Han

& Kamber, 2006) das regras induzidas sobre a presença das ações executadas pelo

agente nos treinamentos dos modelos anteriores. Serão usados, separadamente, os

dados coletados de todos os episódios das Figuras 5.6, 5.12 e 5.17. Neste estudo

não se pretende levar em consideração as probabilidades conjuntas de uma se-

qüência de ações realizadas em um episódio. Apesar de ser uma aproximação da

condição real, esta escolha evita a explosão das combinações possíveis e viabiliza

uma análise que, por mais simples que seja, agrega valor à solução do problema,

como será mostrado a seguir. As ações com maior participação em episódios de

sucesso serão consideradas relevantes e as com menor participação serão conside-

radas irrelevantes e deverão ser removidas dos próximos treinamentos. Espera-se

que sem estas ações o tempo de convergência dos modelos diminua, e que o de-

sempenho aumente.

5.3.1 Análise das Ações com Todos os Atributos

A primeira figura (Figura 5.18a-b) analisada mostra o nível de confiança das ações

para o treinamento com todas as variáveis. Nesta primeira figura percebe-se que

grande parte das ações não passa dos 20% de confiança caso a exploração não

seja incentivada, i.e, se . Isto significa que em 80% das ocorrências destas a-

ções estiveram em episódios de insucesso do agente em todo o treinamento. Algu-

mas ações não alcançam nem os 10%, talvez boa parte destas ações tenham resul-

tado no sucesso do agente por alguma falha do oponente ou até mesmo pelo acaso.

Ações com baixo nível de confiança são boas candidatas para serem removidas,

mas isto depende também do suporte que será analisado mais a frente. A explora-

ção proporcionou um aumento na confiança das ações como pode ser visto na Figu-

ra 5.18b.


Figura 5.18 Confiança das ações extraídas do treinamento do agente com todas as

variáveis para dois níveis de exploração.

A segunda figura (Figura 5.19a-b) mostra o suporte das ações. O suporte in-

dica a proporção da execução de uma ação em relação ao total de ações, indepen-

dente de estarem associadas a episódios de sucesso ou não e dos tipos de ação.

Analisando a figura do suporte percebe-se que a exploração deveria ser mais incen-

tivada ou que o treinamento devesse ter continuado além dos doze mil episódios. O

aumento do suporte quando incentivada a exploração não pode ser observado

quando o parâmetro E foi de 0 para 0.01. No entanto, a Figura 5.19b mostra uma

distribuição mais uniforme do suporte entre as ações com suporte abaixo de 0.2%.

Figura 5.19 Suporte das ações extraídas do treinamento do agente com todas as

variáveis para dois níveis de exploração.

Um dos grandes problemas da baixa exploração do espaço de ações do a-

gente deve-se à grande quantidade de ações. Executar todas estas ações em cada

subespaço do espaço de busca do agente é muito custoso. Se isto fosse realmente

necessário, o tempo de convergência do modelo iria aumentar consideravelmente,

provavelmente produzindo algum aumento no desempenho do agente. Contudo,

grande parte destas ações podem ser consideradas irrelevantes ou desnecessárias.


Eliminando as ações irrelevantes espera-se que o suporte se distribua nas demais

ações que não foram eliminadas.

5.3.2 Análise das Ações com Atributos Eliminados por Taxa de Ganho

Após a eliminação das variáveis irrelevantes pela Taxa de Ganho houve um cresci-

mento individual significativo no suporte de algumas ações (Figura 5.21a), mas tam-

bém proporcionou a redução do suporte em outras ações. Isto deve-se a aceleração

do aprendizado que a eliminação das variáveis pela taxa de ganho proporcionou. O

aumento do suporte de algumas ações indica que o agente pode ter encontrado a

política mais rápido que o modelo anterior, passando a executar estas ações com

mais freqüência. Isto explica a redução do suporte no restante das ações.

Figura 5.20 Confiança das ações extraídas do treinamento do agente após remoção das variáveis segundo a taxa de ganho para dois níveis de exploração.

Figura 5.21 Suporte das ações extraídas do treinamento do agente após remoção das variáveis segundo a taxa de ganho.

Houve uma redução na confiança destas ações (Figura 5.20a) e com a explo-

ração a redução foi maior, ao mesmo tempo em que o crescimento da confiança de


algumas ações aumentou drasticamente. Isto mostra que o agente passou a execu-

tar as ações relevantes com mais freqüência que os modelos anteriores que tinham

todas as variáveis. As variáveis irrelevantes limitaram o agente a um pequeno grupo

de ações.

5.3.3 Análise das Ações com Atributos Eliminados por LVF

A duas últimas figuras (Figuras 5.22 e 5.23) mostram a confiança e o suporte

do treinamento do agente após a remoção das variáveis irrelevantes pelo algoritmo

LVF. O uso do suporte está bem mais distribuído e as confianças das ações aumen-

taram. Isto mostra que o agente está mais consciente em suas ações.

Figura 5.22 Confiança das ações extraídas do treinamento do agente após a remo-ção das variáveis irrelevantes pelo algoritmo LVF para dois níveis de exploração.

Figura 5.23 Suporte das ações extraídas do treinamento do agente após a remoção das variáveis irrelevantes pelo algoritmo LVF para dois níveis de exploração.


5.3.4 Remoção das Ações nos Modelos Discutidos

A Tabela 5.5 mostra a quantidade de variáveis removidas em cada modelo para

e . Devido ao baixo suporte da maior parte das ações o parâmetro

não foi utilizado. A grande quantidade de exemplos armazenados na base de dados

(10 repetições do treinamento com doze mil episódios) permitiu utilizar a medida de

confiança com segurança, pois mesmo com o suporte muito baixo, as ações foram

executadas pelo menos 1000 vezes.

Tabela 5.5 Quantidade de variáveis removidas.

Modelo E Qtde de Ações

Removidas Qtde de Ações

Restantes

Modelo 1 (Todas as Variáveis)

0 37 76 15%

0.01 12 101

0 55 58 20%

0.01 26 87

0 71 42 30%

0.01 65 48

0 89 24 40%

0.01 85 28

Modelo 2 (LVF)

0 17 96 15%

0.01 17 96

0 27 86 20%

0.01 32 81

0 50 63 30%

0.01 70 43

0 71 42 40%

0.01 86 27

Modelo 3 (Taxa de Ganho)

0 31 82 15%

0.01 33 80

0 49 64 20%

0.01 58 55

0 82 31 30%

0.01 87 26

0 93 20 40%

0.01 96 17

A Figura 5.24a-d mostra as curvas de desempenho dos modelos construídos

apenas com as ações relevantes. A quantidade de ações utilizada em cada treina-

mento é apresentada na Tabela 5.5. No Modelo 3 foram removidas a maior quanti-

dade de ações, totalizando 93 e 96 ações para e , respectivamente.

Em seguida o Modelo 1 com 89 ações removidas para .


Na Figura 5.24a com igual a 15% não foi possível notar nenhum aumento

no desempenho em nenhuma das curvas de aprendizado do treinamento com todas

as variáveis. Para o modelo com E=0 construído com as variáveis selecionadas se-

gundo a taxa de ganho e a redundância nota-se uma aceleração no inicio do treina-

mento, mas o desempenho do modelo diminuiu aproximadamente 8% terminando o

treinamento com 50% de sucesso. Com E=0.01 o desempenho do modelo também

diminui aproximadamente 5%. O último modelo testado com foi o construí-

do com as variáveis selecionadas segundo o algoritmo LVF. Para ambos os modelos

construídos com E=0 e E=0.01 pode-se observar uma desaceleração no aprendiza-

do, mas a convergência ficou bem próxima ao modelo construído com todas as vari-

áveis.

Figura 5.24 Curvas de desempenho (média de dez execuções) de todas as aborda-

gens relativas as seleções de ações variando o parâmetro .

Na Figura 5.24b com igual a 20% foi possível notar um aumento de 5% no

desempenho do modelo construído com todas as variáveis para ambos valores do

Comparação do Treinamento(Theta=15%)

N/A E=0 N/A E=0.01 Tx. Ganho E=0 Tx. Ganho E=0.01 LVF E=0

LVF E=0.01

0 2000 4000 6000 8000 10000 12000

Episódio

0

5

10

15

20

25

30

35

40

45

50

55

De

se

mp

enh

o

(a) Comparação do Treinamento(Theta=20%)


LVF E=0.01

0 2000 4000 6000 8000 10000 12000

Episódio

0

5

10

15

20

25

30

35

40

45

50

55

De

se

mp

enh

o

(b)

Comparação do Treinamento(Theta=30%)


LVF E=0.01

0 2000 4000 6000 8000 10000 12000

Episódio

0

5

10

15

20

25

30

35

40

45

50

55

De

se

mp

enh

o

(c) Comparação do Treinamento(Theta=40%)


LVF E=0.01

0 2000 4000 6000 8000 10000 12000

Episodes

0

10

20

30

40

50

60

De

se

mp

enh

o

(d)


parâmetro de exploração (E=0 e E=0.01). As curvas de desempenho para E=0 e

E=0.01 do modelo construído segundo a taxa de ganho e a redundância tiveram de-

sempenho bem próximo durante todo o treinamento. Houve uma aceleração no ini-

cio do aprendizado se comparado com o modelo construído com todas as ações,

mas o desempenho diminui aproximadamente 8% quando E foi igual a zero e conti-

nuou o mesmo para E=0.01. Para o modelo construído com as variáveis seleciona-

das pelo algoritmo LVF o desempenho diminuiu 5% em ambas as curvas (E=0 e

E=0.01).

Na Figura 5.24c com igual a 30% o modelo construído com todas as variá-

veis e E=0 aumentou o desempenho em aproximadamente 5% se comparado com o

modelo com todas as ações. Com as ações selecionadas com igual a 20% o de-

sempenho foi próximo para este modelo. Para o modelo construído com as variáveis

selecionadas segundo a taxa de ganho e a redundância houve uma redução no de-

sempenho para ambas as curvas. O modelo construído com E=0 teve desempenho

de 45% enquanto que para E=0.01 o desempenho foi de aproximadamente 40%.

Com a seleção das ações para o modelo construído com as variáveis selecionadas

pelo algoritmo LVF, o desempenho com E=0 foi o mesmo desempenho do modelo

construído com todas as ações. Com E=0.01 o desempenho foi 10% menor que o

modelo construído com todas as ações.

A Figura 5.24d mostra as curvas de desempenho dos modelos construídos

com igual a 40%. O desempenho do modelo construído com todas as variáveis

obteve os melhores resultados quando foi igual a 30%. Com E=0 houve uma ace-

leração no desempenho do agente. O desempenho do modelo após 6000 episódios

atingiu aproximadamente 50% de sucesso. No fim do treinamento o modelo termi-

nou com aproximadamente 55% de sucesso. Com E=0.01 o modelo também apre-

senta uma aceleração no aprendizado e converge com 50% de sucesso. O desem-

penho do restante dos modelos ficou abaixo do desempenho com todas as ações

exceto para o modelo com E=0.01 construído utilizando as variáveis selecionadas

pelo algoritmo LVF que teve desempenho próximo ao modelo construído com todas

as ações.

5.4 Comparação dos Modelos 80

5.4 Comparação dos Modelos

Para avaliar a eficiência das abordagens utilizadas decidiu-se avaliar o uso da me-

mória e o desempenho do agente no drible. Para isto construíram-se intervalos de

confiança de 95% segundo a distribuição t-student apresentados em gráficos Box-

whisker.

5.4.1 Teste do Desempenho

Para avaliar o desempenho do agente no drible foi retirado de cada curva de apren-

dizado o modelo que teve desempenho próximo a média. Todos estes modelos se-

rão testados 10 vezes no mesmo ambiente em que foram treinados. Cada teste e-

quivale à freqüência relativa de sucesso do agente no drible em 300 episódios. Du-

rante o teste dos modelos a aprendizagem e a exploração não serão realizadas.

Figura 5.25 Comparação do desempenho no teste dos modelos (média de dez exe-

cuções) com todas as variáveis.

A Figura 5.25 compara o desempenho dos modelos construídos com todos os

atributos. Note que a exploração proporcionou um aumento no desempenho em to-

Teste do Modelo(Todos Atributos)

Média

Média±EP

Média±2,262*EP To

da

s A

çõ

es,

E=

0

To

da

s A

çõ

es,

E=

0.0

1

Con

f. 1

5%

, E

=0

Con

f. 1

5%

, E

=0

.01

Con

f. 2

0%

, E

=0

Con

f. 2

0%

, E

=0

.01

Con

f. 3

0%

, E

=0

Con

f. 3

0%

, E

=0

.01

Con

f. 4

0%

, E

=0

Con

f. 4

0%

, E

=0

.01

30

32

34

36

38

40

42

44

46

48

50

52

54

Desem

penho


dos os casos exceto para . No desempenho dos modelos das Figuras 5.26

e 5.27 este comportamento também é observado, exceto para nos mode-

los construídos com os atributos selecionados segundo a taxa de ganho e a redun-

dância.

Figura 5.26 Comparação do desempenho dos modelos (média de dez execuções)

no teste com as variáveis selecionadas segundo a Taxa de Ganho e a Redundância.

Observando as Figuras 5.25, 5.26 e 5.27, nota-se que a seleção de ações

proporcionou um aumento significativo no desempenho dos modelos. Na Figura 5.25

o melhor desempenho foi quando foi igual a 40%. Neste caso, a redução da quan-

tidade de ações foi de aproximadamente 75% de um total de 113 ações.

No modelo construído com os atributos selecionados segundo a taxa de ga-

nho e redundância, o melhor desempenho também foi obtido através da seleção de

ações (Figura 5.26). Apenas no modelo LVF o melhor desempenho foi obtido ape-

nas com a seleção de atributos. No entanto, o desempenho com igual a 40% e

E=0.01 obteve desempenho muito próximo do melhor conforme pode ser visto na

Figura 5.27.

Teste do Modelo(Taxa de Ganho e Redundância)

Média

Média±EP

Média±2,262*EP Todas A

ções,

E=

0

Todas A

ções,

E=

0.0

1

Conf. 1

5%

, E

=0

Conf. 1

5%

, E

=0.0

1

Conf. 2

0%

, E

=0

Conf. 2

0%

, E

=0.0

1

Conf. 3

0%

, E

=0

Conf. 3

0%

, E

=0.0

1

Conf. 4

0%

, E

=0

Conf. 4

0%

, E

=0.0

134

36

38

40

42

44

46

48

50

52

54

56

58

60

Desem

penho


Figura 5.27 Comparação do desempenho dos modelos (média de dez execuções) no teste com as variáveis selecionadas pelo algoritmo LVF.

De uma maneira geral, a seleção de atributos proporcionou um aumento sig-

nificativo no desempenho dos modelos. Apenas quando E foi igual a 0 é que o de-

sempenho dos modelos das Figuras 5.26 e 5.27 foi próximo ao dos modelos da Fi-

gura 5.25. O melhor desempenho foi obtido com a seleção de atributos segundo a

taxa de ganho e redundância.

5.4.2 Uso da Memória

A Figura 5.28 compara o uso da memória com a variação dos parâmetros e nos

modelos construídos com todas as variáveis. A seleção de ações proporcionou uma

redução no uso da memória. No pior caso, com e , o uso da memória

foi reduzido em média 30% a menos do que o modelo com todas as ações. No me-

lhor caso tem-se uma redução de aproximadamente 95%.

Teste do Modelo(LVF)

Média

Média±EP


ções,

E=

0

Todas A

ções,

E=

0.0

1

Conf. 1

5%

, E

=0

Conf. 1

5%

, E

=0.0

1

Conf. 2

0%

, E

=0

Conf. 2

0%

, E

=0.0

1

Conf. 3

0%

, E

=0

Conf. 3

0%

, E

=0.0

1

Conf. 4

0%

, E

=0

Conf. 4

0%

, E

=0.0

1

32

34

36

38

40

42

44

46

48

50

Desem

penho


Figura 5.28 Comparação do uso da memória dos modelos (média de dez execu-

ções) com todas as variáveis.

Figura 5.29 Comparação do uso da memória dos modelos (média de dez execu-ções) com as variáveis selecionadas pelo algoritmo Taxa de Ganho.

Uso da Memória(Todas as Variáveis)

Média

Média±EP

Média±2,262*EP To

da

s A

çõ

es,

E=

0

To

da

s A

çõ

es,

E=

0.0

1

Con

f. 1

5%

, E

=0

Con

f. 1

5%

, E

=0

.01

Con

f. 2

0%

, E

=0

Con

f. 2

0%

, E

=0

.01

Con

f. 3

0%

, E

=0

Con

f. 3

0%

, E

=0

.01

Con

f. 4

0%

, E

=0

Con

f. 4

0%

, E

=0

.01

0

2

4

6

8

10

12

14

16

18

20

Uso da Memória(Taxa de Ganho)

Média

Média±EP


ções,

E=

0

Todas A

ções,

E=

0.0

1

Conf. 1

5%

, E

=0

Conf. 1

5%

, E

=0.0

1

Conf. 2

0%

, E

=0

Conf. 2

0%

, E

=0.0

1

Conf. 3

0%

, E

=0

Conf. 3

0%

, E

=0.0

1

Conf. 4

0%

, E

=0

Conf. 4

0%

, E

=0.0

1

0,4

0,6

0,8

1,0

1,2

1,4

1,6

1,8

2,0

2,2

2,4

Mem

ória e

m M

egabyte

s

5.5 Qualidade do Drible 84

De acordo com a Figura 5.30, os atributos selecionados pelo algoritmo LVF

proporcionou a maior redução no uso de memória, cerca de 900KB contra 2,2MB da

taxa de ganho e 17,7MB do modelo com todos os atributos e ações, i.e., uma redu-

ção de 60% se comparado com a taxa de ganho e mais que 95% se comparado com

a utilização de nenhuma abordagem para a seleção de atributos e ações. Os resul-

tados são significativos e mostram que a seleção de atributos pode diminuir conside-

ravelmente o uso de memória dos modelos baseados em tabelas.

Figura 5.30 Comparação do uso da memória dos modelos com as variáveis selecio-

nadas pelo algoritmo LVF (média de dez execuções).

A combinação dos dois métodos, seleção de ações e atributos, proporcionou

uma redução ainda maior em todas as abordagens, se comparado somente com a

seleção de atributos. Em alguns experimentos foi possível notar um aumento no uso

da memória quando a exploração foi incentivada. No entanto, é um custo necessário

para o desempenho do modelo aumentar.

5.5 Qualidade do Drible

Existem duas medidas que se pode utilizar para medir a qualidade do drible, o tem-

po de execução do drible e a distância final do oponente. Dribles que são realizados

Uso da Memória(LVF)

Média

Média±EP

Média±2,262*EP To

da

s A

çõ

es,

E=

0

To

da

s A

çõ

es,

E=

0,0

1

Con

f. 1

5%

, E

=0

Con

f. 1

5%

, E

=0

,01

Con

f. 2

0%

, E

=0

Con

f. 2

0%

, E

=0

,01

Con

f. 3

0%

, E

=0

Con

f. 3

0%

, E

=0

,01

Con

f. 4

0%

, E

=0

Con

f. 4

0%

, E

=0

,01

0,4

0,5

0,6

0,7

0,8

0,9

1,0

Me

mó

ria e

m K

ilob

yte

s

5.5 Qualidade do Drible 85

rápidos possibilitam jogadas mais rápidas e velocidade é um critério chave para

qualquer estratégia de um time de futebol. A distância do oponente que o agente

conseguiu também é importante para a qualidade do drible. Quanto maior a distân-

cia que o agente conseguir de seu oponente, menores serão as chances de perder a

bola após o drible. Em todos os experimentos o tempo médio do drible ficou em tor-

no de 13 passos e a distância final do oponente em torno de 1.2 metros.

86

Capítulo 6

Conclusão

O principal objetivo deste trabalho foi mostrar como as técnicas de mineração de

dados podem ser utilizadas nos ambientes da aprendizagem por reforço. Os experi-

mentos utilizaram algumas técnicas de mineração de dados para selecionar as vari-

áveis e ações mais relevantes do problema abordado, o drible. A aplicação destas

técnicas serviu para reduzir a dimensionalidade do problema com a eliminação das

variáveis e ações menos relevantes. Foi mostrado que a redução da dimensionali-

dade pode aumentar o desempenho do agente e reduzir o tempo de convergência

dos modelos da aprendizagem por reforço.

Para tornar possível a utilização das técnicas de mineração de dados, inicial-

mente foi preciso que o treinamento do agente estivesse presente em um banco de

dados. O Capítulo 4 mostrou uma possível forma de armazenamento para o treina-

mento do agente através do esquema apresentado na Figura 4.2 (página 51).

Mesmo com o treinamento armazenado em um banco de dados, ainda não é

possível utilizar os algoritmos para a seleção de atributos sem antes transformar o

problema que, naturalmente é por reforço, em um problema supervisionado. A Se-

ção 4.3 (página 48) propôs utilizar a ação do agente como atributo classe. De acordo

com Cohen e Maimon (2005), as ações tomadas pelo agente podem ser considera-

das as respostas desejadas utilizadas na aprendizagem supervisionada. Desta for-

ma foi possível obter todo mapeamento da política do agente. A utilização destes

dados para a seleção de atributos permite identificar quais atributos influenciam na

decisão do agente.

6.1 Resultados e Discussões 87

6.1 Resultados e Discussões

O Drible Uma das contribuições deste trabalho foi demostrar que o algoritmo com-

binado com o aproximador linear CMAC pode ser utilizado com sucesso em proble-

mas como o do drible. O drible é um problema da aprendizagem por reforço de

grande complexidade e pouco abordado na literatura.

Neste trabalho, o ambiente do drible foi composto de 23 variáveis de estado

contínuas e 113 ações realizáveis (ver Tabela 3.4 e Tabela 3.3 nas páginas 33 e

32). Mesmo com esta complexidade, o agente aprendeu a driblar e conseguiu alcan-

çar um desempenho de 45% (Figura 5.6, página 60), no teste o desempenho foi bem

próximo (Figura 5.25, página 80). Após a eliminação de algumas variáveis irrelevan-

tes segundo a taxa de ganho e a redundância (Tabela 5.4, página 64), o modelo

conseguiu atingir um desempenho médio de 55% (Figura 5.12, página 67). No teste,

o desempenho do modelo foi maior quando removidas as variáveis e ações irrele-

vantes (Figura 5.26, página 80).

Convergências mais rápidas foram alcançadas quando as ações irrelevantes

foram removidas. A remoção das variáveis irrelevantes também proporcionou uma

redução no tempo de convergência e, mais importante, um aumento do desempenho

do agente.

O agente utilizou em média 13 passos para conseguir realizar o drible, algo

em torno de 2.5 segundos para concluir. A distância final entre o oponente e o agen-

te ficou em média 1.2 metros. Esta distância permitiu ao agente continuar com a bo-

la após o drible sem a possibilidade de perdê-la para o oponente.

Modelo Utilizado

Através da utilização do algoritmo combinado com o aproximador Linear

CMAC foi possível construir um modelo capaz de aprender através da interação com

o ambiente. Com o uso deste aproximador foi possível construir um modelo capaz

de generalizar. A quantidade de estados visitados pelo agente foi muito menor do

que a quantidade total existente no problema do drible. O modelo construído possibi-


litou utilizar em regiões do espaço de estados nunca visitados, o conhecimento ad-

quirido em regiões vizinhas.

Mesmo com a quantidade de variáveis irrelevantes presentes no treinamento,

o modelo foi capaz de atingir níveis de desempenho muitos bons, o que mostrou sua

tolerância a ruídos. Riedmiller (Riedmiller, 1999) mostrou que o tempo de conver-

gência das redes neurais de múltiplas camadas pode aumentar drasticamente com o

aumento da quantidade de ações. Este comportamento não é observado quando

utilizado o aproximador linear CMAC.

Os experimentos mostraram que o CMAC é uma técnica confiável e adequa-

damente aplicável em ambientes complexos com grande quantidade de ações e va-

riáveis. A grande quantidade de ações e variáveis não foi um obstáculo para o mo-

delo, tendo a convergência garantida em todos os experimentos.

Mineração de Dados na Aprendizagem por Reforço

Nos modelos da aprendizagem por reforço, a qualidade dos atributos e ações é de

grande importância para a convergência e generalização. A escolha cuidadosa dos

atributos do ambiente e ações do agente é de fundamental importância para seu a-

prendizado, pois atributos desnecessários aumentam o espaço de busca, tornando

difícil encontrar uma solução ótima (Coons et al., 2008).

Os experimentos realizados mostraram que a simples aplicação de algumas

técnicas da mineração de dados em problemas da aprendizagem por reforço possi-

bilita aumentar o desempenho destes modelos. Através do uso da mineração de da-

dos foi possível identificar e eliminar as variáveis e ações irrelevantes. Com isto a

complexidade do modelo pode ser reduzida, a generalização aumentada e o tempo

de convergência diminuído.

Seleção de Atributos

De uma maneira geral, as técnicas utilizadas para selecionar atributos proporciona-

ram um aumento no desempenho do treinamento do agente (ver Figuras 5.26 e 5.27

nas páginas 81 e 82). O mesmo pode ser observado no teste dos modelos (Seção

5.4, página 80). A eficiência das técnicas de seleção de atributos utilizada no pro-


blema abordado mostrou desempenhos bem próximos. No entanto, em termos abso-

lutos, a utilização da taxa de ganho permitiu obter o melhor desempenho segundo a

freqüência relativa de sucesso do agente no drible em ambos os casos: treinamento

e teste. Contudo, para utilizar esta técnica é preciso de no mínimo um pouco de co-

nhecimento do problema, pois os atributos mais relevantes não são selecionados

automaticamente, ao invés disto esta técnica apenas faz um ranking entre as variá-

veis.

A remoção das variáveis redundantes e com menor taxa de ganho permitiu

aumentar o desempenho e reduzir o tempo de convergência no treinamento do mo-

delo construído (ver Figura 5.12 na página 67). A quantidade de memória utilizada

por este modelo foi de aproximadamente 2,2 MBytes com E=0 e 1,6 MBytes com

E=0.01; neste caso, houve uma redução de 90% se comparado com o uso de me-

mória do modelo com todas as variáveis. Com isto pode-se dizer que o uso da taxa

de ganho como medida para identificar e selecionar os atributos mais relevantes é

muito adequada a ambientes da aprendizagem por reforço.

Apesar do modelo construído com as variáveis selecionadas pelo algoritmo

LVF ter apresentado desempenho pior que a taxa de ganho, este algoritmo é capaz

de identificar automaticamente subconjuntos de atributos relevantes de todos os

subconjuntos de atributos existentes, onde . Esta abordagem di-

minui consideravelmente o espaço de busca. A modificação do algoritmo proposta

por este trabalho mostrou que o critério de inconsistência é uma medida eficiente

para a avaliação de um subconjunto de atributos.

O algoritmo LVF possibilitou uma redução maior da quantidade de atributos,

se comparado com a taxa de ganho. Conseqüentemente a quantidade de memória

utilizada foi menor, consumindo em média 600 Kbytes, i.e, uma redução de aproxi-

madamente 95% se comparado com o uso de memória do modelo com todas as

variáveis.

Seleção de Ações

De uma maneira geral, as técnicas utilizadas para selecionar ações proporcionaram

um aumento no desempenho do treinamento do agente apenas quando não utilizado

nenhuma abordagem para a seleção de atributos. No teste a combinação das técni-

cas proporcionou um aumento no desempenho dos modelos. Com a combinação da

6.2 Contribuições e Relevância 90

seleção de ações com a seleção de atributos utilizando a taxa de ganho o desempe-

nho do agente no treinamento caiu no mínimo 4%, mas a redução de memória foi

maior. No teste do modelo, a seleção de ações proporcionou um aumento de apro-

ximadamente 4%, no desempenho do modelo.

No treinamento, as variáveis selecionadas pelo algoritmo LVF não reduziu o

desempenho quando foi igual a 40%, mas para houve uma redução de

no mínimo 3%. O mesmo comportamento foi observado no teste do modelo.

As medidas de suporte e confiança mostraram ser eficientes na identificação

das ações mais relevantes. Os experimentos mostraram que a técnica de seleção de

ações pode proporcionar um aumento no desempenho dos modelos da aprendiza-

gem por reforço. Além disto, com a seleção de ações foi possível reduzir o tempo de

convergência em alguns modelos.

Assim como na seleção de atributos, a técnica utilizada para selecionar as

ações proporcionou uma redução no uso da memória em todos os casos (ver Figu-

ras 5.28, 5.29 e 5.30 nas páginas 83 e 84). O pequeno intervalo de confiança em

todos os modelos mostra que a variação do uso da memória entre os treinamentos

foi baixa. O modelo construído com as variáveis selecionadas pelo algoritmo LVF

continuou a apresentar o menor uso da memória, consumindo em média 450KB. Em

seguida a taxa de ganho com 600KB e por último o modelo com todas as variáveis

que consumiu em média 1MB.

6.2 Contribuições e Relevância

Neste trabalho, foram apresentados um modelo de aprendizagem baseado na técni-

ca de aproximação paramétrica CMAC, a modelagem do ambiente do drible como

um problema da aprendizagem por reforço, um esquema para armazenamento dos

dados de treinamento do agente, a seleção dos dados armazenados e a análise dos

resultados do drible e da utilização das técnicas de mineração de dados para au-

mentar o desempenho e reduzir o consumo de memória do modelo.

A utilização das abordagens descritas neste trabalho possibilitou aumentar o

desempenho do modelo CMAC. Outra característica importante foi a redução de

memória que a seleção de atributos e ações proporcionaram. Com o uso das técni-

cas de mineração foi possível notar uma redução de 95% no consumo de memória

dos modelos se comparado com o construído com todas as variáveis. A utilização de

6.3 Trabalhos Futuros 91

17MB de memória nos computadores atuais não apresenta um obstáculo, mas se o

modelo é construído para operar em sistemas embarcados, tais como uma geladei-

ra, câmera fotográfica ou celular a quantidade de memória utilizada pode determinar

o valor final do aparelho. Outra vantagem considerada é a possibilidade da redução

do consumo de energia e processamento. Uma outra vantagem da seleção de atri-

butos e ações foi com relação ao tempo de convergência que diminuiu. Apesar do

tempo de convergência não ter alcançado valor significativos no modelo CMAC, a

utilização da técnica em outros modelos, tais como as redes neurais de múltiplas

camadas podem proporcionar uma redução significativa no tempo de convergência

(Riedmiller, 1999).

Além de possibilitar o uso das técnicas descritas no Capítulo 4, o armazena-

mento do treinamento do agente em um banco de dados através do esquema apre-

sentado na Figura 4.2 (página 51), resultou em uma série de outras vantagens, tais

como a análise do comportamento do agente, possibilidade de transformação das

variáveis, treinamento off-line e outras.

Em suma, as contribuições apresentadas por este trabalho foram:

A utilização das técnicas de mineração de dados para a identificação de

atributos e ações relevantes.

A redução do consumo de memória dos modelos.

Redução da complexidade e aumento do desempenho do agente.

A solução do problema do drible utilizando o algoritmo combina-

do com a técnica de tile-coding.

O produto final da dissertação, o modelo, mostrou ser capaz de realizar o dri-

ble com eficiência, demonstrando que a utilização da mineração de dados em ambi-

entes da aprendizagem por reforço é valida e merece especial atenção como alvo de

novos estudos.

6.3 Trabalhos Futuros

Como trabalhos futuros planeja-se aplicar outras técnicas da mineração de dados

além das descritas neste trabalho. Também pretende-se aplicar as técnicas descri-

6.3 Trabalhos Futuros 92

tas no Capítulo 4 em outros problemas da aprendizagem por reforço que são encon-

trados freqüentemente na literatura, tais como o keepaway (Stone & Sutton, 2001).

Outro trabalho que pretende-se realizar é a utilização das técnicas de mineração

de dados para reduzir a complexidade de outros modelos, tais como uma rede neu-

ral. Segundo Riedmiller (Riedmiller, 1999), a complexidade do problema tem forte

influência no desempenho deste modelo. Deseja-se também verificar o quanto o dri-

ble pode melhorar a eficiência de um time.

93

Apêndice A

Aprendizagem por Reforço

A.1 Introdução

A aprendizagem por reforço não é definida por caracterizar métodos de aprendiza-

gem, mas por caracterizar um problema de aprendizagem e, qualquer método que

seja capaz em solucioná-lo é considerado como um método da aprendizagem por

reforço (Sutton & Barto, 1998). Estes Métodos devem ser capazes de associar a-

ções aos estados do ambiente, para que, de tal forma, possibilite selecionar as me-

lhores ações que maximizem seu sinal de recompensa. Basicamente este tipo de

aprendizagem caracteriza-se em um problema de otimização, onde o agente deve

buscar otimizar a escolha de sua ações, através de sua interação com o ambiente,

em função da recompensa recebida em cada estado visitado.

Em um sistema de aprendizagem por reforço, existem quatro elementos prin-

cipais, são eles: uma política que define o comportamento do agente em um dado

momento, uma função de recompensa que define o objetivo do agente, uma fun-

ção valor que indica os estados que o levam a maior recompensa ao longo do tem-

po, e opcionalmente, um modelo do ambiente que define os estados e outros as-

pectos do ambiente (Sutton & Barto, 1998).

A.1 Introdução 94

Figura A.1 Interação agente-ambiente. Traduzido da fonte: (Sutton & Barto, 1998)

Na Figura A.1, o agente interage com o ambiente em uma seqüência de tem-

po discreto, . A função de recompensa permite o mapeamento de

cada estado do ambiente em um sinal numérico chamado recompensa, . A tarefa

do agente é realizar uma ação em um estado , seguindo uma política que o

possa levar a um estado que resulte em um maior retorno de recompensas

ao longo do tempo, pois estados que aparentemente dão a maior recompensa po-

dem levar a outros que não dão (Sutton & Barto, 1998). A busca por estados que

aumentem a sua recompensa ao longo do tempo, permite que o agente sempre visi-

te os estados que o levem para a maior quantidade de recompensa acumulada e

não para a maior num dado momento. Em suma o agente deve ser orientado para

maximizar o retorno definido por:

( A.1)

onde é o instante de tempo final.

Existem casos em que o ambiente não termina naturalmente em um episódio.

Nestes casos pode facilmente tender ao infinito e conseqüentemente também

tenderá. Para solucionar este problema é utilizada uma taxa de desconto (Sutton &

Barto, 1998). A taxa de desconto permite determinar a importância das recompensas

futuras sobre as passadas. A equação a seguir aplica a taxa de desconto na expres-

são do retorno definida anteriormente:

( A.2)

onde é um parâmetro compreendido no intervalo . Os métodos de aprendiza-

gem por reforço devem especificar como o agente deve mudar a sua política em

A.1 Introdução 95

função de sua experiência para maximizar a soma das recompensas descontadas

que recebe ao longo do tempo (Sutton & Barto, 1998).

Uma política, segundo Sutton e Barto (1998), é o mapeamento dos estados

em probabilidades de se realizar uma ação, denotado por . Este mapeamento é

tido como a probabilidade de selecionar uma ação no instante de tempo quando

o estado é , ou seja, . A estimativa de quanto será prazeroso para o agente

seguir uma determinada política pode ser obtida através de uma função valor.

A função valor pode ser representada por uma função valor-estado ou uma

função valor-ação. A função valor-estado, denotada por , representa o valor de

um estado em uma política . Em outras palavras, a função valor-estado define o

retorno esperado quando o agente inicia em e segue uma política logo após.

Se mantida a estimativa de recompensa das ações separadas para cada es-

tado é possível obter uma função valor-ação. A função valor-ação, denotada por

, define o retorno esperado quando o agente inicia em , realiza uma ação

e segue uma política logo após.

Uma propriedade fundamental das funções valor é que estas satisfazem uma

relação recursiva entre o valor de um estado e os valores de seus estados sucesso-

res (Sutton & Barto, 1998). A equação de Bellman para que mantém esta recursi-

vidade é dada a seguir:

,

( A.3)

de forma similar a equação de Bellman pode ser obtida para uma função valor-ação

,

A.1 Introdução 96

( A.4)

onde em ambas as equações, denota o valor esperado dado que o agente se-

gue uma política aleatória, é probabilidade de transição entre os estados e

se realizada a ação , é a recompensa esperada desta transição, é a pro-

babilidade de uma ação ocorrer no estado e é a taxa de desconto. O processo

que retorna para cada estado o valor de todos os estados sucessores é chamado de

fullbackup ou retorno total (Sutton & Barto, 1998).

A.1.1 Política Ótima

De acordo com Bellman (1952), uma política ótima consiste em uma seqüência de

ações que sejam mais vantajosas de acordo com algum critério estabelecido previ-

amente. A solução de um problema da aprendizagem por reforço é alcançada quan-

do o agente encontra uma política que seja melhor do que todas as outras políticas,

possibilitando receber uma maior quantidade de recompensa ao longo do tempo.

Segundo Sutton e Barto (1998), uma política é melhor que outra política se o

retorno esperado no total dos estados é maior que o da política . Em outras pala-

vras, é melhor que se e somente se para todos os estados.

Se uma política é melhor que todas as outras então esta política, denotada

por , é chamada de ótima. Existe ao menos uma política que é igual ou melhor

que todas as outras políticas e compartilham a mesma função valor-estado, que nes-

te caso é chamada de função valor-estado ótima e é denotada por ou por caso

A.2 Programação Dinâmica 97

se utilize uma função valor-ação (Sutton & Barto, 1998). A função valor-estado ótima

é definida pela equação a seguir:

( A.5)

onde é a função valor-estado ótima, é o estado atual, é probabilidade de tran-

sição entre os estados e se realizada a ação , e é recompensa esperada

desta transição. Para cada estado existe uma ou mais ações que levam o agente

para um estado em que é máximo. Uma política que associa probabilidade

maior que zero apenas para estas ações é considerada política ótima. Outra forma

de encontrar uma política ótima é através uma função valor-ação:

( A.6)

onde é a função valor-ação ótima, é a probabilidade de transição entre os es-

tados e se realizada a ação , e é recompensa esperada desta transição.

As Equações A.5 e A.6 são derivadas do princípio da otimalidade, definido por

Bellman como: “Uma política ótima tem a propriedade de que qualquer que seja o

estado inicial e decisões iniciais, as próximas decisões devem ser constituídas de

uma política ótima” (Bellman, 1952). Este conceito constitui a base da programação

dinâmica e da aprendizagem por reforço (Sutton & Barto, 1998).

A.2 Programação Dinâmica

O termo programação dinâmica refere-se a uma coleção de algoritmos que, dado o

perfeito modelo do ambiente como um processo de decisão de Markov (Markov De-

cision Process ou MDP), é suficiente para se encontrarem políticas ótimas (Sutton &

Barto, 1998).

Um ambiente é dito como Markoviano, ou de possuir a propriedade de Mar-

kov, se todas as informações relevantes do ambiente que descrevem o seu estado


atual sejam suficientes para determinar o seu futuro estado e recompensa (Sutton &

Barto, 1998). Desta forma, a dinâmica do ambiente pode ser formalmente definida

em termos probabilísticos:

ou seja, dados apenas os estados atuais, ambientes que possuem a propriedade de

Markov possibilitam a predição dos próximos estados e recompensa . O estado

atual contém a informação dos estados anteriores. Assim, a decisão de que ação

tomar não depende da seqüência de estados anteriores.

Para utilizar os algoritmos da programação dinâmica é preciso que seja co-

nhecida a probabilidade de transição entre os estados e a recompensa esperada

desta transição. Esta característica limita o uso da programação dinâmica na maioria

dos problemas de aprendizagem por reforço porque, na maioria dos casos, as pro-

babilidades de transição não são conhecidas. Outra restrição deve-se ao alto pro-

cessamento computacional necessário para se encontrar uma política ótima.

A.2.1 Processo de Aprendizagem

O processo de aprendizagem dos métodos da programação dinâmica resume-se em

duas etapas conhecidas como policy evaluation (avaliação da política) e policy im-

provement (otimização da política) (Sutton & Barto, 1998). A etapa de policy evalua-

tion consiste em gerar um episódio, seguindo uma política inicialmente arbitrária , e

calcular as novas estimativas para cada estado visitado durante o episódio.

A próxima etapa, policy improvement, consiste em encontrar uma nova política , de

tal forma que, .

A.2.1.1 Policy Evaluation

O objetivo da etapa de policy evaluation é computar a função valor-estado ou valor-

ação para uma política probabilística ou determinística . De uma maneira simples

as funções valor podem ser encontradas resolvendo-se um sistema de equações

lineares dado pelas Equações A.3 ou A.4. Outro meio para encontrar as funções va-

lor é através de um processo iterativo. Este processo pode ser obtido utilizando as


equações de Bellman para aproximar gradativamente em um procedimento itera-

tivo:

( A.7)

e

( A.8)

Desta forma, é obtida através de uma seqüência de estimativas de fun-

ções valor obtidas através de passagens por todos os estados do am-

biente. Se então é garantido que (Sutton & Barto, 1998).

A.2.1.2 Policy Improvement

A etapa de policy improvement trata de encontrar políticas melhores tornando-as

gulosas em relação à função estado-valor de uma outra política. As equações de

Bellman descritas na subseção anterior referiram-se a uma política probabilística

. Nesta seção as equações A.7 e A.8 são alteradas, para referenciar uma polí-

tica determinística , conforme descrito a seguir.

( A.9)

e

( A.10)

Dada uma política determinística , uma forma para encontrar melhores polí-

ticas é considerar outras ações, onde . Selecionar em cada estado a ação

que aparenta ser melhor de acordo com permite encontrar uma nova política


que seja melhor que ou igual que à anterior. Formalmente esta nova política é dada

por:

( A.11)

Estas ações fazem parte de uma nova política . Se para todo ,

, então seguir permite obter um retorno que é maior que ou

igual a .

A.2.1.3 Policy Iteration

O processo conhecido como policy iteration (Iteração da Política) refere-se à idéia de

que, por meio de sucessivas iterações entre policy evaluation e policy improvement,

é possível se obter uma seqüência monotonicamente crescente de melhores políti-

cas e estimativas que podem convergir para uma política ótima (Sutton & Barto,

1998), ou seja:

Desta forma, se for garantido que o processo de iteração entre as etapas de

policy evaluation e policy improvement ocorra infinitas vezes, é possível encontra-

rem-se as estimativas de cada estado e uma política ótima .

O Algoritmo A.1 mostra o pseudocódigo da policy iteration. Este algoritmo é

dividido nas duas etapas, policy evaluation e policy improvement, descritas anterior-

mente. O algoritmo é resumido a seguir. Dada uma política determinística e inicial-

mente arbitrária a primeira etapa do algoritmo encontra os valores da função valor-

estado para cada estado desta política. A próxima etapa, policy improvement, en-

contra uma nova política fazendo-a gulosa com respeito aos valores de . O

processo se repete a partir da etapa anterior se .


Algoritmo A.1 Algoritmo policy iteration.

Formalmente, o processo de avaliação da política converge apenas quando o

número de iteração tende a infinito, mas na prática, segundo Sutton & Barto (Sutton

& Barto, 1998), o processo pode ser finalizado em poucas iterações. Neste algorit-

mo, a medida de convergência consiste no teste de realiza-

do ao fim da atualização das estimativas de cada estado e, o critério de parada é

atingido quando este valor for suficientemente pequeno (Sutton & Barto, 1998). O

processo iterativo do Algoritmo A.1 é finalizado quando a política não se altera, o

que é considerado como convergência para uma política ótima .

início:

, para todo ;

Policy Evaluation:

repita

;

para cada faça

;

;

;

fim

até ;

Policy Improvement:

;

para cada faça

;

;

se então ;

fim

se então ;

senão vá para Policy Evaluation;

fim


A.2.1.4 Value Iteration

A desvantagem do método iterativo esta relacionada ao tempo necessário para a

convergência de que ocorre somente quando o número de iteração tende a infini-

to (Sutton & Barto, 1998), tornando a convergência de para lenta, já que as pró-

ximas políticas são calculadas somente após o termino da etapa anterior. Felizmente

a etapa policy evaluation pode ser interrompida sem perder a garantia de conver-

gência (Sutton & Barto, 1998). Para isto, o algoritmo value iteration combina as eta-

pas de policy evaluation e policy improvement em uma única passagem pelos esta-

dos do ambiente. A equação resultante é semelhante à equação ótima de Bellman

(Equação A.5):

( A.12)

Para arbitrário, a seqüência converge para sob as mesmas condi-

ções que garantem a existência de (Sutton & Barto, 1998). A combinação entre

as etapas de policy evaluation e policy improvement também pode ser obtida utili-

zando a equação ótima de Bellman para uma função valor-ação. O Algoritmo A.2

apresenta o método value iteration.

Algoritmo A.2 Algoritmo value iteration.

início:

, para todo ;

repita

;

para cada faça

;

;

;

fim

até ;

;

A.3 Algoritmos da Aprendizagem por Reforço 103

A grande desvantagem dos algoritmos policy iteration e value iteration deve-

se às múltiplas passagens pelos estados do ambiente. Se o ambiente tem um núme-

ro muito grande de estados uma única passagem pelos estados teria um custo com-

putacional muito alto (Kaelbling et al., 1996).

A.3 Algoritmos da Aprendizagem por Reforço

Nas seções anteriores foram apresentados os principais conceitos e algumas dificul-

dades encontradas nos métodos da programação dinâmica. A principal dificuldade

encontrada, o que limita o seu uso, é a necessidade do modelo completo do ambien-

te. Como visto anteriormente, o modelo completo do ambiente contém as probabili-

dades de transições entre os estados, sendo esta informação, não encontrada em

grande parte dos problemas da aprendizagem por reforço. Outra dificuldade encon-

trada é o seu alto processamento. A cada iteração, os algoritmos da programação

dinâmica realizam múltiplas passagens por todos os estados do ambiente o que leva

a um custo computacional muito alto. Contudo, os algoritmos da programação dinâ-

mica são exponencialmente mais rápidos do que qualquer busca direta no espaço

de políticas (Sutton & Barto, 1998).

Esta seção aborda os principais métodos da aprendizagem por reforço, cada

qual com suas vantagens e desvantagens. Uma das principais características destes

métodos é a possibilidade de sua utilização em problemas que não disponibilizam o

modelo completo do ambiente. As próximas seções apresentam algoritmos que

permitem que o aprendizado ocorra on-line através da interação do agente com o

ambiente. Este tipo de aprendizado não requer múltiplas passagens por todos os

estados do ambiente a cada iteração, ao invés disto, são utilizados apenas exem-

plos da seqüência de estados, ações e recompensas retiradas da interação do agen-

te com o ambiente. No entanto, é preciso garantir que todas as ações tenham algu-

ma probabilidade de serem escolhidas. De um modo geral, a solução para este pro-

blema é incentivar a exploração assegurando que todas as ações tenham chances

de serem executadas. De acordo com Sutton e Barto (1998), existem dois tipos de

métodos que podem assegurar isto, chamados de métodos on-policy e off-policy.

Basicamente os métodos on-policy avaliam e aperfeiçoam a política que é uti-

lizada para tomar suas decisões, ou seja, estes métodos estimam o valor da política


enquanto a utilizam no controle do agente. Já nos métodos off-policy, estas duas

funções são separadas. A política utilizada para o controle do agente, chamada de

política de comportamento, deve ser independente da política que é avaliada e oti-

mizada, chamada de política de estimação (Sutton & Barto, 1998).

Em ambos os métodos a política é geralmente flexível. Sendo assim, a esti-

mativa de todo par estado-ação tem probabilidade de ser escolhida. Uma

possível variação para estes métodos consiste em fazer com que o agente siga uma

política (Watkins, 1989) descrita a seguir.

Agentes que seguem uma política devem, na maior parte do tem-

po, selecionar uma ação que possui o maior valor de estimativa e, no restante do

tempo, selecionar aleatoriamente uma ação qualquer com probabilidade com o

intuito de explorar o espaço de ações. Contudo, selecionar uma ação através de

uma política permite que, no momento da exploração, todas as ações

possuam mesma probabilidade de serem escolhidas. Isso significa que a probabili-

dade de escolher a segunda melhor ação é igual à probabilidade de escolher a pior

de todas. Em algumas tarefas em que as piores ações são muito ruins, isto pode ser

insatisfatório (Sutton & Barto, 1998).

A solução para este problema é variar a probabilidade de seleção de uma a-

ção de acordo com o valor de sua estimativa de recompensa, ou seja, ações que

tenham uma maior estimativa de recompensa terão probabilidade maior de serem

escolhidas em relação às demais (Sutton & Barto, 1998). Esta regra é conhecida

como softmax (Bridle, 1990). Geralmente, na softmax, a probabilidade de se esco-

lher uma ação em um instante de tempo é calculada pela distribuição de Gibbs a

seguir:

( A.13)

onde é um parâmetro positivo chamado temperatura. Altas temperaturas fazem

com que todas as ações sejam quase equiprováveis.

A.3.1 Monte Carlo

Diferente dos algoritmos da programação dinâmica, o método Monte Carlo (Michie &

Chamber, 1968) possibilita o aprendizado através da experiência do agente com o


ambiente. Embora um modelo seja necessário, este necessita apenas gerar apenas

exemplos de transições entre os estados. O método Monte Carlo estima com-

putando a média dos retornos recebidos após o agente visitar o estado . Neste ca-

so, para garantir que os retornos sejam bem definidos, utiliza-se o método Monte

Carlo apenas em tarefas episódicas.

A convergência do método Monte Carlo é assegurada conforme a lei dos

grandes números (Shen, 2002). Por exemplo, dado um número aleatório retirado

de uma distribuição uniforme com média e variância desconhecidas, é provado

que a média dos valores de possa convergir para se , ou seja,

, onde

. Esta propriedade é conhecida como a

lei dos grandes números. Portanto, se o método Monte Carlo estima o valor de

computando a média dos retornos recebidos em em episódios, conforme

a fórmula abaixo:

( A.14)

então, pela lei dos grandes números, à medida que tende a infinito se a-

proxima de . Estas são teorias que dizem um pouco a respeito da efetividade

do modelo.

As próximas subseções mostram a variação do algoritmo de Monte Carlo para

as duas classes de algoritmos, on-policy e off-policy. Os algoritmos apresentados

nas próximas seções estimam a função valor-ação ao invés da função valor-estado.

A vantagem de se possuir estimativas de estado-ação é a facilidade de sua aplica-

ção em tarefas de controle e onde não se tem um modelo do ambiente (Sutton &

Barto, 1998). Sem o conhecimento do modelo do ambiente a função valor-estado

sozinha não é suficiente para determinar uma política, pois não seria possível obter

a estimativa do próximo estado sem antes executar uma ação.

A.3.1.1 Monte Carlo On-Policy

Esta parte do documento mostra como encontrar melhores políticas utilizando o mé-

todo Monte Carlo, pela abordagem on-policy. O objetivo desta busca é aumentar o

retorno do agente. A Subsubseção A.2.1.3 mostrou como o algoritmo policy iteration


pode gradativamente encontrar políticas melhores através das etapas de policy eva-

luation e policy improvement. O método Monte Carlo pode estimar o valor de

através da média dos retornos recebidos. Esta é a etapa de policy evaluati-

on para o método Monte Carlo. A etapa de policy improvement é realizada tornando

a política gulosa com respeito à função valor, i.e., .

Algoritmo A.3 Monte Carlo on-policy

Uma possível complicação do método Monte Carlo é a possibilidade da con-

vergência para uma política que não será ótima. Isto pode acontecer em casos em

que o agente encontra uma política subótima e permanece nela sem visitar o restan-

te dos pares estado-ação. O método Monte Carlo on-policy assegura que todos os

pares estado-ação serão sempre visitados. Para que isto seja possível deve-se fazer

início:

para cada faça

;

;

fim

repita

Gere um episódio seguindo ;

para cada faça

retorno após a primeira ocorrência de s,a;

;

;

;

fim

para cada faça

;

para todo faça

fim

fim

até ;

fim


com que a política seja sempre flexível, por meio dos métodos apresentados na Se-

ção A.3.

O Algoritmo A.3 mostra o método Monte Carlo on-policy, onde a probabilidade

é atualizada seguindo uma política , ou seja, em um estado a

probabilidade de escolher uma ação seguindo uma política ótima é

e, com

probabilidade

de escolher uma ação aleatória.

A.3.1.2 Monte Carlo Off-Policy

O método Monte Carlo on-policy apresentado na Subsubseção A.3.1.1 estima a fun-

ção valor de uma política dada uma seqüência infinita de episódios gerados por esta

mesma política. Já os métodos off-policy podem estimar a função valor de uma polí-

tica dados os episódios gerados por uma outra política , onde . Porém,

para estimar os valores de utilizando os episódios de é necessário garantir que

toda ação tomada em seja, também, ocasionalmente tomada em (Sutton &

Barto, 1998).

Dado as políticas e , o estado inicial e uma seqüência de estados, ações e

recompensas gerada utilizando , a probabilidade de toda esta seqüência acontecer

em e será denotado por e , respectivamente. Seja o retorno

observado de um estado . Para realizar a média e obter a estimativa de é

necessário ponderar cada retorno observado, pela probabilidade relativa de

ocorrer em e , ou seja, . A estimativa do método Monte Carlo para

após observar retornos é:

( A.15)

Apesar de, a Equação A.15 envolver as probabilidades e que

normalmente são consideradas desconhecidas em problemas onde o método Monte

Carlo é aplicado, nesta equação elas aparecem como uma razão que

pode ser calculada admitindo nenhum conhecimento da dinâmica do ambiente. Seja

o instante de tempo final do -ésimo episódio envolvendo o estado , sendo

assim:


Se

( A.16)

então,

. ( A.17)

Algoritmo A.4 Monte Carlo off-policy

O Algoritmo A.4 apresenta o algoritmo de Monte Carlo off-policy. Neste algo-

ritmo são utilizadas duas políticas e . A política é a política de estimação e é

a política de comportamento. A política de comportamento pode ser qualquer uma,

mas que possa garantir que para todo par estado-ação (e.g., )

e a política de estimação deve ser sempre gulosa (greedy) com respeito aos valores

início:

para cada faça

;

;

;

;

fim

repita

Gere um episódio seguindo ;

;

para cada faça

;

;

;

;

;

fim

para cada faça

;

fim

até ;

fim


de . Uma vantagem deste método é a possibilidade de o agente explorar o

espaço de estados enquanto se mantém em uma política gulosa.

Um problema em potencial apontado por Sutton & Barto (1998) é que a a-

prendizagem deste método é realizada somente quando . Se

é verdade na maior parte do tempo que o aprendizado será lento, principal-

mente para os estados iniciais (Sutton & Barto, 1998).

110

Apêndice B

Modelos Baseados no Gradiente Descendente

B.1 Introdução

Esta seção descreve como a experiência de um limitado sub-conjunto de estados

pode ser utilizada para generalizar, produzindo uma boa aproximação em um con-

junto de estados muito maior. Este subconjunto de estados - conhecidos também

como exemplos de treinamento – é utilizado pelos métodos baseados no gradiente

descendente para aproximar uma função que mapeie este conjunto de estados em

suas respectivas estimativas de recompensa.

De acordo com Sutton e Barto (1998) é possível utilizar qualquer método da

aprendizagem supervisionada que aprenda através de exemplos; o que inclui as re-

des neurais artificiais (Haykin, 1994), árvores de decisão (Quinlan, 1986), e outros

tipos de regressão multivariada (Duda et al., 2000). No entanto, o uso de alguns mo-

delos pode ser problemático em ambientes da aprendizagem por reforço. Por exem-

plo, os modelos construídos com as redes neurais artificiais assumem um conjunto

de exemplos de treinamento estático, conjunto este que é processado várias vezes

pela rede neural até que o erro seja suficientemente pequeno. Porém, é importante

que o aprendizado em ambientes da aprendizagem por reforço ocorra on-line en-

quanto o agente interage com o ambiente ou com o modelo do ambiente. Para isto,

segundo Sutton e Barto (1998), é necessário que os métodos sejam capazes de a-

prender a partir de dados adquiridos incrementalmente.

Os modelos baseados no gradiente descendente são aproximadores parame-

trizados de acordo com um vetor de parâmetros . Na aprendizagem, o vetor de pa-

râmetros é ajustado a cada instante de tempo a fim de reduzir a soma dos erros

quadráticos definida por:

B.1 Introdução 111

( B.1)

onde é o valor esperado, é o valor obtido de uma função diferenciável de

para todo e é um vetor coluna com um número fixo de componentes,

, onde é muito menor que o número total de estados. A

função de custo da Equação B.1 é uma medida de como escolher o vetor de parâ-

metros de tal forma que seja encontrado uma solução ótima que satisfaça a

condição:

( B.2)

onde é o erro total gerado pelo modelo em um conjunto de exemplos.

De acordo com Haykin (1994), este é um problema irrestrito de otimização,

onde deve ser minimizada a função de custo em relação ao vetor de parâme-

tros .

O valor esperado da Equação B.1 é definido de acordo com o método de a-

prendizado escolhido. Por exemplo, o valor esperado para o método Monte Carlo é

(Subseção A.3.1) e dos métodos por diferença temporal é (Seção

2.1).

Os métodos baseados no gradiente descendente minimizam o erro dado pela

Equação B.1 ajustando o vetor de parâmetros, para cada exemplo dado, uma fração

na direção em que o erro seja menor. A atualização de um elemento do vetor de pa-

râmetros dá-se através de:

( B.3)

onde

( B.4)

Este tipo de método é chamado de gradiente descendente pelo fato de os a-

justes em serem proporcionais ao gradiente negativo do erro quadrático dos e-

xemplos (Sutton & Barto, 1998).


B.1.1 Algoritmo do Mínimo Quadrado Médio

O algoritmo apresentado a seguir é baseado na utilização dos valores instantâneos

da função de custo, ou seja,

( B.5)

( B.6)

onde é o sinal de erro no tempo . O fator é apenas para efeito de simplifi-

cação da derivada. O operador gradiente é definido como:

( B.7)

Sendo o vetor gradiente da função de custo definido pela Equação B.5,

então:

( B.8)

De acordo com a regra da cadeia do cálculo, é possível expressar o gradiente

como:

( B.9)

e diferenciando as equações B.5 e B.6 em ambos os lados, obtêm-se, respectiva-

mente:

( B.10)

e

( B.11)

A última derivada parcial da Equação B.9 varia de acordo com o modelo. Se o

modelo é linear, então:


( B.12)

onde é uma função que codifica o sinal de entrada em um vetor binário. A codifi-

cação deste vetor varia de acordo com o modelo utilizado. Finalmente, diferenciando

a Equação B.12 em relação a resulta em:

( B.13)

Substituindo as equações B.10, B.11 e B.13 em B.9 e depois em B.4, é possí-

vel formular o algoritmo do mínimo quadrado médio (LMS – Least Mean Square)

(Widrow & Hoff, 1960) como segue:

( B.14)

A Figura B.1 ilustra o funcionamento da versão linear do algoritmo LMS em

um problema da aprendizagem por reforço. Apresentado o novo estado ao crítico a

recompensa é calculada e o algoritmo LMS é ativado, nesta etapa, o erro é compu-

tado e o processo de aprendizagem se inicia, conforme as equações B.6 e B.3 res-

pectivamente.

Figura B.1 Modelo linear.

As variações da função que codifica o sinal de entrada são apresentadas nas

próximas subseções. A Seção B.2 apresenta a variação não-linear de . O modelo

linear utilizado nos experimentos é descrito na Seção 2.3.

B.2 Redes Neurais Multilayer Perceptron 114

B.2 Redes Neurais Multilayer Perceptron

As Redes Neurais Artificiais (McCulloch & Pitts, 1943) consistem em um método pa-

ra solucionar problemas de inteligência artificial. Originadas da idéia de modelar ma-

tematicamente as habilidades intelectuais humanas, as Redes Neurais Artificiais po-

dem resolver problemas que necessitem do raciocínio lógico, sendo utilizadas em

diversos problemas dos mais variados domínios como reconhecimento de voz e i-

magem, automatização de processos industriais, hospitalares e mecânicos (Haykin,

1994).

Figura B.2 Rede Neural Multilayer Perceptron.

Conectando os neurônios de uma camada com todos os outros da camada

seguinte é possível criar uma estrutura particular de rede conhecida como Multilayer

Perceptron (Múltiplas Camadas de Neurônio). Nessa estrutura, apresentada na Figu-

ra B.2, a saída da camada de entrada é transmitida para todos os neurônios da pri-

meira camada oculta, que por sua vez submete para camadas posteriores até que,

com esse processo, a camada de saída seja alcançada.

Estabelecida a estrutura de uma rede o aprendizado ocorre alterando o estí-

mulo de cada neurônio via o algoritmo back-propagation (Rumelhart et al., 1986), ou

seja, são apresentados para a rede neural os estímulos iniciais e o resultado que ela

deve apresentar até o seu aprendizado.


A aprendizagem de uma Rede Neural Artificial Multilayer Perceptron consiste

em duas fases: Propagação do estímulo e Retropropagação do erro. Na propagação

os estímulos de entrada são propagados por todos os neurônios de todas as cama-

das da rede até a camada de saída. A ativação de um neurônio ativado pela saída

dos neurônios da camada imediatamente à esquerda, pode ser obtido calculan-

do a equação definida a seguir:

( B.15)

onde representa o número de neurônios da camada e é um neurônio especial

chamado de bias. A saída do neurônio é obtida computando a função de ativação

sigmoid definida a seguir:

( B.16)

Esta função pode ser de outra natureza, desde que seja, não linear, contínua

e diferenciável. A continuidade da função é um requisito devido ao gradiente des-

cendente trabalhar com derivadas para retropropagar os erros.

Depois de propagado os estímulos de entrada, deve-se retropropagar o erro

- gerado na saída do neurônio da camada de saída - calculado por:

( B.17)

onde o termo , conforme visto na Seção Apêndice B, varia de acordo com o méto-

do de aprendizado utilizado, ou seja,

( B.18)

para o algoritmo Q-Learning,

( B.19)

para o algoritmo Sarsa, e

( B.20)

para o algoritmo Monte Carlo.

O cálculo dos ajustes nos pesos sinápticos de um neurônio dá-se atra-

vés da equação:


( B.21)

onde é a taxa de aprendizado que determina a intensidade de ajuste dos pesos

sinápticos e é um termo que varia de acordo com a camada na qual se encontra o

neurônio .

Para os neurônios da última camada, o termo é definido como segue:

( B.22)

onde é a derivada da função de ativação. Normalmente é utilizada a fun-

ção sigmóide logística ou a tangente hiperbólica, da família das squashing functions.

Caso os neurônios não estejam na camada de saída o erro não pode ser apli-

cado diretamente a eles. Neste caso, utiliza-se a equação:

( B.23)

onde são todos os termos dos neurônios que estão na camada imediatamen-

te à direita do neurônio oculto e são todos os pesos sinápticos associados

ao neurônio .

Os novos pesos sinápticos passam a ser atualizados pela equação:

( B.24)

A Rede Neural Artificial do tipo Multilayer Perceptron possui a propriedade de

aproximador universal de funções com grande capacidade de generalização e de

alto desempenho devido a seu processamento paralelo e distribuído (Haykin, 1994).

Foi provado que uma rede Multilayer Perceptron com uma camada oculta pode a-

proximar qualquer função conhecida com uma precisão especificada (Hornik et al.,

1989).

O Algoritmo B.1 mostra a combinação das redes neurais com o algoritmo Q-

Learning. Conforme apresentado, a rede neural é iniciada com seu vetor de pesos

aleatórios implicando em um conjunto de ações e estados arbitrários no inicio do

aprendizado.

Note que para obter a resposta desejada é preciso conhecer a estimativa de

recompensa do estado sucessor. Isto é um pouco problemático para o aprendizado

da rede neural, pois esta estimativa possui uma margem de erro. É possível eliminar


esta margem de erro combinando as redes neurais com o algoritmo de Monte Carlo

ao invés do algoritmo Q-Learning.

Outro problema associado à utilização deste aproximador em ambientes da

aprendizagem por reforço diz respeito à sua característica de aproximador global, ou

seja, ao aproximar de as estimativas de recompensa de outros estados

também serão afetadas, o que aumenta muito o tempo de convergência do algorit-

mo.

Algoritmo B.1 Combinação do algoritmo Q-Learning com as redes neurais artificiais multilayer perceptron.

início:

inicie uma rede neural com o vetor de parâmetros randômico;

para cada faça

estado inicial do episódio;

para cada faça

estimativa de produzida pela rede neural.

fim

escolha uma ação seguindo uma política derivada de ;

repita

realize a ação , observe a recompensa, , e o próximo estado, ;

para cada faça

;

fim

escolha uma ação seguindo uma política derivada de ;

;

;

; /* taxa de aprendizado, resposta desejada e

* estimativa dada pela rede neural. */

;

;

até ;

fim

fim

118

Referências Bibliográficas

Agakov, F. et al., 2006. Using Machine Learning to Focus Iterative Optimization. In CGO '06:

Proceedings of the International Symposium on Code Generation and Optimization.

Washington, 2006. IEEE Computer Society.

Aha, D.W., Kibler, D. & Albert, M.K., 1991. Instance based learning algorithms. Machine

Learning, pp.37-66.

Albus, J.S., 1971. A Theory of Cerebellar Function. Mathematical Biosciences, pp.25-61.

Albus, J.S., 1975. A new approach to manipulator control: The cerebellar model articulation

controller (CMAC). Journal of Dynamic Systems, Measurement, and Control, pp.220-27.

Alhajj, R. & Kaya, M., 2003. Employing olap mining for multiagent reinforcement learning.

Design and application of hybrid intelligent systems, pp.759-68.

Bagnell, J.A. & Schneider, J., 2001. Autonomous helicopter control using reinforcement

learning policy search methods. In Proceedings of the International Conference on Robotics

and Automation., 2001. IEEE.

Barto, A.G., Sutton, R.S. & Anderson, C.W., 1990. Neuronlike adaptive elements that can

solve difficult learning control problems. Artificial neural networks: concept learning, pp.81-

93.

Bellman, R., 1952. On the Theory of Dynamic Programming. In Proceedings of the National

Academy of Sciences., 1952.

Boer, R. & Kok, J., 2002. The Incremental Development of a Synthetic Multi-Agent System:

The UvA Trilearn 2001 Robotic Soccer Simulation Team. Master Thesis, Faculty of Science:

University of Amsterdam.

Referências Bibliográficas 119

Boyan, J. & Moore, A., 1995. Generalization in Reinforcement Learning: Safely

Approximating the Value Function. In Neural Information Processing Systems 7. The MIT

Press. pp.369-76.

Braga, A.P.S. & Araújo, A.F.R., 2002. Applying topological maps to accelerate reinforcement

learning in mobile robot navigation. In IEEE International Conference on Systems, Man and

Cybernetics. Hammamet, 2002. IEEE.

Brassard, G. & Bratley, P., 1996. Fundamentals of Algorithms. New Jersey: Prentice Hall.

Bridle, J.S., 1990. Training stochastic model recognition algorithms as networks can lead to

maximum mutual information estimates of parameters. In Advances in Neural Information

Processing System: Proceedings of the 1989 Conference. Morgan Kaufmann. pp.211-17.

Brindley, G.S., 1964. The use made by the cerebellum of the information that it receives from

sense organs. IBRO Bull.

Cavazos, J. & Moss, J.E.B., 2004. Inducing heuristics to decide whether to schedule. In

Proceedings of the ACM SIGPLAN'04 conference on programming language design and

implementation., 2004. ACM Press.

Cavazos, J. & Moss, J.E.B., 2006. Hybrid optimization: Which optimization to use? In

International Conference on Compiler Construction., 2006. ACM Press.

Cheny, M. et al., 2003. RoboCup Soccer Server.

Cohen, S. & Maimon, O., 2005. Reinforcement-Learning: An Overview from a Data Mining

Perspective. In Data Mining and Knowledge Discovery Handbook. Springer. pp.469-86.

Coons, K.E. et al., 2008. Feature selection and policy optimization for distributed instruction

placement using reinforcement learning. In PACT’08: Proceedings of the 17th international

conference on Parallel architectures and compilation techniques. New York, 2008. ACM.

Crites, R.H. & Barto, A.G., 1996. Improving elevator performance using reinforcement

learning. In Advances in Neural Information Processing Systems 8., 1996. MIT Press.

Dayan, P., 1992. The convergence of TD(λ) for general λ. Machine Learning, pp.341-62.

Duda, R.O., Hart, P.E. & Stork, D.G., 2000. Pattern Classification. 2nd ed. Wiley-Interscience.


Fayyad, U.M. & Irani, K.B., 1993. Multi-interval discretization of continuousvalued attributes

for classification learning. In Thirteenth International Joint Conference on Articial

Intelligence., 1993.

Gennari, J.H., Langley, P. & Fisher, D., 1989. Models of incremental concept formation.

Artificial Intelligence, pp.11-61.

Grossman, S.P., 1967. The Motor System and Mechanics of Basic Sensory-Motor Integration.

In Textbook of Physiological Psychology. New York: Wiley. Ch. 4.

Hall, M.A., 1999. Correlation-based Feature Selection for Machine Learning. PhD Thesis,

Departament of Computer Science: The University of Waikato.

Han, J. & Kamber, M., 2006. DataMining: Concepts and Techniques (The Morgan Kaufmann

Series in Data Management Systems). 2nd ed. Morgan Kaufmann.

Haykin, S., 1994. Neural Networks: A Comprehensive Foundation. New York: Macmillan.

Hornik, K., Stinchcombe, M. & White, H., 1989. Multilayer feedforward networks are

universal approximators. Neural Networks, pp.359-66.

Hunt, E., Martin, J. & Stone, P., 1966. Experiments in Induction. New York: Academic Press.

Jain, R., 1991. The Art of Computer Systems Performance Analysis: Techniques for

Experimental Design, Measurement, Simulation, and Modeling. New York: Wiley-

Interscience.

Kaelbling, L.P., Littman, M.L. & Moore, A.W., 1996. Reinforcement Learning: A Survey.

Journal of Artificial Intelligence Research, pp.237-85.

Kheradmandian, G. & Rahmati, M., 2009. Automatic abstraction in reinforcement learning

using data mining techniques. Robotics and Autonomous Systems, Julho.

Kitano, H. & Asada, M., 1998. Robocup humanoid challenge: Tha’s one small step for a robot,

one giant leap for mankind. In Proceedings of the IEEE/RSJ International Conference on

Intelligent Robots and System (IROS-98)., 1998.

Kitano, H. et al., 1995. Robocup: The robot world cup initiative. In Proceedings of the IJCAI-95

Workshop on Entertainment and AI/Alife., 1995.


Kitano, H. et al., 1997. Robocup: The robot world cup initiative. In Proceedings of the First

International Conference on Autonomous Agents (Agent-97)., 1997.

Kohavi, R., 1995. Wrappers for Performance Enhancement and Oblivious Decision Graphs.

PhDthesis, Stanford University.

Kohavi, R. & John, G., 1996. Wrappers for feature subset selection. Artificial Intelligence,

special issue on relevance, p.273–324.

Kohavi, R. & Sommerfield, D., 1995. Feature subset selection using the wrapper method:

Overfitting and dynamic search space topology. In In Proceedings of the First International

Conference on Knowledge Discovery and Data Mining., 1995. AAAI Press.

Kononenko, I., 1995. On Biases in Estimating Multi-Valued Attributes. In 14th International

Joint Conference on Articial Intelligence., 1995.

Langley, P., 1994c. Selection of relevant features in machine learning. In In Proceedings of

the AAAI Fall Symposium on Relevance., 1994c. AAAI Press.

Langley, P. & Sage, S., 1994a. Induction of selective Bayesian classifiers. In Proceedings of the

Tenth Conference on Uncertainty in Artificial Intelligence. Seattle, 1994a. Morgan Kaufmann.

Langley, P. & Sage, S., 1994b. Oblivious decision trees and abstract cases. In In Working

Notes of the AAAI-94 Workshop on Case-Based Reasoning. Seattle, 1994b. AAAI Press.

Lin, C.-S. & Kim, H., 1991. CMAC-based adaptive critic self-learning control. In IEEE

Transactions on Neural Networks., 1991. IEEE.

Liu, H. & Motoda, H., 1998. Feature Selection for Knowledge Discovery and DataMining.

Norwell: Kluwer Academic Publishers.

Liu, H. & Setiono, R., 1996. A probabilistic approach to feature selection - A filter solution. In

13th International Conference on Machine Learning., 1996. Morgan Kaufmann.

Lu, H., Yuan, S. & Lu, S.Y., 1996. On preprocessing data for effective classification. In ACM

SIGMOD’96 Workshop on Research Issues on Data Mining and Knowledge Discovery., 1996.

ACM.


Matoušek, K. & Aubrecht, P., 2006. Data modelling and pre-processing for efficient data

mining in cardiology. In New Methods and Tools for Knowledge Discovery in Databases.,

2006. Information Society.

McCulloch, W. & Pitts, W., 1943. A Logical Calculus of Ideas Immanent in Nervous Activity.

Bulletin of Mathematical Biophysics, pp.115-33.

Michie, D. & Chamber, R.A., 1968. BOXES: An experiment in adaptive control. In Machine

Intelligence 2., 1968. Oliver and Boyd.

Mitchell, T.M., 1997. Machine Learning. New York: McGraw-Hill.

Oliveira, R. et al., 2009. A Data Mining Approach to Solve the Goal Scoring Problem. Neural

Networks, IEEE - INNS - ENNS International Joint Conference on Neural Networks, pp.2347-

52.

Quinlan, J.R., 1986. Induction of decision trees. Machine Learning, pp.81-106.

Quinlan, J.R., 1993. C4.5: Programs for machine learning. California: Morgan Kaufmann.

Riedmiller, M., 1999. Concepts and facilities of a neural reinforcement learning. Journal of

Dynamic Systems, Measurement, and Control, pp.323-38.

Riedmiller, M., 2005. Neural fitted Q iteration – first experiences with a data efficient neural

reinforcement learning method. In In 16th European Conference on Machine Learning.,

2005. Springer.

Riedmiller, M.A. et al., 2001. Karlsruhe brainstormers - a reinforcement learning approach to

robotic soccer. In RoboCup 2000: Robot Soccer World Cup IV. London, 2001. Springer-Verlag.

Rumelhart, D.E., Hinton, G.E. & Williams, R.J., 1986. Learning Internal Representations by

Error Propagation. Parallel Distributed Processing: Explorations in the Microstructure of

Cognition, pp.318-62.

Rummery, G.A., 1995. Problem Solving with Reinforcement Learning. PhDthesis, Cambridge

University.

Russell, S.J. & Norvig, P., 2003. Artificial Intelligence: A Modern Approach. 2nd ed. Prentice

Hall.


Shannon, C.E., 1948. A mathematical theory of communication. Bell System Technical

Journal, pp.379-423.

Shen, L., 2002. A law of large numbers and a central limit theorem for biased random

motions in random environment.

Silberchatz, A., Korth, H.F. & Sudarshan, S., 1999. Sistema de Banco de Dados. São Paulo:

Makron Books.

Stephenson, M., Amarasinghe, S., Martin, M. & O’Reilly, U.-M., 2002. Meta optimization:

Improving compiler heuristics with machine learning. In Proceedings of the ACM SIGPLAN’03

Conference on Programming Language., 2002. ACM Press.

Stone, P., 1998. Layered Learningin Multi-Agent Systems. PhD thesis, School of Computer

Science: Carnegie Mellon University.

Stone, P. & Sutton, R.S., 2001. Scaling reinforcement learning toward RoboCup soccer. In

Proc. 18th International Conf. on Machine Learning. San Francisco, 2001. Morgan Kaufmann.

Stone, P., Sutton, R.S. & Kuhlman, G., 2005. Reinforcement learning for robocup soccer.

Internationa lSociety for Adaptive Behavior, pp.165-88.

Sutton, R.S., 1988. Learning to predict by the methods of temporal differences. In Machine

Learning., 1988. Kluwer Academic Publishers.

Sutton, R.S. & Barto, A.G., 1998. Reinforcement Learning: An Introduction. Cambridge: The

MIT Press.

Tesauro, G., 1994. Td-gammon, a self-teaching backgammon program, achieves master-level

plays. Neural Computation, pp.215-19.

Vieira, D.C.L., Adeodato, P.J.L. & Gonçalves Jr., P.M., 2010. Improving Reinforcement

Learning Algorithms by the Use of Data Mining Techniques for Feature and Action Selection.

In Proceeding of the 2010 IEEE Conference on Systems, Man and Cybernetics (SMC2010).

Istanbul, 2010.

Watkins, C.J.C.H., 1989. Learning from Delayed Rewards. PhDthesis, Cambridge University.

Widrow, B., Gupta, N.K. & Maitra, S., 1973. Punish/Reward: Learning with a Critic in Adaptive

Threshold Systems. IEEE Transactions on Systems, Man, and Cybernetics, pp.455-65.


Widrow, B. & Hoff, M.E., 1960. Adaptive switching circuits. In 1960 WESCON Convention

Record Part IV. New York, 1960. Mit Press.

Documents

Pós-Graduação em Ciência da Computação · Paulemir Campos, Paulo Gonçalves e Rubens Bernante, ... d e f são jogadores, g é o goleiro e b é a bola. Os objetos são vistos