Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
DESENVOLVIMENTO DE UM SISTEMA DE APRENDIZADO POR REFORCO ¸ ˆ - UMA ANALISE ´ PARA TIMES DE ROBOS DE DESEMPENHO POR MEIO DE TESTES ESTAT´ ISTICOS ´ Luiz Carvalho Ottoni∗, Rubisson Duarte Lamperti†, Erivelton Geraldo Andre Nepomuceno∗, Marcos Santos de Oliveira‡ ∗
Grupo de Controle e Modelagem, Departamento de Engenharia El´etrica, Universidade Federal de S˜ ao Jo˜ ao del-Rei, Pra¸ca Frei Orlando, 170, Centro, 36307-352 - S˜ ao Jo˜ ao del-Rei, MG, Brasil
†
Grupo de Controle e Modelagem, Programa de P´ os-Gradua¸ca ˜o em Engenharia El´etrica, Universidade Federal de S˜ ao Jo˜ ao del-Rei, Pra¸ca Frei Orlando, 170, Centro, 36307-352 - S˜ ao Jo˜ ao del-Rei, MG, Brasil ‡
Departamento de Matem´ atica e Estat´ıstica, Universidade Federal de S˜ ao Jo˜ ao del-Rei, Pra¸ca Frei Orlando, 170, Centro, 36307-352 - S˜ ao Jo˜ ao del-Rei, MG, Brasil
Emails:
[email protected],
[email protected],
[email protected],
[email protected] Resumo— O presente trabalho apresenta uma metodologia de modelagem da t´ ecnica de aprendizado por refor¸co para times de futebol de robˆ os 2D. A implementa¸c˜ ao da estrat´ egia de aprendizagem consiste de quatro etapas: defini¸ca ˜o e discretiza¸ca ˜o das a¸c˜ oes dos agentes; defini¸c˜ ao e discretiza¸c˜ ao dos estados do ambiente no qual os agentes est˜ ao inseridos; defini¸c˜ ao dos valores dos refor¸cos da tabela R, para cada par Estado (S) X A¸ca ˜o (A); implementa¸c˜ ao no Simulador RcSoccerSim da Robocup de Futebol de Robˆ os. Al´ em disso, ´ e proposta uma an´ alise estat´ıstica por meio do teste T-Pareado para compreender o sistema de aprendizagem quando submetido ` a competi¸c˜ ao entre outros times. Palavras-chave—
Aprendizado por Refor¸co, Futebol de Robˆ os, An´ alise Estat´ıstica
Abstract— This paper presents a methodology for modeling the technique of reinforcement learning for teams of robots 2D. The implementation of the learning strategy consists of four steps: definition and discretization of the actions of agents; definition and discretization of the states of the environment in which the agents are inserted, defining the values of the reinforcement R table for each pair state (S) X Action (A), implementation of the simulator of RoboCup Robot Soccer. Furthermore, we propose a statistical analysis by paired t-test to understand the learning system when subjected to competition from other teams. Keywords—
Reinforcement Learning, Robot Soccer, Statistical Analysis
1
Introdu¸ c˜ ao
A possibilidade do desenvolvimento de m´aquinas ou sistemas Inteligentes tem sido o alvo de pesquisadores de diversas partes do mundo (Russell, 2004). Na d´ecada de 90, as m´ aquinas inteligentes tornaram-se realidade e est˜ ao cada vez mais presentes na sociedade (Nascimeno Jr., 2009; Texeira et al., 2009; Lacerda et al., 2009a; Garcia, 2003; Lacerda et al., 2009b). Dentre os diversos exemplos da utiliza¸c˜ ao de m´aquinas inteligentes est˜ao: o uso de sistemas especialistas em tomadas de decis˜ oes, o uso da Inteligˆencia Computacional para o controle de processos industriais, e a utiliza¸c˜ao de robˆ os na realiza¸c˜ ao de tarefas repetitivas ou de elevado risco para o ser humano. A complexidade de algumas tarefas pode se tornar ainda maior quando se trata de m´ aquinas autˆonomas, ou seja, m´aquinas capazes de estabelecerem a¸c˜oes devido a eventos dinˆ amicos imprevis´ıveis (Kim and Oh, 2010). Por´em, a evolu¸c˜ao nesse cen´ario traz grandes avan¸cos `as pesquisas tecnol´ogicas (Garcia, 2003). A Inteligˆencia Artificial (IA) ´e uma ´area da ciˆencia que desenvolve a autonomia de m´aqui-
ISBN: 978-85-8001-069-5
nas. V´arias t´ecnicas de inteligˆencia artificial s˜ao adotadas como, algoritmos gen´eticos (Fraccaroli, 2010a), aprendizado por refor¸co (Silva et al., 2010; Kerbage et al., 2010), aprendizado por refor¸co acelerado por heur´ısticas (Celiberto Jr, 2006), redes neurais artificiais (Sim˜oes et al., 2007) e sistemas fuzzy (Fraccaroli, 2010a) na tentativa de encontrar a melhor solu¸c˜ao para o problema. O Aprendizado por Refor¸co (AR) ´e uma t´ecnica de aprendizado, na qual o agente aprende por meio de intera¸c˜ao direta com o ambiente e seu algoritmo converge para uma situa¸c˜ao de equil´ıbrio (Sutton, 1998). No AR, um agente pode aprender em um ambiente n˜ao conhecido previamente, por meio de experimenta¸c˜oes. Dependendo de sua atua¸c˜ao, o agente recebe uma recompensa ou uma penaliza¸c˜ao e, desta forma, o algoritmo encontra um conjunto de a¸c˜oes que levam o agente a percorrer o caminho ´otimo. A este conjunto, formado pelas melhores a¸c˜oes, d´a-se o nome de pol´ıtica ´otima. Na busca de desenvolver a Inteligˆencia Artificial (IA) e a rob´otica, uma importante organiza¸c˜ao internacional, a Robocup, escolheu o jogo de futebol como o principal t´opico de pesquisa, procurando inova¸c˜oes que pudessem ser aplicadas
3557
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
em problemas reais. Para o desenvolvimento de times de robˆ os s˜ ao necess´ arias v´ arias tecnologias, como exemplo a coopera¸c˜ ao de sistemas multiagentes, a aquisi¸c˜ ao de estrat´egias, o sensoreamento em tempo real, a fus˜ ao de sensores, entre outros. A categoria de simula¸c˜ ao 2D da Robocup simula partidas de futebol de robˆ os autˆonomos. Nesta liga existem robˆ os (agentes) virtuais, o qual todo o ambiente ´e simulado. Um simulador fornece aos agentes todos os dados que seriam obtidos na realidade por meio dos seus sensores e calcula o resultado das a¸c˜ oes de cada agente. Cada jogador ´e visto como um agente individual, e o time como um sistema multiagente totalizando 11 (onze) jogadores por equipe. Este trabalho apresenta uma metodologia para a Aprendizagem por Refor¸co para times de futebol de robˆ os 2D. Al´em disso, ´e proposta uma an´alise estat´ıstica por meio do teste T-Pareado para compreender o sistema de aprendizagem quando submetido `a competi¸c˜ ao entre equipes que utilizam de outras t´ecnicas de inteligˆencia artificial. Este artigo est´ a organizado em se¸c˜ oes, a qual a Se¸c˜ao 2 introduz o conceito da Aprendizagem por refor¸co, algoritmo Q-learning (Watkins, 1989), e o teste T-Pareado (Hines et al., 2006). Na Se¸c˜ao 3 ´e apresentada a implementa¸c˜ ao da Estrat´egia de Aprendizagem, por meio da Discretiza¸c˜ao das A¸c˜oes, dos Estados e a Defini¸c˜ ao da Matriz de Recompensa. A an´ alise dos resultados obtidos ´e apresentada Se¸c˜ ao 4. Em seguida, a conclus˜ao do trabalho ´e apresentada na Se¸c˜ ao 6. 2 2.1
Fundamenta¸ c˜ ao Te´ orica
Processos de Decis˜ ao de Markov
Um Processo de Decis˜ ao de Markov (MDP - Markov Decision Process) ´e uma forma de modelar processos, na qual as transi¸c˜ oes entre estados s˜ao probabil´ısticas. No MDP ´e poss´ıvel observar e interferir no processo periodicamente executando a¸c˜oes (Bertsekas, 2001; Puterman, 1994). Cada a¸c˜ao tem uma recompensa, a qual depende do processo. A defini¸c˜ ao de recompensas pode ser dada em fun¸c˜ao apenas do estado, sem que estas dependam da a¸c˜ao executada. Os processos s˜ao ditos de Markov (ou Markovianos) quando s˜ao modelados obedecendo `a propriedade de Markov, ou seja, o efeito de uma a¸c˜ ao em um estado depende apenas da a¸c˜ao e do estado atual do sistema, e n˜ao de como o processo chegou a tal estado. Os processos de decis˜ao modelam a possibilidade de um agente (ou tomador de decis˜ oes) interferir periodicamente no sistema executando a¸c˜ oes, diferentemente da Cadeia de Markov, na qual n˜ao se interfere no processo. MDPs podem ser aplicados diversas ´areas (White, 1993). A cada ´epoca de decis˜ ao, o agente tomador
ISBN: 978-85-8001-069-5
de decis˜oes usa uma regra de decis˜ao para escolher a pr´oxima a¸c˜ao. Uma forma simples de regra de decis˜ao ´e um mapeamento direto de estados em a¸c˜oes. O conjunto de todas as regras de decis˜ao (uma para cada ´epoca de decis˜ao) ´e chamado de pol´ıtica. Normalmente, o objetivo ´e encontrar uma pol´ıtica que otimize um crit´erio de desempenho das decis˜oes. Uma especifica¸c˜ao das probabilidades de resultados para cada a¸c˜ao em cada estado poss´ıvel ´e chamada de modelo de transi¸c˜ao, denotado por T (s, a, s). T (s, a, s) ´e utilizado para denotar a probabilidade de alcan¸car o estado s′ se a a¸c˜ao a for executada no estado s (Russell, 2004). Um MDP ´e definido pela qu´adrupla (S, A, T, R) onde (Bianchi, 2004): • S: ´e um conjunto finito de estados do ambiente; • A: ´e um conjunto finito de a¸c˜oes que o agente pode realizar; • T : SxA → Π(S): ´e a fun¸c˜ao de transi¸c˜ao de estado, onde Π(S) ´e uma fun¸c˜ao de probabilidades sobre o conjunto de estados S. T (st , at , st+1 ) define a probabilidade de realizar a transi¸c˜ao do estado st para o estado st+1 quando se executa a a¸c˜ao at . • R : SxA → R: ´e a fun¸c˜ao de recompensa, que especifica a tarefa do agente, definindo a recompensa recebida (ou o custo esperado), ao longo do tempo. Resolver um MDP consiste em computar a pol´ıtica π: SxA que maximiza (ou minimiza) alguma fun¸c˜ao, geralmente a recompensa recebida (ou o custo esperado), ao longo do tempo (Bianchi, 2004). Na se¸c˜ao 2.2 ser´a mostrada a t´ecnica de Aprendizagem por Refor¸co, na qual ´e fundamentada nos Processos de Decis˜ao de Markov. 2.2
Aprendizado Por Refor¸co
O Aprendizagem por refor¸co (AR) ´e um formalismo da IA que permite a um agente aprender a partir da sua intera¸c˜ao com o ambiente no qual ele est´a inserido (Watkins, 1992; Neri et al., 2011). A ideia central da t´ecnica de aprendizado por refor¸co ´e que as percep¸c˜oes s˜ao utilizadas n˜ao apenas para agir, mas ao mesmo tempo, para melhorar a habilidade do agente para agir no futuro. A aprendizagem ocorre `a medida que o agente observa suas intera¸c˜oes com o ambiente e com seus pr´oprios processos de tomada de decis˜ao. Normalmente, o tipo de realimenta¸c˜ao dispon´ıvel para o aprendizado ´e um fator importante na determina¸c˜ao da natureza do problema (Russell, 2004). O aprendizado por refor¸co pode ser entendido como uma forma dos agentes aprenderem o que
3558
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
fazer, particularmente quando n˜ao existe nenhum professor dizendo ao agente que a¸c˜ ao ele deve executar em cada circunstˆ ancia. Para isso, o agente precisa saber que algo de bom aconteceu quando ganhar, e que algo de ruim aconteceu quando perder. Essa esp´ecie de realimenta¸c˜ ao ´e chamada de recompensa ou refor¸co (Russell, 2004). 2.2.1
Algoritmo Q-learning
O m´etodo de aprendizagem por refor¸co Q-learning (Watkins, 1992; Neri et al., 2011) ´e um algoritmo que permite estabelecer autonomamente uma pol´ıtica de a¸c˜oes de maneira interativa. A ideia b´ asica do Q-learning ´e que o algoritmo de aprendizagem aprende um fun¸c˜ ao de avalia¸c˜ao ´otima sobre todo o espa¸co de pares estado-a¸c˜ao SxA. Desde que o particionamento do espa¸co de estados do robˆ o e do espa¸co de a¸c˜ oes n˜ao omita e n˜ao introduzam novas informa¸c˜ oes relevantes. Quando a fun¸c˜ ao ´otima Q for aprendida, o agente saber´a qual a¸c˜ ao resultar´ a na maior recompensa em uma situa¸c˜ ao particular s futura (Monteiro, 2004). A fun¸c˜ao Q(s, a) de recompensa futura esperada ao se escolher a a¸c˜ ao a no estado s, ´e aprendida atrav´es de tentativa e erro segundo a Equa¸c˜ao (1): Qt+1 = Qt (st , at )+α[rt +γVt (st+1 )−Qt+1 (st , at )] (1) onde α ´e a taxa de aprendizagem, rt ´e a recompensa, resultante de tomar a a¸c˜ ao a no estado s, γ ´e fator de desconto e o termo Vt (st+1 ) = maxa Q(st+1 , at ) ´e a utilidade do estado s resultante da a¸c˜ao a, obtida utilizando a fun¸c˜ ao Q que foi aprendida at´e o presente (Monteiro, 2004). A pol´ıtica de a¸c˜ oes adotada foi a ε-gulosa(εGreedy), onde o agente tem grande probabilidade de escolher a a¸c˜ ao a com o maior refor¸co Q(s, a) no estado s. A forma procedimental do algoritmo Qlearning ´e (Watkins, 1992; Monteiro, 2004): Para cada s,a inicialize Q(s,a)=0 Observe s Repita • Selecione a¸c˜ ao a usando a pol´ıtica de a¸c˜ oes ε-gulosa • Execute a a¸c˜ ao a • Receba a recompensa imediata r(s,a) • Observe o novo estado s’ • Atualize o item Q(s,a) de acordo com a equa¸c˜ ao (1) • s ← s’ At´e que crit´erio de parada seja satisfat´ orio
ISBN: 978-85-8001-069-5
2.3
Futebol de Robˆ os Simulado
A categoria de simula¸c˜ao 2D da Robocup simula partidas de futebol de robˆos autˆonomos. O simulador apresenta caracter´ısticas de um ambiente dinˆamico, ruidoso, cooperativo e coordenado (Fraccaroli, 2010a). Nesta liga n˜ao existem robˆos/agentes f´ısicos, todo o ambiente e os agentes s˜ao virtuais. O simulador fornece aos agentes todos os dados que s˜ao obtidos na realidade por meio de sensores e calcula o resultado das a¸c˜oes de cada agente. A simula¸c˜ao 2D permite definir as estrat´egias de jogo para um time de robˆos formado por doze agentes robˆos. Cada partida realizada tem dura¸c˜ao de aproximadamente dez minutos, valor este correspondente a seis mil ciclos de simula¸c˜ao, sendo separado em dois tempos de aproximadamente cinco minutos (Fraccaroli, 2010b). 2.3.1
Time Base Agent2D (Helios Base)
O time Helios (Akiyama et al., 2011) do Jap˜ao, foi o campe˜ao da categoria de simula¸c˜ao 2D da Robocup em 2010 e 2012. Os desenvolvedores resolveram disponibilizar na Internet o c´odigo base do time. Essa iniciativa veio para facilitar o surgimento de novas equipes na categoria de simula¸c˜ao 2D da Robocup. Foi escolhido utilizar o c´odigo base do Helios (Agent2D) pois ele disponibiliza algumas habilidades b´asicas j´a implementas, como intercepta¸c˜ao de bola, chute, drible e movimenta¸c˜ao. Al´em disso, j´a oferece implementado a conex˜ao com o RoboCup Soccer Server, servidor de execu¸c˜ao dos jogos 2D da Robocup, criada atrav´es de um socket, que possibilita enviar e receber mensagens. 2.3.2
Time UaiSoccer2D (UFSJ)
Na UFSJ o time de futebol de robˆos simulado ´e o UaiSoccer2D (Ottoni et al., 2012). O Time UaiSoccer2D, que foi analisado neste trabalho, foi resultado da implementa¸c˜ao do aprendizado por refor¸co e modifica¸c˜oes na estrutura do Agent2D. A Equipe UaiSoccer2D utiliza testes estat´ısticos para verificar o comportamento do sistema multiagente cooperativo (time de robˆos) de acordo com a estrat´egia de jogo utilizada (Ottoni et al., 2011). Nas pr´oximas se¸c˜oes, ´e feita uma breve introdu¸c˜ao sobre a an´alise estat´ıstica empregada neste trabalho. 2.4
Hip´ oteses Estat´ısticas
Uma hip´otese estat´ıstica ´e uma afirmativa sobre a distribui¸c˜ao de probabilidade de uma vari´avel aleat´oria. Os procedimentos de teste de hip´otese se ap´oiam no uso de informa¸c˜ao em uma amostra aleat´oria da popula¸c˜ao de interesse. Para testar uma hip´otese, ´e necess´ario extrair uma amostra
3559
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
aleat´oria, calcular uma estat´ıstica de teste apropriada a partir dos dados amostrais e, ent˜ao, usar a informa¸c˜ao contida na estat´ıstica de teste para tomar a decis˜ ao (Hines et al., 2006).
1. Defini¸c˜ao e discretiza¸c˜ao das a¸c˜oes dos agentes;
2.5
3. Defini¸c˜ao dos valores dos refor¸cos da tabela R, para cada par Estado (S) X A¸c˜ao (A);
Teste t Emparelhado
O Teste t Emparelhado (teste t-pareado) de duas amostras ocorre quando as observa¸c˜ oes sobre as duas popula¸c˜ oes s˜ ao coletadas aos pares. Cada par de observa¸c˜ oes (X1j , X2j ), ´e extra´ıdo sob condi¸c˜oes idˆenticas, mas essas condi¸c˜ oes podem mudar de um para outro par (Hines etc all, 2006). Seja (X11 , X21 ), (X12 , X22 ), ..., (X1n , X2n ) um conjunto de n observa¸c˜ oes emparelhadas, para as quais supomos que X1 ∼ N (µ1 , σ12 ) e X2 ∼ N (µ2 , σ22 ). Defina as diferen¸cas entre cada par de observa¸c˜oes como Dj = X1j , −X2j , j = 1, 2, ..., n (Hines et al., 2006). As diferen¸cas Dj s˜ ao distribu´ıdas normalmente, com m´edia µ = E(X1 −X2) = E(X1 )−E(X2 ) = µ1 −µ2 , (2) de modo que um teste sobre igualdade de µ1 e µ2 pode ser obtido realizando-se um teste t de amostra u ´nica sobre µD . Este teste ´e apropriado quando as diferen¸cas pareadas seguem uma distribui¸c˜ao normal. Especificamente, testar H0 : µ1 = µ2 contra H1 : µ1 ̸= µ2 ´e equivalente a testar H0 : µD = 0, H1 : µD ̸= 0,
(3)
com µD = µ1 − µ2 . A estat´ıstica de teste apropriada para a Equa¸ca˜o (3) ´e ¯ D √ , t0 = SD / n
(4)
∑ ¯ = 1 D Dj n j=1
(5)
em que n
e ∑n 2 SD
=
j=1
¯2 Dj2 − nD
n−1
(6)
s˜ao a m´edia e a variˆ ancia amostrais das diferen¸cas. Rejeitar´ıamos H0 : µD = 0 (o que implica que µ1 ̸= µ2 ) se t0 > tα/2,n−1 ou se t0 < −tα/2,n−1 . As alternativas unilaterais s˜ao tratadas de maneira an´ aloga (Hines et al., 2006). 3
Implementa¸ c˜ ao da Estrat´ egia de Aprendizagem
A metodologia adotada para a desenvolvimento da estrat´egia de aprendizagem ´e dividida em quatro etapas, as quais s˜ao:
ISBN: 978-85-8001-069-5
2. Defini¸c˜ao e discretiza¸c˜ao dos estados do ambiente no qual os agentes est˜ao inseridos;
4. Implementa¸c˜ao no Simulador RcSoccerSim da Robocup de Futebol de Robˆos. 3.1
Discretiza¸c˜ ao das A¸c˜ oes
Nesta etapa s˜ao definidas as poss´ıveis a¸c˜oes de um agente no campo de futebol de robˆos simulado. As a¸c˜oes abaixo s˜ao apenas para o agente com posse de bola. 1. A¸c˜ao: Drible R´apido (Carregar a bola em dire¸c˜ao ao gol com velocidade alta); 2. A¸c˜ao: Drible Lento (Carregar a bola em dire¸c˜ao ao gol com velocidade baixa); 3. A¸c˜ao: Drible Normal (Carregar a bola em dire¸c˜ao ao gol com velocidade normal); 4. A¸c˜ao: Passe/Chute (Passar a bola para um companheiro ou chutar em gol); 5. A¸c˜ao: Segurar a Bola (Prender a bola junto ao corpo); 6. A¸c˜ao: Avan¸car com a Bola. 3.2
Discretiza¸c˜ ao dos Estados
A intera¸c˜ao dos agentes com o mundo virtual ´e interpretado por meio dos estados do ambiente. Nestes estados s˜ao definidas as caracter´ısticas do ambiente durante uma partida de futebol de robˆos. As caracter´ısticas levadas em considera¸c˜ao s˜ao o posicionamento dos robˆos da pr´opria equipe com a posse da bola e a distˆancia dos advers´ arios. Nos Estados de 1 a 3, o agente advers´ario mais pr´oximo est´a posicionado atr´as do robˆo com bola em rela¸c˜ao ao eixo X, ou seja, o X do oponente ´e menor. J´a nos Estados de 4 a 6, o agente advers´ario mais pr´oximo est´a posicionado a frente do robˆo com bola em rela¸c˜ao ao eixo X, ou seja, o X do oponente ´e maior. 1. Estado: Advers´ario Longe Atr´as (A distˆancia entre os dois agentes ´e maior que 4.5 m); 2. Estado: Advers´ario Perto Atr´as (A distˆancia entre os dois agentes ´e menor que 4.5 m e maior que 2.5 m); 3. Estado: Advers´ario Muito Perto Atr´as (A distˆancia entre os dois agentes ´e menor que 2.5 m);
3560
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
4. Estado: Advers´ ario Longe na Frente (A distˆancia entre os dois agentes ´e maior que 4.5 m); 5. Estado: Advers´ ario Perto na Frente (A distˆancia entre os dois agentes ´e menor que 4.5 m e maior que 2.5 m); 6. Estado: Advers´ ario Muito Perto na Frente (A distˆancia entre os dois agentes ´e menor que 2.5 m). As figuras 1 e 2 apresentam o sistema de eixos X,Y na plataforma de futebol de robˆ os simulado da Robocup.
forma, o objetivo de ”marcar um gol”pode ser desmembrado em ”obter posse de bola”, ”driblar em dire¸c˜ao `a meta”e ”chutar em dire¸c˜ao ao gol”. A partir disso, neste trabalho, ao definir as recompensas imediatas, o objetivo foi valorizar cada passo necess´ario para que o time de robˆos marcasse um gol. Ou seja, o objetivo foi que o time aprendesse uma estrat´egia de jogo visando um comportamento ofensivo com posse de bola. Essa abordagem ´e distinta de usar refor¸cos somente quando h´a gols (recompensas) ou perda de bola (penaliza¸c˜oes). A Matriz de Recompensa possui cinco valores distintos, sendo que: • -1 - significa que o par sxa n˜ao ´e indicado para ser executado; • 0 - significa que o par sxa possui grau de relevˆancia muito pequeno; • 5 - significa que o par sxa possui grau de relevˆancia pequeno; • 10 - significa que o par sxa possui grau de relevˆancia m´edio; • 20 - significa que o par sxa possui grau de relevˆancia alto.
Figura 1: Sistemas de coordenadas X,Y do campo de futebol simulado 2D para o time que est´a atacando para a direita.
Figura 2: Sistemas de coordenadas X,Y do campo de futebol simulado 2D para o time que est´a atacando para a esquerda.
Os estados (linhas) que apresentam os valores 10 ou 20 foram definidos como os mais relevantes. Ou seja, de acordo com o modelo, ´e melhor para o robˆo com posse de bola se estiver em um estado que possui algum refor¸co imediato m´edio ou alto. A matriz de recompensas Estado (S) x A¸c˜ao (A) ´e apresentada na tabela 1 de refor¸co (R), em que as linhas representam os estados do ambiente e as colunas as a¸c˜oes que os agentes podem tomar. Tabela 1: Matriz de Estado/A¸c˜ao A1 A2 E1 -1 -1 E2 0 -1 E3 5 -1 E4 -1 -1 E5 -1 5 E6 -1 -1
3.4 3.3
Defini¸c˜ ao da Matriz de Recompensas
O ambiente do futebol de robˆ os simulado envolve uma grande complexidade, em termos de n´ umero de a¸c˜oes, para que o time de robˆ os alcance a recompensa principal ao marcar um gol. Um m´etodo comum, usado originalmente no treinamento de animais, ´e chamado de modelagem de recompensa, e envolve oferecer recompensas adicionais por ”fazer progressos”(Russell, 2004). Dessa
ISBN: 978-85-8001-069-5
Recompensa A3 A4 A5 -1 20 -1 0 -1 -1 -1 -1 -1 -1 20 -1 0 0 -1 -1 10 10
A6 -1 0 -1 -1 0 -1
Implementa¸c˜ ao no Simulador
A etapa de implementa¸c˜ao da estrat´egia de aprendizagem por refor¸co foi realizada no simulador RcSoccerSim de futebol de robˆos em duas dimens˜ oes da Robocup. O objeto de estudo foi o Time UaiSoccer2D. Os parˆametros do algoritmo Q-learning, a taxa de aprendizagem (α) e o fator de desconto (γ) foram fixados em 0,95. Para armazenar as informa¸c˜oes aprendidas pelos robˆos foi criado um arquivo denominado
3561
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
q.txt. Nesse arquivo, a matriz Q (6x6) de aprendizado foi iniciada com zero para cada par estado X a¸c˜ao, indicando a inexistˆencia de inteligˆencia no time antes da primeira simula¸c˜ ao. O modelo apresentado visou apenas o aprendizado quando o agente estivesse com a posse de bola. Dessa forma, somente um robˆ o por vez acessa o arquivo q.txt, mas o conhecimento de cada um dos agentes fica acumulado na Matriz Q. Resultando em uma comunica¸c˜ao entre os jogadores denominada de Quadro-Negro. O Quadro-Negro ´e uma estrutura comum a todos os agentes, no caso o q.txt, onde podem realizar a escrita e a leitura das informa¸c˜ oes aprendidas por cada robˆ o. Essa estrutura de comunica¸c˜ ao visa acelerar o aprendizado dos robˆ os, visto que, as experiˆencias dos agentes de acumulam em uma u ´nica estrutura. O processo de aprendizagem (treinamento) aconteceu adotando o Time Helios2011 (Akiyama et al., 2011) como advers´ ario. 4
An´ alise dos Resultados
Procurou-se com este trabalho, verificar o comportamento do time de robˆ os (UaiSoccer2D), ap´os duas fases de treinamento do algoritmo de aprendizado por refor¸co. Avaliando a eficiˆencia da Matriz Q acumulada ap´os 30 e 90 simula¸c˜ oes. • Fase 1: Ap´os 30 jogos de treinamento foi acumulada a Matriz Q1 ; • Fase 2: Ap´os 90 jogos de treinamento foi acumulada a Matriz Q2 . Questionando ent˜ ao, se houve evolu¸c˜ ao de desempenho do time de robˆ os na Fase 2 em rela¸c˜ao a Fase 1. Como foi analisado o comportamento ap´os duas fases da mesma estrat´egia de aprendizado, verificou-se uma rela¸c˜ ao de dependˆencia entre as amostras. O teste mais adequado `a rela¸c˜ ao de dependˆencia de duas amostras ´e o teste t-pareado (Bussab, 2012). O teste t-pareado unilateral foi aplicado utilizando as seguintes hip´ oteses: • H0 : a m´edia de gols sofridos na valida¸c˜ao da Fase 2 ´e igual a m´edia de gols sofridos na valida¸c˜ao da Fase 1; • Ha : a m´edia de gols sofridos na valida¸c˜ao da Fase 2 ´e menor a m´edia de gols sofridos na valida¸c˜ao da Fase 1; Dessa forma, ap´os 30 e 90 jogos de treinanento, a Matriz Q foi congelada para efetuar os jogos de valida¸c˜ ao. Nessas simula¸c˜ oes de valida¸c˜ao, a Matriz Q n˜ ao sofreu atualiza¸c˜ oes. Para a valida¸c˜ao das Fases de aprendizado foram selecionados aleatoriamente 6 times advers´arios da simula¸c˜ao 2D, disponibilizados na Internet. Entre esses times se encontram as equipes participantes do mundial 2011 da Robocup: Helios2011
ISBN: 978-85-8001-069-5
(2o colocado/Jap˜ao), Hfutengine2011 (9o colocado/China), Aua2d (11o colocado/China) e Rione (13o colocado/Jap˜ao); o time base Agent2D (Helios Base); e o time UaiSoccer2D2011. Estes times, testados em 5 jogos contra cada Matriz Q (Q1 e Q2 ) geradas pelas duas fases do aprendizado do UaiSoccer2D, totalizaram 30 jogos de valida¸c˜ao por fase, 60 jogos no total. O somat´orio dos gols sofridos total contra cada time foi utilizado como um banco de dados para a aplica¸c˜ao do teste (Tabela 2). Foram realizadas todas as etapas de testes no software Minitab 14 (vers˜ao acadˆemica). Inicialmente foi realizado um teste de normalidade para a diferen¸ca, entre valida¸c˜ao da Fase 1 e Fase 2, dos Gols Sofridos, Saldo de Gols e Gols Feitos, a fim de verificar a aplicabilidade do teste t-pareado. Nos trˆes casos a suposi¸c˜ao de normalidade foi satisfeita a partir do teste de normalidade de KolmogorovSmirnov (Kolmogorov, 1933; Smirnov, 1948). Tabela 2: Gols Sofridos pelo UaiSoccer2D na Valida¸c˜ao de cada Fase de Aprendizado Time Advers´ ario Q1 Q2 Agent2D 17 11 Aua2d 0 1 Helios2011 25 14 Hfutengine2011 7 3 Rio-ne 8 4 UaiSoccer2D2011 0 0 M´ edia 9,5 5,5 p-valor: 0,03668822 Se o p-valor (P-Value) for menor ou igual a 0,05, isto indica que devemos rejeitar H0 e aceitar Ha , ou seja, a Matriz Q2 obteve melhor desempenho que a Matriz Q1 , mas se o p-valor (P-Value) for maior que 0,05, devemos aceitar H0 , ou seja, o algoritmo de aprendizado n˜ao evoluiu da Fase 1 para a Fase 2. Como o p-valor (P-Value) resultou em 0,03668822, conclui-se que o comportamento do Time de Robˆos ap´os 90 jogos de treinamento (Fase 2) foi superior estatisticamente em rela¸c˜ao ao desempenho ap´os apenas 30 jogos de treino (Fase 1), com respeito ao n´ umero de gols sofridos em um jogo. J´a as tabelas 3 e 4, com os saldo de gols e os gols feitos revelam que a Matriz Q2 (Fase 2) n˜ao obteve desempenho superior significativo em rela¸c˜ao a esses crit´erios. 5
Conclus˜ oes
Este trabalho teve como meta modelar uma estrat´egia de aprendizado por refor¸co (AR) no dom´ınio do futebol de robˆos em duas dimens˜oes (2D). Para isso, foi adotado o algoritmo Q-learning. A modelagem de uma inteligˆencia artificial por meio da t´ecnica de aprendizagem por refor¸co para um
3562
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
Tabela 3: Saldo de Gols por Fase de Apendizado Time Advers´ ario Q1 Q2 Agent2D -1 -6 Aua2d 23 22 Helios2011 -24 -13 Hfutengine2011 26 39 Rio-ne 23 30 UaiSoccer2D2011 120 121 M´ edia 27,833 32,167 p-valor: 0,098053308
Tabela 4: Gols Feitos por Fase de Apendizado Time Advers´ ario Q1 Q2 Agent2D 16 5 Aua2d 23 23 Helios2011 1 1 Hfutengine2011 33 42 Rio-ne 31 34 UaiSoccer2D2011 120 121 M´ edia 37,333 37,667 p-valor:0,452474988
time de robˆ os auxilia na tomada decis˜ ao do sistema multiagente no ambiente de simula¸c˜ao. A implementa¸c˜ ao da t´ecnica de aprendizagem, faz com que a equipe de futebol de robˆ os se adapte `as condi¸c˜oes da partida em resposta `as a¸c˜oes do advers´ario. As an´alises estat´ısticas indicaram uma evolu¸c˜ao no comportamento do time em rela¸c˜ ao `a diminui¸c˜ao no n´ umero de gols sofridos, ap´ os 90 jogos de treinamento (Fase 2). Ou seja, estatisticamente o time ap´os a Fase 2 sofreu menos gols que o time ap´os a Fase 1. Dessa forma, a estrat´egia de AR implementada apresentou melhores resultados ap´ os mais jogos de treinamento. No entanto, os testes tamb´em revelaram que n˜ao ocorreu evolu¸c˜ ao estatisticamente significante com rela¸c˜ao aos gols feitos e saldo de gols. Nos pr´oximos trabalhos, ser˜ ao propostas an´alises sobre uma quantidade de jogos de treinamento superiores as apresentadas neste artigo. Dessa forma, ´e pretendido verificar se ao longo do tempo o n´ umero de gols sofridos continuar´a a cair. Al´em disso, visualizar se em algum momento o n´ umero de gols feitos e saldo de gols aumentar˜ao significativamente entre Fases de Treinamento do Aprendizado por Refor¸co.
Agradecimentos Agradecemos `a CAPES, CNPQ, FAPEMIG, PPGEL, UaiSoccer2D, UAIrobots e UFSJ pelo apoio.
ISBN: 978-85-8001-069-5
Referˆ encias Akiyama, H., Shimora, H., Nakashima, T., Narimoto, Y. and Okayama, T. (2011). Helios2011 team description, Robocup 2011 . Bertsekas, D. (2001). Dynamic programming and optimal control., Belmont, MA: Athena Scientific. (ISBN 1-886259-08-6.). Bianchi, R. A. C. (2004). Uso de heur´ıstica para a acelera¸c˜ ao do aprendizado por refor¸co., Master’s thesis, Tese (Doutorado) Escola Polit´ecnica da Universidade de S˜ao Paulo. Bussab, W. B. e Morettin, P. (2012). Estat´ıstica B´ asica, 7st edn, Saraiva. Celiberto Jr, L. A. e Bianchi, R. A. C. (2006). Aprendizado por refor¸co acelerado por heur´ıstica para um sistema multi-agentes, In 3rd Workshop on MSc dissertations and PhD thesis in Artificial Intelligence. . Fraccaroli, E. S. (2010a). An´ alise de Desempenho de Algoritmos Evolutivos no Dom´ınio do Futebol de Robˆ os, Disserta¸c˜ao apresentada `a Escola de Engenharia de S˜ao Carlos da Universidade de S˜ao Paulo. Fraccaroli, E. S. e Carlson, P. M. (2010b). Time gearsim 2010 da categoria robocup simulation 2d., In Competi¸c˜ ao Latino Americana de Rob´ otica. 2010. Garcia, A. C. B. e Sichman, J. S. (2003). Agentes e Sistemas Multiagentes., Vol. 11, In Sistemas Inteligentes: Fundamentos e Aplica¸c˜oes, Rezende, S. O., chapter 11, pp. 269–306. Hines, W. W., Montgomery, D. C., Goldsman, D. M. and Borror, C. M. (2006). Probabilidade e Estat´ıstica na Engenharia, LTC. Kerbage, S. E. H., Antunes, E. O., Almeida, D. F. and Rosa, P. F. F. (2010). Generaliza¸c˜ao da aprendizagem por refor¸co: Uma estrat´egia para robˆos autˆonomos cooperativos., In Competi¸c˜ ao Latino Americana de Rob´ otica. 2010. Kim, Y. C., C. S.-B. and Oh, S. R. (2010). Mapbuilding of a real mobile robot with ga-fuzzy controller., International Journal of Fuzzy Systems. pp. 696–703. Kolmogorov, A. . (1933). Sulla determinazione empirica di una legge di distribuzione, G. Inst. Ital. Attuari 4: 83. Lacerda, M. J., Texeira, W. W. M. and Nepomuceno, E. G. (2009a). Aloca¸c˜ao de agentes para controle de epidemias utilizando algoritmo gen´etico., In IX Simp´ osio Brasileiro de Automa¸c˜ ao Inteligente .
3563
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
Lacerda, M. J., Texeira, W. W. M. and Nepomuceno, E. G. (2009b). Controle da propaga¸c˜ao espacial de epidemias: Uma abordagem utilizando agente inteligente., In IX Simp´ osio Brasileiro de Automa¸c˜ ao Inteligente . Monteiro, S. T. e Ribeiro, C. H. C. (2004). Desempenho de algoritmos de aprendizagem por refor¸co sob condi¸c˜ oes de ambiguidade sensorial em rob´ otica m´ovel, Revista Controle & Automa¸c˜ ao Vol.15 no.3. Nascimeno Jr., C. L. e Yoneyama, T. (2009). Inteligˆencia Artificial em Controle e Automa¸c˜ ao., 1st edn, Edgard Blucher.
Watkins, C. J. (1989). Models of delayed reinforcement learning., Master’s thesis, PhD thesis, Psychology Department, Cambridge University, Cambridge, United Kingdom. Watkins, C. J. e Dayan, P. (1992). Technical note q-learning, Machine Learning . White, D. J. (1993). A survey of applications of markov decision processes., The Journal of the Operational Research Society 44(11): 10731096.
Neri, J. R. F., Santos, C. H. F. and Fabro, J. A. (2011). Descri¸c˜ ao do time gpr-2d 2011, Competi¸c˜ ao Brasileira de Rob´ otica 2011. Ottoni, A. L. C., Lamperti, R. D. and Nepomuceno, E. G. (2012). Uaisoccer2d: Team description paper robocup 2012, Robocup 2012 2012. Ottoni, A. L. C., Nepomuceno, E. G., Oliveira, F. F. and Oliveira, M. S. (2011). An´ alise do comportamento de sistemas multiagentes cooperativos por meio de testes estat´ısticos, In X Encontro Mineiro de Estat´ıstica . Puterman, M. L. (1994). Markov decision processes: Discrete stochastic dynamic programming., New York, NY: Wiley-Interscience (ISBN 0471619779.). Russell, S. J. e Norving, P. (2004). Inteligˆencia Artificial., 2st edn, Campus. Silva, A. T. R., Silva, H. G., Santos, E. G., Ferreira, G. B., Santos, T. D. and Silva, V. S. (2010). ibots 2010: Descri¸c˜ ao do time., In Competi¸c˜ ao Latino Americana de Rob´ otica. 2010. Sim˜oes, M. A. C., Silva, H., Meyer, J., Oliveira, J. D., Cruz, L., Pessoa, H. and L., A. R. (2007). Bahia 2d: Descri¸c˜ ao do time., In XIII Simp´ osio Brasileiro de Automa¸c˜ ao Inteligente . Smirnov, N. (1948). Tables for estimating the goodness of fit of empirical distributions, Annals of Mathematical Statistics 19: 279. Sutton, R., e. B. A. (1998). Reinforcement Learning: an introduction., 1st edn, Cambridge, MA: MIT Press. Texeira, W. W. M., Teles, F., Barbosa, A. M., Silva, M. A., Nepomuceno, E. G. and Queiroz Melo, M. F. A. (2009). Modelagem e controle de um sistema multiagente cooperativo: vis˜ao global e local aplicadas ao problema da aloca¸c˜ao de recursos., In IX Simp´ osio Brasileiro de Automa¸c˜ ao Inteligente. .
ISBN: 978-85-8001-069-5
3564
