4o. SBAr- SimpósioBrasileirode Automação Inteligente, SãoPaulo, Sp,08-10de Setembrode 1999

APRENDIZADO DECOMPORTAMENTO PORREFORÇO DOAMBIENTE

Leonardo A. Scárduascardua@pcs.usp.br

. JoséJ. da Cruzjaime@lac.usp.br

AnnaH. R. Costaanna@pcs.usp.br

Departamento de Engenharia EletrônicaDepartamento de Engenharia de Computação e Sistemas Digitais

Escola Politécnica - Universidade de São Paulo.Av. Prof. Luciano Gualberto, Travessa 3, 158

Cidade Universitária - São Paulo - SPCEP: 05508-900

Resumo - Este artigo descreve um agente capaz de aprender aescolher suas ações de maneira a atingir seu objetivo ao enfrentarum adversário num ambiente dinâmico. O agente utiliza recom-pensas obtidas do ambiente para avaliar e aperfeiçoar a qualidadede seu próprio comportamento no domínio do futebol de robôs.Um rede neural é avaliada no que diz respeito a sua adequaçãocomo aproximador para a função valor de pares estado-ação nodomínio do futebol de robôs.

Palavras chave: aprendizado por reforço, redes neurais, apren-dizado de comportamento, futebol de robôs

1 INTRODUÇÃOA abordagem de aprendizado por reforço é uma alternativa muitoeficaz ao treinamento supervisionado de redes neurais . Ao invésde ter um professor externo que indica a saída correta para cadaentrada da rede neural, o aprendizado por reforço simplesmenteproduz um sinal de reforço que indica a qualidade da saída darede.

De acordo com (Sutton and Barto 1998), são quatro os princi-pais elementos de um sistema de aprendizado por reforço: umapolítica, uma função recompensa, uma função valor e, algumasvezes, um modelodo ambiente.

A politica é um mapeamento dos estados detectados para asações a serem tomadas em correspondência a esses estados.

A função recompensa define o objetivo em um problema deaprendizado por reforço. Em termos gerais, a função recom-pensa mapeia cada par fomiado por um estado s e uma ação a(ou apenas o estado s) em um único número. Este número indicao benefício, num sentido imediato, obtido por se escolher a açãoa quando no estado s.

A função valor indica o benefício que se pode esperar obter alongo prazo, por selecionar a ação a quando no estado s. Pode-se dizer que o valor de um par estado-ação, sob uma dada políti-ca, é o total de recompensa que um agente pode esperar receberquando, seguindo esta política, toma a ação a quando se encon-

171

tra no estado s. O único objetivo de um agente de aprendizadopor reforço é maximizar a recompensa total que ele obtém a lon-go prazo. Em outras palavras, ele busca ações que oconduzam aestados de valor mais elevado, sendo o valor de um estado defi-nido de maneira semelhante ao valor de um par estado-ação. Osmétodos para determinação dos valores dos estados, ou dos pa-res estado-ação são os componentes mais importantes de quasetodos os sistemas de aprendizado por reforço .

Em um contexto estocástico, um modelo que descreva as pro-babilidades de transição de estados e as recompensas imediatasresultantes destas transições não está usualmente disponível. Poresta razão, o agente de aprendizado por reforço aprende atravésde interação direta com o ambiente.

O objetivo principal da presente pesquisa é desenvolver umaequipe de agentes capaz de aprender um comportamento coope-rativo unicamente observando o impacto de suas ações sobre oambiente. Para atingir esta meta, foi desenvolvido um agente ca-paz de aprender a escolher suas ações observando as recompen-sas do ambiente . A primeira fase do desenvolvimento, descritaneste artigo, pretende avaliar uma rede neural (RN) no que dizrespeito à sua adequação como aproximador para a função valorde pares estado-ação no domínio do futebol de robôs.

O Servidor de Futebol RoboCup é um domínio simulado de fute-bol de robôs que permite a realização de jogos entre duas equipesde até 11 jogadores, onde cada jogador é controlado por um úni-co processo. O servidor opera em ciclos de simulação de 100 ms(este parâmetro é ajustável, sendo 100 seu valor usual (Andre etalo 1999)). Ele requer que os agentes atuem em tempo real. Asalterações no ambiente são influenciadas pelas ações de ambasas equipes de agentes. Esta combinação de características o tor-na um domínio bastante complexo e realista, onde as decisõessão tomadas em etapas e a saída de uma decisão não pode sercompletamente prevista. Cada decisão produz alguma recom-pensa imediata e afeta o ambiente, influenciando a recompensarecebida pela próxima decisão a ser tomada .

O.agente aprendiz é essencialmente um agente de aprendizadopor reforço cujo objetivo principal é obter a máxima recompensa .a longo prazo. Este objetivo pode ser atingido escolhendo a açãoque possui o maior valor em face do sinal do estado atual. Oagente deve aprender ao mesmo tempo em que interage com oambiente, uma vez que ele não dispõe de conhecimento prévio arespeito da tarefa ou do domínio em questão .

240. SBAI - Simpósio Brasileiro de Automação Inteligente, São Paulo, Sp,08-10 deSetembro de 1999

O AGENTE APRENDIZ Isto impõe o uso de um aproximador para a função valor. Aarquitetura escolhida deve atender no mínimo às seguintes con-dições :

• Como não é possível saber de antemão as características dafunção valor num dado domínio , a arquitetura de aproxi-mação deve ser um bom aproximador genérico ao menospara funções contínuas .

Já que não é prático utilizar tabelas na memória para armazenaro valor correspondente a cada par estado-ação que pode ser ex-perimentado pelo agente (veja a Seção 2. 1), decidiu-se usar umaRN para aproximar tais valores.

A estrutura do agente é muito simples, mas, ainda assim, muitoeficiente. Sua operação pode ser descrita pelo seguinte algorit-mo:

1. Obtenha o estado do ambiente.

·2. Se o momento é de escolha da melhoração:

(a) Use a RN para avaliar cada uma das ações possíveisà luz do sinal de estado.

(b) Escolha a ação que tem o melhor valor estimado.

3. Se o momentoé de escolha aleatória:

(a) Escolha aleatoriamente dentre os elementos do con-junto de ações possíveis.

4. Execute a ação escolhida.

5. Obtenha a recompensa.

6. Atualize o valor estimado da RN.

2.1 O Estado do AmbienteNeste trabalho, consideram-se jogos com apenas dois jogado-res, sem goleiros . Um jogador utiliza a estrutura de aprendizadoapresentada ao passo que o outro escolhe suas ações aleatoria-mente. O jogador aprendiz percebe o ambiente de acordo com oseguinte sinal de estado:

• O ângulo da bola com relação ao agente aprendiz;

• A distância da bola ao agente aprendiz;

• O ângulo do adversário com referência ao agente aprendiz;

• A distância do adversário ao agente aprendiz.

Conforme (Andre et ai. 1999), o tamanho do campo é 105 x68 unidades, onde a unidade é irrelevante. A função arctan éutilizada para calcular os ângulos relativos acima. Não é feitadiscrctização alguma das distâncias e ângulos relativos calcula-dos. Como o servidor opera com precisão de ponto flutuante, háem realidade um espaço de estados de dimensão enorme.

2.2 Porque Uma Rede Neural Como Aproxi-mador da Função Valor

Está claro que a representação escolhida para o estado, toma im-praticável manter em tabelas os valores dos pares estado-ação.

172

• Deve ser capaz de lidar com ambientes ruidosos.

• Deve ser capaz de trabalhar em tempo real.

O Teorema de Existência do Mapeamento Neural de Kolmogorov(Hetch-Nielsen 1990) provê a sustentação matemática para o usode perceptronsde três camadas como aproximadores universaispara funções contínuas.

2.3 Codificando o Objetivo do Agente Comoum Sinal de Recompensa

No contexto de aprendizado por reforço, o sinal de recompensaé utilizado para codificar o que se deseja que o agente faça. Istoocorre no caso presente, onde a recompensa que se segue à es-colha de cada ação é usada para informar o agente se a escolhafoi "boa" ou "má".

Neste trabalho, considera-se "boa" a escolha de uma ação quetenha todas as suas pré-condições (restrições que, dado o sinaldo estado atual, devem ser obedecidas de forma que a ação sejaaplicável) satisfeitas pelo sinal do estado que o agente percebedo ambiente . Neste caso o sinal de recompensa é positivo.

Se alguma das pré-condições da ação escolhida não é satisfeita,o sinal de recompensa é negativo. Em outras palavras, o objetivocodificado é aprender a escolher ações que tenham todas as pré-condições satisfeitas pelo sinal do estado recebido. Tanto esteobjetivo, quanto o método aqui usado para calcular a recompen-sa, são destinados apenas a prover um meio simples e válido,para avaliar a rede neural como aproximador da função valorneste domínio.

2.4 Aprendizado do Valor de um Par Estado-Ação

Para aprender este valor, a RN é alimentada com a ação escolhi-da pelo agente e com o sinal de estado detectado. A saída darede deve ser igual à recompensa recebida imediatamente pe-lo agente. Em outras palavras, "valor" aqui tem o significadode recompensa imediata. Contudo, dado o objetivo proposto aoagente, não énecessário estimar o valor dos pares ação-estado,no sentido amplo da teoria do aprendizado por reforço; o apren-dizado das recompensas imediatas será suficiente no caso destetrabalho.

Se a RN for capaz de aprender as recompensas imediatas, serácapaz de aprender os valores dos pares estado-ação, como calcu-lados usualmente na solução de problemas de aprendizado porreforço .

2.5 A Rede NeuralA RN é um perceptron multi-camada totalmente conectada. Hásete neurônios de entrada, dez neurônios na camada escondida

RESULTADOSPara avaliar a eficácia da abordagem proposta, foram realizadosexperimentos consistindo numa série de jogos de 10 minutos. Oagente aprendiz enfrenta um adversário que escolhe suas açõesaleatoriamente, sendo esta a única diferença entre eles.

3

Se o agente aprendiz efetivamente aprender a escolher ações emque as pré-condições estão satisfeitas pelo estado do ambiente,ele será capaz de vencer um agente com seleção de ações aleató-ria.

40. SBAI - SimpósioBrasileiro deAutomação Inteligente, São Paulo, Sp,08-10 de Setembrode 1999

e um na camada de saída . Os neurônios da camada escondi- consistentemente, se não enfrentar oposição.da utilizam a tangente hiperbólica como função de ativação, aopasso que o neurônio de saída apenas soma todas as suas entra-das. O método de treinamento é o algoritmo de retro-propagação(Haykin 1999).

Na camada de entrada, foi deixado um neurônio para cada va-riável de estado existente e para cada ação possível, perfazendoo total de dez neurônios. A lógica que norteou a escolha donúmero de neurônios na camada intermediária foi a de ter umaunidade de processamento escondida para cada variável de en-trada da rede, enquanto a escolha da configuração da camada desaída é justificada por se desejar um único valor como resultadodo processamento da rede.

Os resultados, apresentados nas Tabelas 1 e 2 e Figura 1, mos-tram que neste caso, ambos os jogadores apresentam o mesmodesempenho.

Experimento 1 - O agente aprendiz sempre seleciona uma açãoaleatória e não aprende a partir das recompensas recebidas doambiente. Portanto, o agente aprendiz na realidade age exata-mente como um jogador aleatório. O objetivo deste experimentoé avaliar o desempenho de dois jogadores aleatórios.

2.6 Escolha da Melhor AçãoA escolha é baseada unicamente no sinal de estado recebido pe- .lo agente. No instante de escolher urna ação, o agente alimentaa entrada da RN com o sinal de estado atual e com a ação queestá sendo avaliada; a saída da RN é então armazenada. Esteprocedimento é repetido para cada ação existente e o' agente es-colhe aquela que produz a saída da RN de valor numérico maiselevado.

Cada acão passível de escolha pelo agente, é implementada porurna rotina (ver seção 2.7) e identificada unicamente por um nú-mero positivo.

3.1 Resultados Experimentais

2.7 Conjunto de AçõesCada agente dispõe de um conjunto de três ações , onde cada açãoé implementada por uma rotina que possui todas as informaçõesnecessárias à execução da ação .

2.7.1 Alcancea Bola

Pré-condições: A bola não pode estar dentro de uma distânciade chute do agente.

Efeito: Move o agente na direção da bola . Quando o agenteatinge a bola, ele pára a uma distância de chute dela.

Número do Jogo Jogador Aprendiz Jogador Aleatôrio1 5 22 2 53 3 44 4 45 3 56 4 37 3 58 5 49 5 510 6 4

2.7.2 Chuteem Direção ao Gol Adversário Tabela 1: O placar de cada partida no experimento 1.

Pré-condições: A bola deve estar a urna distância de chute doagente.

Efeito: A bola é chutada em direção ao gol adversário.

2.7.3 Girea Bola

Pré-condições: A bola deve estar a urna distância de chute doagente e atrás dele com relação ao gol adversário. .

Efeito: A bola é girada em direção ao gol adversário e mantida auma distância de chute do agente até se localizar na direção dogol, quando então é chutada.

Estatísticas Jogador Aprendiz JogadorAleatórioNúmero de gols 40 41Número de vitórias 4 4

2.8 Ciclo de Decisão Tabela 2: Algumas estatísticas referentes ao experimento 1.

Ambos os agentes devem decidir qual ação cada um tomará acada ciclo de simulação. O conjunto de ações e o curto ciclo desimulação permitem que mesmo o agente aleatório marque gols

173

40. SBAI - SimpósioBrasileiro de Automação Inteligente, São Paulo, SP, 08-10 de Setembro de 1999

Gols Gols10 • • . . . • . 109 "Aprendiz_Exp_l11 9 "Aprendiz_Exp_2 118 87 "Aleatorio_Exp_l11 -+-- • 7 "Aleatorio_Exp_2" -+--

6 · 65 · 54 r-, 43V :32 · 21 . . • . • • . . 11 2 3 4 5 6 7 8 9 10 1 2 3 4 ·5 6 7 8 9 10

Jogos Jogos

Figura 1: Placar médio no experimento 1.

Experimento 2 - Aleatoriamente com probabilidades 0.2 e 0.8 , .respectivamente, uma das seguintes escolhas é feita:

1. A ação de maior valor é selecionada.

2. Uma ação do conjunto de ações disponíveis é selecionadaaleatoriamente.

Inicialmente os pesos da RN foram escolhidos aleatoriamente,sendo depois alterados de acordo com o processo de aprendiza-do ao longo de cada jogo. O objetivo deste experimento é avaliaro efeito do processo de aprendizado sobre o desempenho do jo-gador.

Os resultados apresentados nas Tabelas 3 e 4, e na figura 2, mos-tram que neste caso, o agente aprendiz está se tomando superiorna medida que aumenta o número de jogos.

Númerodo Jogo JogadorAprendiz JogadorAleatório1 5 52 9 33 2 74 3 55 6 26 6 27 2 68 6 39 7 210 5 2

Tabela 3: O placar de cada partida no experimento 2.

Estatísticas JogadorAprendiz JogadorAleatórioNúmero de gols 51 37Número de vitórias 6 3

Tabela 4: Algumas estatísticas referentes ao experimento 2.

174

Figura 2: Placar médio no experimento 2.

Experimento3 - As escolhas 1 e 2 definidas no Experimento 2foram feitas aqui aleatoriamente, porém com probabilidades 0.8e 0.2, respectivamente.

Da mesma forma que no Experimento 2, inicialmente os pesosda RN foram escolhidos aleatoriamente, sendo depois alteradosde acordo com o processo de aprendizado ao longo de cada jogo.

Também aqui, o objetivo é avaliar o efeito do processo de apren-dizado sobre o desempenho do jogador.

Os resultados apresentados nas Tabelas 5 e 6, e na figura 3, mos-tram que neste caso, o agente aprendiz se toma muito superiorna medida que aumenta o número de jogos.

Númerodo Jogo JogadorAprendiz JogadorAleatório1 6 42 7 23 5 44 10 25 7 36 7 37 7 28 8 49 . 9 410 10 2

Tabela 5: O placar de cada partida no experimento 3.

Estatfsticas JogadorAprendiz JogadorAleatórioNúmero de gols 76 30Número de vitórias 10 O

Tabela 6: Algumas estatísticas referentes ao experimento 3.

6 CONCLUSÕESO agente aprendiz proposto aprendeu a escolher suas ações uti-lizando unicamente as recompensas obtidas da interação com oambiente. É importante enfatizar que ele não dispunha de qual-quer conhecimento prévio a respeito do domínio de futebol derobôs. A RN aprendeu a jogar apenas observando as recompen-sas obtidas ao jogar.

Leonardo A. Scardua é apoiado pelo CNPq, através do proces-so No. 141802/97-9. Anna H.R. Costa recebe o apoio parcialda Fapesp, através do processo No. 98/06417-9. José J. daCruz é apoiado parcialmente pelo CNPq, através do processoNo. 304071/85-4 (RN).

7 AGRADECIMENTOS

Um aspecto importante a ser salientado é que o aprendizado éfocado naturalmente na trajetória de estados seguida pelo agen-te aprendiz. Este aspecto reduz enormemente a complexidadedo espaço de estados, explicando o rápido aprendizado que per-mitiu ao agente vencer todos os jogos no terceiro experimento,mesmo tendo no início utilizado pesos aleatórios na RN. A pri-meira etapa do desenvolvimento desta pesquisa, descrita nesteartigo, objetivou estudar uma RN como um avaliador de açõesno domínio do futebol de robôs . Os resultados obtidos são ani-madores . O próximo passo deverá consistir em fazer o agenteaprender apenas através da observação dos resultados dos jogos .

O futebol de robôs requer que o agente aprenda e aja em temporeal. A saída de cada ação não é completamente previsível devi-do ao ruído aleatório introduzido pelo Servidor de Futebol Robo-Cup. As alterações no ambiente são influenciadas pelas ações deambas as equipes de agentes. Esta combin ação de fatores tornaeste domínio bastante complexo e realista. Essa complexidadepermite afirmar que a tecnologia em desenvolvimento pode seraplicada a tarefas reais que requerem o aprendizado de uma polí-tica de controle em um ambiente em que o espaço de estados éenorme. Alguns exemplos práticos importantes são o problemado despacho de elevadores e a alocação dinâmica de canais emsistemas de telefonia celular (Sutton and Barto 1998).

REFERÊNCIASBIBLIOGRÁFICAS

9 10

"

876

"

5

40. SBAI - SimpósioBrasileirode Automação Inteligente, São Paulo, Sp,08-10 de Setembrode 1999

estão os algoritmos genéticos (Kuzuaki et ai. 1998),(Matsumura1998), a programação genética (Andre and Teller 1998), o ra-ciocínio baseado em caso C'case-based reasoning") (Burkhard et

"Aprendiz_Exp_3" alo1998) e o aprendizado por reforço (Andou 1998) .

43

Gols10 ,-_,_--,-...---,.-,---r-r---r---,98765432l'----'--..L.---I.-...a---I........II--...........--1 2

Os resultados da simulação mostram que:

• O número médio de gols por jogo do jogador aleatório di-minui consistentemente .a medida que aumenta a probabi-lidade de selecionar a ação de maior valor para o agenteaprendiz;

Figura 3: Placar médio no experimento 3.

4 DISCUSSÃO

ct O número médio de gols por jogo do jogador aprendiz au-menta consistentemente a medida que aumenta a probabili-dade de selecionar a ação de maior valor;

• O número de vitórias do agente aprendiz aumenta consis-tentemente, chegando a atingir lO, na medida que aumentaa probabilidade de selecionar a ação de maior valor.

Uma vez que a única diferença entre os três experimentos é aprobabilidade de o agente aprendiz selecionar a ação de melhorestimativa, é claro que esta é a causa das alterações nas estatís-ticas dos experimentos . Por causa do fato de que o aumentodesta probabilidade melhorou o desempenho do agente aprendize deteriorou o do jogador aleatório, é claro também que o agenteaprendiz extraiu um aprendizado útil do mecanismo definido. Is-to permitiu ao agente aprendiz consistentemente vencer o agentealeatório.

Estes resultados tomam claro o fato de que um perceptron multi-camada é capaz de aproximar a função valor para um agente deaprendizado por reforço, no domínio do futebol de robôs.

Jogos

5 TRABALHOS CORRELATOSO trabalho relatado neste artigo foi inspirado no Gamão-ID deTesauro (Tesauro 1995), uma RN que é capaz de se auto-ensinara jogar gamão jogando contra si própria e aprendendo a par-tir dos resultados. O "backgammon", assim como o futebol derobôs , é um domínio em que as decisões são tomadas em eta-pas, com um elevado número de estados possíveis, o que tomaimpossível a utilização de uma abordagem de aprendizado super-visionado para a RN. Ambos os domínios envolvem jogo contraum adversário desconhecido.

Andou, Tomolúto (1998). A robocup team which reinforces po-sition observationally. In: Proceedings of the Second Ro-boCup Workshop. Paris. pp. 361-363.

Andre, David and Astro Teller (1998). Evolving team darwinunited. In: Proceedings ofthe Second RoboCup Workshop.Paris. pp. 317-323.

Andre, David, Corten E., Dorer K., Gugenberger P., Joldos M.,Kummeneje i; Navratil I P., Itsuki N., Riley P., Stone P.,Takahashi T. and Yeap T. (1999). Soccerserver manual. In:www.dsv.su.se/johank/RoboCup/manual.

Muitos pesquisadores têm usado métodos de aprendizado nodomínio do futebol de robôs . Entre os métodos mais comuns

Burkhard, Hans-Dieter, Jan Wendler, Pascal Gugenberger,Kay Schroder and Ralf Kuhnel (1998). At-humboldt in

175

40. SBAI - SimpósioBrasileiro de Automação Inteligente, São Paulo. SP, 08-10 de Setembro de 1999

robocup-98. In: Proceedings of the Second RoboCupWorkshop. Paris. pp. 331-337.

Haykin, Simon (1999).Neural Networks: a comprehensivefoun-dation 2nd ed. Prentice-Hall.

Hetch-Nielsen, Robert (1990) . Neurocomputing. Addison Wes-ley. New York.

Kuzuaki, Endo, Ito Sadaharu, Hiroyuki Yamaguchi, Ibui Nobuoand Kotani Yoshiyuki (1998) . Team description for don-guri. In: Proceedings of the Second RoboCup Workshop.Paris. pp. 305-308.

Matsumura, Takeshi (1998). Description of team erika. In : Pro-ceedings ofthe SecondRoboCup Workshop.Paris. pp. 309-315. .

Sutton, Richard S. and Andrew G. Barto (1998). ReinforcementLearning: an introduction. Addison Wesley.MIT Press.

Tesauro, Gerald (1995). Temporal difference learning and td-gammon. Communications ofthe ACM 38(3) ,815-825.

176