- Universidade Federal Fluminense
Transcrição
- 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