"Implementação de estratégias para futebol de robôs utilizando
Transcrição
"Implementação de estratégias para futebol de robôs utilizando
Implementação de Estratégias para Futebol de Robôs utilizando Campos Potenciais ∗ Gedson Faria SCE – ICMC – USP [email protected] Luı́za C. F. Teizen SCE – ICMC – USP [email protected] Resumo Neste trabalho apresenta-se uma abordagem para construção de estratégias para futebol de robôs utilizandose a técnica de campos potenciais. Para isto, desenvolveuse módulos de ataque e defesa, os quais foram testados no simulador da FIRA (SimuroSot). Embora o método de campos potenciais possua limitações o resultado dos experimentos foram bastante satisfatórios fazendo com que nossa estratégia ganhasse da estratégia padrão que acompanha o simulador. 1. Introdução A idéia de robôs jogando futebol foi mencionada, pela primeira vez, pelo professor Alan Mackworth, em um artigo de 1992, intitulado “On Seeing Robots”[13]. Desde então, duas grandes organizações mundiais estabeleceramse como referência na área de Futebol de Robôs. São elas a RoboCup e FIRA (Federation of International Robotsoccer Association). Ambas deram inı́cio às suas atividades no ano de 1996. A RoboCup é uma iniciativa japonesa que, atualmente, conta com o apoio maciço de grandes empresas de tecnologia. Já a FIRA, por sua vez, é uma iniciativa do meio acadêmico coreano. Com o passar dos anos, ambas as iniciativas tornaram-se organizações de âmbito internacional, que realizam campeonatos anualmente. As duas entidades possuem diversas categorias, que envolvem simulação, micro-robôs e até robôs bı́pedes. Futebol de robôs é uma iniciativa internacional voltada à pesquisa e educação, visando promover desenvolvimentos ligados às áreas de Inteligência Artificial e Robótica Inteligente [10]. Uma das maiores razões do futebol de robôs ser adotado como ambiente de estudo é o fato deste ser um problema padrão e portanto, a pesquisa pode ser claramente definida e acompanhada. Além disto, através da adoção deste problema pode-se fazer avaliações de várias teorias, algoritmos, arquiteturas e desempenhos. Tudo isto ∗ Apoio financeiro da CAPES Roseli A. F. Romero SCE – ICMC – USP [email protected] aliado a uma grande variedade de tecnologias que podem ser integradas e analisadas [5]. Várias técnicas tem sido aplicadas para construir os comportamentos de ataque, defesa e cooperação para os robôs. A estratégia utilizada pelo time Guaraná consiste em utilizar uma máquina de estados para selecionar as ações de ataque e defesa. Após selecionada a ação, um processo iterativo é executado para selecionar uma rota sem colisões até sua meta [5]. Park et al. [15] propôs uma abordagem na qual dividiu o campo em quadrantes de ataque e defesa. Cada quadrante possui um único robô que planeja suas trajetórias utilizando a técnica de campos potenciais [1]. Sendo que, para esta estratégia foi considera a existência de áreas de intersecção entre os quadrantes e foi utilizado um algoritmo de aprendizado por reforço [16] conhecido como Q-learning [18] para selecionar qual robô deveria chutar a bola. Uma outra técnica de campos potenciais na qual se utiliza um mapa para representar o ambiente [6], conhecida como Virtual Field Histogram (VFH) [3], foi utilizada por Gomes & Campos [8] para que os robôs planejassem suas trajetórias livres de colisões. No presente trabalho, a técnica de campos potenciais que está sendo utilizada se assemelha a abordagem MotorSchema proposta por Arkin [1] acrescida de técnicas que permitem encontrar metas especı́ficas para cada robô. Uma meta, ou ponto de atração, foi a forma utilizada para implementar tanto as estratégias de ataque como as defesa. A meta atrai o robô fazendo com que ele se posicione no campo de acordo com a estratégia escolhida para ele. Ao mesmo tempo, cada robô considera a posição dos outros robôs como um ponto de repulsão. Assim, cada robô planeja sua trajetória até sua meta desviando dos demais robôs. Este trabalho está organizado como segue. Na seção 2, uma revisão sobre campos potenciais. As modificações na implementação dos módulos que calculam as forças de atração e as estratégias de ataque e defesa utilizadas são apresentadas na seção 3. Finalmente, na seção 4, as conclusões e sugestões para trabalhos futuros. 2. Campos Potenciais 2.1. Força de Repulsão A idéia de imaginar forças atuando sobre um robô foi sugerida por Khatib [9]. Neste método, obstáculos exercem forças repulsivas e a meta aplica uma força atrativa sobre o → − robô. A força resultante F é composta de uma força atrativa direcionada para a meta e forças repulsivas proveniente de obstáculos. Sendo que para cada nova posição do robô todas as forças deverão ser novamente calculadas. Com isto, é possı́vel que o robô desvie dos obstáculos e chegue até a meta. Krogh [11] aprimorou este conceito ao considerar a velocidade do robô na vizinhança dos obstáculos. Thorpe [17] aplicou o método campo potencial para planejamento off-line. Krogh & Thorpe [12] sugeriram uma combinação do método para planejamento de caminhos locais e globais utilizando para isto uma abordagem denominada Generalized Potential Field. Para os métodos acima descritos assumiu-se um modelo conhecido do mundo, com formas geométricas predefinidas representando obstáculos e o caminho do robô é gerado off-line. No entanto, Brooks [4] e Arkin [1] se destacam dentre os primeiros trabalhos realizados em um ambiente real. Eles utilizaram robôs móveis equipados com sensores ultrassônicos (sonar) para calcular os campos potenciais. Brooks utilizou campos potenciais como um controlador reflexivo sem nenhum tipo de raciocı́nio deliberativo. O controlador simplesmente reage executando ações diretamente ligadas as percepções, resultando assim em respostas imediatas a estı́mulos externos. Um método similar, denominado Motor Schema, foi utilizado por Arkin em seus robôs. Este método consiste em ativar vários comportamentos simultâneos que produzem um vetor força (atração ou repulsão) como resposta. A direção a ser seguida pelo robô será o vetor resultante da soma de todos os vetores gerados. No entanto, os robôs operam em baixa velocidade, desviando de obstáculos a uma velocidade de 0.12 cm/sec. Tanto Brooks como Arkin não armazenam informações do ambiente, calculam o campo potencial sobre os dados recebidos pelos sensores em cada instante de tempo. Em uma outra abordagem, sugerida por Borenstein & Koren [2], utiliza-se um mapa para representar o ambiente com seus obstáculos [6]. A partir da probabilidade de uma célula estar ocupada é que será gerado o campo potencial para uma dada posição do robô. Outras abordagens utilizando campos potenciais para o planejamento de trajetórias utilizando robôs móveis foram sugeridas por Faria & Romero [7], Pacheco & Costa [14] e Gomes & Campos [8]. Nas subseções seguintes será mostrado como realizar os cálculos das forças de repulsão, atração e da força resultante. Na Figura 1(a) mostra-se que a força de repulsão decai ao se afastar de um obstáculo, pois a força de repulsão → − ( Fr ) é um vetor cujo módulo é inversamente proporcional ao quadrado da distância (d) entre o robô (R) e objeto ob→ − servado (O) (Figura 1(b)). O vetor Fr também pode ser rey Fr y Fr θF r ∆y d R x O Fr ∆x (a) x (b) Figura 1. (a)Força de repulsão na vizinhança de um obstáculo; (b) Força de repulsão do objeto O sobre um robô localizado em R. presentado por suas componentes: módulo e direção, apresentados na Equação 1. ¯→ ¯ Q ¯− Fr ¯ = 2 e θ→ − = arctan(−∆y, −∆x) Fr d (1) sendo que: Q representa um escalar constante de repulsão; arctan é uma função na qual se considera os sinais de ∆x e ∆y para fornecer o ângulo correto cuja tangente seja (−∆y/−∆x); e os sinais negativos de ∆x e ∆y fornecem uma direção oposta ao objeto detectado (O). Para calcular a força de repulsão para vários obstáculos, deve-se fazer o somatório dos vetores das forças de repulsão geradas, como mostrado na Equação 2. − → → − FR = ∑ Fr (2) 2.2. Força de Atração Na Figura 2(a) e Figura 2(b) mostra-se o¯campo poten→ −¯ cial de atração, no qual deve-se considerar ¯ Fa ¯ constante para que o agente seja atraı́do pela meta mesmo estando distante da mesma (Equação 3). ¯→ ¯ ¯− Fa ¯ = C e θ→ − = arctan(∆y, ∆x) Fa (3) no qual C representa um escalar constante de atração. Note que ∆x e ∆y diferem da Equação 1 por não estarem acompanhados do sinal negativo. Como resultado, a direção do vetor força de atração será na direção da meta. y ∆y 3.1. Estratégias de Jogo M m Fa y Fa R Fax θF a ∆x (b) (a) x Figura 2. (a)Campo de atração constante; (b)Atração entre o robô R e a meta M. 2.3. Força Resultante Ao realizar a soma dos vetores força de atração e força de repulsão obtém-se a força resultante dada pela Equação 4. → − → − → − F = Fr + Fa O sistema foi construı́do visando comportamentos tanto de ataque quanto de defesa. O sistema foi iniciado com comportamentos mais simples e no decorrer do projeto foram implementadas rotinas mais elaboradas. Para tanto, será descrito a seguir os passos seguidos na construção das estratégias utilizadas pelos robôs. FASE I Nesta fase optou-se por fazer com que a bola atraı́sse um robô artilheiro e que este também desviasse dos robôs de seu próprio time. Apesar dos chutes serem certeiros, o robô não direcionava a bola ao gol adversário. Esta estratégia criou um comportamento no qual o robô segue a bola para chutá-la sem se importar para qual direção a bola pudesse ir, podendo inclusive marcar gols contra (Figura 4). Embora, isto não fosse desejado, observou-se que o robô utilizando o método de campos potenciais atingia sua meta com precisão. (4) 80 Para ilustrar a superposição dos campos de atração e repulsão, mostra-se na Figura 3 o campo e a trajetória obtida para encontrar a meta. 70 Campo Gol1 60 Gol2 home 0 home1 50 home2 home3 40 home4 oponente 0 30 oponente 1 oponente 2 20 oponente 3 oponente 4 bola 10 0 0 20 40 60 80 100 Figura 4. Caso no qual um robô utilizando-se da estratégia “seguir a bola” marca um gol contra. Figura 3. Campo potencial e trajetória seguida evitando obstáculos. 3. Modelagem do Problema As estratégias de jogo foram montadas utilizando-se o conceito de campos potenciais, seja para desviar dos outros robôs (força de repulsão) seja para encontrar e chutar a bola (força de atração). As rotinas foram implementadas em módulos e inicialmente estão rodando no simulador da FIRA e em breve será transferida para um time de robôs reais. O simulador da FIRA passa para as rotinas as seguintes informações: limites do campo, limites dos gols, posição e orientação de todos robôs, posição da bola e que time tem a posse da bola. FASE II Para criar um comportamento de defesa, foram criadas quatro retas imaginárias (l1 , l2 , l3 e l4 ) que cortam o campo longitudinalmente e uma reta (r) que liga o centro do gol a bola (Figura 5). Como a bola está sempre em movimento, a reta r deverá ser atualizada antes de cada movimento, pois a estratégia de defesa consiste em fazer com que cada robô não-atacante n seja sempre atraı́do pelo ponto de intersecção de sua reta ln com a reta r. FASE III Uma estratégia mais elaborada foi implementada para que o robô atacante passasse a evitar os gols contra. Para isto, foi criada uma reta imaginária s que passa pelo centro do gol adversário e pela bola. Com isto, encontra-se um ponto (P) pertencente a s de modo que P fique a uma distância constante (i) da bola. A partir destes dados faz-se com que o robô 80 70 Campo Gol1 60 Gol2 home 0 home1 50 home2 goleiro atacante vetor de atração home3 40 home4 oponente 0 30 oponente 1 r oponente 2 20 oponente 3 bola oponente 4 l1 l2 l3 l4 bola 10 0 0 Figura 5. Estratégias de ataque e defesa da fase II. dirija-se ao ponto P para poder chutar a bola. Para construir este comportamento, considerou-se que a bola repelisse e que o ponto P atraı́sse o robô (Figura 6). Note que, se a força de repulsão da bola for maior 20 40 60 80 100 Figura 7. Robô contornando a bola e chutando ao gol corretamente. é possı́vel observar que estes mesmos obstáculos atrapalham o atacante a alcançar a bola. Um fato que deve 80 força de atração I s P bola 70 Campo Gol1 60 Gol2 home 0 home1 50 home2 home3 40 home4 oponente 0 30 oponente 1 oponente 2 20 oponente 3 oponente 4 bola 10 0 0 Figura 6. Estratégias de ataque da fase III. do que a atração do ponto P então o robô nunca conseguirá atingir P. Por este motivo, considerou-se que a bola repele menos que os outros objetos, ou seja, a bola possui uma constante de repulsão menor do que Q. Deve-se observar também que o robô não pode chutar a bola antes de alcançar o ponto P ou pelo menos uma área próxima de P. Quando isto ocorrer, o robô muda de comportamento passando a perseguir a bola e com isto, aumenta as possibilidades de chutes certeiros ao gol adversário e evita gols contra. Este comportamento pode ser observado na Figura 7. Contudo, a tarefa de encontrar as constantes de atração K e de repulsão Q é feita empiricamente. Uma atração alta provoca colisões pois a bola atrai mais do que os obstáculos repelem, entretanto, valores altos para repulsão podem atrapalhar o robô a alcançar a bola. Isto pode ser observado na Figura 8 na qual mostrase o comportamento de desvio de obstáculo. Também 20 40 60 80 100 Figura 8. Desvio de obstáculo e chute ao gol. ser considerado, é que todos os robôs se movem constantemente e assim comportamentos como o mostrado na Figura 8 dificilmente ocorrem. A dinâmica do jogo também minimiza o problema de mı́nimos locais no qual força de atração e força de repulsão se anulam impedindo o movimento. 4. Conclusão e Trabalhos Futuros Vários jogos com todos os robôs em movimento foram realizados para testar os comportamentos implementados. Todavia, também foram observados os comportamentos para um único robô em movimento, pois não é uma tarefa fácil analisar o comportamento de um robô em um ambiente dinâmico. A partir destes testes, observou-se que: (1) O comportamento de seguir a bola utilizando-se potencial de atração foi muito satisfatório. No entanto, quando combinado com o comportamento para evitar colisões, sua eficiência fica bastante alterada. Isto pode ser observado na Figura 8 na qual os obstáculos atrapalham o atacante a alcançar a bola; (2) O método de ataque implementado na FASE III foi bastante eficiente reduzindo o número de gols contra e fazendo com que o time que o estivesse utilizando passasse a ganhar o jogo; (3) O fato dos robôs estarem em movimento minimiza o problema de mı́nimos locais no qual força de atração e força de repulsão se anulam impedindo o movimento. (4) Os robôs movimentam-se rapidamente, a uma velocidade máxima de 317cm/s, mesmo assim, o método de campos potenciais mostrou-se bastante eficiente no controle de trajetória. O maior problema foi encontrar empiricamente os valores para as constantes de repulsão Q e atração K. Para cada nova modificação na estratégia novos valores tinham que ser testados. Isto ocorre, pois são estas constantes que determinam a distância com que o robô irá desviar dos obstáculos. Como solução para este problema, pretendese utilizar o potencial dos algoritmos de aprendizado por reforço [16] para encontrar valores ótimos para as constantes de repulsão Q e de atração K. Embora minimizado ainda ocorrem situações de mı́nimos locais, no qual força de atração é igual a de repulsão. Isto acontece normalmente quando algum obstáculo fica entre o robô e a bola. Para solucionar este problema, pretende-se a utilizar do método Virtual Field Histogram (VFH) proposto por Borenstein & Koren [3]. Referências [1] Arkin, R. C. (1989). Motor schema-based mobile robot navigation. The International Journal of Robotics Research, 4(8), 92–112. [2] Borenstein, J. & Koren, Y. (1989). Real-time obstacle avoidance for fast mobile robots. IEEE Transactions on Systems, Man, and Cybernetics, 19(5), 1179–1187. [3] Borenstein, J. & Koren, Y. (1991). The vector field histogram – fast obstacle avoidance for mobile robots. IEEE Journal of Robotics and Automation, 7(3), 278– 288. [4] Brooks, R. A. (1986). A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, 2(1), 14–23. [7] Faria, G. & Romero, R. A. F. (2000). Incorporating fuzzy logic to reinforcement learning. In Proceedings of the 9th IEEE International Conference on Fuzzy Systems, volume 1 (pp. 847–851). [8] Gomes, M. R. S. & Campos, M. F. M. (2001). Desvio de obstáculos para micro-robôs móveis utilizando campo potencial. In Anais do V Simpósio Brasileiro de Automação Inteligente (SBAI) Canela/RS. [9] Khatib, O. (1985). Real-time obstacle avoidance for manipulators and mobile robots. In IEEE International Conference on Robotics and Automation (pp. 500–505). St. Louis, Missouri. [10] Kitano, H., Kuniyoshi, Y., Noda, I., Asada, M., Matsubara, H., & Osawa, H. (1997). Robocup: A challenge problem for ai. AI Magazine, 1(18), 73–85. [11] Krogh, B. H. (1984). A generalized potential field approach to obstacle avoidance. In International Robotics Research Conference Bethlehem, Pennsylvania. [12] Krogh, B. H. & Thorpe, C. E. (1986). Integrated path planning and dynamic steering control. In Proceedings of the 1986 IEEE International Conference on Robotics and Automation (pp. 1664–1669). San Francisco, California. [13] Mackworth, A. K. (1993). On seeing robots. In A. Basu & X. L. World (Eds.), Computer Vision: Systems, Theory, and Applications (pp. 1–13). Singapore: World Scientific Press. [14] Pacheco, R. N. & Costa, A. H. R. (2002). Navegação de robôs móveis utilizando o método de campos potenciais. In M. T. S. Sakude & C. de A. Castro Cesar (Eds.), Workshop de Computação WORKCOMP’2002 (pp. 125–130). ITA – São José dos Campos/SP: SBC. [15] Park, K.-H., Kim, Y.-J., & Kim, J.-H. (2001). Modified uni-vector field navigation and modular q-learning for soccer robots. In Proceedings of the 32nd International Symposium on Robotics - ISR (pp. 19–21). [16] Sutton, R. S. & Barto, A. G. (1998). Reinforcement learning: An introduction. In MIT Press Cambridge, MA. [5] Costa, A. H. R. & Pegoraro, R. (2000). Construindo robôs autônomos para partidas de futebol: O time Guaraná. SBA Controle e Automação, 11(3), 141–149. [17] Thorpe, C. (1984). Path Relaxation: Path Planning for a Mobile Robot. Technical Report CMU-RI-TR84-05, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA. [6] Elfes, A. (1989). Occupancy Grids: A Probabilistic Framework for Robot Perception and Navigation. PhD thesis, Carnegie Mellon University. [18] Watkins, C. J. C. H. (1989). Learning from Delayed Rewards. PhD thesis, University of Cambridge.
Documentos relacionados
"Robôs móveis inteligentes: principios e técnicas".
que seja designada a um robô móvel a tarefa de percorrer, sem colisões, o trajeto de um ponto a outro de uma fábrica. Se o robô conseguir executar esta tarefa com sucesso, conduzindo-se até ...
Leia mais