LEVANTAMENTO DE ESTRATÉGIAS DE GRANDES

LEVANTAMENTO DE ESTRATÉGIAS DE GRANDES EQUIPES DA
CATEGORIA SMALL-SIZE
Autor: Denis de Castro Pereira
Supervisão: André Luiz Carvalho Ottoni
Departamento de Software – Equipe UaiSoccer Robot Team
Universidade Federal de São Joao Del-Rei – UFSJ
São João Del-Rei, 2010
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
1. RoboDragons (Japão) Ano: 2008
•
Habilidade de cooperação entre 3 robôs: essa habilidade é chamada de “1-2-3 chuta”, que
executa uma série de passes e, em seguida, um tiro à meta. Para colocar cada robô em sua
posição adequada, é fundamental conseguir com sucesso essa cooperação.
•
Método da região dominante: O método de região dominante é um tipo de diagrama de
Voronoi. É calculado com relação a dois agentes, um dos quais é um colega e o outro é um
adversário. O diagrama divide a área do campo de futebol em duas regiões, onde uma
região é a que a equipe pode chegar mais rápido do que o adversário, enquanto
a outra é a que o adversário pode chegar mais rápido.
•
Algoritmo para o tiro 1-2-3:
[Processo de Seleção de ação]
Seja A o robô segurando a bola, e sejam B e C os robôs que colaboraram.
if (Robot A have a shoot line)
{ Robot A shoots.} else {
Search open space which is able to make a shooting line.
Robot C moves to the open space.
Calculate a dominant region.
if (Pass line is in the dominant region of the teammate)
{Direct play between robots A and C.} else {
Robot B moves to the appropriate position.
1-2-3 shoot play among robots A, B and C.
}
}
•
Posicionamento inicial:
O robô A tem a posse da bola e joga por um dos lados do campo, o robô B é o robô de
posicionamento central (um pouco recuado em relação a A e C), e o robô C joga pelo outro
lado.
O objetivo é uma troca de passes rápida entre os 3 robôs a fim de ludibriar a marcação dos
zagueiros do time rival e um conseqüente tiro ao gol numa linha livre, ou seja, sem nenhum
corpo a frente do gol.
1º Passo: O robô C se move para o espaço aberto que tem uma linha de tiro ao objetivo.
2º Passo: Se a linha de passe atravessa a região dominante do oponente, o robô B se move
para frente até sair dessa região. Como resultado, uma linha da passagem é feita nessa
região dominante (se este não for o caso, um re-agendamento é realizado). O robô B vira
para o robô C.
3º Passo: O robô A passa a bola para o robô B, então o robô B a passa para
o robô C, de acordo com o algoritmo de execução direta.
4º Passo: O robô C chuta a bola em direção ao gol.
2
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
2. GEAR (USP - São Paulo) Ano: 2008
O time é primeiramente dividido entre goleiro e linha, onde o goleiro obviamente é
responsável por não deixar a bola entrar no gol e ficar sempre protegendo o mesmo,
enquanto os outros robôs do tipo linha têm um conjunto de comportamentos baseados
em mapas potenciais. Assim, os robôs de linha usam um sistema de Inteligência
Artificial (IA) híbrida. Esta IA é composta pelos seguintes comportamentos:
•
get ball - movimenta o robô para chegar até a bola;
•
make pass - o robô procura e executa um passe;
•
wait pass - o robô espera o passe de quem está com a bola;
•
shoot - tenta chutar para o gol;
•
defend - tenta ficar entre a bola e o gol.
•
Esses são os possíveis comportamentos dos robôs, sendo que um dado robô
possui um destes comportamentos num dado momento do jogo. Este
comportamento é dado por uma função de motivação, a qual é definida por um
conjunto de variáveis que favorecem a utilização de um dado comportamento.
•
Todos os comportamentos citados acima utilizam os mapas potenciais para
executar a navegação (quando necessária), ou para tomar uma decisão que leve a
execução de um comportamento (como por exemplo, o robô que está menos
marcado).
3
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
3. Furgbol (RS) Ano: 2008
•
São Assumidos robôs e bola como agentes. A máquina de estado
está associada a cada agente. Uma Central de Sistema Deliberativo
percebe o ambiente (estado do agente) e possíveis planos de ações
associados
a
cada
membro
da
equipe.
Esta
fase
tem
dois
módulos principais: o Módulo de Visão Global e o Módulo de Planejamento.
•
O sistema de captura e processamento de imagens da FURG em 2008 era o sistema
RGB (red-green-blue), o módulo de Visão global se definia nesse sistema.
•
Todas as informações extraídas através do sistema de visão são enviadas para o
sistema de estratégia que irá planejar e tomar decisões que nortearão os robôs
através
do
campo
de
jogo.
Com as posições atuais e passadas, o Módulo de planejamento nos dá a melhor ação
associada a cada membro da equipe.
•
O módulo de planejamento é baseado em um modelo de mundo em que cada agente
tem um estado no jogo. Ele está relacionado com o estado dos jogadores e da bola.
As transições são dadas em função da dinâmica durante o jogo.
•
Etapa de percepção: Esta etapa transforma posição e informações de velocidade em
estados
associados
a
cada
agente.
Um conjunto de estados e transições (ações) são definidos para os estados da bola.
Eles são definidos com base nas posições relativas entre robôs e bola.
Estado
DISPUTADO
POSSSE
LIVRE
ADVERSÁRIO
GOL
Descrição
2 robôs adversários estão
perto da bola
Apenas
robôs
companheiros estão perto
da bola
Nenhum robô perto da bola
Apenas robôs adversários
estão perto da bola
A bola está nos limites do
gol
Ação
Recuperar a bola do
adversário
Se mover (com a bola)
Se mover (sem a bola)
Seguir o adversário
Chutar
•
Para a estratégia do goleiro tem-se o cálculo da intersecção entre uma linha reta
vertical (paralela à linha do meio) que cruza o centro do eixo do gol e uma linha reta
obtida a partir da posição atual e anterior da bola. O ponto de intersecção é para
onde o robô deve mover-se.
•
A estratégia do defensor usa como informação a posição topológica da bola, para
mover o robô para a defesa da meta. Cada área tem uma linha vermelha vertical, que
4
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
representa o seu centro. Esta estratégia calcula a interseção entre esta linha vermelha
e uma linha reta criada a partir da posição atual e anterior da bola. O ponto de
interseção representa para onde um robô de defesa deve ir.
•
O papel do atacante é dividido em três diferentes estratégias, de acordo com a bola e
localização de robôs.
•
A primeira é aplicada quando o robô mais próximo à bola pode atacar. Ele ativa o
dispositivo de drible e vai em frente carregando a bola ou chuta na direção do gol
oposto. Ela acontece quando uma linha reta do centro da bola e do centro deste robô
cruza a linha reta vertical da meta, resultando em um ponto dentro dos limites da
meta.
•
A segunda estratégia de ataque ocorre quando a interseção anteriormente descrita
resulta em um ponto fora dos limites do gol oposto. Neste caso, o robô deve ser
colocado em uma posição válida para que ele possa carregar a bola para o gol.
Esta posição pode ser obtida pela interseção de uma linha reta que une os centros do
gol adversário e da bola com uma circunferência de raio pré-definido centrado na
bola.
•
A última abordagem acontece quando a interseção da primeira estratégia de
aproximação resulta em um ponto fora dos limites da meta oposta e a bola não está
entre o robô e a meta oposta. Neste caso, uma intersecção entre uma linha reta
vertical que passa pelo centro da bola e uma circunferência com um raio prédefinido centrado na mesma é realizada. Depois disso, a segunda e a primeira
estratégia de aproximação são aplicadas.
•
Cada uma destas três funções básicas fornece uma posição alvo para onde cada robô
deve mover-se. Além disso, o módulo de planejamento decide quando um robô deve
girar ou ativar o dispositivo de drible ou de chute. Estas ações acontecem quando o
robô está suficientemente próximo da bola para carregá-la ou chutá-la. A fim de
driblar ou chutar, o robô deve girar de forma que os dispositivos se posicionem em
frente à bola. O robô gira se o ângulo entre a sua frente e a posição correta é menos
de uma constante definida na interface.
•
A etapa de planejamento define o movimento do robô para chegar à posição alvo
evitando obstáculos. Assim, primeiro é verificado se uma trajetória linear para
a posição de destino é possível, sem qualquer colisão. Em seguida, a trajetória e os
obstáculos
no
campo
são
considerados
como
polígonos.
Se um dos vértices de um polígono que representa um obstáculo está dentro do
polígono da trajetória, haverá uma colisão.
•
Se o caminho em linha reta não é possível, aplica-se o método de decomposição
aproximada da pilha. Esta abordagem permite um planejamento de trajetória do
robô, sem qualquer colisão. Este método foi escolhido por ser simples, para fornecer
uma decomposição uniforme e de ser adequado para viabilizar a
realização de Precisão.
5
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
•
O método divide o campo em três células possíveis: vazia, ocupada ou de mistura.
As células vazias não contêm obstáculos em seu interior. As cheias são
completamente cheia de obstáculos. A célula de mistura contém uma parte cheia de
obstáculos e algumas partes vazias. As células de mistura são obtidas dividindo-se o
quadro principal pelo recuo das células até que ele receba um tamanho mínimo de
células, ou até que não fique nenhuma célula vazia ou cheia. Se escolhermos um
bom tamanho mínimo, suficiente para evitar obstáculos, temos um
tempo de processamento razoável.
•
Partindo do princípio de que, no final do processo, as células que foram divididas
estão cheias ou vazias, um gráfico é criado ligando as células vazias vizinhas. Para
uma célula ser vizinha de outra, um ponto comum é o suficiente. Posteriormente, é
executado um algoritmo de caminho mais curto que usa a ”Programação dinâmica
de Dijkstra”. No nosso gráfico, este algoritmo dá o caminho mais curto entre dois
nós (células vazias), dando uma trajetória otimizada prevista para cada robô, sem
colisão.
•
O planejamento de caminho é convertido em Vetores de velocidade e enviado para
os robôs.
6
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
4. Botnia Dragon Knights (China-Finlândia) Ano: 2008
A estratégia foi um pouco alterada em relação ao ano anterior. A mudança mais
importante é a inexistência da atribuição de “posições” aos robôs, ou seja, não existem
atacantes ou defensores. Em vez disso, concentrou-se na atribuição de tarefas mais
adequadas para certos robôs em um determinado tempo:
- Goleiro – a regra é única e exclusiva do goleiro, defesa da meta.
- TakeBall - é uma tarefa confiada ao robô mais próximo da bola. Ele tenta chegar
a bola e, se possível disparar para o gol ou passar para outro robô que têm melhor
posição para disparar.
- ProtectGoal - o robô tenta cobrir o caminho para o gol da melhor forma possível. Ele
tenta chegar ao oponente a certa distância e bloqueia o caminho para a meta.
- Defender - abrange os robôs adversários livre, torna-os incapazes de receber um passe.
- FindClearSpot - vai para uma posição de onde se pode receber um passe de outro robô
do time e tem o caminho da meta livre para o chute.
•
Para o Goleiro, a tarefa é atribuída de antemão, e não muda durante o jogo.
TakeBall é atribuído ao robô mais próximo da bola. A estratégia calcula o custo
de cada tarefa para cada robô e em seguida, atribui tarefas a robôs, de modo que
o custo total seja o menor possível.
•
Este sistema garante que a eficiência seja muito alta, com os robôs fazendo
menos trabalho, sendo mais rápidos, e consumindo menos energia. A maior
vantagem do sistema é que a estratégia não é esquemática. As posições não são
previamente definidas e, assim, torna mais difícil a previsão para as equipes
adversárias.
7
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
5. B-Smart (Alemanha) Ano: 2008
A principal característica dessa equipe é a divisão entre três instantes de estratégia:
antes, durante e depois do desenvolvimento da jogada.
Um agente prevê a parte de inteligência artificial do sistema de software. Ele
recebe uma representação abstrata do mundo (o modelo do mundo) e calcula
vetores de movimento de cada robô da própria equipe. A fim de facilitar a leitura de
dados, a aplicação é dividida em três módulos básicos: pré-comportamento,
comportamento e pós-comportamento.
O módulo de pré-comportamento extrai informações gerais, mas necessárias do
modelo de mundo real, por exemplo, uma formação adequada. Alguns módulos tentam
adivinhar se um comportamento anteriormente escolhido funcionou bem para a própria
equipe e calcula dados utilizados mais tarde no processo decisório.
Os módulos de comportamento consistem basicamente no cálculo do movimento
desejado para cada robô, como por exemplo, o melhor caminho a seguir ou o melhor
companheiro para o passe.
Os resultados são então passadas para o módulo de pós-comportamento.
Cada robô tem o seu próprio conjunto de módulos de pós-comportamento. A sua tarefa
consiste em calcular o vetor de movimento para a posição de destino determinado.
Portanto, o planejador faz a detecção de possíveis colisões, a fim de se evitar obstáculos
e assim encontrar uma maneira segura para chegar ao destino dos robôs. Posteriormente,
um controlador PID analisa o caminho. Assim, o comando final é passado para o
módulo de comunicação.
•
Planejamento do Caminho: O sistema de planejamento do caminho é baseado na
aleatoriedade
em
tempo
real.
A idéia é utilizar as vantagens de um caminho que se modifica a todo tempo para
criar uma “árvore de possíveis caminhos” que se modificam a fim de encontrar
aperfeiçoar o trajeto.
O sistema cria uma árvore composta de vários pontos através do modelo de mundo real,
e executa o melhor caminho livre de colisões para chegar ao objetivo escolhido como
um alvo.
Para a criação de testes, o sistema faz uma varredura nos caminhos dos 5 agentes.
Após uma rápida exploração aleatória da árvore, um sistema reativo de pesquisa
chamado Dynamic Safety é utilizado. Ele melhora desempenho do planejamento de
caminhos, alterando a variação de valores e tentando evitar colisões.
8
Denis de Castro - Departamento de Software
Equipe UaiSoccer Robot Team – 2010
6. Conclusão
Estas equipes têm algumas diferenças quanto as suas estratégias, mas cada uma tem um
ponto forte que pode ser trabalhado para gerar o melhor desempenho possível para a
nossa equipe.
•
Botnia knight dragons: sem posições pré-definidas no campo de jogo, cada robô
ganha mais autonomia, podendo realizar jogadas mais bem estruturadas.
•
B-Smart: Módulo baseado em três intantes: antes, durante e depois do
desenvolvimento da jogada. Com essa divisão é mais fácil a extração máxima de
detalhes do campo, dos robôs e da bola.
•
Furgbol: Assumir robôs e bola como agentes. Realização do método das células.
Células vazias, ocupadas ou de mistura. Esse método é bem eficaz no que diz
respeito às colisões com outros corpos durante o trajeto do robô de um ponto ao
outro do campo de jogo.
•
Gear: Estratégias de jogadores de linha baseados em mapas potenciais. Em cada
momento do jogo um robô executa a melhor estratégia baseada nos mapas
potenciais.
•
RoboDragons: habilidade de cooperação entre 3 robôs, estratégia bastante
eficiente como mostrado no vídeo da equipe. Consiste numa troca de passes
entre três robôs e um conseqüente tiro à meta.
7. Referências
http://www.fei.edu.br/~flaviot/LARC2008/equipesRobocup.html
http://small-size.informatik.uni-bremen.de/robocup2008:teams
9