oxente team: implementação de habilidades de jogo em um time de

OXENTE TEAM: IMPLEMENTAÇÃO DE HABILIDADES DE JOGO EM UM TIME
DE FUTEBOL DE ROBÔS SIMULADO UTILIZANDO OTIMIZAÇÃO HEURÍSTICA
Andrea Cassia Peixoto Bitencourt∗
Ana Cláudia Fiorin Pianesso∗
[email protected]
[email protected]
João Paulo Rocha Portela de Sousa
∗
Julhilson Silveira Ferreira Júnior∗
[email protected]
[email protected]
Marcelo Santos Linder
Ricardo Perrone da Silva∗
[email protected]
[email protected]
∗
Orientador Augusto Loureiro da Costa ∗
[email protected]
∗
Programa de Pós-Graduação em Mecatrônica, Universidade Federal da Bahia
Departamento de Engenharia Mecânica - Escola Politécnica
Departamento de Ciência da Computação - Instituto de Matemática
CEP: 40210-630, Salvador, BA, Brasil
RESUMO
A inteligência artificial mostra-se como um dos mais
promissores ramos da ciência da computação. Para testes
e consolidação de métodos e teorias, atualmente utiliza-se
competições de futebol entre robôs, a RoboCup. Este artigo
pretende melhorar a atuação de um time de futebol de robôs,
melhorando as habilidades de chute e de passe, inclusive
melhorando a saída de bola do goleiro. Foi utilizado como
base o sistema multiagente base do time da Universidade de
Amsterdam, que disponibiliza somente as habilidades básicas.
PALAVRAS-CHAVE:
Inteligência
RoboCup, Sistemas Multiagentes
Artificial
Distribuída,
1 INTRODUÇÃO
A Inteligência Artificial Distribuída (IAD) é uma das áreas da
Inteligência Artificial (IA) que mais se desenvolveu nos últimos
anos e apresenta um enorme potencial de aplicação (Cheny
et al., 2002). Segundo Weiss (1999), esta área envolve o estudo,
construção e aplicação de sistemas multiagente, onde agentes
inteligentes (entidade lógica ou física) interagem para realizar
um conjunto de objetivos ou tarefas.
Uma forma comum de incentivo à pesquisa em IA, mais
especificamente em IAD é a proposta de problemas padrão. Um
problema bastante interessante, que vêm atraindo interesse de
diversos grupos de pesquisa em robótica e IA e que será o foco
deste trabalho é a realização de partidas de futebol entre robôs
VII SBAI / II IEEE LARS. São Luís, setembro de 2005
autônomos. Esta proposta surgiu da iniciativa de um grupo de
pesquisadores da área, e em 1997 resultou na Primeira Copa
Mundial de Futebol de Robôs (RoboCup) em Nagoya, Japão.
Esta proposta apresenta a possibilidade de utilização de diversas
tecnologias e áreas de pesquisa distintas. Em relação à IA,
há espaço para a implementação de diferentes técnicas como
cooperação em sistemas multiagentes, sistemas especialistas,
lógica nebulosa, redes neurais, dentre outras (Stone e Veloso,
2000).
Pelas características do problema e dos desafios envolvidos
numa partida de futebol, o futebol de robôs tornou-se um
importante laboratório principalmente para a pesquisa na área de
sistemas multiagente. O jogo coletivo e, como tal, a participação
de todos para que o objetivo principal (marcar o maior número
de gols e vencer a partida) seja alcançado depende da atuação
coletiva. É necessário que haja interação e comunicação entre
os membros da mesma equipe para que se obtenha sucesso.
Talentos individuais não são garantias de bons resultados, o
ponto chave é cooperação.
Desta forma, ao contrário dos paradigmas tradicionais da IA,
os SMA deixam de dar atenção às iniciativas, seja mental
(IA simbolista) ou neural (IA conexionista) de compreender e
simular o comportamento humano isoladamente para abordar
a idéia de Comunidade Inteligente (Bittencourt, 1998). Este
conceito representa um sistema em que o comportamento social
de comunidade possui características inteligentes, formada por
agentes autônomos inseridos em um ambiente comum e capazes
de se comunicar e cooperar para alcançar uma meta global (Briot
e Demazeau, 2002).
1
Considerando os aspectos citados, este artigo descreve a
aplicação de problemas de coletividade utilizando sistemas
multiagente. O domínio de aplicação é um time de futebol de
robôs simulado participante de diversos campeonatos mundiais.
O objetivo é implementação de habilidades de jogo e tomada
de decisão dos agentes para obtenção de estratégias de jogo e
conseqüentemente melhoramento do desempenho do time.
de Futebol Simulado, foco deste artigo, jogadores virtuais e
independentes (agentes) jogam futebol num campo virtual
simulado por computador como pode ser observado na
figura 1, em que os jogos são divididos em dois tempos de
5 minutos (de Boer et al., 2002).
Na seção 2 encontra-se uma breve descrição do RoboCup e suas
características. Na seção seguinte é apresentado o problema
futebol de robôs com suas características, arquitetura proposta
bem como os componentes integrantes desta arquitetura e suas
funcionalidades. A seção 4 descreve as principais características
do objeto de estudo deste trabalho, o time UvA Trilearn. Na
seção 5 é apresentada a implementação de estratégicas de jogo,
com a metodologia utilizada e resultados obtidos e por fim
encontra-se as conclusões e perspectivas para futuros trabalhos.
2 ROBOCUP
A RoboCup segundo Asada et al. (2000), Kitano et al. (1997)
e Kitano et al. (1995) trata-se de uma iniciativa internacional
que visa fomentar a investigação e a integração das áreas da
Inteligência Artificial e da Robótica no sentido de promover
a evolução de algumas teorias, algoritmos, aprendizagem e
arquiteturas de sistemas multiagente.
O fato deste campeonato se tratar de robótica coletiva, na qual se
trabalha com equipes de robôs e não com habilidades de um robô
isoladamente, torna-o um ambiente propício para investigação
de problemas apresentados na área de Inteligência Artificial
(Foroughi et al., 2001). Apesar das vantagens apresentadas, esse
fato agrava muitos problemas como os relativos à coordenação
e à orientação dos jogadores. No caso da RoboCup, há ainda a
característica de serem realizadas partidas entre times diferentes,
o que torna os problemas relatados ainda mais complexos
(de Boer et al., 2001).
Atualmente a RoboCup é composta de diferentes provas e
modalidades em que são implementados e testados diversos
problemas de IA. Nem todas as provas que atualmente integram
este campeonato faziam parte do seu formato original. As
modalidades atuais desta competição estão descritas no próximo
item.
2.1 As modalidades da RoboCup
O formato da RoboCup é baseado principalmente em um
problema padrão: jogar futebol. Este fato é considerado por
Stone e Veloso (2000) uma grande vantagem em relação a outros
formatos de competições com propósitos semelhantes. Desse
modo concentram-se recursos e esforços num mesmo tipo de
atividade, segundo regras comuns que todos conhecem e avaliam
(de Boer et al., 2002). Atualmente existem outras modalidades
de competição, nem todas envolvidas com futebol. As principais
atividades englobadas pela RoboCup no atual formato estão
descritas nos itens a seguir.
• Competição de Futebol (RoboCup Soccer) - é considerada
a atividade mais importante do compeonato. Inclui cinco
competições: simulação, pequeno porte (18 cm), médio
porte (50 cm), robôs de quatro patas e humanóides. Na Liga
VII SBAI / II IEEE LARS. São Luís, setembro de 2005
Figure 1: Ambiente Simulado - Time UvA Trilearn X Time
FCPortugal
• Salvamento (RoboCup Rescue) - nesta modalidade as
competições desenvolvem-se em torno de robôs capazes
de efetuar salvamentos em situações de desastre. Inclui
uma competição de simulação e uma competição com robôs
reais (RoboCup, 2005c).
• RoboCup Junior - é fundamentalmente uma iniciativa
educativa e de sensibilização, que combina cooperação
com competição. Crianças e jovens utilizando uma infraestrutura simples criam equipes de robôs para jogar futebol
(2 contra 2), dançar ou resgatar vítimas (RoboCup, 2005b).
3 FUTEBOL SIMULADO DE ROBÔS
O futebol simulado de robôs foi concebido para ser executado
em um ambiente distribuído, levando-se em conta uma variedade
de problemas científicos tais como: processamento em tempo
real, robustez de comunicação com ruído, cooperação entre
diversos agentes até processamento incompleto de informações.
Logo, fica evidenciada a natureza abrangente com que o futebol
simulado aborda diversas áreas do conhecimento. A simulação
é assegurada por uma arquitetura cliente/servidor em que o
servidor central é o (Soccerserver), e os jogadores constituem
os clientes. Desta forma, observa-se que há uma arquitetura
multiagente suportando a simulação(Kitano et al., 95, 97).
No (Soccerserver) é modelado um campo de futebol virtual
composto por duas equipes (Noda e Frank, 2000). Cada equipe
é constituída por onze jogadores, tendo como objetivo vencer
a partida marcando um número maior de gols que a equipe
adversária. Os clientes, que desempenham o papel de jogador,
se conectam ao (Soccerserver) via socket UDP/IP(Kitano et al.,
95), onde toda a partida é simulada(Cheny et al., 2002). O jogo
de futebol no campo virtual é controlado pelo Soccerserver de
acordo com o conjunto de regras do jogo. Além de simular
os movimentos da bola e dos jogadores, o servidor é ainda
responsável pela comunicação entre os clientes. As percepções
2
e ações dos jogadores são mapeadas em mensagens enviadas e
recebidas através do protocolo de comunicação executado entre
o Soccerserver e os agentes num ambiente de rede. Todas as
ações são tomadas pelos próprios clientes de forma autônoma,
que recebem do servidor informações visuais, auditivas e físicas
(Noda e Stone, 2000). Em virtude da arquitetura adotada, há
flexibilidade para que os jogadores sejam implementados em
qualquer linguagem de programação, desde que haja suporte
para o protocolo UDP (Noda e Stone, 2000). A figura 2 ilustra
as interações entre os componentes nesta arquitetura.
Soccer Monitor
Time A
Time A
A arquitetura do agente utilizada pelo time é hierárquica,
contendo três camadas com níveis diferentes de abstração
apresentada na figura 3 (de Boer e Kok, The Netherlands,2002).
A camada de base é a Interaction Layer responsável pela
interação com o ambiente de simulação soccer server . A
camada de nível médio é a Skills Layer a qual utiliza
funcionalidade disponibilizada pela camada Interaction Layer
para construir um modelo do ambiente e implementar as várias
habilidades de cada agente (intercepção de bola etc.). A camada
mais alta na arquitetura é a Control Layer que contém o
componente de raciocínio do sistema. Nesta camada, a melhor
ação possível é selecionada da Skills Layer que depende do
estado do ambiente atual e a estratégia atual do time.
Cliente 1
Soccer Server
UDP/IP
Cliente 11
UDP/IP
...
...
Cliente 1
et al. (2001) várias estratégias utilizadas em times como FC
Portugal-2000, CMUnited-99, Cyberoos-2000, dentre outros
foram aproveitadas.
Cliente 11
Figure 2: Arquitetura simplificada dos componentes envolvidos
na simulação
O servidor é constituído por três módulos que permitem a
comunicação com os clientes (Noda et al., 97). Os módulos
são o servidor (soccerserver), o visualizador (soccermonitor) e
o vídeo (logplayer). O servidor é o responsável por realizar a
simulação de jogos utilizando para tal uma arquitetura clienteservidor. O monitor é a ferramenta que permite visualizar os
jogos virtuais realizados com o auxílio do simulador. Comunicase com o servidor também através de sockets UDP, recebendo
deste as posições de todos os objetos no campo virtual. Efetua
depois o display gráfico desta informação de forma a permitir
aos humanos a visualização do jogo. O vídeo é uma aplicação
que permite a visualização de jogos pré-gravados (arquivos log).
A sua utilização é associada à utilização de um monitor de forma
a poder visualizar os jogos.
4 O TIME UVA TRILEARN
Entre os times participantes da liga simulada da Robocup, o
time UvA Trilearn foi escolhido para ser utilizado como base
de estudo e investigação de técnicas de IA, especificamente
a implementação de habilidades de jogo para sistemas
multiagentes. A escolha desse time deu-se em função de alguns
fatores tal como a documentação completa disponibilizada e
os artigos descrevendo algumas técnicas utilizadas pelo próprio
time.
A sua primeira versão foi elaborada em 2001 pelos estudantes
Remco de Boer e Jelle Kok da área de computação e Inteligência
Artificial do grupo Intelligent Autonomous Systems (IAS) da
University of Amsterdam (de Boer et al., 2001) como parte dos
seus projetos de conclusão de curso, tendo continuação nos
trabalhos do doutorado de Jelle Kok. O foco dado nesta versão
do time foi apenas nas estratégicas básicas dos jogadores (passe,
chute...) construídas desde o inicio. Nas versões posteriores
foram acrescentadas gradativamente habilidades e estratégias de
jogo, interação, percepção e comunicação. Segundo de Boer
VII SBAI / II IEEE LARS. São Luís, setembro de 2005
Figure 3: Arquitetura UVA Trilearn
Durante uma partida de futebol, percepções entram no sistema
através da Interaction Layer e é enviada para a Skills Layer
onde elas são usadas para atualizar o modelo do ambiente do
agente. A informação mais recente do estado do ambiente
é então usado pela Control Layer para considerar a melhor
ação possível. A ação selecionada pela Control Layer é
trabalhada subseqüentemente fora na Skills Layer que determina
o comando de atuação apropriado. Este comando é executado
então pelo módulo de Actuador Control na Interaction Layer.
Estão apresentadas na lista abaixo, as colocações nos
campeonatos em que o time UvA Trilearn participou.
German Open 2001 - 5◦ lugar
World Cup 2001 - 4◦ lugar
German Open 2002 - 1◦ lugar
World Cup 2002 - 4◦ lugar
German Open 2003 - 1◦ lugar
American Open 2003 - 1◦ lugar
World Cup 2003 - 1◦ lugar
American Open 2004 - 1◦ lugar
World Cup 2004 - 4◦ lugar
World Cup 2005 - 10◦ lugar
3
4.1 O Código disponibilizado
O código liberado pela equipe de desenvolvimento, referente ao
time que participou da Robocup 2003, contém implementação
das camadas Interaction Layer e Skills Layer, compreendendo
métodos de sincronização agente-ambiente, modelo do
ambiente, e algumas habilidades dos jogadores.
Dentre as características do time básico liberado destacamse: a) a estratégia de chute, onde o jogador ao interceptar
a bola chuta-a para a direção oposta de forma aleatória
indiferentemente da posição do seu oponente no campo; b)
a formação do time, onde os jogadores permanecem em suas
posições estratégicas determinadas pelo seu tipo (home position)
levando em consideração a posição da bola.
Aspectos relacionados a habilidades de drible e modelagem
do oponente na habilidade de interceptação, que também são
considerados aspectos do nível básico de decisão não estão
disponíveis no código liberado.
A intenção da equipe oficial de desenvolvimento do time era
liberar um código básico para servir como ponto de partida para
elaboração de novos times. Considera-se que o código liberado é
um bom inicio para investigação de sistemas multiagentes, mas
não suficientemente bom para ser usado em competições.
Figure 4: Área Delimitada para chute a gol
entre os centros do jogador com a posse da bola e os possíveis
receptores, cujos comprimentos são definidos como "D". Em
seguida, é analisada a distância "d" entre os centros de todos
oponentes e este segmento. Caso não haja adversário a uma
distância "d" inferior a 1/5 de "D", o jogador é considerado
desmarcado.Esta análise é ilustrada na figura 5. A mesma
heurística foi utilizada em relação à saída de bola a partir do
goleiro.
O código foi desenvolvido utilizando-se a linguagem orientada a
objetos C++, e a concepção da arquitetura adotada no algoritmo
encontra-se estruturada em um conjunto de classes. Classes
responsáveis pelo nível de decisão mais alto não fazem parte do
código liberado e não serão abordados neste artigo.
5 IMPLEMENTAÇÃO DAS HABILIDADES
No código liberado, na habilidade de chute, o jogador mais
rápido intercepta a bola e chuta em direção do gol, escolhendo
um dos lados do gol como alvo, considerando apenas o tempo
decorrido no jogo. Para efetuar o chute o jogador escolhe o
canto esquerdo se o tempo for par e o canto direito se este for
ímpar. Isso é feito sem se levar em conta a posição do jogador
em relação ao gol inimigo, a posição de seus companheiros de
time e a posição de seus oponentes. A habilidade de passe
não foi implementada no código liberado. Os demais jogadores
se movem para a posição estratégica que é determinada pela
formação e pela posição da bola.
O trabalho relatado neste artigo propõe a implementação da
habilidade de passe e a otimização da habilidade de chute a gol,
através da utilização de técnicas de IA. A habilidade de chute a
gol foi otimizada a partir de regras heurísticas de acordo com a
seguinte lógica: é verificada a distância entre o jogador e o gol
adversário. Caso a distância seja menor que 1/3 do comprimento
do campo, é efetuado o chute a gol. A figura 4 ilustra a área de
chute.
Caso o jogador se encontre fora da área delimitada para o chute
a gol, será verificada a possibilidade do passe. A habilidade de
passe foi também implementada a partir de regras heurísticas
e possibilita o jogador tomar a seguinte decisão: passar a bola
para o companheiro mais apto ou chutar a gol. O companheiro
mais apto é definido como aquele que se encontra na posição
mais ofensiva e sem marcação. São traçados segmentos de reta
VII SBAI / II IEEE LARS. São Luís, setembro de 2005
Figure 5: Tomada de decisão para o passe
5.1
Resultados Obtidos
Após a implementação das habilidades, pôde-se observar que o
time melhorou muito a qualidade do passe, tornando possível a
triangulação. Houve também um aumento considerável da posse
de bola, devido à redução da interceptação pelo oponente. A
saída de bola a partir do goleiro foi notadamente otimizada, com
uma redução drástica dos passes errados. A eficácia do chute
a gol foi aperfeiçoada, já que o mesmo só é efetuado a uma
distância mais representativa em relação à possibilidade de gol.
Foram realizadas várias simulações confrontando o time oficial
UvA Trilearn 2003 com o time baseado no código liberado pela
equipe de desenvolvimento, sem alterações. Em seguida, foram
realizadas partidas entre o UvA Trilearn 2003 e o time baseado
no código modificado. Comparações de desempenho entre os
cenários descritos podem ser realizadas a partir da análise da
tabela 1. De acordo com os resultados apresentados observa-se
um avanço considerável a partir das alterações realizadas.
6 CONCLUSÕES E TRABALHOS FUTUROS
Os resultados obtidos neste trabalho com a implementação da
habilidade de passe e a otimização da habilidade de chute a gol
4
Table 1: Resultados obtidos em simulações antes e depois da
implementação de estratégias de jogo
Partida
Time Básico Time Oxente
UvA Trilearn 2003
13 X 0
9X2
UvA Trilearn 2003
15 X 0
7X1
UvA Trilearn 2003
12 X 1
12 X 3
UvA Trilearn 2003
17 X 2
9X4
UvA Trilearn 2003
13 X 0
7X3
UvA Trilearn 2003
15 X 0
7X2
foram consideradas satisfatórios. A melhoria de desempenho
do time pôde ser comprovadas não apenas pelos resultados das
partidas realizadas, mas também a partir da observação dos
jogos.
RoboCup (2005a). Robocup World Championship Games,
http://www.robocup.org/games/31.html.
RoboCup
(2005b).
RoboCupJunior,
http://www.robocup.org/junior/index.html.
RoboCup (2005c). RoboCupRescue: The Grand Challenge,
http://www.robocup.org/games/36.html.
Stone, P. e Veloso, M. (2000). Layered Learning and Flexible
Teamwork in RoboCup Simulation Agents, springer verlag
edn, RoboCup-99: Robot Soccer World Cup III.
Weiss, G. (1999). Multiagent Systems: A Modern Approach to
Distributed Artificial Intelligence.
As habilidades implementadas são consideradas neste trabalho,
apenas os passos iniciais de melhoria no processo de tomada
de decisão. Pode-se acrescentar a estas habilidades, aspectos
relacionados a comunicação e sincronismo entre os agentes
agentes, bem como a capacidade dos mesmos realizar avaliações
e sugestões em uma jogada específica.
REFERÊNCIAS
Asada, M., Veloso, M., Tambe, M., Noda, I. e Kitano (2000).
Overview of RoboCup, Computer Science.
Briot, J. P. e Demazeau, Y. (2002). Principes et architecture des
systemes multiagents, Paris.
Cheny, M., Foroughi, E., Heintz, F., Huangy, Z., Kapetanakis,
S., Kostiadis, J., Noda, I., Obst, O., Riley, P., Steens, T.,
Wangy, Y. e Yiny, X. (2002). RoboCup Soccer Server - for
Soccer Server Version 7.07 and later.
de
Boer,
R.,
Kok,
J. e Groen,
F. (2001).
UvA
Trilearn
2001
Research
Abstract,
http://www.science.uva.nl/
jellekok/robocup
edn,
RoboCup-2001.
de Boer, R., Kok, J. e Groen, F. (2002). UvA Trilearn 2001 Team
Description, berlin edn, Robocup-2001: Robot Soccer
World Cup V. Springer Verlag.
de Boer, R. e Kok, J. R. (The Netherlands,2002). The
Incremental Development of a Synthetic Multi-Agent
System: The UvA Trilearn 2001 Robotic Soccer Simulation
Team, university of amsterdam edn, Master’s Thesis.
Foroughi, E., Heintz, F., Kapetanakis, S., Kostiadis, K.,
Kummeneje, J., Noda, I., Obst, O., Riley, P. e
Steffens, T. (2001).
RoboCup Soccer Server User
Manual: for Soccer Server version 7.06 and later,
http://sourceforge.net/projects/sserver.
Kitano, H., Asada, M., Kuniyoshi, Y., Noda, I. e Osawa,
E. (1995). RoboCup: The Robot World Cup Initiative,
agents97 edn, Proceedings of the First International
Conference on Autonomous Agents.
Kitano, H., Tambe, M. e Stone, P. (1997). The RoboCup
Synthetic Agent Challenge, ijcai97 edn, International Joint
Conference on Artificial Intelligence.
VII SBAI / II IEEE LARS. São Luís, setembro de 2005
5