"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.