- Universidade Federal Fluminense

ÍCARO DOS SANTOS
FRANÇA
SIMULAÇÃO DE MOVIMENTO DE ROBÔS NUM
AMBIENTE COOPERATIVO DE FUTEBOL
Dissertação apresentada ao
Departamento de Engenharia
Mecânica da UFF como parte
dos requisitos para a obtenção
do título de Mestre de Ciências
em Engenharia Mecânica.
Orientadora:
Fabiana R. Leta
Departamento de Engenharia Mecânica
Universidade Federal Fluminense
Niterói
2001
AGRADECIMENTOS:
Ao professor Heraldo S. da Costa Mattos pela orientação e estímulo neste trabalho
e durante o curso de mestrado, concernente às noções de Cálculo Tensorial, e à professora
Aura Conci, pelas noções de Teoria dos Autômatos.
2
“Omne tulit punctum,Qui miscuit utile dulci”
( Horácio, Arte Poética, 343 )
“Sublata causa, tollitur effectus”
(Aristóteles, Metafísica ,VIII)
3
SUMÁRIO:
I - AGRADECIMENTOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 2
II- EPÍGRAFE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
III- SUMÁRIO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
IV- RESUMO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
V- ABSTRACT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .8
1. - INTRODUÇÃO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9
1.1 - ORGANIZAÇÃO DA TESE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
2. - FUTEBOL DE ROBÔS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .10
2.1 - HISTÓRICO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . 10
2.2 - MULTIDISCIPLINARIDADE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .11
2.3 - CATEGORIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
2.3.1- MIROSOT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21
2.3.2- HUROSOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .22
2.3.3- NAROSOT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4
2.3.4- KEPHERASOT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 - SISTEMA DE FUTEBOL DE ROBÔS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
2.4.1- ESTRUTURA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
2.4.2- SISTEMA DE VISÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.3- INTELIGÊNCIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3. - SISTEMAS EXISTENTES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .29
3.1 - EXEMPLO DE UM SISTEMA REAL – EQUIPE GUARANÁ . . . . . . . . . . . . 29
3.1.1- ESTRATÉGIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 - SISTEMA DE VISÃO. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.1.3 - DETERMINAÇÃO DE TRAJETÓRIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2. - OUTROS SISTEMAS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2.1 -CARNEGIE-MELLON UNIVERSITY MILIBOT SIMULATOR.. . . . . . . . . . 47
3.2.2. - TOKYO -U SIMULATOR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.3 - ROBOWIN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.4. -UNESP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.3 – COMPARAÇÃO DE SISTEMAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4-SIMULADOR DE FUTEBOL DE ROBÔS . . . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . 54
4.1- CONSIDERAÇÕES INICIAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2 - IMPLEMENTAÇÃO DE UM SIMULADOR DE FUTEBOL . . . . .. . . . . . . . . . 57
4.3 - SIMULADOR DE FUTEBOL DE ROBÔS DESENVOLVIDO . . . . . . . . . . . . 62
5 - RESULTADOS OBTIDOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
6- CONCLUSÕES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
7 –REFERÊNCIAS BIBLIOGRÁFICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8 – BIBLIOGRAFIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5
APÊNDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
A. -APÊNDICE:
ALGORITMO DE VISÃO COMPUTACIONAL . . . . . . . . . . . . . . . .. . . . . . . . . . . . 81
A.1 - DEFINIÇÃO DOS MOMENTOS
GEOMÉTRICOS DE INTERESSE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
A. 2 - ESPECIFICAÇÃO DO PONTO DE
OPERAÇÃO (“THRESHOLDING”) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
6
LISTA DE FIGURAS
Figura 2.1 Esquema do sistema de navegação
de um robô móvel autônomo. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 19
Figura 2.2 Orientação do robô por meio das etiquetas. . . . . . . . . . . . . . . . . . . . . . . . . . 20
Figura 2.3 Foto de jogadores da liga MIROSOT,
patrocinados pela PMC-Sierra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Figura 2.4 Time Narosot brasileiro – “Bravo” – em ação. . . . . . . . . . . . . . . . . . . . . . . 24
Figura 2.5 Jogador de um time S- Kepherasot. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 25
Figura 3.1 Comportamento do goleiro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Figura 3.2 Estados do goleiro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Figura 3.3 Área de transição. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Figura 3.4 Comportamento do defensor e do atacante. . . . . . . . . . . . . . . . . . . . . . . . . . 35
Figura 3.5 Etiqueta de separação dos robôs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Figura 3.6 Fotografia do Time Guaraná em ação . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 37
Figura 3.7 Evitando obstáculos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Figura 3.8 Simulador Millibot da Carnegie-Melon University. . . . . . . . . . . . . . . . . . 49
Figura 3.9. Interface do Simulador Robocup Oficial. . . . . . . . . . . . . . . . . . . . . . . . . . . 50
Figura 3.10 Simulador UNESP – CBFR ( Oficial ). . . . . . . . . . . . . . . . . . . . . . . . . . 52
Figura 3.11 Tabela 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
7
Figura 4.1 Interface Visual do Simulador
de Pegoraro & Costa ( 1998). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Figura 4.2 Sistema de navegação original . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Figura 4.3 Sistema de navegação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
Figura 4.4 Sistema de navegação modificado em JAVA . . . . . . . . . . . . . . . . . . . . . . . 67
Figura 4.5 Fluxograma do sistema de navegação
do simulador de futebol de robôs . . . . . . . . . . . . . . . . . . . . . . . . .68
Figura 4.6 Fluxograma do algoritmo de “Clipping”. . . . . . . . . . . . . . . . . . . . . . . . . . . 69
Figura 4.7. Possíveis localizações da bola (coordenadas Xb,Yb) com relação
ao jogador (A,B,C,D,E,F,G,H), explicando o algoritmo apresentado
na figura 4.6 e definindo os 8 quadrantes possíveis de localização
da bola. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
Figura 4.8. Determinação dos parâmetros de ângulo do jogador e da bola. . . . .. . . . . . 71
Figura 5.1 Sequência de imagens do simulador desenvolvido
em JAVA . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Figura 5.2 (a). Manobra complexa do atacante azul . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Figura 5.2 (b). manobra complexa do atacante azul . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8
RESUMO:
A presente tese é o primeiro trabalho na UFF na área de robôs autônomos móveis
a estabelecer um procedimento de pesquisa em termos de trajetórias de movimentos de
robôs em ambientes randômicos, juntamente com uma revisão sobre os conceitos
envolvidos. Através do exame de um problema padrão onde um grande escopo de
tecnologias pode ser integrado e examinado
(sistemas de navegação, Visão
Computacional, algoritmos de Inteligê ncia Artificial e transmissão de dados remotos)
escolhe-se como paradigma as competições existentes de futebol de robôs. Este ambiente
cooperativo de simulação de movimento servirá de base para testes de futuras pesquisas de
estratégias em tais ambientes. Para isto tem-se como um dos paradigmas o sistema
desenvolvido pela Escola Politécnica de São Paulo para o time de futebol de robôs
“Guaraná”, que segue as regras preconizadas pela MIROSOT coreana.
9
ABSTRACT:
The present thesis is the first work on Mobile Autonomous Robots done at
UFF to foster AI and Autonomous Mobile Robots research proceedings about movement
trajectories in a randomical environment and a resume of the adopted proceedings on these
subject. At examing a standard problem where a wide range of technologies can be
integrated and organized (navigation systems, machine vision, AI algorithms and so on)
that is described by the main paradigms as the system developped by The Escola
Politécnica de São Paulo for the soccer robot team called “GUARANÁ”, which follows up
the competition rules of the korean MIROSOT.
10
1. INTRODUÇÃO
Muitos sistemas de navegação têm sido propostos para o controle autônomo de
robôs móveis em ambiente cooperativo ( mais de um robô que coopera com outros robôs
para um resultado comum ), podem-se citar como exemplo o sistema com lentes “Olho-dePeixe” [6] e o “Spartan” [4]. As medidas de posição são muito importantes e alguns
sistemas de navegação têm incorporado um sensor omnidirecional para a obtenção do
ambiente em torno do robô móvel.
A motivação desta tese consiste no estudo de sistemas simulados que podem ser
implementados em sistemas reais de navegação. Em trabalhos prévios, (Kurata, Grattan e
Uchiyama, 1998 [5]; Pegoraro e Costa, 1998 [2]; Herbert e Hennenberger, 1998 [4]) tais
sistemas de navegação têm sido propostos para coletar este tipo de informação pelo uso de
métodos tais co mo:
(1) Rotação da câmera por meios mecânicos e,
(2) Transformando um campo omnidirecional em uma imagem
11
simples, pelo uso de um elemento ótico especial, por exemplo
espelhos cônicos, hiperbólicos e por lentes especiais, como a
Olho-de-Peixe”.
Assim na presente tese discute-se
um sistema de navegação simulado, que
futuramente pode ser implementado em caso real, considerando-se um sensor visual
omnidirecio nal para um robô móvel de um time de futebol de robôs. O sensor visual é
composto simplesmente por uma câmera CCD (Charged Couple Device) acima do campo
de futebol de robôs. Pela obtenção do centróide do robô e do ponto de referência através do
sensor CCD, obtem-se a posição do robô móvel com respeito ao solo integrando dois
conjuntos de informações:
(1) A posição relativa entre o alvo de referência no robô e a câmera no
teto
(2) O ângulo rotacional do robô relativo aos eixos principais de referência.
Para a obtenção destes parâmetros geométricos faz-se necessário um programa de
reconhecimento de imagens que distingua os dados do robô móvel dos do cenário geral ao
fundo, assim como dos outros robôs do time adversário e a bola. Um programa de
determinação automática que distingua os parâmetros relevantes para o sistema de
navegação, elegante e geometricamente preciso, deve ser usado.
12
1.1 ORGANIZAÇÃO DA TESE
No capítulo 2, apresenta-se um histórico sobre os campeonatos de futebol de robôs,
destacando-se um histórico das competições de futebol de robôs (seção 2.1),
multidisciplinaridade e detalhes da categoria MIROSOT (seções 2.2 e 2.3), sistema de
posicionamento e algoritmo de visão computacional (seção 2.4) com abordagens sobre os
momentos geométricos de interesse.Apresenta-se um caso real – o Time Guaraná , seu
sistema de visão computacional e de posicionamento. Por fim tem-se uma análise detalhada
de outros tipos de simuladores de ambientes cooperativos entre robôs (capítulo 2.7).
Com estes subsídios, pode-se iniciar a implementação computacional de um
simulador de futebol de robôs: o programa inicial de Pegoraro & Costa em DELPHI (seção
3.1), o programa do autor em JAVA, com um exame de certos detalhes do programa de
Pegoraro & Costa (capítulos 3.2 e 3.3) e uma analise do programa em JAVA do autor
(Capítulo.4), uma avaliação (capítulo 5) e a conclusão(capítulo 6). No Apêndice encontrarse-ão subsídios teóricos necessários para trabalhos futuros de implementação de um sistema
de visão de futebol de robôs.
13
2. FUTEBOL DE ROBÔS
2.1. HISTÓRICO
Na história da Inteligência Artificial e da Robótica, o ano de 1997 pode ser
considerado como o momento de decisão: em Maio de 1997 o IBM Deep Blue derrotou o
campeão mundial de xadrez. Em 4 de Julho de 1997, a Missão Pathfinder da NASA
conseguiu um pouso bem sucedido na superfície de Marte e seu veículo robô – Sojourner realizou a contento suas atividades programadas.
A idéia do futebol de robôs foi pela primeira vez mencionada pelo Professor Alan
Mackworth (University of British Columbia, Canadá) e uma série de artigos sobre o projeto
de futebol de robôs foi publicado por este grupo. Independentemente, um grupo de
pesquisadores japoneses organizou um workshop sobre grandes desafios em Inteligência
Artificial em Outubro de 1992 em Tóquio. Este grupo iniciou uma séria discussão sobre o
uso de futebol de robôs para a promoção da Ciência e da Tecno logia. Séries de estudos
foram feitos sobre possibilidades tecnológicas, impacto social e possibilidades financeiras.
Em adição, as primeiras regras de competição foram delineadas para competição de futebol
de robôs e simuladores. Como resultado destes estudos em Junho de 1993 um grupo de
pesquisadores incluindo Minoru Asada, Yasuo Kuniyoshi e Hiroaki Kitano decidiram
iniciar a competição de futebol de robôs, primeiramente chamada de J-League, e dentro de
um mês receberam apoio entusiástico de vários outros pesquisadores de todo o mundo.
14
Com este apoio internacional a competição foi rebatizada de Robot World Cup Iniciative
ou “RoboCup”.
Concorrente a esta discussão, muitos outros pesquisadores utilizaram o jogo de futebol
como domínio de pesquisa. Por exemplo, Itsuki Noda, do Laboratório Eletrotécnico
Governamental do Japão (ETL), conduziu uma série de pesquisas em robótica multi-agente
usando o futebol e criou o primeiro simulador de futebol de robôs, mais tarde adotado como
o modelo oficial da SONY . Outros como Minoru Asada, da Universidade de Osaka e os
professores Manuela Veloso e Peter Stone, da Universidade Carnegie-Melon,
desenvolveram seus próprios sistemas, ampliando o escopo da RoboCup a um efetivo nível
internacional. A primeira competição oficial da RoboCup (patrocinada pela SONY) , com
suas respectivas conferências tecnológicas, foi realizada em Nagoya, Japão, de 23 a 29 de
Agosto de 1997. Mais de quarenta times participaram de todas as partes do mundo. O
vencedor da J-League foi o AT-Humboldt, da Universidade Humboldt, Alemanha, que
venceu o time AndHill do Instituto de Tecnologia de Tóquio na final. O terceiro lugar foi
para o ISI Synthetics (ISIS) da ISI/USC, que derrotou o CMUnited da Universidade
Carnegie-Melon.
Atualme nte a nível mundial, existem duas federações envolvidas com o Futebol de
Robôs: a RoboCup e a FIRA (Federation of International Robot- Soccer Association Federação Internacional de Futebol de Robôs Autônomos). Cada uma delas possui suas
próprias regras, torneios, conferências técnicas e patrocinadores principais. Existem
também as chamadas ligas (NAROSOT, KEPHERASOT e outras), que são subdivisões
baseadas no tamanho e complexidade dos robôs. Cada uma destas ligas segue regulamentos
próprios porém todas têm um objetivo em comum: promover a evolução de uma tecnologia
15
e facilitar o acompanhamento e o progresso desta. Uma destas propostas é a Micro Robot
Soccer Tournment – MIROSOT, promovida pela FIRA.
O início efetivo do envolvimento brasileiro com o futebol de robôs autônomos
ocorreu em julho de 1995, quando o Instituto de Automação ( IA ) do Centro Tecnológico
de Informática da UNESP enviou alguns pesquisadores para o Centro de Pesquisas KAIST
(Korean Advanced Institiute of Science and Technology) em Seul, Coréia do Sul. A
viagem à Coréia foi uma resposta ao convite realizado a toda a comunidade internacional
pelo prof. Dr. John-Hwan Kim, para que pesquisadores envolvidos com os diversos
aspectos da robótica autônoma se reunissem e elaborassem um plano comum de
experimentação. Este grupo – a partir das regras básicas estipuladas pelos pesquisadores
coreanos – gerou as normas e acordos do que viria a ser a atual FIRA
2.2. MULTIDISCIPLINARIDADE
Como desafio tecnológico, o futebol de robôs é composto por vários problemaspadrão envolvendo teorias, algoritmos e arquiteturas de programação, que podem ser
utilizados para tratar das complexidades do dia-à-dia. Tais áreas incluem: fusão de sensores
em tempo real, comportamento reativo, aprendizagem, planejamento em tempo real,
sistemas multiagentes, reconhecimento de contexto, visão robótica, estratégias de decisão,
controle motor, controle de inteligência robótica e muito mais.
Além de propiciar o desenvolvimento destas áreas e de motivar prêmios como o
Scientific Challenge Awards e o Engineering Challenge Awards, programas de pesquisas
como os da RoboCup provêm um fórum para pesquisas de alta qualidade e de alto impacto,
tais como The RoboCup Physical Agent Phase I. Este consiste de três tarefas: movimento
16
da bola, recebimento da bola e passagem da bola. A tarefa de movimento da bola examina a
habilidade do robô de se aproximar da bola e para mover a bola até o lugar desejado por
meio de dribles ou chutes. Tal tarefa é desenvolvida sob trê s condições: ausência de
obstáculos, obstáculos estacionários e obstáculos móveis. A tarefa de recebimento da bola é
similar, exceto no detalhe em que lida com a interceptação de recebimento de bola. Após
estas duas tarefas terem sido razoavelmente cumpridas, a terceira tarefa – passar a bola pode então tomar lugar.
A construção de um sistema de medida de posição é composta essencialmente de
um sensor visual e de um alvo de referência sobre o robô móvel. O sistema inercial de
coordenadas está localizado na câmera CCD no teto, bem sobre a origem Ow, cuja altura Zr
é conhecida (cf. Figura 2.1, para as seguintes considerações) A origem do sistema de
coordenadas do alvo de referência está no topo do robô móvel, e seu eixo X é fixo,
apontando sempre para frente do robô móvel, segundo a regra de Ixx > Iyy (elemento da
matriz de inércia Ixx maior do que Iyy) ou pelo uso de uma tarja rosa na etiqueta-alvo de
referência propostos na seção 2. A altura do alvo de referência em relação ao solo – altura
máxima do robô ou diâmetro da bola – Zv – também é conhecida.
A posição relativa do robô em relação à câmera CCD é obtida através de dois
ângulos: um ângulo de zênite β entre o eixo Z do sistema de referência do robô móvel e a
câmera, e o ângulo azimutal α entre o eixo fixo X e o eixo Zw ( que projeta-se para o centro
da câmera CCD ). A distância do centróide da imagem ao centróide do objeto é r. O ângulo
θ, entre o eixo X e o centróide do alvo de referência captado pela câmera CCD, é igual ao
ângulo α entre o eixo X e o eixo da lente da câmera. As coordenadas do alvo de referência
são rotacionadas, acompanhando o movimento do robô, tornando-se necessário compensar
17
o ângulo rotacional α, que é obtido como parâmetro derivado da matriz de inércia I –
juntamente com a excentricidade e o traço – ou pela instalação de um giroscópio no interior
do robô móvel. Partindo destas considerações geométricas, a posição do robô em relação à
sala (xv ,yv ) é obtida pelo uso das equações seguintes:
x v = R. cos φ = Z c . tan β . cos(α + θ − π ) = ( Z r − Z v ). tan( r / f ). cos(α + θ ´−π )
y v = R. cos φ = Z c . tan β . cos(α + θ − π ) = ( Z r − Z v ). tan( r / f ). sen( α +θ − π ).
( 2 .1)
onde a constante f é a distância focal de lente, e a constante Zc é a distância do alvo de
referência até o sensor visual. O programa de processamento de imagens e os circuitos de
integração em tempo real e de comando são separados do robô e tem sua fonte de energia
externamente ao sistema. A distância r e o ângulo e o ângulo azimutal α podem ser
calculados a partir das coordenadas (xm ,ym ) do centróide da imagem pelo uso da equação
seguinte:
α = arctan( yt − y p / xt − x p )
18
( 2.2)
Figura 2.1. Esquema do sistema de navegação de um robô móvel autônomo
Ao fim deste procedimento de processamento, a posição do robô (xv ,yv ) é
calculada pelo uso das equações, comparando o valor do ângulo medido θc pelo ângulo
rotacional do robô α medido do eixo x do robô até o vetor (cp ,ct),com cp sendo o centróide
p (Cf. Figura 2.1) e ct o centróide da cor do time t. Para as dimensões do robô (padrão
MIROSOFT ) e da resolução da imagem usada é observado um desvio máximo de ±10
graus. A posição (x,y) de cada robô de um time de futebol de robôs resulta da média
ponderada das posições dos centróides da etiqueta do time e da etiqueta rosa (abordagem
particular de Pegoraro & Costa para o Time Guaraná – os dois centróides são empregados
para determinar o sentido de movimentação do robô):
19
xm =
ym =
c1 xt + c 2 x p
c1 + c 2
c1 y t + c2 y p
,
( 2.3)
c1 + c 2
onde (x t,yt) são as coordenadas do centróide do elemento da cor do time; (x p ,yp) são as
coordenadas do centróide do elemento p e c1 e c2 são fatores dependentes do tamanho das
etiquetas. As posições dos robôs adversários e da bola são definidos pelas coordenadas dos
centróides dos elementos das cores do time adversário e da bola, respectivamente As
orientações são determinadas pela direção do movimento, dada pela diferença entre a
posição dos elementos na imagem atual e na anterior.
Figura 2.2. Movimento do robô, orientado segundo a posição das etiquetas
20
2.3 CATEGORIAS
2.3.1 MIROSOT
Esta categoria é disputada entre dois times, cada um composto por três robôs de
dimensões máximas de 7,5 cm x 7,5 cm x 7,5 cm, num campo verde retangular de madeira
de 130 cm x 90 cm. Uma câmera instalada a uma altura mínima de 2 metros acima do
campo captura imagens do jogo, que são transmitidas a um computador (o ff – board)
responsável por um ciclo de controle bem definido. Cada time é identificado por etiquetas
de 3,5 cm x 3,5 cm colocadas sobre os robôs, sendo que um time deve possuir etiquetas
amarelas e outro, azuis. A bola utilizada é uma bola de golf laranja [2].
A liga S-MIROSOT possui as mesmas características, mas é disputada por times
compostos somente de um jogador e o goleiro,
21
Figura 2.3: Foto de jogadores da liga MIROSOT, patrocinados pela PMC-Sierra.
2.3.2 HUROSOT
A HUROSOT (Humanoid Robot World Cup Soccer Tournament – Torneio de
futebol de robôs com robôs humanóides) e´ uma liga de competição entre robôs
humanóides. Um robô humanóide tem duas pernas e seu tamanho é limitado à 40 cm em
altura e 15 cm em diâmetro – as pernas serão de 15 cm de diâmetro. A partida será
disputada entre dois times, cada um consistindo de três robôs, um dos quais sendo o
goleiro. Três componentes do time serão “humanos” são permitidos na partida: o treinador
e dois assistentes.
22
Os robôs humanóides já estão em fase de desenvolvimento, mas as regras ainda
estão sendo preparadas. A liga S-HUROSOT (Single Humanoid Robot World Cup
Tournament – torneio de futebol de robôs com robôs humanóides simples) possui as
mesmas carcaterísticas, mas é disputada por times compostos somente de um jogador e a
bola.
2.3.3 NAROSOT
A NAROSOT (Nano Robot World Cup Soccer Tournament – Torneio mundial de
futebol de Nano -robôs) é uma liga de competição de futebol de robôs de nano-tecnologia.
O tamanho de um robô será limitado à menos do que 3,75 x 3,75 x 3,75cm e a partida será
disputada entre dois times, cada um com três robôs, sendo um dos robôs o goleiro. Três
componentes “humanos” são permitidos na partida: o treinador e dois assistentes. Um
computador de controle é permitido para cada time, para o processamento de visão e outros
programas de localização e identificação. A S-NAROSOT (Single Nano Robot World Cup
Soccer Tournament – torneio mundial de futebol de nano-robôs) possui as mesmas
características, mas é disputada por times compostos somente de um jogador e o goleiro.
23
Figura 2.4 : Time Narosot brasileiro – “Bravo” – em ação.
2.3.4 KEPHERASOT
A KEPHERASOT (Khepera Robot World Cup Soccer Tournament - Torneio
mundial de futebol de robôs do tipo Kephe ra ) é uma liga de competição de futebol de
robôs com robôs kephera (besouro). A partida é jogada entre dois times, cada um
consistindo de três robôs kephera, um dos quais é o goleiro. Três componentes “humanos”
são permitidos em cada partida: o “treinador” e dois assistentes, com um computador de
controle por time, principalmente dedicado ao processamento de visão e outros programas
de localização e identificação. Exceto pelo tamanho dos robôs e do campo, as regras da
competição são similares às da MIROSOT. A S-KEPHERASOT (Single Khepera Robot
World Cup Soccer Tournament - Torneio mundial de futebol de robôs com robôs Kephera)
Possui as mesmas características, mas é disputada por times compostos somente de um
jogador e o goleiro.
24
Figura 2.5 : Jogador de um time S- Kepherasot.
25
2.4. SISTEMA DE FUTEBOL DE ROBÔS
2.4.1 ESTRUTURA
Sistemas de futebol de robôs são chamados sistemas de controle inteligente multiagente. Um sistema de controle inteligente é um sistema que pode controlar incertezas, é
autônomo e com capacidade de aprendizado. Este tipo de sistema tem que ser equipado
com a habilidade de reagir à vizinhança, processar dados, resolver problemas aprendizado
e raciocínio. Lógica Fuzzy, Redes Neurais Artificiais e Computação Evolucionária são os
algoritmos que podem melhorar a inteligência de um sistema de futebol de robôs. Todos
estes algoritmos são motivados pelo fato que eles podem imitar o raciocínio e o padrão de
comportamento de um ser huma no. Um sistema multi-agente consiste de vários
subsistemas individuais, com seus mecanismos próprios de movimento, que podem se
comportar independentemente e também cooperar com os outros membros de seu time. A
vantagem de se usar um sistema multiagente é que ele pode resolver problemas bastante
complicados, que de outra forma seriam de resolução difícil.
Um sistema de futebol de robôs possui as características tanto de um sistema
multi-agente como de um sistema de controle inteligente – daí o interesse em seu estudo.
Um sistema de futebol de robôs consiste em robôs, sistema de visão, equipamento de
comunicação e um computador principal. Para a construção de tal sistema, são necessárias
várias tarefas como: escolher uma CPU, projetar o mecanismo de movimento dos robôs,
26
escolher sensores, programas e o comportamento dos robôs. A inteligência pode ser
construída na CPU principal, dentro do robô móvel ou em ambos. Isto faz a diferença entre
um sistema de futebol de robôs baseado na visão e um sistema de futebol de robôs
baseado nos robôs (item 2.4.3).
2.4.2 SISTEMA DE VISÃO
O sistema de visão é utilizado para encontrar objetos em um playground, por
exemplo. No futebol de robôs, este procedimento tem como fundamneto a dife renciação
plena ( segmentação ) de todos os componentes da imagem – robôs e bola – do fundo da
imagem, por meio de procedimentos de “Thresholding” (Cf. Apêndice desta tese). A
identificação de cada componente do time e da bola é providenciada pela escolha judiciosa
das cores de cada time – azul e laranja - pois permitem um contraste maior (Cf. capítulo
3.1.2, onde a técnica empregada pelo TIME GUARANÁ é explicada com alguns detalhes
adicionais) e que emprega subtração inicial de imagens entre componentes da imagem e
plano de fundo.é empregado um sistema RGB de três cores e não um padrão de cinza, pois
a informação das cores é utilizada para localizar a posição dos objetos já que, com somente
imagens em escala de cinza, é difícil distinguir entre objetos de brilho semelhantes[3].
2.4.3 INTELIGÊNCIA
A escolha do ambiente de futebol de robôs como fonte de estudo da presente tese
deve integrar conceitos de diversas áreas como: Visão Computacional, Agentes
27
Autônomos, Multi-Age ntes, Inteligência Artificial, Robótica, Controle, Sistemas de Tempo
Real, Engenharia de Software, entre outros. Nenhum sistema integrando todos estes
conceitos é superior ou melhor do que outro: somente são distintos onde a inteligência
artificial é constituída. As propriedades destes sistemas [3] são descritas abaixo:
1) Sistema de futebol de robôs baseado em visão:
a) Sistema de futebol de robôs por controle remoto sem inteligência instalada
individual. Vantagem: estrutura simples e fácil de se construir, programação
flexível.
Desvantagem: requer computação realmente rápida e não
permite instalação de outros sensores como de toque
ou infravermelho.
b) Sistema de futebol de robôs com Inteligência Artificial à bordo
Vantagem: sistema fácil de modularizar e expandir e permite
o uso de sistemas de visão menos eficientes.
Desvantagem: risco de perca de consistência entre o programa
principal de navegação e o sistema de Inteligência
Artificial instalado nos robôs.
2) Sistema de futebol de robôs baseado nos próprios robôs:
Vantagem: fácil desenvolvimento com múltiplos robôs, com
resposta rápida e efetiva a mudanças ambientais.
Desvantagem: construir o robô é complicado e as
comunicações entre eles devem ser totalmente
eficientes.
28
3. SISTEMAS EXISTENTES
3.1. EXEMPLO DE UM SISTEMA REAL – EQUIPE GUARANÁ
3.1.1 ESTRATÉGIAS
No time “Guaraná”[2] foram utilizados três comportamentos estratégicos principais,
que cada robô pode assumir de acordo com sua posição: goleiro, defensor e atacante. Um
robô fixo é designado para ser o goleiro, devendo sempre manter este comportamento. Já os
outros dois robôs alternam de comportamento, dependendo do estado do jogo; no entanto
sempre um deles é o atacante e o outro o defensor.
O comportamento do goleiro consiste em colocar-se na posição projetada da bola na
linha defensiva do gol. Nas outras situações, o goleiro permanece sempre em frente ao gol.
Este transita entre três estados, cada um com uma ação associada: colocar-se na posição
projetada do movimento da bola (estado i); colocar-se na posição final da bola yb (estado ii)
e colocar-se no centro do gol (estado iii). O programa de simulação anexo exemplifica de
forma clara estes comportamentos.
29
O estado i do goleiro é o mais importante – é nele que as defesas realmente
acontecem. Nele, a linha de defesa é determinada por x gol ( linha onde o robô deve
permanecer) e por yprev (ordenada prevista do cruzamento da bola e da linha xgol). O yprev é
calculado pela equação:
y prev = yb −
dyb ( xb − x gol )
(3.1)
dxb
sendo
(x b ,yb ) a coordenada da bola,
(dx b,dyb ) os deslocamentos em x e y, da bola observados nos últimos quadros,
xgol a linha onde o robô goleiro deve permanecer para não sair da área nem invadir o gol.
Nos três estados (i, ii, iii ) a abcissa do robô é sempre x gol. Já a ordenada dos estados
nos estados i e ii é calculada, mas sempre respeitando os limites do gol:
y g min ≤ y prev ≤ y g max
onde:
30
(3 . 2 )
ygmin e ygmax são os limites inferior e superior do gol.
Estes valores estão definidos pelas dimensões do campo e do gol. Já as transições
entre os três estados ocorrem segundo as seguintes regras:
(1) xb < d1 e dxb < 0,
(2) xb <d2 e dxb < 0,
(3) xb ≥ d2
onde:
(x b ,yb ) é a coordenada da bola,
dxb é o deslocamento da bola (dx b >0, indica bola se dirigindo ao campo adversário ),
d1 é o limite estratégico a partir do qual o robô goleiro pode chegar à posição prevista da
bola para efetuar a defesa (valor empírico: 40 cm),
d2 é o limite estratégico a partir do qual se considera que não existe perigo iminente.
Figura 3.1. Comportamento do goleiro
31
Figura 3.2. Estados do goleiro
A posição alvo do defensor situa-se na coordenada y da bola em uma faixa de
defesa distanciada de 30cm a 60cm do gol, bloqueando a bola para evitar sua trajetória ao
gol ou obstruindo um possível chute do adversário. Porém, o defensor sai do caminho da
bola para permitir que o atacante do mesmo time leve a bola para longe da área de defesa.
Quando o defensor e a bola estão em uma situação favorável com respeito ao gol
adversário, ocorre uma permuta de comportamento do defensor com o atacante,
simplificando e agilizando uma situação de ataque ao gol adversário. As situações
favoráveis acontecem quando o defensor é o robô mais próximo da bola e, além disso,
quando ele se encontra na área de transição.
32
Figura 3.3. Área de transição.
O atacante tem dois estados distintos: (i) modo de posicionamento, quando o
alvo g é colocado atrás da bola numa posição que permita a condução da bola ao gol
adversário ou o bloqueio da bola empurrada por um atacante adversário – dessa forma, este
posicionamento serve também para fortalecer a defesa; (ii) modo de condução, quando o
robô se desloca e corrige sua trajetória – alterando o alvo g´ - para conduzir a bola de forma
a alcançar o gol adversário. Estas transições ocorrem segundo as seguintes regras:
(1) xb - d1 > x d ,
(2) xb + d 1 < x d,
(3) xa < x b < x d e ya – yb < d2 e yd – yb < d2 ,
y g min ≤ yb +
( y a − yb )(x b − x g )
≤ y g max,
(x a − x b )
(4) xb – xd < d3 e
33
(5) xb – xa < d3 e
y g min ≤ yb +
( y a − yb )(x b − x g )
≤ y g max,
(x a − x b )
(6) xa – xb > d4 ,
sendo:
(x b, yb ) a coordenada da bola,
(x a ,ya ) a coordenada do robô atacante,
(x d ,yd ) a coordenada do robô defensor,
d1 ,d2 ,d3 ,d4 valores determinados empiricamente sendo 4,20,4,8 cm, respectivamente,
ygmin , ygmax são os limites inferior e superior do gol,
xg é a coordenada da linha de gol do campo adversário.
Na figura 3.2 são apresentados os comportamentos do defensor e do atacante, onde os
números indicados referem-se às regras, sendo que o defensor e atacante podem, no
decorrer do jogo, trocar de comportamento estratégico.
34
Figura 3.4. Comportamentos do defensor e do atacante
3.1.2. SISTEMA DE VISÃO.
No sistema de sensoriamento visual desenvolvido para o “Time Guaraná”[2] o
reconhecimento dos objetos de interesse no campo – jogadores e bola – é baseado nas cores
da imagem capturada pela câmera, sendo que um conjunto de pixels adjacentes de cor
laranj a identifica a bola; de cor azul, os robôs de um time e de cor amarela, os robôs de
outro time. Para a completa identificação e localização dos robôs no time, além da etiqueta
com a cor característica, exigida pelas regras, uma segunda etiqueta de cor rosa foi
utilizada, ambas margeadas por uma moldura preta: para evitar que duas etiquetas da
mesma cor, porém colocadas em robôs distintos que estejam em contato, possam ser
identificadas como um único elemento, evitando um alinhamento acidental. O ciclo de
controle do sistema foi definido pela taxa de aquisição de imagens, que neste caso é de 30
35
quadros por segundo, ou seja, um quadro a cada 33 ms. Assim, em períodos de 33 ms. uma
nova imagem refletindo o estado atual do campo torna-se disponível ao computador para
processamento.
O módulo de visão computacional possui uma fase inicial (off-line) de
calibração, executada previamente ao início da partida. A fase off-line ocorre cerca de vinte
minutos antes da partida, quando as equipes preparam os times, instalam os equipamentos e
calibram o módulo de visão computacional, que nesta fase desempenha duas tarefas de
importância vital: os valores limites para classificação das cores e a determinação do
modelo de campo vazio. Durante a partida (fase on-line), a visão identifica, localiza e
rastrea a bola e os jogadores no campo.
A definição dos valores limites para a classificação das cores utilizadas no jogo –
azul, amarela, rosa e laranja – é feita através da iteração direta com um operador humano: a
princípio seleciona-se a cor a ser calibrada e depois apresentam-se continuamente imagens
do campo, onde a cor de interesse é selecionada pelo operador. Para cada seleção, são
calculados as relações R/G e G/B do valor RGB do pixel. Após diversas seleções, os
limites superior e inferior das relações R/G e G/B são estabelecidos como valores limites
para serem usados na classificação da cor calibrada: este processo deve ser repetido para
cada cor de interesse, principalmente para observar se há superposição dos limites de
aceitação para diferentes cores.
36
.
Figura 3.5 Etiqueta de cores dos robôs
Figura 3.6 – Fotografia do Time Guaraná em ação, mostrando as etiquetas
coloridas.
37
Durante uma partida, para acelerar o processamento de imagens, é realizada uma
fase preliminar de subtração da imagem atual do campo com uma imagem modelo do
campo vazio – sem jogadores e sem a bola. Esta subtração é realizada somente nas bandas
R e G da imagem. A definição da imagem modelo do campo vazio também é realizada na
fase de calibração do sistema. São adquiridas N imagens do campo vazio, a um intervalo dT
entre as aquisições, para melhor refletir as oscilações de luminosidade devidas tanto à
iluminação não homogênea quanto aos ajustes automáticos de algumas câmeras utilizadas.
No time “Guaraná”, os valores de N e dT foram definidos empiricamente como 5 imagens
e 1 segundo, respectiva mente. Para determinar a imagem modelo do campo vazio, calculase a média entre as N imagens:
N
p ( x, y) =
∑p
i =1
i
( x, y)
,
N
(3 .3)
x = xi..., xf ;
y = yi... yf ;
onde:
p(x,y) é o valor do pixel na coordenada (x,y) da imagem modelo do campo vazio,
pi(x,y) é o valor do pixels na coordenada (x,y) da i-ésima imagem do campo vazio,
N é o número de imagens consideradas,
(xi,yi)(xf,yf) são as coordenadas superior esquerda e inferior direita que definem os limites
do campo na imagem. Estes limites dependem da fixação da câmera em relação ao campo,
38
a qual deve ser feita de forma que todo o campo possa ser visualizado na imagem e que
longitudinalmente o campo esteja alinhado com o eixo horizontal da imagem.
A partir da imagem modelo, calculam- se os desvios dos valores dos pixels em
relação às outras N imagens, definindo os limites de variação em R e G:
LR = max ( r ( p( x, y)) − r ( pi ( x, y)) );
(3 . 4 )
i = 1...N ;
x = x i ...x f ; y = y i ... y f ;
LG = max ( g ( p( x, y )) − g ( p i ( x, y )) );
i = 1...N ;
x = x i ...x f ; y = y i ... y f .
onde:
LR,LG são os limites vermelho e verde da imagem, respectivamente, que serão utilizados
na subtração da imagem, durante a fase On-line do sistema,
r(p),g(p) são os componentes vermelho e verde do pixel p, respectivamente,
p(x,y) é o valor do pixel na coordenada (x,y) da imagem modelo do campo vazio,
(xi,yi),(xf,yf) são as coordenadas superior esquerda e inferior direita que definem os limites
do campo na imagem,
N é o número de imagens consideradas.
39
Quando uma imagem é capturada, gera-se inicialmente a imagem diferença
pd (x,y) da subtração desta imagem atual pa (x,y) com a imagem modelo do campo vazio
p(x,y):
r ( p d ( x, y )) = r ( p( x, y)) − r ( pa ( x, y)) ;
g ( p d ( x, y) ) = g ( p ( x, y)) − g ( pa ( x, y)) ;
(3.5)
x = xi,..., xf ; y = yi,..., yf
onde:
pd (x,y) é o módulo da diferença do valor do pixel na coordenada (x,y) da imagem atual com
a imagem modelo do campo vazio,
pa (x,y) é o valor do pixel na coordenada (x,y) da imagem atual- última imagem capturada,
p(x,y) é o valor do pixel na coordenada (x,y) da imagem modelo do campo vazio,
r(p),g(p) são os componentes vermelho e verde, respectivamente, do pixel p,
(xi,yi),(xf,yf) são as coordenadas superior esquerda e inferior direita que definem os limites
do campo na imagem.
40
Os valores não nulos da imagem diferença correspondem aos elementos de
interesse e a ruídos. Como p(x,y), pd (x,y) e pa (x,y) são densidades de probabilidades,
correspondendo aos valores de pixel em um ponto determinado, o método de subtração de
imagens na verdade é um processo de determinação de threshold ótimo para fins de
processame nto da imagem.
3.1.3 DETERMINAÇÃO DE TRAJETÓRIA
O sistema de sensoriamento visual é o mesmo proposto em parte por Kurata,
Grattan & Uchiyama [6] e por Pegoraro & Costa [2], mesmo para um caso inteiramente
diferente, é de aplicação válida nesta tese. Consiste principalmente de uma câmera CCD
(tipo KP-M1, produzida por Hitachi Denshi Co. Ltda, ou JVC com saída em S-VHS). O
programa de processamento de imagens é projetado para a obtenção do centróide e da
elipse de inércia da imagem, com circuitos de processamento para sua integração em tempo
real, utilizando como interface o Vídeo for Windows da Microsoft, que possibilita a
aquisição de imagens digitais oriundas de qualquer placa digitalizadora compatível (PCI
PixelView PV-Bt-848, por exemplo) , desde que seja capaz de operar em pelo menos 30
quadros por segundo com 24 bits RGB. O “Hardware” do sistema é composto de um
conversor analógico/digital, três processadores digitais de sinais (DSP), dois divisores
analógicos e elementos condicionantes de sinal adequados, controlados por um
microprocessador PC Pentium II 233 MHz. O princípio de operação de cada elemento do
circuito é basicamente o mesmo, sendo o cálculo do centróide e da elipse de inércia
realizado através dos momentos de primeira e de segunda ordem.
41
Após identificar cada objeto na imagem, o sistema de coordenadas em pixels é
transformado em sistema cartesiano de campo (com unidades de 0.5 cm para cada pixel).
As fórmulas serão apresentadas consideram o campo de defesa no lado esquerdo:
s(i , j , r ) = d (etime (i ), erosa ( j ) ) + d (etime (i).eant ) )
li time ≤ netime (i ) ≤ ls time
li rosa ≤ nerosa (i ) ≤ ls rosa
0cm ≤ d (etime (i ), erosa ( r ) ) ≤ 14 cm
4cm ≤ d (etime (i ), erosa ( j ) ) ≤ 7cm
(3 . 6 )
no lado esquerdo do campo (menor x). Quando a partida é iniciada, cada robô é
identificado por um operador humano. A partir deste instante, a identificação se dá por
intermédio de um algoritmo de rastreamento, que usa um método de otimização exaustiva
para encontrar a solução de mínimo custo do seguinte sistema:
Na expressão 3.6:
r = 1,2,3 é o número do robô considerado,
i = 1,2,...,n é o número de um dos n elementos da cor do time encontrado na imagem,
j = 1,2,...,m é o número de um dos m elementos da cor rosa encontrados na imagem,
s(i,j,r) é a função-objetivo a ser minimizada,
d(e1,e2 ) é a distância cartesiana entre os elementos e1 e e2 no sistema de coordenadas,
etime(i) é o centróide do i- ésimo elemento com a cor do time,
erosa(i) é o centróide do j-ésimo elemento rosa,
eant(r) é o centróide do elemento da cor do time do r-ésimo robô identificado na imagem
anterior,
42
netime (i) é o número de pixels no i-ésimo elemento da cor do time,
nerosa (j) é o número de pixels no j-ésimo elemento da cor rosa,
litime e lstime são os limites inferior e superior do número de pixels, que definem, que
definem a faixa válida do tamanho do elemento ( etiqueta ) da cor do time,
litime e lstime são os limites inferior e superior de número de pixels, que definem a faixa
válida do tamanho do elemento ( etiqueta da cor rosa ).
Figura 3.7 Evitando obstáculos
Os valores de litime e lstime, litime e lstime mudam de acordo com o tamanho da
etiqueta, da resolução da imagem usada e da posição da câmara e receberam 60, 80, 20 e
30, respectivamente. Este algoritmo de otimização é aplicado para cada um dos três robôs
43
do time, resultando em 3 pares de elementos diferentes (elemento da cor do time, elemento
rosa), cada um associado a um robô.
Inicialmente calcula-se a trajetória do robô r da posição atual s até a posição
alvo g , utilizando uma reta Rsg [2]. Se a trajetória de um obstáculo O cruzar Rsg , calcula-se
um alvo intermediário g´ para o robô r (Cf. Figura 3.7), levando-se em consideração o
ponto Pi onde as trajetórias de O e r se interceptariam e a posição atual do robô. Neste
processo, a velocidade e direção do obstáculo definem o ponto de intercepção P i e o tempo
da colisão t c. Se t c é menor que o tempo t g que o robô r levaria para alcançar o alvo g (isto
é, 0< t c < tg ) então um alvo intermediário g´ é definido. O alvo g´ é localizado a uma
distância d do obstáculo O, perpendicularmente a Rsg , considerando o caminho s-g´-g mais
curto. A distância d também é definida empiricamente. As bordas do campo também
impõem restrições à escolha do caminho s-g´-g mais curto, uma vez que o robô também
deve evitar colisões com as bordas. Este processo de evitar colisões é iterativo, sendo
aplicado a um obstáculo por vez – aquele que estiver mais próximo do robô r: se o
obstáculo O estiver muito próximo do robô, o alvo intermediário g´escolhido ainda poderá
resultar em colisão. Após o robô iniciar seu movimento, o ângulo de orientação medido a
partir da diferença de rotação entre as rodas motoras esquerda e direita (Cf. Figura 2.6), ψ,
é controlado para mantê-lo na direção da próxima meta e após isto ele percorre uma linha
reta, da forma mais suave possível. A combinação da distância até o alvo e os sub-alvos
intermediários ( para evitar eventuais obstáculos) determinam a trajetória do robô. A
trajetória é traçada a partir do ponto representativo s , sendo diferente daquele traçado pelo
eixo de direção, porque:
44
(1) O ângulo de manobra real ψ s se posicionará entre 90º e 270º em relação ao
eixo x do campo, e
(2) A posição (x m,ym ) e o ângulo α do ponto representativo s são dados pelas
seguintes equações, que explicam a dinâmica do robô móvel:
dT
x m (t ) = ∫ V m cosψ s cosαdt,
(3 . 7 )
0
dT
y m (t ) = ∫ V m cosψ s sen αdt
0
dT
α (t ) = ∫ ω (t )dt = ∫ (Vm / Ltd ) senψdt
dT
0
0
Com Ltd sendo a distância entre o eixo motor e o eixo de direção do robô móvel, dT o
tempo de enquadramento – uma imagem a cada 33ms – e α , Vm ( no caso do time
“Guaraná”, V m é constante e estipulado como 1 m/s) ωm dados pelo cálculo dos momentos
de segunda ordem:
ωm =
V m dα I xx − I yy
=
.
,
Ltd dT
I yy
V m = ω m .Ltd =
dα (I xx − I yy )
(3.8)
dT .I yy
Entretanto, é necessário modificar o valor de referência do ângulo de manobra
para ser maior, com a finalidade de trazer o ponto representativo s o mais próximo possível
do eixo de direção [6]. O ângulo ψm entre a direção do veículo e o alvo ( ou sub -alvo) mais
45
próximo deve ser escolhido como ângulo de manobra em vez do ângulo ordinário ψ s. Esta
mudança significa um ganho variável K(ψ s,Rsg ), que será empregado no sistema. A variável
ganho muda com a alteração do ângulo de manobra ordinário ψs e com a distância Rsg . Seu
valor calculado torna -se maior a medida que a distância Rsg do robô até o próximo sub-alvo
torna-se menor. Pelo uso da variável ganho, o desempenho do robô pode ser melhorado.
O ponto de interseção P i = (x i,yi) é definido como o ponto onde a trajetória do
robô r cruza a trajetória do obstáculo 0. Uma aproximação utilizada por Pegoraro & Costa
(1998) é a seguinte: o número de quadros nx que decorrem no instante atual até r e O se
interceptarem em x e o número de ny até r e O se interceptarem em y são:
xr − xo
,
dx o − dxr
y − yo
ny = r
dy o − dy r
nx =
(3.9)
Onde (x r,yr) são as coordenadas do robô; (xo ,yo ) são as coordenadas do obstáculo e dx r, dy r,
dxo ,dyo são os deslocamentos do obstáculo e do robô, dados pela diferença entre a posição
atual e a anterior. Se nx < 0 ou ny<0, não existe ponto de intersecção. O número de quadros
até a interseção é dado por: ni=min(nx,ny). No início da iteração do cálculo, nx e ny podem
ser diferentes e ni pode corresponder a um número menor que o número real de quadros até
a intersecção; entretanto nx e ny convergem para o mesmo valor nos próximos passos de
iteração ( como já foi dito, cada passo de iteração dT corresponde a 33ms, ou seja, a cada
quadro de imagem). O ponto de interseção (x i,yi) é calculado como segue:
46
x i = n i dx o + x o ,
y i = n i dy o + y o .
(3.10)
3.2. OUTROS SISTEMAS
Outros sistemas de simulação de futebol de robôs usam diferentes procedimentos e
algoritmos de navegação. O primeiro simulador desenvolvido por Itsuki Noda para a
SONY, por exemplo, é escrito em linguagem LISP para funcionar em ambiente de CAD, e
é patente privada da própria SONY (Cf. página oficial da Robocup na internet). Existem
simuladores mais recentes, como o ROBOWIN que emprega os mais avançados
procedimentos como a lógica FUZZY, com implementos sofisticados de programação
estatística e de competição on-line.
Neste item apresenta-se uma breve análise de alguns sistemas de simulação de
ambientes cooperativos entre robôs.
3.2.1. CARNEGIE-MELLON UNIVERSITY MILIBOT SIMULATOR
Seu simulador foi projetado para testar algoritmos e arquiteturas para times de robôs
multidistribuído e ganhou o quarto lugar na primeira Robocup ( time com interdependência
entre robôs com assistência de um líder de time para coordenar movimentação e sensores).
Possui as seguintes características: suporte multiplataforma - GUI (Graphics Universal
47
Interface) server e simulador escritos inteiramente em JAVA (v.1.0); capacidade de ser
observado em webpage, robôs conectados via socket ou porta serial (os programas para os
robôs podem ser escritos em C++ e o GUI em JAVA); controles e interface dinamicamente
configurados (configuração dos robôs e do painel de controle carregados a partir de
scripts); habilidade de “arrastar e soltar” os robôs durante a operação e habilidade de
adicionar obstáculos durante operação. Além destas, o simulador pode admitir outras
configurações de painel de controle e suporte para vários tipos de robôs e configurações. O
simulador possui; pacotes configuráveis para simulação e caso real, controle dos robôs de
forma local ou distribuída (cada robô pode ser controlado de forma independente ou em
conjunto); controle de um único time ou vários times em conjunto, no caso do simulador,
cada robô virtual tem seu próprio algoritmo de navegação; suporte de arquivos de texto e
outros arquivos com informações; suporte à e ventos: iniciar, terminar, faltas e etc.
A guisa de comentário: pode ser dito que este é um sistema quase perfeito, mas que
funciona melhor em ambiente industrial do que em competição oficial entre times de robôs,
pois seu algoritmo principal de navegação tem como prioridade a detecção e a navegação
por entre obstáculos e não manobras e trajetórias de competição. Sua complexidade
excessiva custou-lhe a vitória na primeira Robocup porém ainda é um dos melhores
simuladores de robôs em ambiente cooperativo já desenvolvidos.
48
Figura 3.8. Simulador Millibot da Carnegie-Melon University
3.2.2. TOKYO-U SIMULATOR
Atualmente é o simulador padrão da Robocup, adotado também pela Humboldt
Universitat zu Berlin e que foi copiado integralmente pelo ROBOWIN. Suas características
são: suporte multiplataforma com GUI server e simulador escritos inteiramente em C++
(Borland C++ v.4.5); capacidade de partidas on-line via socket ou porta serial e suporte
para vários tipos de estratégias (Lógica FUZZY, Lógica Mu e outras) e suporte a eventos:
49
iniciar, terminar, chute inicial e outros. O programa principal do simulador admite
interfaces configuráveis tanto para Windows como para Linux ou Sun OS: o modelo oficial
de Itsuki Noda, por exemplo, usa uma interface desenvolvida por Klaus Dorer, AlbertLudwig Universitat zu Freiburg para Windows ou Linux RedHat v.6.0.
É o padrão Robocup Jr. oficial, pois permite partidas on-line e off-line (partidas
jogadas diretamente pela internet ou como simulador simples). Porém uma análise mais
detalhada mostra que no caso off-line trata-se mais de uma animação com seqüências fixas
de imagens, em que a alteração da estratégia utilizada – Fuzzy ou outras – provoca
variações no esquema original. Como trata-se de um simulador didático, este aborda casos
simples de competições de forma original.
Figura 3.9. Interface do Simulador Robocup Oficial.
50
3.2.3. ROBOWIN
É uma versão um pouco melhorada do Tokyo-U original, feita pelo autor da
interface do Robocup oficial: Klaus Dorer, com maiores facilidades para competições offline mas com o mesmo ambiente GUI, mesmo suporte a eventos e mesmas classes em C++
para a navegação dos robôs. Possui como acréscimo um módulo especial descrevendo o
comportamento estratégico de cada jogador individualmente e logfiles previamente
gravados – o que dispensa a obrigatoriedade de acessar a internet para realizar as partidas.
Porém, compartilha a mesma deficiência básica do Tokyo-U/ Humboldt Universitat zu
Berlin: as partidas off-line são animações, ou seja, seqüências pré-determinadas de imagens,
cujas variações básicas ilustram os vários comportamentos estratégicos à disposição dos
times de jogadores.
3.2.4. UNESP – CBFR
O mesmo sistema do simulador da Escola Politécnica de São Paulo, mas com
uma série de vantagens. O Simulador UNESP – CBFR (Copa Brasil de Futebol de Robôs)
tem como características: não possuir suporte multiplataforma (roda somente no Windows)
e apresenta somente partidas off-line. As imagens são unidas dinamicamente por arquivos
DLL. Possui suporte a eventos variados como iniciar partida, faltas, placar, etc, o que o
torna mais didático do que o Simulador de Pegoraro & Costa, por exemplo.
51
Figura 3.10 – Simulador UNESP – CBFR ( Oficial )
3.3 COMPARAÇÃO DOS SISTEMAS
A grande maioria dos sistemas existentes para avaliação pública, porém, segue as
mesmas linhas de programação: navegação por implementação de equações cinemáticas
clássicas em tempo real ou com o uso de bancos de imagens pré-gravadas – o que é usual
em simuladores implementados JAVA e C++ - utilizando sequências ordenadas de métodos
e rotinas ou por meio de união dinâmica de arquivos e recursos (DLL), que é procedimento
usual em programas desenvolvidos em
DELPHI. Na Tabela 3.1 apresentam-se as
principais características de alguns simuladores à título de comparação.
52
Tabela 3.1. Principais características dos simuladores Carnegie-Mellon,
Tokyo-U/Robowin e UNESP/GUARANÁ.
Carnegie-Mellon
Tokyo-U e Robowin
UNESP
e
GUARANÁ
Multiplataforma
Sim
Sim
(Windows
, Não
(Windows, Linux e Linux e SUN OS)
(somente
Windows)
SUN OS )
Suporte a eventos
Sim
(
Suporte Sim ( Suporte para Sim ( Suporte para
completo
para eventos de futebol)
eventos de futebol –
futebol e para uso
O simulador UNESP
industrial)
possui
variedade)
Partidas via internet
sim
sim
Linguagem
JAVA ( GUI server C++
em JAVA e robôs (Borland C++4.5 e
opcionalmente
em seguintes)
C++)
.
53
não
DELPHI
maior
4. SIMULADOR DE FUTEBOL DE ROBÔS – PROGRAMA EM DELPHI
4.1. CONSIDERAÇÕES INICIAIS
A presente simulação foi desenvolvida baseada nas estratégias propostas por
Pegoraro & Costa (descritas no item 2.6) , tendo como fundamento as regras da FIRA. Seus
aspectos principais estão codificados em um programa em DELPHI que descreve de forma
completa o comportamento de uma partida de futebol de robôs, consistindo de cinco partes
principais:
(1) o arquivo executável,
(2) Estrate1.pas,
(3) Estrate2.pas,
(4) Estrate1.dll,
(5) Estrate2.dll,
Os programas Estrate1.pas e Estrate2.pas são detalhados na distribuição oficial do
simulador em DELPHI: descrevem de forma completa os comportamentos estratégicos .
Estão escritos em Pascal e têm como referência direta os arquivos Estrate1.dll e
Estrate2.dll, que são bibliotecas de links dinâmicos (bitmaps dos robôs jogadores, do
campo e etc.).
Estrate1.pas pode ser divido em três partes, ou subrotinas básicas:
54
•
A primeira parte constitui-se do algoritmo posicional do time de futebol de robôs. Se o
robô atacante estiver dentro de certas coordenadas cartesianas (uma faixa do campo
determinada por valores empíricos de X e Y) e em um ângulo diferente de 90 graus, ele
é eleito para a função de atacante – de outro modo, ele será escolhido para defesa. O
robô goleiro ocupará sempre uma posição Ymax e Ymin, delimitando a grande área
antes do gol. Uma vez determinado qual o robô que ocupa uma posição melhor em
relação a bola, passa-se a segunda parte, que trata do algoritmo de navegação do robô
móvel.
•
Na segunda parte, se X robô > X bola e – principalmente – para Y robô > Ybola,
aplicam-se as fórmulas para se achar o ângulo α do robô móvel, determinando-se assim
a posição do robô móvel em relação a bola.
•
Na terceira parte, o programa checa novamente a imagem do campo de futebol de
robôs, registra a nova posição do robô e da bola e computa um novo ângulo α para o
robô móvel, repetindo este procedimento para cada intervalo de imagem dT.
O Estrate2.pas tem também três partes significativas:
•
A primeira parte idêntica a Estrate1.pas – o programa delimita as regiões do campo,
identificando os robôs que estão nelas e designando- lhes o papel ou de atacante ou de
defensor. Uma vez cumprida esta tarefa, o programa parte para a segunda parte.
•
Na segunda parte, o programa calcula as posições relativas do robô atacante e da bola e
computa a velocidade e a aceleração que este deve ter para alcançar a posição
(X,Y)robô = (X,Y)bola.
55
•
Na terceira parte, o programa checa novamente a imagem do campo, dos robôs e da
bola para o intervalo de tempo seguinte dT, computando a velocidade e a aceleração
dos robôs atacante e defensor para a nova configuração de imagem.
Os arquivos em DLL podem ser resumidos da seguinte maneira:
Estrate1.dll
(1)
Bitmaps - imagens dos jogadores do futebol de robôs – padronizados para o
simulador e arquivos de imagens para leitura direta, no caso real
(2) Menu - como mostrado na window do simulador,
(3) Dialog- barra de tarefas e janelas de diálogo,
(4) Stringtable - string de valor “101”,
(5) Font - fontes principais usadas no programa,
(6) Accelerators - 0, 101, VIRTKEY,
(7) Rcdata- dados opcionais para o arquivo resource (.rc),
(8) Cursor- padronizado para todos os casos,
(9) Icon- padronizado para o caso do simulador,
(10) Versioninfo - informações sobre a versãodo programa,
(11) DLGinit- dados opcionais para arquivos DLGinit.
Estrate2.dll:
Possui a mesma e strutura do arquivo anterior,porém para o time adversário.
56
4.2. DETALHES DE IMPLEMENTAÇÃO DO SIMULADOR
Como visto na proposta de
simulador de futebol de robôs de Pegoraro &
Costa[2], a questão fundamental é criar um conjunto de ações representadas por um
programa de computador, que represente fielmente o que acontece em uma competição de
futebol de robôs. Analisando-se o problema e diversas soluções, nota-se que o sistema de
navegação proposto para o simulador é o ideal como ponto de partida para
desenvolvimentos futuros. Tal desenvolvimento consiste simplesmente em um programa
em linguagem DELPHI (ou PASCAL) com arquivos encadeados dinamicamente ( arquivos
DLL) cujo procedimento é basicamente calcular uma linha reta entre o centróide do robô e
a bola, reta esta que tem como parâmetros as coordenadas do robô e da bola, juntamente
com o ângulo que o vetor posição do centróide da bola faz com origem das coordenadas e o
eixo das abcissas.
57
Figura 4.1. Interface Visual do Simulador de Pegoraro & Costa ( 1998).
Figura 4.2. Sistema de navegação original.
58
No código fonte em Pascal este sistema é encontrado codificado nas seguintes
instruções principais:
1) Para a bola parada: se a coordenada yr do robô for maior do que a coordenada yb
da bola, a rotina empregada determina uma nova coordenada y tendo como
parâmetros a coordenada y inicial, mais a tangente do ângulo que a bola faz com o
referencial inercial multiplicada pela diferença da distância (coordenada x) entre o
jogador e a bola. Deste modo, calcula uma linha reta entre o centróide do robô até
o centróide da bola, com o coeficiente angular dado pela tangente do ângulo que a
bola faz com o referencial fixo ao sistema, como visto na sequência de instruções
abaixo:
begin
novoy:=round(dlldados[17]+( (sin((pi/180)*dlldados[15])/cos((pi/180)*
dlldados[15]))*(dlldados[21]-(37+dlldados[16])) ));
end
No caso de yr do robô ser menor do que yb da bola, o conjunto de instruções é o
mesmo com apenas a troca do sinal referente ao termo da tangente da reta.
59
2) Para a bola em movimento o esquema original é igualmente simples: no decorrer
do jogo a bola ocupa diversas posições no campo, e os jogadores de ambos os
lados devem se adaptar às mudanças ocorridas, conforme representado
esquematicamente na Figura 4.3:
Figura 4.3 Sistema para bola em movimento.
O código fonte para estas rotinas de programação da bola em movimento, é
organizado da seguinte maneira:
1)
Temos yr do robô for igual ao yb da bola. Se a coordenada xb da bola for menor que
coordenada xr do robô e se ângulo que o centróide do robô faz com o plano de referência
for diferente de 180 graus, então a rotina realiza a seguinte verificação: se o ângulo a
calculado pelo programa for igual ou diferente do ângulo que a bola faz com o plano de
referência, verifica-se em seguida se as coordenadas xb da bola são maiores ou menores das
60
do jogador, alocando-se então a velocidade da bola e do jogador de acordo com esta regra
de decisão. Com isto o programa determina uma velocidade para o robô ( 0, 1 ou 2000),
conforme pode ser observado a seguir:
begin
dllacao:=1;
dllangulo:=180-dlldados[25];
end {end do angulo robô <>180}
else
begin
dllacao:=0;
dllveloc:=2000;
end;{end do angulo robô = 180}
end {end do x bola < x robô }
2) No caso contrário da regra de decisão, para o ângulo do robô diferente de
zero, o
robô “corrige” seu ângulo em relação ao referencial fixo ao sistema, tornando-o o mais
similar possível ao ângulo da bola (assumindo a velocidade angular ω). Calcula, então, a
trajetória em linha reta. A bola, no programa original, é posta em movimento por uma
função do tipo randomize, que é utilizada de maneira similar nas outras rotinas do
programa:
61
begin
dllacao:=1;
dllangulo:=180-dlldados[25];
end {end do angulo robô <>180}
else
begin
dllacao:=0;
dllveloc:=2000;
end;{end do angulo robô = 180}
end {end do x bola < x robô }
4.3.
SIMULADOR DE FUTEBOL DE ROBÔS DESENVOLVIDO
Baseado no simulador descrito no item 4.2, propõe-se uma nova visão deste
problema, encarando-o de um ponto de vista bem diverso. Em primeiro lugar escolheu-se,
para um simulador de futebol de robôs aperfeiçoado, a linguagem JAVA, em lugar do
DELPHI original. Esta escolha se deve ao fato de que a linguagem JAVA garante
portabilidade para o simulador, isto é, dá a capacidade de poder ser executado diretamente
em qualquer navegador apto para JAVA (Internet Explorer ou Netscape). Além disso, o
62
interpretador JAVA é multi-thread, o que permite refletir de forma direta no simulador a
concorrência característica do problema sendo simulado.
JAVA, assim como DELPHI, é uma linguagem Orientada a Objetos. Pode-se
portanto utilizar os conceitos de: – Classe e Herança [8] . “Classe” é um modelo para vários
objetos com recursos semelhantes e herança é o mecanismo que organiza as classes e seus
comportamentos. O programa de simulação de futebol de robôs em JAVA possui somente
uma única estrutura de classe – a classe Simulador, que é do tipo “Thread”, com os
métodos hierárquicos característicos da classe “Applet”.
A sintaxe “Simulador” ( “thread” único) pode ser dividido nas seguintes partes
principais:
1) A rotina para importar as classes em JAVA adequadas ao programa, que se
limitam as instruções:
import java.awt.*;
import java.awt.Font;
2) A classe pública ( única e principal), subclasse da classe “Applet” (que por
sua vez é subclasse da classe “thread”) em que
o programa principal se
insere da seguinte forma:
public class Simulador extends java.applet.Applet implements Runnable
3) O método public void init que inicia o programa e que declara quais imagens
serão carregadas pelo programa e desenhadas na tela. O termo método é
característico da terminologia Orientada a Objetos (classes encapsulam
atributos - variáveis - e incorporam os métodos – públicos ou privados- que
63
manuseiam estes atributos). O void init executa-se apenas uma vez pelo
navegador aplicado,
4) O método public void paint (também chamado como Graphics screen) que
desenha as figuras na tela. O termo void, análogo ao similar em C/C++,
declara que uma função do programa não retorna um valor explícito ao final.
5) O método public void start, que inicia o thread, isto é, habilita-o a ser
executado imediatamente. Ele entra em uma fila de instruções e concorre
com os outros threads habilitados. Para ser executado, é necessário o método
run.
6) O método public void run, que é o programa em questão (dentro do “thread”)
juntamente com a entrada de execução do código, tendo o run sido
previamente estabelecido.
7) O método public void stop, que termina o programa: executado toda a vez
que a aplicação for desativada – faz par com start.
public void stop() {
if (runner != null) {
runner.stop();
runner = null;
}
}
8) O método public void update (Graphics screen), que desenha o movimento
seguinte dos elementos móveis da tela – isto é feito quadro-a-quadro.
public void update(Graphics screen) {
64
Paint(screen);
}
}
Outras modificações propostas sofisticam o controle da trajetória do robô à bola.
No original em DELPHI o robô chuta a bola em qualquer direção, ditada pela posição
relativa do robô à bola. No esquema proposto, calcula-se ou interpola-se um ponto
Figura 4.4 Sistema de navegação modificado em JAVA
para a bola em movimento.
intermediário , conforme mostrado na Figura 4.4, tendo como parâmetro o dobro do ângulo
a original como primeira aproximação. Outros valores – um terço, um quarto e outros
podem ser empregados para refinar o resultado, pois eles acrescentariam mais estágios na
aproximação do jogador à bola, permitindo assim um controle mais sofisticdo da trajetória.
Tome-se como exemplo inicial o jogador Defensor 1 ( jogador 2 do time azul): o
jogador de defesa do time azul possui uma estratégia otimizada: primeiro traça uma linha
65
reta até a bola e em seguida interpola um ponto a um terço da distancia até a bola, alinhada
com a meta adversária [9]. Sendo o simulador uma reprodução simplificada dos
procedimentos usuais de uma partida de futebol de robôs, o programa inicia a computação
com o sinal de entrada do sistema de navegação, enviando um fator de aceleração aos
“jogadores” (valor unitário, positivo ou negativo dependendo das posições relativas dos
jogadores no campo). Estes dados serão processados pela rotina de programação da
seguinte maneira: com os fatores de aceleração em tempo unitário, são calculadas as
velocidades lineares (sendo um simulador, fatores de torque ou de correção diferencial
entre coordenadas calculadas e reais no campo não entrarão na computação) e, a partir daí,
as novas coordenadas dos jogadores são calculadas por meio das interpolações necessárias.
Mais adiante será visto que no caso real, a sequência de passos é diferente, pois o programa
realmente inicia com os dados visuais coletados pelo sensor CCD e os dados enviados aos
robôs são processados de forma ligeiramente diferente pelo programa de processamento de
imagens. O simulador serve tão somente para avaliar os algoritmos de navegação
empregados – e neste aspecto a simulação deve seguir o mais próximo possível o caso real.
Acelerações nas
Coordenadas x e y
sim
X defensor1 >
(380-38 )
66
Aceleração em x
igual a –1
(valores unitários)
não
X defensor1 <
x da bola
sim
Aceleração em x
Igual a 1
(valores
unitários)
não
sim
(x da bola –
X defensor)
> 150
Aceleração do jogador
Em x = -1
(valores unitários)
não
Aceleração
em x=1
2ª passo de programa.
Novo x igual a uma
interpolação linear, com
um
ponto calculado a um
terço da distancia do
jogador à bola
1º passo de
programa: novo x
igual a um
acréscimo simples
1º passo de
programa: novo x
igual à um acréscimo
simples
2ª passo de programa: novo x igual
a uma interpolação linear, com um
ponto calculado a um terço da
distancia do jogador à bola
Figura 4.5: Fluxograma do sistema de navegação do simulador de futebol de robôs
As alterações no programa original podem ser codificadas em JAVA de forma
similar ao programa em PASCAL, mas de forma mais simples: acrescentam-se as
instruções necessárias às instruções de trajetória (na forma de uma interpolação “robusta”),
de forma que o bloco do programa primeiro executa a primeira instrução – ponto
intermediário a um terço da distância entre o jogador e a bola - e em seguida calcula uma
67
linha reta simples entre os centróides do jogador e da bola, o mais alinhado possível com a
meta adversária.
Para o rebote da bola com os jogadores e dos jogadores entre si, utilizou-se um
algoritmo chamado de “Clipping”. No simulador de Pegoraro & Costa usou-se uma
manipulação de arquivos DLL para gerar tal efeito. Entretanto o autor achou mas simples e
conve niente utilizar o algoritmo de “Clipping”, que permite a utilização de um único bloco
de instruções ( “thread”) . Temos a imagem da bola ( coordenadas X bola, Y bola) e a
imagem de um jogador ( coordenadas X jogador, Y jogador). Partindo destes parâmetros o
algorítmo de “clipping” realiza uma série de testes de aferição de resultados para cada
configuração jogador-bola, examinando os casos em que há intersecção das imagens do
jogador e da bola ( Cf. Figura 4.4).
X da bola <
(xjogador - 22)
A,D,F,
A,B,D,F,G
sim
não
B,C,E,G,H
X da bola >
(xjogador+22)
não
sim
C,E,H
Y da bola <
(yjogador+22)
H
E
sim
não
A bola continua
na trajetória
original
não
E,C
Y da bola >
(yjogador-22)
sim
C
O ângulo que a bola faz com o plano de referência é – por
simetria - invertido em sinal para que a bola rebata no
limite da imagem do jogador. Para cada face pode ser feito
um fluxograma de “Clippimg” semelhante
Figura 4.6: Fluxograma do algoritmo de “Clipping”
68
Este algoritmo de pode ser expandido para a criação de regras de decisão – que
permitem uma sofisticação maior na estratégia do jogo, para evitar colisões entre os
jogadores e para fornecer mais vivacidade ao jogo, evitando um confronto simétrico de
estratégias opostas (Cf. Figura 4.7).
Figura 4.7. Possíveis localizações da bola (coordenadas Xb,Yb) com relação
ao jogador (A,B,C,D,E,F,G,H), explicando o algoritmo apresentado
na figura 4.6 e definindo os 8 quadrantes possíveis de localização
da bola.
Estas regras de decisão são adaptadas para todas as relações entre os jogadores e
a bola, e entre os jogadores entre si. Pode-se igualmente ampliar e sofisticar o alcance de
tais regras, tomando-se o cuidado de não “forçar” resultados determinados ou causar
movimentos da bola e dos jogadores não condizentes com as regras da competição de
69
futebol e robôs. No caso real a sequencia empregada – e os parâmetros em jogo - são
ligeiramente diferentes.
Como o sistema navegação no caso real recebe os dados da câmera CCD através do
Programa de Processamento de Imagens, estes deverão passar por um pré-processamento,
que será detalhado a seguir:
1) Primeiro calculam-se os ângulos dos jogadores e da bola, juntamente com o
centróide. Toma-se por exemplo o ângulo e o centróide de um jogador e da bola:
Figura 4.8. Determinação dos parâmetros de ângulo do jogador e da bola.
2) Sendo o objetivo principal para fins de navegação a obtenção de uma reta entre o
centróide do jogador e da bola, esta é computada como tendo o coeficiente de
inclinação m a tangente de (b – a). Ora, esta tangente é o módulo da reta e é
proporcional à velocidade que o jogador deve ter para alcançar a posição em que
a bola está, segundo esta mesma linha reta [2]. Portanto, o sistema de navegação
70
deverá enviar ao jogador um sinal – positivo ou negativo - que será o pulso de
aceleração necessário para alcançar a posição da bola,
3) A equação empregada para este caso será:
V = V0 ± a.∆ t
Sendo V
( 4 .1)
velocidade final, V 0 a velocidade inicial – geralmente nula , a a
aceleração e ∆t o intervalo de tempo entre um segmento de programa e outro.
Portanto, o sistema envia um sinal para o jogador, para que seus motores iniciem
o movimento com um pulso de aceleração a no intervalo ∆t.
4) Para o caso real, outros fatores que devem ser pré-processados antes do envio do
sinal de “acelerar” ou “desacelerar” são o torque do veículo e as correções
diferenciais entre a posição computada e a posição real, obtidas pela calibração
do sistema de sensoriamento visual no campo antes de começar a partida de
futebol de robôs.
5) O programa principal então tem duas opções para calcular as novas coordenadas
dos jogadores e da bola: ou por meio da fórmula cinemática direta:
x = x 0 + V0 ∆t +
a∆t 2
2
( 4.2)
ou por meio de passos intermediários: calculando-se primeiro a velocidade e em
seguida as posições relativas. Este método é o que foi empregado no simulador
pois permite passos intermediários de interpolação e um refinamento maior no
71
sistema de navegação (tempo unitário e aceleração unitária para o caso do
simulador. Outros valores podem ser empregados, resultando em valores
diferentes):
V = V0 + a*t : t = 1 (tempo unitário),
xd1move = V.
( codificação válida para todos os jogadores: xPosition = coordenada x do
centróide da bola. V0 é a velocidade inicial, geralmente nula )
xd1 = (xd1+1) - 1*(xd1 - xPosition)*xd1move/10 - xd1move*(xd1move1)*(xPosition-xd1)*(xPosition-xd1)/40
72
5. RESULTADOS OBTIDOS
Foi apresentado nesta tese uma proposta de simulador de futebol de robôs em
linguagem JAVA capaz de utilizar o sistema proposto por Pegoraro & Costa [2]. Este
ambiente permite operações multi-thread, que sào importantes para simulações que
envolvam cooperação entre robôs. Na presente tese adotou-se apenas um thread por
simplificação. Apesar disso, o simulador desenvolvido permite futuras ampliações,
inserindo-se os conceitos multi- thread.
Testes objetivos foram feitos, provando ser o simulador em JAVA, dentro das
premissas empregadas, consistente em teoria e bastante prático. Porém algo deve ser dito
sobre o verdadeiro trabalho em uma implementação: raramente um algoritmo permanece
impecável após os primeiros testes, sendo necessário ajustes complementares para que o
sistema simule as ações da forma exata como prescrito pelo projetista.
Na figura 5.1 apresenta-se uma sequência de imagens do início da partida, em que
a estratégia de movimentação e a trajetória de cada componente do time de futebol de robôs
é vista na sua forma mais simples: cada jogador vai em direção à bola pelo caminho
estrategicamente mais simples.
73
Figura 5.1. Sequência de imagens do simulador desenvolvido em JAVA
ilustrando as trajetórias dos jogadores segundo o algoritmo
descrito nesta seção.
Nas Figuras 5.2 (a) e (b) temos uma situação mais complexa: a bola é rebatida
velozmente de uma seção do campo para a seção adversária (do campo do time laranja para
o campo do time azul). O jogador atacante azul, mais veloz e mais hábil que o similar no
time laranja, toma a iniciativa e manobra parabolicamente, evitando os outros jogadores
que também estão indo em direção à bola, até alcançar esta e chutá- la de volta à meta
adversária.
74
Figura 5.2 (a): Manobra complexa do atacante azul.
75
Figura 5.2 (b). Manobra complexa do atacante azul.
76
Está claro que estas estratégias não são definitivas ou estanques: como o programa
do simulador é em JAVA e está aberto, qualquer modificação ou sofisticação estratégica é
permitida visando a melhor demonstração dos princípios lógicos e de Inteligência Artificial
desenvolvidos.
77
6. CONCLUSÕES
Foi desenvolvida nesta tese uma simulação de movimento de robôs num ambiente
cooperativo de futebol, através de algoritmos que permitem o direcionamento e o
posicionamento de um conjunto de robôs. Tendo como paradigma o trabalho feito no time
de futebol de robôs “Guaraná” da Escola Politécnica de São Paulo, foram apresentados
comentários ao programa em DELPHI do simulador de futebol de robôs desenvolvido a
partir dos trabalhos em que tais algoritmos ( parte deles embasados em linhas puramente
empíricas ) encontraram sua justificação.
Mostrando como um todo a validade do sistema de navegação proposto, o
simulador de futebol de robôs foi elaborado em JAVA, e aponta para uma série de
confirmações experimentais e práticas dos princípios tratados nesta tese. Abrindo portas
para futuras modificações, um dos resultados mais significativos foi a aplicação plena dos
métodos e recursos da linguagem JAVA, devido à sua portabilidade ( capacidade de ser
executado em vários tipos de navegadores). Com o código inteiramente aberto o usuário
poderá futuramente alterar os modos de navegação de cada jogador individualmente ou em
grupo ( adotando o sistema de navegação mais apropriado) e realizar toda a sorte de
aperfeiçoamentos de forma livre e direta .
Para a continuidade da tese, podem ser propostos aperfeiçoamentos no
simulador de futebol de robôs em JAVA e o aproveitamento das estratégias de
movimentação nele desenvolvidas para a implementação de times de futebol de robôs .
78
Desenvolvimentos de interesse são o uso de múltiplos “threads” ou blocos de instruções
específicos para cada componente do time de futebol de robôs, estratégias e manobras mais
sofisticadas e a criação de sub-classes poderá permitir alterações de estratégias.
Outro aspecto importante para a continuidade do trabalho proposto nesta tese
consiste num aprofundamento dos conceitos de Visão Computacional - com análises de
métodos de seleção de imagens, estudos comparativos de cores nos times e como estas
afetam o rendimento do time e do processamento das respectivas imagens. Paralelamente,
sugere-se a construção mecânica dos próprios robôs jogadores de futebol e a utilização de
todas estas técnicas e procedimentos integrados em um caso real – o futebol de robôs
completo e plenamente funcional, que será o teste essencial para os conceitos
desenvolvidos até aqui neste trabalho. Por fim, o uso intensivo da Inteligência Artificial –
que permitirão a adoção de estratégias eficientes de cooperação entre robôs com o objetivo
final de vencer uma partida de futebol real - coroará todo e qualquer desenvolvimento nesta
área da robótica.
79
7. REFERÊNCIAS BIBLIOGRÁFICAS
[1] CAPRARI R. S.: “Method of target detection in images by moment analysis of
correlation peaks”, in “Applied Optics ”, , volume 38, number 8, pp1317-1324
March 1999.
[2] COSTA A.H.R., PEGORARO R. et Al: “Construindo robôs autônomos para partidas de
futebol: o time GUARANÁ”, Anais do IV SBAI, pp 457-462 ,1998,
[3] KIM J. H., “Classification of a robot soccer system”, in “Korea Advanced Institute of
Science and Technology (KAIST) Reports”,pp 1-15, 1999.
[4] KURATA J., GRATTAN K.T., UCHIYAMA H.: “Navigation system for a mobile
robot with a visual sensor using a fish-eye lens “ , in “Review of Scientific
Intruments”, Volume 69, number 2, February 1998,
[5] MILLER P.C., CAPRARI R.S., “Demonstration of improved automatic targetrecognition performance by moment analysis of correlation peaks”, in “Applied
Optics”, vol.38, No. 8, March 1999.
[6] ROBOCUP OFFICIAL SITE. 1998; FIRA OFFICIAL SITE. 1998; www.ia.cti.br
www.robotics.com/robots.html ,
etc.
[7] WYLIE C. R., JR., “Advanced Engineering Mathematics ”, Mcgraw-Hill Inc., Third
Edition, pp 97-108, 1965.
[8] RAMON, F. “JAVA – Guia de Consulta Rápida”, NOVATEC,1999.
80
8. BIBLIOGRAFIA
[1] GUO R., PANDIT S.M., “Automatic threshold selection based on histogram modes and
a discriminant criterion”, in “Machine Vision and Applications ”, volume
10,pp 1325-1331, 1998,
[2].HERBERT T.J, HENNEBERGER B.E., “Optical filtering approach to regularized
tracking of na object´s position and orientation”, in “ Applied Optics”, vol.37.
number 32, pp 208-218, November 1998,
81
APÊNDICES
APÊNDICE A: ALGORITMO DE VISÃO COMPUTACIONAL
A.1 – INTRODUÇÃO
O método mais comum de detecção automática de objetos e seu reconhecimento é a
filtragem linear por meio de um filtro de correlação. Este é o caso de sinais temporais (
sequência discreta de imagens) e sinais espaciais ( as próprias imagens ). O impulso de
resposta do filtro, também chamado de “função de espalhamento pontual por sinais” é
escolhido para fornecer uma saída de baixo impulso generalizado quando o sinal de entrada
não somente vem com ruídos, mas também quando tem pico acentuado ( alvo de referência
imerso em um cenário com muitos sinais de ruído). Um sensor apropriado ( a câ mera CCD)
registra o alvo de referência e fornece um sinal de saída baseado no valor da correlação em
um dado ponto ser maior do que algum valor de “Thresholding”. É o que é chamado de
“Detetor de Ponto”.
O sistema proposto aqui pode ser empregado para suplementar o desempenho de tal
“Detetor de Ponto” pois combina parâmetros geométricos de segunda ordem, criando uma
estrutura matemática que formaliza esta decisão estratégica e designa medidas quantitativas
das formas dos momentos geométricos dos valores de pico.
82
A .2 DEFINIÇÃO DOS MOMENTOS GEOMÉTRICOS DE INTERESSE
Embora as definições seguintes pertençam as variáveis contínuas x e y, as
distribuições de planos de correlação reais vêm de detetores de pixels, portanto x e y são
realmente valores discretos e as integrais são na realidade somatórios. O pico de correlação
que está sendo caracterizado é a função intensidade de posição p(x,y) >0, cuja região de
suporte é o domínio fechado D ( se necessário, o pico será truncado na fronteira de D).
Embora em principio não haja restrição na forma da função p(x,y), a utilidade da análise de
momentos é concebida em p(x,y) pela representação de um um ou mais picos isolados ( no
caso do futebol de robôs, deve-se indicar, dentro do domínio D os valores de pico dos
alvos de referência dos robôs e da bola ). Sendo a região de suporte D excessivamente
grande, os valores de pico desaparecerão antes de alcançar as fronteiras ( o que não ocorre
no futebol de robôs). Observa -se que p(x,y) é a função distribuição de imagem do sinal de
saída do filtro de correlação e não do sinal de entrada da imagem (Caprari, 1998, que é a
base para as definições seguintes ).
O momento escalar zero (m), análogo à massa de um corpo rígido e a área do
83
objeto em pixels, é
n
n
m = ∑ ∑ p( x, y),
x= 1 y = 1
( A.1)
onde n é o número total de pixels em uma dada direção, x ou y, supondo-se uma imagem
quadrada..
O momento primeiro
ou posição do centróide do objeto, análogo ao centro de
massa de um corpo rígido, tem como componentes
Cx =
1 n n
∑ ∑ xp( x, y ),
m x =1 y =1
Cy =
1 n n
∑ ∑ yp( x, y )
m x =1 y =1
( A..2 )
O momento segundo, matriz I, análogo ao tensor de inércia de um corpo rígido de
massa unitária, é u´a matriz simétrica com elementos
( análogos aos Raios de Giração em relação ao centróide ).
( A.3)
84
2
I xx =
1 n n
∑ ∑ (x − C x ) p xn
m x= 1 y = 1
I yy =
1 n n
∑ ∑ (y − C y ) pxy
m x =1 y =1
I xy =
1 n n
∑ ∑ ( x − C x )(y − C y ) p xy
m x =1 y =1
2
Vetores e matrizes que definem momentos de ordem maior podem ser derivados a
priori, mas a análise será conduzida na matriz de inércia e na elipse de inércia associada.
Sendo D uma região invariante (i.e., D não é influenciado por p(x,y)), todos os
momentos tensores podem ser formalmente vistos como combinações dos sinais de saída
dos bancos de filtros lineares operando no plano de correlação e este paradigma pode
facilitar o desenvolvimento de detetores estatísticos otimizados.
Diagonalizando I por uma transformação de similaridade, demonstra-se que os
momentos principais de inércia I11 > I22 > 0 são os autovalores de I:
I 22
{
{
(
)
(
)
1
(I xx + I yy ) + (I xx − I yy )2 + 4 I xy2
2
1
2
= (I xx + I yy ) − (I xx − I yy ) + 4I xy2
2
I 11 =
1/ 2
1/ 2
},
},
( A.4 )
Os eixos principais de inércia são os autovetores correspondentes. Considera-se o
ângulo do eixo principal maior medido à partir do eixo x:
85
 (I − I xx )
θ = arctg  11
 (+ π ),
I xy


( A.5 )
onde θ ∈[-π/2, π/2].A adição de π só deve ser realizada quando o ângulo obtido da função
inversa for negativo, de forma a garantir a condição θ∈[0, π]) . É importante ressaltar que θ
fornece a direção do robô.
Embora os eixos maiores e menores da elipse de inércia sejam a transposição dos
( A.6 )
eixos principais correspondentes do pico, a excentricidade da elipse de inércia
 1 − I 22 

e = 
 I 11 
1/ 2
é uma boa medida da anisotropia do contorno de pico.
O traço da matriz de inércia,
( A.7)
t = I xx + I yy = I 11 + I 22
86
análogo ao momento de inércia polar, é uma boa medida para a extensão do pico no plano
xy.
A matriz de inércia simétrica têm 3 elementos independentes dos quais foram
derivadas 3 grandezas θ, e e t. Mais tarde será mostrado que as interpretações geométricas
de θ, e e t estão alinhadas com aspectos da forma do pico de distribuição.
A .3 ESPECIFICAÇÃO DO PONTO DE OPERAÇÃO (“THRESHOLDING”)
O ângulo θ , a excentricidade e e o traço t são, como parâmetros de momentos de
segunda ordem ,bons candidatos para a discriminação entre os picos do alvo e o do cenário
somente se há uma diferença estatística entre os dois tipos de pico, caracterizados pelos
parâmetros dos momentos. Os histogramas dos picos do alvo são estimativas empíricas de
funções de densidade de probabilidade dos parâmetros de 2º orem, dado que o pico de
correlação corresponde à um alvo legítimo, assim como o pico do cenário. Esta informação
é necessária e suficiente para nos permitir o projeto de um discriminador de alvo-cenário .
Para cada intervalo no domínio dos parâmetros ( o que também vale para o caso de multithresholding) podemos integrar o histograma do alvo corretamente normalizado para a
obtenção da detecção da probabilidade do objeto Pd e, respectivamente, para o histograma
87
do cenário, obtendo-se assim a probabilidade de “alarme falso” correspondente Pfa. Um
intervalo de campo diferente leva à um ponto diferente no plano PfaPd, formando as
Características Operativas de Resposta (ou C.O.R., Caprari,1998)
Antes do detetor de threshold ser totalmente especificado, permanece a questão de
se nominar um intervalo (ou intervalos ) no domínio dos parâmetros nos quais a detecção
dos alvos é favorecida, o que equivale à nominar um ponto operativo ( ou vários pontos,
para o caso de muitos alvos) na região COR, coincidente com o alvo de referência – no
caso, o centróide . Na situação na qual a COR é crescente de forma monótona e contínua , a
maneira mais convencional e simples de selecionar um ponto de operação na COR é
escolher um valor de Pfa que especifica totalmente a região do domínio dos parâmetros
atribuidos ao alvo, ou seja, especifica o threshold que deve ser excedido – que aliás é
melhor especificado para um número discreto de pontos do que para um “continuum”.
Escolhe-se o ponto de operação (“threshold”) definindo-se uma medida de
detecção universal efetiva, função das probabilidades de detecção do alvo e dos alarmes
falsos η(Pfa,Pd):
η (Pfa, Pd ) =
ln (0.005 + 0.995 Pfa) [1 + exp (− 0.5 / 0.06 )]Pd 0.4
*
ln (0.005 )
{1 + exp [− (− Pd − 0.5 / 0.06 )]}
88
( A.8 )
η é o produto de uma função monotonamente decrescente de Pfa por uma função
monotonamente crescente Pd. Os dois fatores de η levam os valores de 0 a 1 nas suas
extremidades. η depende de Pfa com uma queda logarítmica que compensa – ou penaliza –
diminuições ou aumentos de Pfa (diferenças de iluminação, ruído e outros fatores
externos).
Sendo o ângulo, a excentricidade e o traço para a correlação dos picos de alvo
estatisticamente independentes e normalmente distribuídos, então sua densidade de
probabilidade é:
p(θ , e, t | alvo ) =
1
(2π )3 / 2 σ θ − tσ e −t σ t− t
 − (θ t − µθ −t ) 2 (e − µ e − t )2 (t − µ t − t )2 
exp 
−
−

σ 2 θ −t
σ e2− t
σ t2− t 

( A.9 )
onde µθ-t e σ θ-t 2 são, respectivamente, a média e a variância da distribuição dos ângulos dos
picos do alvo, com o domínio dos ângulos escolhidos para assegurar uma distribuição
unimodal. µe-t e σe-t2 são, respectivamente, a média e a variância da distribuição de
excentricidade dos picos do alvo. µt-t e θt-t2 são, respectivamente, a média e a variãncia da
distribuição do traço dos picos de alvo. θt é o parâmetro de ângulo expresso no mesmo
domínio da distribuição do ângulo de alvo caracterizado por µe-t e σ e-t 2. E e t são,
respectivamente, a excentricidade e o traço.
89
Do mesmo modo, se o ângulo, a excentricidade e o traço dos picos de correlação
do cenário são estatisticamente independentes e normalmente
distribuídos, então a densidade de probabilidade condicionada ao pico de correlação do
p (θ , e, t | cenário ) =
 − (θ ct − µθ −c )2 (e − µe −c )2 (t − µt −c )2 
exp
−
−

σ e2−c
σ t2−c 
(2π )3 /2σ θ −cσ e−cσt −c  σ 2θ −c
1
cenário é:
( A.10 )
µθ-c e σθ-c2 são, respectivamente, a média e a variância da distribuição dos ângulos dos
picos do cenário, com o domínio dos ângulos escolhidos para assegurar u´a distribuição
unimodal a mais diferente possível dos picos de alvo. µe-t e σe-t 2 são, respectivamente, a
média e a variância da distribuição de excentricidade dos picos do alvo são,
respectivamente, a média e a variância da distribuição do traço dos picos do cenário. θt é o
parâmetro de ângulo expresso no mesmo domínio a distribuição do ângulo de cenário
caracterizado por µe-c e σe-c2 . E e t são, respectivamente, a excentricidade e o traço. Nota-se
que os parâmetros do ângulo θt e θc são computados como estão, indiferente se o detetor
escolher entre ângulo ou o alvo para o threshold.
A Razão de Semelhança do parâmetro de momento de segunda ordem é definido
como
90
L(θ , e, t ) =
p(θ , e, t | alvo)
p(θ , e, t! cenário )
( A.11)
A detecção do alvo estatisticamente ótima é alcançada pela regra de decisão como
δ (θ , e, t ) = 1 ...L(θ , e, t ) ≥ τ
( A.12 )
δ (θ , e, t ) = 0...L (θ , e, t ) < τ
onde a escolha do threshold τ’ é ditada pela regra δ=1 ( ou 0 ) correspondendo à escolha do
alvo – ou cenário – para referência de threshold.
A extensão do método para o caso de múltiplos thresholds – o caso do futebol de
robôs, por exemplo, em que a imagem da bola e dos robôs da competição devem ser
distinguidos da do restante do cenário – é direta devido ao próprio critério discriminante.
Por exemplo, no caso de 3 thresholds, assume-se somente 2: 1 <= τ1 <= τ 2 <= L, pela
separação de três classes de domínios C0 para [ 1,...,τ 1 ], C1 para [τ1 +1,...,τ2 ] e C2
[τ2 +1,...τ3 ]. O critério de medida σ θ2 ( ou σ t 2 e até mesmo η) é então função de duas
91
variáveis τ1 e τ2 , e um conjunto ótimo de thresholds
τ1 * e τ2 * é selecionado pela
maximização de σθ2 .
(
)
σ θ2 τ 1*τ 2* = max σ θ2 (τ 1 , τ 2 )
(A.13)
Deve-se notar que os thresholds selecionados geralmente tornam-se menos
precisos à medida que o número de classes a serem separadas cresce – o que é devido ao
critério de medida a ser definido em uma escala de cinza unidimensional ( para o caso de
cores, tem-se três canais , correspondendo à escala de cores RGB – vermelho, verde e azul )
. Entretanto, para o caso do futebol de robôs, temos apenas 2 ou 3 thresholds ( bola, cor
definida em escala de cinza do nosso time e cor definida em escala de cinza do time
adversário)), o que torna a computação simples e torna desnecessário processos especiais
de detecção.
Antecipando o problema da detecção e navegação do robô móvel, à ser
apresentado em detalhes na seção 3, as propriedades anisotrópicas da matriz de inércia são
importantes para a determinação e guia do robô móvel rumo à bola. Assumindo-se que o
robô seja de superfície superior quadrada, com um alvo de referência sobre este de uma
forma qualquer ( elipse, por exemplo, embora não seja o caso do futebol de robôs ) , cujos
centróides sejam coincidentes, determina-se, através do traço, o momento de inércia polar
de ambos:
I poq = I xx' + I yy ' (quadrado)
I poe = I xx ' + I yy ' (elipse)
92
( A.14)
Os momentos de inércia da elipse são os que são computados pelo programa de
thresholding, e os do quadrado são dados invariantes do problema . Passando-se aos dois
momentos de inércia polares, com c=d e a e b os semi-eixos da elipse:
I poq
I poe
c2 2
=
c +d 2
3
a 2 + b2
=
4
(
)
3  3
a
4cd  4cd

b


( A.15)
então
I xx ' =
3
,
12
3
I yy' =
3  3 
b
a
4cd  4cd 
,
12
( A.16 )
e
com a regra: se Ixx´> Iyy´, a direção dada será a do eixo x do referencial móvel.
93
94