Desenvolvimento de sistema de controlo de movimento para plataformas móveis autónomas

Universidade do Minho Escola de Engenharia Tiago João Fernandes Maia Desenvolvimento de Sistema de Controlo de Movimento para Plataformas Móveis Autónomas outubro de 2019 Desenvolvimento de Sistema de Controlo de Movimento para Plataformas Móveis Autónomas Tiago João Fernandes Maia UMinho | 2019 Escola de Engenharia Tiago João Fernandes Maia Desenvolvimento de Sistema de Controlo de Movimento para Plataformas Móveis Autónomas Dissertação de Mestrado Ciclo de Estudos Integrados Conducentes ao Grau de Mestre em Engenharia Eletrónica Industrial e Computadores Trabalho realizado sob a orientação do Professor Doutor António Fernando Macedo Ribeiro outubro de 2019 ii DIREITOS DE AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho Atribuição CC BY https://creativecommons.org/licenses/by/4.0/ iii AGRADECIMENTOS Esta secção é dedicada a todas as pessoas que de uma forma, direta ou indireta, contribuíram e apoiaram-me ao longo do curso, que termina com esta dissertação. A todos deixo aqui os meus sinceros agradecimentos. Em primeiro lugar quero agradecer ao meu orientador Professor Dr. Fernando Ribeiro e ao Professor Dr. Gil Lopes, por me terem dado a oportunidade de fazer parte do LAR e do projeto Minho Team MSL. Oportunidade essa que me ajudou a evoluir como pessoa e profissional, dando-me a possibilidade de aprender a trabalhar em equipa e de pôr em prática alguns conhecimentos adquiridos no curso. Obrigado por todo o apoio e confiança que depositaram em mim. Agradeço aos meus amigos e colegas que encontrei no LAR, pela partilha de conhecimento e pelos dias e noites que passamos a trabalhar para alcançar o objetivo mais desejado, fazer um jogo completo na MSL. Às minhas três irmãs, agradeço muito por toda a ajuda e incentivo quando mais necessitei. Por último, e mais importante, um agradecimento muito especial ao meu pai, João Maia e à minha mãe, Maria da Conceição pela oportunidade que me deram para continuar a estudar, sem vocês nada disto era possível. Obrigado por tudo. A todos, muito obrigado. iv DECLARAÇÃO DE INTEGRIDADE Declaro ter atuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. v DESENVOLVIMENTO DE SISTEMA DE CONTROLO DE MOVIMENTO PARA PLATAFORMAS MÓVEIS AUTÓNOMAS RESUMO Nas últimas décadas tem-se verificado um crescimento acentuado em projetos na área da robótica móvel e autónoma, nomeadamente para acompanhamento de pessoas idosas ou com deficiências, ou mesmo para tarefas domésticas. Este crescimento deve-se em boa medida à evolução de áreas como a eletrónica e a informática que permitiram uma redução dos custos de desenvolvimento e um considerável aumento na velocidade de processamento. Isso tem permitido um desenvolvimento considerável em algoritmos de controlo, inteligência artificial e visão por computador. Esta dissertação tem como objetivo a implementação e validação de uma arquitetura de controlo de movimento, baseada no planeamento da trajetória, com aplicação prática na equipa de futebol robótico do Laboratório de Automação e Robótica (LAR) da Universidade do Minho, denominada Minho Team. A equipa é constituída por 5 robôs futebolistas de tamanho médio (até 80 cm de altura e 40 kg de peso) que foram desenvolvidos com todos os requisitos para participar no RoboCup, mais propriamente numa liga denominada de Middle Size League (MSL). Estes robôs são totalmente autónomos e operam num ambiente extremamente dinâmico, constituído por obstáculos dinâmicos que se deslocam a velocidades elevadas (por vezes atingindo os 4 m/s). Cada um dos robôs da Minho Team faz o planeamento da sua trajetória entre a posição atual e uma posição pretendida. A trajetória é planeada de forma a obter o melhor compromisso entre a trajetória mais curta e a mais suave, evitando colisões com obstáculos em campo. Para isso, foram implementados métodos associados a um planeamento global e adicionados outros algoritmos a estes métodos, formando um modelo de planeamento da trajetória eficiente e robusto. Para transformar a representação contínua do espaço de jogo num mapa discreto foi utilizado o método do diagrama de Voronoi, sendo a pesquisa pela trajetória mais curta realizada pelo algoritmo de Dijkstra. Para construir uma trajetória suave foi utilizado o método de curvas paramétricas polinomiais, e para determinar o melhor movimento ao longo de uma trajetória foi implementado o controlador PID em malha fechada. O principal objetivo desta solução é permitir que os robôs em campo consigam jogar futebol com a máxima velocidade possível, obedecendo às regras de jogo, nomeadamente, não colidir com os robôs adversários nem robôs cooperativos (robôs da Minho Team). Palavras-Chave: Controlo, MSL, Planeamento da Trajetória, Robótica. vi DEVELOPMENT OF MOTION CONTROL SYSTEM FOR AUTONOMOUS MOBILE PLATFORMS ABSTRACT In the recent decades, there has been a pronounced growth in projects in the area of autonomous mobile robotics, particularly for assisting elderly or incapacitated people as well as helping with domestic tasks. This growth is due to the evolution of areas such as electronics and advanced computing, that allowed a reduction of development costs and a considerable increase in processing speed. This has allowed considerable development in control algorithms, artificial intelligence and computer vision. This dissertation aims at the implementation and validation of a motion control architecture, based on trajectory planning, with practical application in the robotic soccer team of the Laboratory of Automation and Robotics at the University of Minho, called Minho Team. The team consists of 5 mediumsized soccer robots (up to 80 cm in height and 40 kg in weight) which were developed with all the requirements to participate in RoboCup, more specifically in a league called Middle Size League (MSL). These robots are fully autonomous and operate in an extremely dynamic environment, constituted by dynamic obstacles that move at high speeds (sometimes up to 4 m/s). Each robot of the Minho Team makes planning for its trajectory between the current position and the desired position. The trajectory is planned in such a way as to obtain the best balance between the shortest and the smoothest trajectories in a way to also avoid collisions with obstacles in the field. For this matter, methods associated with global planning were implemented and other algorithms were added to these methods forming an efficient and robust trajectory planning model. The Voronoi diagram’s method was used to transform the continuous representation of the game space into a discrete map being the search for the shortest trajectory performed by the Dijkstra algorithm. To build a smooth trajectory, the parametric polynomial curves method was used. And to determine the best movement along a trajectory, the closed-loop PID controller was implemented. The main objective of this solution is to allow robots to play soccer with the possible maximum speed, obeying the rules of the game, namely, not to collide with the enemy robots or the cooperative robots (Minho Team robots). Keywords: Control, MSL, Path Planning, Robotics. vii ÍNDICE Capítulo 1 Introdução .......................................................................................................... 1 1.1. Enquadramento e Motivação ............................................................................................. 1 1.1.1. RoboCup ................................................................................................................... 3 1.1.2. Middle Size League .................................................................................................... 4 1.1.3. Minho Team .............................................................................................................. 5 1.2. Descrição do Problema ..................................................................................................... 6 1.3. Objetivos ......................................................................................................................... 6 1.4. Publicações ..................................................................................................................... 7 Capítulo 2 Estado da Arte .................................................................................................... 8 2.1. CAMBADA ....................................................................................................................... 8 2.2. Carpe Noctem Cassel ....................................................................................................... 9 2.3. Tech United Eindhoven ................................................................................................... 11 2.4. Discussão do Estado da Arte ........................................................................................... 12 Capítulo 3 Fundamentos Teóricos .................................................................................... 15 3.1. Navegação Autónoma ..................................................................................................... 15 3.1.1. Planeamento da Trajetória ........................................................................................ 16 3.1.1.1. Tipos de Planeamento da Trajetória .................................................................... 17 3.1.1.2. Espaço de Configuração .................................................................................... 19 3.1.1.3. Diagrama de Voronoi ......................................................................................... 21 3.1.1.4. Triangulação de Delaunay .................................................................................. 22 3.1.1.5. Dualidade entre Voronoi e Delaunay ................................................................... 23 3.1.1.6. Algoritmo de Dijkstra ......................................................................................... 25 3.1.1.7. Curvas Paramétricas Polinomiais ....................................................................... 29 3.1.2. Controlo do Movimento ............................................................................................ 32 3.1.2.1. Sistema de Controlo em Malha Fechada ............................................................. 32 3.1.2.2. Controlador PID ................................................................................................ 33 3.1.2.3. Controlador PID Digital ...................................................................................... 35 3.2. Robot Operating System ................................................................................................. 36 3.2.1. Arquitetura ROS ....................................................................................................... 37 xiv Figura 6.12 – Trajetória mais curta e suave. O ponto laranja representa a posição da bola................ 90 Figura 6.13 – Trajetórias percorridas pelo robô relativas à trajetória inicial apresentada na Figura 6.12 . .......................................................................................................................................... 90 Figura 6.14 – Tipo de comportamento do robô. (a) Trajetória mais curta e suave. (b) Trajetória percorrida pelo robô..................................................................................................................... 90 Figura 6.15 – Tipo de comportamento do robô. (a) Trajetória mais curta e suave. (b) Trajetória percorrida pelo robô..................................................................................................................... 91 Figura 6.16 – Trajetória mais curta e suave para cada robô (robôs 1 e 2 ). ....................................... 91 Figura 6.17 – Trajetórias percorridas pelos robôs 1 e 2 , relativas às trajetórias iniciais apresentadas na Figura 6.16 . ........................................................................................................................... 92 Figura 6.18 – Trajetórias percorridas pelos robôs 1 e 2 , relativas às trajetórias iniciais apresentadas na Figura 6.16 . ........................................................................................................................... 92 Figura 6.19 – Trajetórias percorridas pelos robôs 1 e 2 , relativas às trajetórias iniciais apresentadas na Figura 6.16 . ........................................................................................................................... 93 Figura 6.20 - Robôs da Minho Team no Festival Nacional de Robótica 2017 em Coimbra. ................ 95 xv LISTA DE ACRÓNIMOS ISO International Organization for Standardization FIFA Fédération Internationale de Football Association 2D Duas Dimensões 3D Três Dimensões MSL Middle Size League LAR Laboratório de Automação e Robótica FNR Festival Nacional de Robótica A* A Star API Application Programming Interface CGAL Computational Geometry Algorithms Library EC Espaço de Configuração DOF Degrees Of Freedom ROS Robot Operating System GPS Global Positioning System CAD Computer-Aided Design IDE Integrated Development Environment PID Proportional Integral Derivative ADC Analog-to-Digital Converter IMU Inertial Measurement Unit 1 Capítulo 1 INTRODUÇÃO Esta dissertação surge no âmbito do Mestrado Integrado em Engenharia Eletrónica Industrial e Computadores da Universidade do Minho, com o objetivo de documentar o trabalho desenvolvido durante o projeto de dissertação denominado Desenvolvimento de Sistema de Controlo de Movimento para Plataformas Móveis Autónomas . Este capítulo inicia com o enquadramento deste projeto na robótica em geral e a motivação para a realização do mesmo. Posteriormente, é apresentado o problema que se pretende resolver e também são definidos os objetivos para esta dissertação. 1.1. ENQUADRAMENTO E MOTIVAÇÃO A robótica surgiu com a intenção de oferecer sistemas que permitam auxiliar os humanos em algumas tarefas e substituí-los noutras com maior velocidade, precisão e segurança [1]. Estes sistemas, constituídos por plataformas mecânicas, hardware e software , são desenvolvidos com a aplicação de conceitos de áreas como a matemática, física, química, biologia e de áreas que estudam o corpo humano, tal como, a neurologia [1]. A evolução tecnológica verificada nas últimas décadas, permitiu o desenvolvimento de robôs móveis que se deslocam autonomamente em diversos ambientes. Contudo não existe uma solução otimizada que consiga abranger a enorme variedade de aplicações que existe atualmente para robôs móveis. Por esse facto, a robótica móvel continua em constante evolução. Para além da importância da evolução tecnológica, o crescimento da robótica deve-se ao esforço da comunidade científica no desenvolvimento em algoritmos de controlo, inteligência artificial e visão por computador. A presença em competições robóticas, como exemplo o RoboCup, tem um peso muito importante para este desenvolvimento, sendo uma forma dos investigadores apresentarem e partilharem ideias. Esta crescente evolução tem contribuído de forma significativa para o desenvolvimento de plataformas, que posteriormente resultam em novos produtos para o mercado. Esses produtos estão focados em dois tipos de robôs, os industriais e os de serviços. Os robôs de serviço, tipicamente móveis, são utilizados no auxílio a tarefas realizadas por humanos, sendo capazes de navegar e de se adaptarem INTRODUÇÃO 2 aos ambientes onde atuam. Os robôs assistentes em hospitais como o HOSPI da Panasonic [2] (ver Figura 1.1 ) são um bom exemplo de robôs de serviço. Estes realizam diferentes tarefas, desde a entrega de medicamentos, amostras médicas para análise e anotações médicas de casos de pacientes, proporcionando assim aos profissionais responsáveis pelos cuidados médicos mais tempo na assistência aos pacientes. O HOSPI, através do conhecimento prévio do mapa do hospital, tem a capacidade de escolher a melhor trajetória para se deslocar para um determinado local e utilizar sensores para se desviar de obstáculos, caso seja necessário deve calcular um novo percurso. Localização, desvio de obstáculos e planeamento da trajetória são tarefas indispensáveis para o funcionamento deste tipo de robôs. Figura 1.1 – Robô de entrega autónomo Panasonic-HOSPI [2]. Auxilia nas tarefas hospitalares. Um robô industrial é definido pela norma ISO 8373 [3] como sendo um manipulador de três ou mais eixos, controlado automaticamente e programável, pode ser fixo ou móvel para o uso em aplicações de automação industrial. As indústrias de produção de eletrodomésticos, automóvel, alimentar, semicondutores e plásticos são algumas das áreas da aplicação destes robôs, pois o aumento de produtividade, a qualidade dos produtos e a operação em ambientes difíceis e perigosos para os humanos são algumas das vantagens que a indústria obtém com estes robôs. Alguns robôs são programados para realizarem ações repetidamente sem nenhuma variação, estas ações são determinadas por rotinas pré-programadas que especificam a posição, força e aceleração dos movimentos [4]. Outros são mais flexíveis nas linhas de produção recorrendo a câmaras, que através de algoritmos de visão por computador e inteligência artificial conseguem se adaptar a possíveis variações na produção. INTRODUÇÃO 3 1.1.1. ROBOCUP O RoboCup [5] é um encontro científico internacional promovido pela RoboCup Federation, que tem como objetivo promover o estudo e o desenvolvimento da inteligência artificial, robótica e de áreas relacionadas. Na sua criação foi definida uma meta, o principal objetivo a longo prazo: “ No ano de 2050, uma equipa de robôs totalmente autónomos humanoides, ser capaz de vencer um jogo de futebol contra a equipa campeã do mundo de futebol humano, cumprindo as regras oficiais da FIFA ” [5]. A primeira edição decorreu em 1997 em Nagoya no Japão, sendo realizado anualmente em várias cidades por todo o mundo, como em Lisboa, em 2004 [6]. Cada edição é constituída por competições de diferentes categorias e um simpósio, onde é possível aos participantes apresentarem e discutirem os seus trabalhos de investigação. Atualmente o RoboCup é constituído pelas seguintes categorias: RoboCupSoccer, RoboCupRescue, RoboCup@Home, RoboCupIndustrial e RoboCupJunior. Cada uma destas categorias é constituída pelas seguintes ligas: • RoboCupSoccer o Humanoid League ▪ KidSize ▪ TeenSize ▪ AdultSize o Standard Platform League o Middle Size League o Small Size League o Simulation League ▪ Simulation 2D ▪ Simulation 3D • RoboCupRescue o Rescue Robot League o Rescue Simulation League ▪ Agent Simulation and Infrastructure ▪ Virtual Robot • RoboCup@Home o Open Platform League o Domestic Standard Platform League INTRODUÇÃO 4 o Social Standard Platform League • RoboCupIndustrial o RoboCup@Work League o RoboCupLogistics League • RoboCupJunior o Soccer o OnStage o Rescue ▪ CoSpace 1.1.2. MIDDLE SIZE LEAGUE A Middle Size League (MSL) foi uma das ligas criadas no início do RoboCup, em 1997. Nesta liga os robôs devem jogar futebol de acordo com as regras do RoboCup, que se baseiam nas regras oficiais da FIFA, com algumas alterações necessárias para um jogo de futebol com robôs [7]. Um jogo tem duas partes de 15 minutos cada e um intervalo que não deve exceder os 10 minutos. Disputado por duas equipas, cada equipa pode jogar com 5 robôs que devem ter no máximo 80 cm de altura, 52 cm × 52 cm na base e um peso máximo de 40 kg, tendo estes de apresentar cor maioritariamente preta. Cada um dos robôs tem de jogar autonomamente, contendo os seus próprios sensores. Através do wireless podem partilhar informação em tempo real entre os elementos da equipa e com um computador externo, denominado de Base Station , que atua como um treinador e não tem qualquer tipo de sensor. À semelhança de um jogo de futebol humano, na MSL também existem regras que devem ser cumpridas durante o jogo e para isso é atribuído a humanos a tarefa de fazer valer essas regras, normalmente é nomeado um árbitro e um ou mais assistentes. Como os robôs ainda não detetam sons, as faltas ou as ações marcadas pelo árbitro são entendidas pelos robôs através da utilização de um computador com uma interface denominada de Referee Box . Esta interface envia comandos sobre as situações de jogo para a Base Station de cada uma das equipas, como o start , stop , kick-off e entre outras decisões do árbitro. O campo de jogo é verde, tem no máximo 18 m × 12 m e as linhas são brancas. As balizas têm 2 m de largura e 1 m de altura. INTRODUÇÃO 5 A MSL desde a sua existência tem oferecido grandes desafios a nível científico, pois o ambiente de jogo é extremamente dinâmico e os robôs deslocam-se a velocidades elevadas, por vezes atingindo os 4 m/s. Este ambiente é ainda mais complexo pelo facto de não existir uma observação total do espaço de jogo, por isso, cada robô tem o seu sistema de visão. Para que seja possível jogar é necessário a perceção do espaço de jogo por parte de cada um dos robôs, fusão sensorial, algoritmos para o controlo do movimento e ainda a colaboração entre os múltiplos robôs, através de estratégias de jogo. Figura 1.2 - Jogo da MSL no RoboCup European Open 2016. 1.1.3. MINHO TEAM A Minho Team é a equipa de futebol robótico do Laboratório de Automação e Robótica (LAR) da Universidade do Minho. Esta surgiu em 1998 e tem participado ativamente na Middle Size League, em eventos nacionais e internacionais, tais como o Festival Nacional de Robótica (FNR) e o RoboCup. Fez a sua primeira participação no RoboCup em 1999, sendo uma das primeiras equipas a surgir nestas provas, onde tem colaborado ao longo destes anos para a evolução do estado da arte desta competição. A equipa desde que iniciou a sua atividade tem desenvolvido várias versões de robôs para competir na MSL, tal como ilustrado na Figura 1.3 . Nessas versões foram implementadas algumas soluções inovadoras que ainda hoje são utilizadas por outras equipas, tais como, o sistema de chuto eletromagnético e o dribbler [8], [9], [10], [11], [12]. A Minho Team nem sempre competiu devido à saída dos seus elementos, pois esta contou com vários alunos que quando concluíam o curso terminavam a sua ligação com a equipa e não existia continuidade do trabalho desenvolvido. Alguns alunos que atualmente estão na equipa retomaram o INTRODUÇÃO 6 projeto em 2015, dando início à remodelação da plataforma anterior desenvolvida em 2011. No Capítulo 4 será apresentada a versão mais atual dos robôs da Minho Team. Figura 1.3 – Evolução da Minho Team. 1.2. DESCRIÇÃO DO PROBLEMA O RoboCup apresenta atualmente um elevado nível de competitividade e a MSL não é exceção. Para este nível de exigência é necessário que software , hardware e mecânica estejam bem estruturados. Visão por computador, inteligência artificial, gestão das comunicações, planeamento da trajetória e controlo são algoritmos importantes para a coordenação destes robôs. Na MSL cada uma das duas equipas em jogo é constituída por 5 robôs futebolistas de tamanho médio (até 80 cm de altura e 40 kg de peso), são robôs totalmente autónomos e operam num ambiente extremamente dinâmico, constituído por obstáculos dinâmicos que se deslocam a velocidades elevadas (por vezes atingindo os 4 m/s). Neste ambiente dinâmico cada robô necessita de se deslocar de um ponto A para um ponto B sem colidir com os obstáculos em campo, exceto a bola, caso contrário pode ser assinalado falta. Para isso, terá de planear constantemente uma trajetória, de preferência a mais curta e a mais suave, e percorrer essa trajetória no menor tempo possível. 1.3. OBJETIVOS O principal objetivo desta dissertação passa pela implementação e validação de uma arquitetura de controlo de movimento, baseada no planeamento da trajetória, com aplicação prática na equipa de futebol robótico da Universidade do Minho, denominada Minho Team. O objetivo inicial para todos os elementos da equipa foi a reconstrução e melhoramento da plataforma de cada robô, desenvolvida em 2011. Para isso, foram atribuídas tarefas a cada um dos elementos, no que diz respeito à estrutura mecânica, ao hardware e ao desenvolvimento de software . INTRODUÇÃO 7 Outro objetivo é publicar o software desenvolvido no trabalho desta dissertação, de modo a contribuir para o crescente estado da arte da robótica, do RoboCup e mais especificamente da MSL. Para alcançar os objetivos supracitados, será necessário trabalhar nas seguintes tarefas: • Estudo do estado da arte em algoritmos de planeamento da trajetória utilizados em robótica e em algumas equipas que participam na MSL; • Estudo dos algoritmos a implementar nesta dissertação para o planeamento da trajetória e para o controlo do movimento; • Implementação de todos os algoritmos num módulo individual do restante software da Minho Team utilizando o ROS ( Robot Operating System ); • Implementação de ferramentas/ software que possibilite a configuração dos parâmetros que necessitam de ajuste; • Testar todo o software desenvolvido utilizando o simulador da Minho Team; • Testar todo o software no campo de pequenas dimensões disponível no LAR; • Testes em ambiente de competição/jogar um jogo da MSL; É também um objetivo desta dissertação que o software desenvolvido possa ser reutilizado noutros tipos de robôs. 1.4. PUBLICAÇÕES H. Ribeiro, P. Silva, R. Roriz, T. Maia, R. Saraiva, G. Lopes, and A. F. Ribeiro, “Fast Computational Processing for Mobile Robots’ Self-Localization,” Proc. - 2016 Int. Conf. Auton. Robot Syst. Compet. ICARSC 2016 , no. March, pp. 168–173, 2016. 8 Capítulo 2 ESTADO DA ARTE Neste capítulo é feita uma análise à arquitetura de controlo de movimento, mais especificamente, o planeamento da trajetória para os robôs de algumas equipas que participam na MSL. CAMBADA, Carpe Noctem Cassel e Tech United Eindhoven são as equipas descritas neste capítulo, pois são as que publicam a informação sobre este tema com maior detalhe. 2.1. CAMBADA CAMBADA é a equipa de futebol robótico da Universidade de Aveiro [13]. Este projeto começou em 2003, contando com várias participações na Middle Size League em eventos nacionais e internacionais. Nas suas participações destaca-se o primeiro lugar no RoboCup em 2008. Esta equipa faz a discretização da representação do espaço de jogo, ou de trabalho, em células, utilizando o método aproximado de decomposição em células. Cada célula tem uma resolução de 50 cm × 50 cm e pode ser do tipo: posição atual (azul), posição pretendida (vermelho), obstáculo (preto), espaço livre (verde). Na Figura 2.1 é apresentado um exemplo da discretização da representação do espaço de jogo com as cores de cada célula. Para a pesquisa pela trajetória entre a posição atual e a posição pretendida é implementado o algoritmo A* ( A Star ). Este algoritmo foi modificado para evitar colisões com os adversários, como também, manter uma distância segura para que estes não consigam tirar a bola. Este A* modificado consiste em não considerar células a uma distância 𝑛 de células com obstáculo. Um exemplo de duas trajetórias obtidas pelo A* e A* modificado podem ser observadas na Figura 2.1 . As células com a cruz magenta formam a trajetória obtida pelo algoritmo A* e as células com a cor amarela formam a trajetória obtida pelo A* modificado [14]. O software desta equipa é implementado com a linguagem de programação C++. A implementação do algoritmo para a discretização da representação do espaço de jogo e para a pesquisa da trajetória é auxiliado pela API Libtcod [15]. Esta API é bastante utilizada por desenvolvedores de jogos e está disponível em diferentes linguagens de programação. 15 Capítulo 3 FUNDAMENTOS TEÓRICOS Neste capítulo serão apresentados os métodos e respetivos conceitos para o desenvolvimento desta dissertação. O primeiro subcapítulo é sobre navegação autónoma, que inicia com uma breve introdução, e de seguida são apresentados alguns métodos e respetivos conceitos sobre o planeamento da trajetória e controlo do movimento, sendo estes descritos com a intenção de serem implementados em robôs móveis autónomos. O segundo subcapítulo é uma introdução ao ROS ( Robot Operating System ) e à sua arquitetura. 3.1. NAVEGAÇÃO AUTÓNOMA Os robôs ou veículos móveis autónomos têm ganho cada vez mais importância na sociedade, devido ao crescente investimento na investigação e desenvolvimento por parte de diversas entidades, de forma a desenvolver soluções para aplicações industriais, hospitalares, domésticas, militares, exploração espacial e mais recentemente nos transportes. Com esta expansão e exigência, foi indispensável ao longo dos últimos anos o desenvolvimento de sistemas móveis autónomos robustos e adaptáveis a qualquer tipo de ambiente. Um dos problemas fundamentais num sistema móvel autónomo é a navegação. Um robô ou veículo móvel autónomo tem de se mover entre a posição atual e a posição pretendida, de modo eficaz. Para que tal seja possível são necessários os seguintes processos: (a) perceção do espaço de trabalho: através da recolha de informação de todos os sensores, (b) localização e construção de um mapa: com os dados obtidos na perceção do espaço de trabalho é construído um mapa onde os obstáculos são mapeados. É também determinada a localização (posição e orientação) do robô no mapa, (c) planeamento da trajetória: encontra a melhor trajetória a ser percorrida pelo robô, e (d) controlo do movimento: calcula os valores para o controlo dos motores, de modo a que o robô percorra a trajetória obtida no processo anterior. Na Figura 3.1 são apresentados de uma forma geral os processos de navegação [21]. FUNDAMENTOS TEÓRICOS 16 Figura 3.1 - Organização geral dos processos de navegação, adaptado de S. G. Tzafestas (2013) [21]. Planeamento da trajetória e controlo do movimento são os processos de navegação investigados e implementados neste trabalho de dissertação. Tal como já foi mencionado no início deste capítulo, todos os métodos e respetivos conceitos apresentados no atual subcapítulo, sobre estes dois processos de navegação, serão descritos com a intenção de serem implementados em robôs móveis autónomos. Contudo, é importante referir que estes podem ser implementados noutros tipos de robôs, tais como robôs manipuladores (braço robótico), robôs móveis/manipuladores e robôs humanoides. Para estes dois processos de navegação existem diversos métodos, por isso serão apresentados apenas aqueles que foram implementados no trabalho desta dissertação. O motivo para a utilização de cada método será descrito no Capítulo 5 IMPLEMENTAÇÃO . 3.1.1. PLANEAMENTO DA TRAJETÓRIA O planeamento da trajetória ou como é mais conhecido em inglês, Path Planning , é um dos processos de navegação supracitados no atual subcapítulo NAVEGAÇÃO AUTÓNOMA . Este processo tem como objetivo, determinar uma trajetória ótima para o sistema autónomo. Com essa trajetória ótima o robô ou veículo móvel autónomo deve ser capaz de se deslocar da posição atual para outro local e, eventualmente, para a posição pretendida final, ao mesmo tempo evitando quaisquer obstáculos. Uma trajetória tem também um determinado custo que deve ser minimizado, esse custo pode ser em relação: (a) comprimento: encontrar a trajetória mais curta, (b) tempo: a trajetória a percorrer no menor tempo Espaço de Trabalho Perceção do Espaço de Trabalho Localização e Construção de um Mapa Planeamento da Trajetória Controlo do Movimento Atuadores Sensores Trajetória Posição/ Mapa de Posições Tarefa/Posição Desejada Dados Percebidos FUNDAMENTOS TEÓRICOS 17 possível, (c) esforço: minimizar o consumo de energia do robô, (d) espaço: aumentar o espaço de manobra para o robô, e/ou, (e) segurança: minimizar a possibilidade de qualquer colisão com obstáculos. Para resolver um problema de planeamento da trajetória é indispensável analisar o espaço de trabalho ou ambiente antes de optar por qualquer tipo de planeamento (global, local ou uma combinação dos dois), ou por qualquer método. Desta forma, é necessário analisar qual o conhecimento disponível que o robô móvel autónomo tem sobre o espaço de trabalho e saber qual o tipo de obstáculos que possam existir. O espaço de trabalho onde se encontra o robô pode ser totalmente conhecido, parcialmente conhecido ou totalmente desconhecido. Na maioria dos casos é parcialmente conhecido, isto significa que o robô não tem um conhecimento completo de todos os obstáculos no espaço de trabalho. Os obstáculos podem ser, obstáculos estáticos ou obstáculos em movimento. 3.1.1.1. TIPOS DE PLANEAMENTO DA TRAJETÓRIA O planeamento da trajetória pode ser global, local ou uma combinação dos dois, criando um sistema de planeamento híbrido [22], [23]. O planeamento global está inserido numa arquitetura de controlo/navegação deliberativa (ver Figura 3.2 ), este tipo de planeamento exige um mapa com a representação total do espaço de trabalho para obter uma trajetória ótima com uma posição precisa até à posição pretendida. Porém, é difícil obter um mapa completo, por isso, este planeamento não é adequado para um espaço de trabalho dinâmico (obstáculos em movimento). Figura 3.2 - Arquitetura de controlo/navegação deliberativa. Informação Sensorial Modelação do Espaço de Trabalho (Construção de um Mapa) Planeamento da Trajetória Atuação FUNDAMENTOS TEÓRICOS 18 Os algoritmos para o planeamento global exigem uma elevada capacidade de processamento e memória. O tempo de resposta é relativamente mais lento, que pode originar atraso na navegação. O planeamento local está inserido numa arquitetura de controlo/navegação reativa (ver Figura 3.3 ), esta surgiu depois da arquitetura deliberativa com o objetivo de superar os problemas de navegação em espaços dinâmicos e totalmente desconhecidos. Desta forma, a arquitetura reativa é baseada em comportamentos, que dependem da informação sensorial. Isto é, o robô obtém informação local do espaço que o rodeia através de sensores, posteriormente, uma função de transferência recebe a informação e seleciona um comportamento. Para terminar, é enviado os comandos necessários para os atuadores com base no comportamento selecionado. Assim, com o planeamento local da trajetória já não é necessário construir um mapa completo do espaço de trabalho, sendo executado com o robô em movimento [24] e com a informação obtida localmente. Este tipo de planeamento também oferece uma resposta rápida para gerar uma nova trajetória no espaço dinâmico e exige pouco processamento. Contudo, não produz uma trajetória tão eficaz como o planeamento global, não sendo adequado para tarefas mais complexas. Figura 3.3 - Arquitetura de controlo/navegação reativa. Cada uma das duas arquiteturas já apresentadas tem as suas vantagens e desvantagens, não existindo por isso uma solução ótima. Para resolver melhor o problema de navegação surgiu a arquitetura de controlo/navegação híbrida, esta é uma combinação das caraterísticas da deliberativa com a reativa, que dá origem a um planeamento da trajetória bastante robusto. Na Figura 3.4 é apresentada a estrutura mais comum para a arquitetura híbrida, sendo esta constituída por três camadas: deliberativa, controlo de execução e reativa. A camada deliberativa é responsável pela fusão sensorial, construção do mapa com a representação do espaço de trabalho e do planeamento global da trajetória. A camada de controlo de execução faz a conexão entre a camada deliberativa e a camada reativa, com a tarefa de coordenar os comportamentos, de modo a que o robô Informação Sensorial Comportamento 1 Comportamento 2 Comportamento N . . . Atuação FUNDAMENTOS TEÓRICOS 19 percorra a trajetória planeada na camada deliberativa. A camada reativa define um comportamento e envia os comandos necessários para os atuadores. Figura 3.4 - Arquitetura de controlo/navegação híbrida. O tipo de planeamento da trajetória implementado neste trabalho de dissertação é o planeamento global, sendo que os métodos e respetivos conceitos apresentados nas secções seguintes fazem parte deste tipo de planeamento. O motivo para a escolha do planeamento global da trajetória será descrito no Capítulo 5 IMPLEMENTAÇÃO . 3.1.1.2. ESPAÇO DE CONFIGURAÇÃO O primeiro passo para obter uma solução para o problema do planeamento da trajetória de um robô é, criar uma representação do espaço de trabalho no qual o robô está inserido [25]. Essa representação a que se dá o nome de espaço de configuração (EC) é aplicado em robôs manipuladores (braços robóticos) e na maioria dos robôs móveis [26]. No trabalho desenvolvido nesta dissertação, é considerado o espaço de configuração apenas para o espaço de trabalho de robôs móveis. No espaço de trabalho existem locais ocupados (obstáculos) e locais não ocupados (espaço livre) [27]. Desta forma, para planear uma trajetória, o robô e o espaço de trabalho devem ser modelados por um modelo matemático adequado. Por isso, um espaço de estados é utilizado na configuração do robô (espaço) [22]. O espaço de estados é constituído por um vetor de dimensão 𝑁, que deve descrever com precisão o estado do robô no seu ambiente. A dimensão do vetor determina o número de graus de liberdade (DOF). No caso de um robô móvel sem braço robótico, DOF corresponde ao número de parâmetros independentes necessários para especificar o movimento [22]. Assim, o espaço de estados é definido pelos parâmetros: posição e orientação do robô no espaço de trabalho. Deliberativa Controlo de Execução Reativa Atuação Informação Sensorial FUNDAMENTOS TEÓRICOS 20 No cálculo da trajetória, quanto maior o número de graus de liberdade maior é a complexidade computacional, aumentando assim exponencialmente o tempo de cálculo. Por isso, o objetivo é simplificar ao máximo o problema, de modo a aumentar a eficácia dos algoritmos. Um exemplo, é de um robô móvel sem braço robótico que pode ter no máximo seis graus de liberdade (6 DOF), definidos pela posição e orientação nos eixos coordenados 𝑥, 𝑦 e 𝑧, isto significa, que pode mover-se em qualquer direção no espaço tridimensional (3D). Para simplificar, a abordagem mais comum é considerar o movimento num espaço a duas dimensões (ver Figura 3.5 ), restringindo assim o número de graus de liberdade para três: posição do robô nas coordenadas (𝑥, 𝑦) e a orientação. Figura 3.5 - (a) Representação de um objeto ou robô no espaço de trabalho (espaço a três dimensões). (b) Espaço de configuração com o mesmo objeto ou robô (espaço a duas dimensões). Para o planeamento da trajetória geralmente assume-se que o robô é holonómico (não apresenta restrições no movimento, ou seja, pode mover-se em qualquer direção com uma qualquer orientação) [26]. A orientação pode ser assim excluída do planeamento, como também é possível assumir que o robô tem uma forma circular no espaço de configuração (ver Figura 3.6(a) ). Portanto, o robô é representado apenas pela sua posição (𝑥, 𝑦). A forma mais prática e simples na implementação dos algoritmos para o planeamento da trajetória, é representar o robô como um ponto e aumentar o tamanho dos obstáculos de acordo com o raio do robô, para obter um espaço de configuração equivalente (ver Figura 3.6(b) ) [22], [27]. Na Figura 3.6(b) é possível observar que o espaço de configuração (EC) é constituído por dois tipos de locais: 𝐸𝐶𝑜𝑏𝑠𝑡 e 𝐸𝐶𝑙𝑖𝑣𝑟𝑒. Os locais com obstáculos (𝐸𝐶𝑜𝑏𝑠𝑡) é espaço ocupado que o robô tem de evitar, enquanto que os locais não ocupados (𝐸𝐶𝑙𝑖𝑣𝑟𝑒) é espaço livre onde o ponto que representa a posição do robô se pode mover. Assim, o problema do planeamento da trajetória é, encontrar uma trajetória entre a posição atual e uma posição pretendida no espaço de configuração livre [21]. (a) (b) FUNDAMENTOS TEÓRICOS 21 Figura 3.6 – Exemplo de um espaço de configuração. (a) Representação de três obstáculos com formas diferentes (cor mais escura) e um robô com uma forma circular. (b) O mesmo espaço de (a) mas com os obstáculos e limites do espaço expandidos de acordo com o raio do robô, pois este é representado por um ponto. 𝑬𝑪𝒍𝒊𝒗𝒓𝒆 é o espaço livre e 𝑬𝑪𝒐𝒃𝒔𝒕 é o espaço ocupado por obstáculos. Esta figura é adaptada de R. Jitendra (2007) [22] e de M. Queirós (2014) [28]. 3.1.1.3. DIAGRAMA DE VORONOI Como já citado na secção ESPAÇO DE CONFIGURAÇÃO , o problema do planeamento da trajetória é, encontrar uma trajetória entre a posição atual e uma posição pretendida no espaço de configuração livre (𝐸𝐶𝑙𝑖𝑣𝑟𝑒). O espaço de configuração é um mapa que faz a representação geométrica contínua do espaço de trabalho do robô, porém, este mapa deve ser transformado num mapa discreto, adequado ao algoritmo de pesquisa da trajetória a ser implementado [21]. Uma das abordagens para obter um mapa discreto tem o nome de roadmap [27]. Esta abordagem consiste em conectar o espaço de configuração livre através de uma rede de curvas, tendo cada um dos métodos de roadmap existentes uma configuração de mapa diferente. Um desses métodos é o diagrama de Voronoi, que será descrito nesta secção. O diagrama de Voronoi é uma estrutura de geometria computacional utilizada em diversas aplicações. Este diagrama produz uma rede de curvas (ou arestas) que dão forma a possíveis trajetórias no espaço de configuração livre e que maximizam a distância entre o robô e os obstáculos [27]. No entanto, uma trajetória obtida diretamente do diagrama de Voronoi pode não ser ótima, no caso em que se pretende a trajetória mais curta, pois em alguns locais a distância pode ser longa entre os obstáculos e as arestas que compõem a trajetória [29]. Neste caso, existem estratégias/algoritmos que podem ser adicionadas a este diagrama, ou então, a implementação de outro método de roadmap , como até mesmo, a utilização de outro tipo de abordagem para obter um mapa discreto. Para uma trajetória segura, longe dos obstáculos, o diagrama de Voronoi é ótimo. 𝐸𝐶𝑙𝑖𝑣𝑟𝑒 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 𝐸𝐶𝑜𝑏𝑠𝑡 (a) (b) FUNDAMENTOS TEÓRICOS 22 Este diagrama, para um conjunto de pontos no plano, consiste na subdivisão desse plano em regiões, em que cada ponto tem uma região associada. Normalmente, estes pontos denominam-se por sítios e as regiões por regiões de Voronoi [30]. Cada região de Voronoi é um polígono convexo limitado ou ilimitado. As arestas do diagrama podem ser segmentos de reta ou semirretas. Seja 𝑆 um conjunto de 𝑛 sítios do diagrama de Voronoi 𝐷𝑉(𝑆). Uma aresta é comum a duas regiões adjacentes de dois sítios (𝑠𝑖,𝑠𝑗∈𝑆), se cada ponto da aresta é equidistante de 𝑠𝑖 e 𝑠𝑗. Assim, os pontos da aresta estão mais próximos destes dois sítios do que qualquer outro sítio de 𝐷𝑉(𝑆). Cada vértice do diagrama é equidistante de três ou mais sítios e três ou mais arestas têm um vértice em comum [31]. Qualquer ponto (ou local) dentro de uma determinada região de Voronoi, está mais próximo do sítio dessa região do que qualquer outro sítio de 𝐷𝑉(𝑆). Na Figura 3.7 é apresentado um exemplo de um diagrama de Voronoi de 14 sítios no plano. Figura 3.7 - Diagrama de Voronoi de 14 sítios (ou pontos) no plano. 3.1.1.4. TRIANGULAÇÃO DE DELAUNAY Uma triangulação de um conjunto de pontos no plano é um grafo 𝐺(𝑉,𝐸), onde os vértices 𝑉 correspondem ao conjunto de pontos e 𝐸 é o conjunto de arestas formadas por pares de vértices distintos. Um grafo de uma triangulação tem como propriedades: (a) conter um conjunto de vértices 𝑉= {𝑣1,…,𝑣𝑛}, com 𝑛≥3 vértices distintos no plano e não todos colineares e (b) as arestas não se intercetam, exceto nos extremos, ou seja, nos vértices. Portanto, podem ser adicionados pontos, desde que nenhuma aresta nova intersete numa outra aresta já existente. Com estas propriedades é garantido que cada uma das faces, exceto as externas ao grafo, é um triângulo [32], [33]. Para a construção de uma triangulação de um conjunto de pontos, existem diversas soluções possíveis. Uma triangulação muito utilizada e descrita nesta secção é a triangulação de Delaunay, pois aresta (semirreta) vértice região de Voronoi limitada aresta (segmento de reta) região de Voronoi ilimitada sítio (ou ponto) FUNDAMENTOS TEÓRICOS 23 está relacionada diretamente com o diagrama de Voronoi, existindo assim uma dualidade entre as duas estruturas. A triangulação de Delaunay de um conjunto de pontos 𝑉 é um grafo denotado por 𝑇𝐷(𝑉). Esta triangulação tem como propriedades: (a) a circunferência circunscrita a um triângulo ∆𝑣𝑖𝑣𝑗𝑣𝑘∈ 𝑇𝐷(𝑉), não contém nenhum outro vértice (ponto) de 𝑉 no seu interior, (b) uma aresta de 𝑇𝐷(𝑉) é formada por dois vértices (𝑣𝑖,𝑣𝑗∈𝑉) se, e somente se, existe uma circunferência que passa apenas por 𝑣𝑖 e 𝑣𝑗 e não contém nenhum outro vértice de 𝑉 no seu interior, e (c) o ângulo mínimo interno de cada triângulo é maximizado, de forma a aproximar-se de um triângulo equilátero [33], [34]. Na Figura 3.8 é apresentado um exemplo de uma triangulação de Delaunay de 14 pontos no plano e ainda a representação de uma circunferência circunscrita a um triângulo, sem qualquer vértice no seu interior. Figura 3.8 - Triangulação de Delaunay de 14 pontos no plano e circunferência circunscrita a um triângulo. 3.1.1.5. DUALIDADE ENTRE VORONOI E DELAUNAY A triangulação de Delaunay de um conjunto de pontos 𝑆 é o grafo dual 𝑇𝐷(𝑆) do diagrama de Voronoi 𝐷𝑉(𝑆) [33]. A Figura 3.9 ilustra a dualidade das duas estruturas. Nesta secção são apresentadas algumas propriedades sobre esta dualidade. Uma dessas propriedades é direcionada ao conjunto de pontos (no exemplo da Figura 3.9 são os pontos a preto), sendo estes comuns a 𝑇𝐷 e 𝐷𝑉, e tal como já foi mencionado nas duas secções anteriores, para 𝑇𝐷 os pontos correspondem aos vértices dos triângulos e para 𝐷𝑉 correspondem aos sítios das regiões de Voronoi. É também possível verificar que duas regiões de Voronoi adjacentes, têm os respetivos sítios conectados por uma aresta de 𝑇𝐷 [35]. FUNDAMENTOS TEÓRICOS 24 Figura 3.9 - Diagrama de Voronoi 𝑫𝑽(𝑺) e Triangulação de Delaunay 𝑻𝑫(𝑺). Na Figura 3.10 é possível observar outra propriedade, que deve ser interpretada da seguinte forma: a circunferência circunscrita a um triângulo ∆𝑣𝑖𝑣𝑗𝑣𝑘∈𝑇𝐷(𝑆), não contém nenhum outro ponto de 𝑆 no seu interior [33], e o circuncentro (centro da circunferência) corresponde a um vértice de 𝐷𝑉(𝑆). Figura 3.10 - Diagrama de Voronoi 𝑫𝑽(𝑺), Triangulação de Delaunay 𝑻𝑫(𝑺), e ainda a representação de uma circunferência circunscrita a um triângulo de 𝑻𝑫(𝑺), com o circuncentro (ponto a vermelho) a corresponder a um vértice de 𝑫𝑽(𝑺). Isto é uma das propriedades da dualidade entre 𝑻𝑫(𝑺) e 𝑫𝑽(𝑺). Os algoritmos existentes para construir um diagrama de Voronoi podem ser demorados para determinadas aplicações. Como a triangulação de Delaunay de um conjunto de pontos é o grafo dual do diagrama de Voronoi e os algoritmos existentes para construir a triangulação são menos demorados, 𝐷𝑉(𝑆) 𝑇𝐷(𝑆) 𝐷𝑉(𝑆) 𝑇𝐷(𝑆) FUNDAMENTOS TEÓRICOS 31 A representação analítica de uma curva, geralmente, é dividida por partes, isto é, uma curva como a de (b) ou (c) da Figura 3.13 pode ser constituída por uma união de pequenas curvas, pois não é possível representar analiticamente a curva completa. Esta divisão depende de alguns fatores, tais como, o número de pontos de controlo, o tipo de curva a implementar e o grau do polinómio. Posto isto, uma curva paramétrica polinomial tem para cada dimensão ou eixo coordenado, a seguinte equação: 𝑃(𝑡)=𝑐0+𝑐1𝑡+𝑐2𝑡2+⋯+𝑐𝑘𝑡𝑘 (3.1) Nesta equação ( Equação 3.1 ), 𝑐𝑘 são os coeficientes polinomiais, 𝑘 é o grau do polinómio e 𝑡 é o parâmetro supracitado, que geralmente é limitado entre 0 e 1. O grau do polinómio define se a curva é linear, quadrática, cúbica e entre outras, sendo as curvas cúbicas as mais utilizadas. Para uma curva cúbica o grau do polinómio é igual a 3, oferecendo um resultado bastante satisfatório para a maioria das aplicações, pois curvas com o grau do polinómio inferior a 3 têm uma forma pouco flexível, enquanto que as curvas com o grau do polinómio superior a 3 têm um custo computacional superior e também podem surgir oscilações no formato da curva, não sendo por isso o ideal para a maioria das aplicações. As curvas paramétricas polinomiais podem existir em qualquer espaço (dimensão). Como neste trabalho de dissertação as curvas são implementadas num espaço bidimensional (2D), será apresentada nas Equações 3.2 , 3.3 e 3.4 a forma geral de uma curva paramétrica polinomial cúbica 2D, sendo um ponto da curva para um determinado 𝑡 dado por 𝑃(𝑡)=[𝑥(𝑡)𝑦(𝑡)]. 𝑥(𝑡)=𝑐3𝑥𝑡3+𝑐2𝑥𝑡2+𝑐1𝑥𝑡+𝑐0𝑥 𝑦(𝑡)=𝑐3𝑦𝑡3+𝑐2𝑦𝑡2+𝑐1𝑦𝑡+𝑐0𝑦 (3.2) 𝑃(𝑡)=𝑇∙𝐶=[𝑡3𝑡2𝑡 1][𝑐3𝑥 𝑐3𝑦 𝑐2𝑥 𝑐2𝑦 𝑐1𝑥 𝑐1𝑦 𝑐0𝑥 𝑐0𝑦] (3.3) A matriz de coeficientes 𝐶 da Equação 3.3 é definida pela matriz base 𝑀 e pela matriz geométrica 𝐺, onde 𝐶=𝑀∙𝐺. A matriz base contém os coeficientes de alguns polinómios que definem o tipo de curva, enquanto que a matriz geométrica contém os pontos de controlo (quatro para curvas cúbicas) definidos pelo tipo de curva [40], [41], [42]. FUNDAMENTOS TEÓRICOS 32 𝑃(𝑡)=𝑇∙𝑀∙𝐺 (3.4) As curvas paramétricas polinomiais mais utilizadas são as curvas de Hermite, Bézier e B-Spline, sendo a curva de Hermite, uma curva de interpolação, e a de Bézier e B-Spline são curvas de aproximação, no entanto, a curva de Bézier cúbica faz a interpolação do primeiro e último ponto de controlo. 3.1.2. CONTROLO DO MOVIMENTO O controlo do movimento é um dos processos de navegação supracitados no atual subcapítulo NAVEGAÇÃO AUTÓNOMA . Este processo tem como objetivo, calcular os valores necessários para o controlo dos motores, de modo a que o robô ou veículo móvel autónomo percorra a trajetória obtida no processo Planeamento da Trajetória . Normalmente, o tempo que um robô demora a percorrer uma trajetória é um fator muito importante, no entanto, no caso de um robô se mover a uma velocidade excessiva para uma determinada trajetória, ou numa parte dessa trajetória, por exemplo, uma curva fechada, este pode afastar-se da trajetória pretendida e possivelmente colidir com obstáculos. Para um robô com movimento holonómico, tal como os robôs utilizados no trabalho desta dissertação, é necessário determinar valores para controlar os movimentos de translação e rotação, e também a direção do movimento de translação. Assim, existem vários movimentos possíveis para este tipo de robô, sendo por isso necessário determinar o melhor movimento ao longo de uma trajetória. Além disso, é possível que uma determinada tarefa exija um movimento específico, por exemplo, um robô que tem um objeto na sua posse e tem de percorrer a trajetória em segurança. Posto isto, uma solução para o problema de controlo do movimento é implementar o controlador PID em malha fechada. Com este controlador é possível que um sistema, no caso deste trabalho, o robô ou o conjunto de sistemas que este possui, seja levado do estado atual para o estado pretendido de modo eficaz. 3.1.2.1. SISTEMA DE CONTROLO EM MALHA FECHADA Um sistema de controlo em malha fechada, ou como também é frequentemente citado na literatura, sistema de controlo por realimentação, permite que a resposta do sistema não seja afetada por perturbações externas ou por alterações inesperadas no valor dos parâmetros do sistema [43]. Na Figura 3.14 é possível observar o diagrama de um sistema de controlo com realimentação negativa [44]. FUNDAMENTOS TEÓRICOS 33 Neste tipo de sistema de controlo, o sensor ou o conjunto de sensores medem a saída do sistema a controlar, isto é, medem a variável a controlar 𝑦. Desta forma, o controlador recebe o valor do erro, que consiste na diferença entre o valor de referência 𝑦𝑟𝑒𝑓 (valor desejado para 𝑦) e o valor medido pelo sensor 𝑦𝑓. Posteriormente, o algoritmo implementado para o controlador gera o valor da variável de comando 𝑢 que irá para o atuador, alterando assim o estado atual do sistema caso o erro seja diferente de zero. É de salientar que o atuador no diagrama apresentado faz parte do bloco Sistema a Controlar . A principal desvantagem deste sistema de controlo é na estabilidade, pois é possível existirem oscilações causadas pelo ajuste excessivo dos parâmetros do controlador. Figura 3.14 – Diagrama de um sistema de controlo com realimentação negativa. 3.1.2.2. CONTROLADOR PID O controlador PID, aplicado em sistemas de controlo em malha fechada, é bastante utilizado na indústria e noutras aplicações, por exemplo, robôs de serviços. O algoritmo deste controlador faz uma soma de três ações: Proporcional Integral Derivativa (PID) [44]. Desta forma, o algoritmo pode ser descrito pela seguinte equação: 𝑢(𝑡)=𝐾(𝑒(𝑡)+1 𝑇𝑖∫𝑒(𝜏)𝑑𝜏 𝑡 0+𝑇𝑑𝑑𝑒(𝑡) 𝑑𝑡 ) (3.5) Nesta equação e tal como apresentado na secção anterior, 𝑢 é a variável de comando e a variável 𝑒 representa o erro. 𝐾, 𝑇𝑖 e 𝑇𝑑 são parâmetros, sendo 𝐾 o ganho proporcional do controlador, 𝑇𝑖 a constante de tempo da ação integral e 𝑇𝑑 a constante de tempo da ação derivativa. De seguida, será apresentada a influência que cada uma das três ações pode ter no sistema de controlo. Ação Proporcional. Esta ação de controlo, tal como é possível verificar pela Equação 3.6 , é proporcional ao erro. Desta forma, quanto maior for o ganho 𝐾, mais rápida é a resposta do sistema a Controlador Sistema a Controlar Sensor 𝑒 − + 𝑢 𝑦 𝑦𝑟𝑒𝑓 𝑦𝑓 FUNDAMENTOS TEÓRICOS 34 controlar e o erro em regime permanente diminui. No entanto, um ganho muito elevado pode aumentar a oscilação da resposta do sistema e com isso demorar mais tempo a estabilizar no valor pretendido para este. 𝑢(𝑡)=𝐾 𝑒(𝑡) (3.6) Ação Integral. Esta ação permite eliminar o error em regime permanente, pois só com a ação proporcional, geralmente, não é possível eliminá-lo. Na Equação 3.7 é possível verificar que esta ação consiste no cálculo integral do erro ao longo do tempo. Isso leva a que o valor do erro seja somado. Desta forma, enquanto o valor do erro for diferente de zero, o valor da ação integral irá aumentar ao longo do tempo, até que o erro em regime permanente seja zero. A constante de tempo 𝑇𝑖 tem impacto na estabilidade e no tempo de resposta do sistema. Assim, para um valor baixo desta constante, mais rápida será a resposta. No entanto, como desvantagem, a oscilação aumenta e com isso o tempo que o sistema demora a estabilizar no valor de referência pretendido também aumenta. Por outro lado, quando a constante tende para um valor elevado, a resposta será mais lenta e com menos oscilação. 𝑢(𝑡)=𝐾(1 𝑇𝑖∫𝑒(𝜏)𝑑𝜏 𝑡 0) (3.7) A ação integral, na prática, não é implementada isoladamente, sendo acompanhada pela ação proporcional que dá origem a um controlador PI, ou então pode ser adicionada também a ação derivativa, para criar um controlador PID. Para o controlador PI a variável de comando tem a seguinte equação: 𝑢(𝑡)=𝐾(𝑒(𝑡)+1 𝑇𝑖∫𝑒(𝜏)𝑑𝜏 𝑡 0) (3.8) Ação Derivativa. Esta ação melhora a estabilidade e diminui o tempo de resposta do sistema. Na Equação 3.9 é possível verificar que esta ação consiste no cálculo da derivada do erro ao longo do tempo. Desta forma, a variável de comando tem um controlo mais previsível, sendo mais rápida a resposta do sistema para uma alteração no valor desta variável. A constante de tempo 𝑇𝑑 tem impacto no ajuste desta ação de controlo. Assim, para um valor elevado desta constante, mais rápida será a resposta do sistema para uma alteração no valor da variável de comando. No entanto, como desvantagem, o sistema pode ficar instável se o valor do erro oscilar muito num curto espaço de tempo. FUNDAMENTOS TEÓRICOS 35 𝑢(𝑡)=𝐾(𝑇𝑑𝑑𝑒(𝑡) 𝑑𝑡 ) (3.9) Tal como a ação integral, na prática, a ação derivativa não é implementada isoladamente, sendo acompanhada pela ação proporcional que dá origem a um controlador PD, ou então adicionar ainda a ação integral, para criar um controlador PID. 3.1.2.3. CONTROLADOR PID DIGITAL Na secção anterior foi apresentado o controlador PID analógico ou contínuo, tendo sido este algoritmo implementado inicialmente para o controlo de diversos sistemas. Contudo, com o desenvolvimento dos microprocessadores e microcontroladores, onde sistemas conectados a estes funcionam por amostragem, surgiu a necessidade de adaptar este algoritmo para a forma discreta. Posto isto, o algoritmo para o controlador PID na forma discreta ou digital, pode ser descrito pela seguinte equação: 𝑢(𝑡𝑛)=𝑃(𝑡𝑛)+𝐼(𝑡𝑛)+𝐷(𝑡𝑛) (3.10) Nesta equação, 𝑡𝑛 representa o momento em que é feita a amostragem, sendo apresentadas nas Equações 3.11 , 3.12 e 3.14 as três ações deste controlador na forma discreta. Assim, a ação proporcional pode ser descrita pela Equação 3.11 , sendo que 𝐾𝑝, denominado ganho proporcional , é equivalente ao 𝐾 apresentado no PID contínuo. 𝑃(𝑡𝑛)=𝐾𝑝 𝑒(𝑡𝑛) (3.11) Na Equação 3.12 é possível verificar a ação integral na forma discreta, sendo que esta equação recursiva consiste em multiplicar o erro no instante de tempo 𝑡𝑛, pelo ganho integral 𝐾𝑖 e pelo tempo 𝑇 entre amostras, ou seja, o tempo entre 𝑡𝑛−1 e 𝑡𝑛. Ao valor desta multiplicação é somado o valor da ação integral obtido em 𝑡𝑛−1. 𝐼(𝑡𝑛)=𝐼(𝑡𝑛−1)+𝐾𝑖 𝑇 𝑒(𝑡𝑛) (3.12) O ganho integral é descrito pela seguinte equação: 𝐾𝑖=𝐾 𝑇𝑖 (3.13) FUNDAMENTOS TEÓRICOS 36 A ação derivativa na forma discreta é dada pela Equação 3.14 . Tal como é possível verificar, o ganho derivativo 𝐾𝑑 é multiplicado pelo valor da diferença entre o erro nos instantes 𝑡𝑛 e 𝑡𝑛−1. O valor desta multiplicação é dividido pelo tempo 𝑇 entre amostras. 𝐷(𝑡𝑛)=𝐾𝑑 𝑒(𝑡𝑛)−𝑒(𝑡𝑛−1) 𝑇 (3.14) O ganho derivativo é descrito pela seguinte equação: 𝐾𝑑=𝐾 𝑇𝑑 (3.15) 3.2. ROBOT OPERATING SYSTEM O Robot Operating System (ROS) é uma framework open-source que atualmente é bastante utilizada na área da robótica [45]. Qualquer aplicação robótica engloba um conjunto de diferentes tarefas. O trabalho em equipa e o desenvolvimento de módulos individuais para cada uma das tarefas, pode tornar-se num processo muito difícil, devido à complexidade de algumas aplicações robóticas. Foi por este motivo que surgiu o ROS, que contribui significativamente para o desenvolvimento de plataformas robóticas, pois tem a vantagem de simplificar a comunicação entre módulos e desenvolver software robusto. O objetivo do ROS, é incentivar o desenvolvimento colaborativo de software para aplicações robóticas [45]. Por exemplo, um laboratório tem um grupo de programadores que são especialistas em mapeamento de ambientes e contribuem com o software para ser integrado num robô de auxílio em tarefas hospitalares. Outro grupo domina visão por computador e desenvolve um software para a deteção de obstáculos para o mesmo robô. Desta forma, o ROS promove a reutilização de software , ou seja, os módulos de software desenvolvidos para um robô de auxílio em tarefas hospitalares podem ser integrados em diferentes plataformas robóticas. Com este conceito de reutilização e com ajuda de muitos colaboradores, são criadas bibliotecas em áreas como a navegação, visão por computador, simulação, perceção e controlo. O ROS foi desenvolvido em diversas instituições e para diversos robôs. No ano 2000, a Universidade de Stanford, com dois projetos envolvendo inteligência artificial, criou sistemas de software dinâmicos com a intenção de os usar em robôs. Em 2007, o laboratório de investigação robótica Willow FUNDAMENTOS TEÓRICOS 37 Garage, deu continuidade ao desenvolvimento do ROS, com a criação de pacotes de software já testados em robôs [45]. Apesar do seu nome, o Robot Operating System (ROS) não é um sistema operativo convencional, mas sim uma framework . Contudo, este fornece alguns serviços de um sistema operativo [46], que são: a abstração de hardware , comunicação entre processos, controlo de baixo nível e gestão de pacotes. 3.2.1. ARQUITETURA ROS A arquitetura do ROS é baseada em nós, sendo que um nó é um processo que executa uma tarefa para a qual foi criado. Uma aplicação robótica que é constituída por um conjunto de tarefas e usa o ROS, contém um conjunto de nós. Esta abordagem permite: (a) um software modular, (b) se existir algum problema com um dos nós ou “desativar” propositadamente um nó, o programa pode continuar a ser executado, pois os restantes nós são individuais e (c) a complexidade do software é menor em comparação com outras estruturas. O ROS cria internamente uma rede, em que os nós estão conectados diretamente a outros nós. A rede é configurada pelo ROS Master , que permite aos nós se localizarem entre eles. Sem o Master , não é possível a comunicação entre os nós. O protocolo normalmente usado para a comunicação é chamado TCPROS, que assegura a gestão de mensagens e serviços ROS. Este protocolo usa sockets TCP/IP. A comunicação entre os nós pode ser feita por duas formas distintas: mensagens e serviços. Uma mensagem é uma estrutura de dados, que contém uma ou mais “variáveis” de diferentes tipos de dados (char, int, float, bool, entre outros). Para a gestão da troca de mensagens entre os nós, existem os tópicos. Os tópicos oferecem uma comunicação unidirecional, onde os nós podem publicar ou subscrever as mensagens. Isto é, um nó se enviar uma mensagem, está a publicar no tópico, por outro lado, se um nó subscrever um ou mais tópicos, recebe as mensagens que circulam no(s) tópico(s) que subscreveu. É também de salientar que vários nós podem publicar e subscrever num único tópico, e um nó pode publicar em vários tópicos. Os serviços oferecem uma comunicação bidirecional entre dois nós para a troca de mensagens, usando o paradigma pedido/resposta entre cliente/servidor. Este tipo de comunicação funciona da seguinte forma: o nó cliente envia um pedido ao nó servidor através de uma mensagem e aguarda pela resposta do nó servidor, que irá enviar uma ou mais mensagens. As mensagens trocadas entre os nós, são definidas na configuração do serviço. Na Figura 3.15 é possível observar a arquitetura de um exemplo de uma rede ROS. FUNDAMENTOS TEÓRICOS 38 Figura 3.15 – Exemplo de uma rede ROS. Nó Tópico Nó Nó Tópico Publica Subscreve Publica Publica Subscreve Serviço ROS Master 39 Capítulo 4 MINHO TEAM Conforme mencionado na secção 1.1.3 do Capítulo 1 , a equipa Minho Team tem participado ativamente na Middle Size League (MSL), em eventos nacionais e internacionais. A primeira participação no RoboCup foi em 1999, sendo uma das primeiras equipas a surgir nesta prova, contribuindo ao longo destes anos para a evolução do estado da arte desta competição. A equipa desde que iniciou a sua atividade, em 1998, tem desenvolvido várias versões de robôs, de modo a acompanhar a constante evolução tecnológica e, consequentemente, melhorar o desempenho para competir ao mais alto nível na MSL. A plataforma anterior, desenvolvida em 2011, não tinha a estrutura mecânica muito estável e também existiam alguns problemas com o hardware , que não era muito eficiente e tinha algumas falhas intermitentes. Por isso, a equipa decidiu reconstruir e melhorar a plataforma, sendo que todo o processo de reconstrução foi desenvolvido no Laboratório de Automação e Robótica (LAR) da Universidade do Minho [47]. Foi também desenvolvido todo o software e implementado novos algoritmos. Neste capítulo será apresentada a estrutura mecânica da plataforma após a sua reconstrução. Também será apresentada a nova arquitetura de hardware , sendo que alguns componentes da plataforma anterior foram reaproveitados. Posteriormente, será feita uma breve descrição da arquitetura de software implementada nos robôs, e por último, será apresentado o simulador da Minho Team. Os subcapítulos ESTRUTURA MECÂNICA , HARDWARE e ARQUITETURA DE SOFTWARE serão descritos apenas para um único robô, uma vez que os outros são uma cópia dele, exceto o guarda-redes que tem algumas partes diferentes. 4.1. ESTRUTURA MECÂNICA Na MSL existem regras para as dimensões, peso e cor dos robôs, porém não é exigido qualquer formato para a estrutura mecânica. Por este motivo, a estrutura desenvolvida por cada uma das equipas é variável, sendo as formas circular, triangular e quadrada as mais usadas para a base dos robôs. Na Minho Team a base da plataforma atual é circular com 50 cm de diâmetro, que desta forma cumpre o limite máximo de 52 cm × 52 cm determinado pelas regras. É na base que estão incorporados os MINHO TEAM 40 atuadores, tais como: motores para a locomoção, chuto eletromagnético e o sistema de manipulação de bola ou dribbler . A manipulação da bola e o chuto são ações executadas por dois sistemas independentes. De seguida, será apresentada a mecânica, ou mecanismos, destes dois sistemas, sendo que na secção seguinte será apresentado o hardware incluído nestes mesmos sistemas. O sistema de manipulação de bola tem como objetivos reter e driblar a bola de forma a mantê-la na posse do robô (ver Figura 4.1(g) ) e, ao mesmo tempo, exercer movimento na bola, respeitando assim a regra que não permite o bloqueio da bola quando esta se encontra na posse do robô. O mecanismo e o hardware deste sistema, integrados na plataforma anterior, foram substituídos, permitindo ao robô mover-se em qualquer direção com uma qualquer orientação sem perder a bola. O novo mecanismo (ver Figura 4.1(f) ) é um protótipo com uma estrutura idêntica a outras equipas, sendo constituído por dois braços de controlo e duas rodas com dois pneus de borracha que oferecem a fricção necessária para reter a bola. O sistema de chuto é fundamental para efetuar o passe e a marcação de golos. Na plataforma atual, este sistema contém um mecanismo em forma de alavanca (ver Figura 4.1(e) ) que impulsiona a bola, sendo esta alavanca impulsionada com pouca força para efetuar um passe ou com bastante força para fazer a bola descrever uma trajetória parabólica. Na secção 4.2.1.1 CHUTO ELETROMAGNÉTICO será apresentado todo o hardware responsável pelo impulso na alavanca. No que diz respeito ao sistema de visão utilizado pelos robôs da Minho Team, exceto o guardaredes, este é semelhante a todas as outras equipas, sendo um sistema de visão omnidirecional catadióptrico (ver Figura 4.1(b) ), que consiste na utilização de uma câmara a apontar para o centro de um espelho convexo [48]. Para adquirir uma imagem com uma qualidade razoável, sem deformações, é necessário um suporte capaz de ajustar a distância entre a câmara e o espelho, como também ajustar o alinhamento entre o centro da câmara e o centro do espelho. No trabalho desenvolvido pelo elemento da equipa André Pereira, no sistema de visão, este optou por desenvolver um novo suporte, uma vez que o da plataforma anterior não oferecia a possibilidade de ajustar a distância pretendida e também não era possível ajustar o centro da câmara com o espelho. Para obter a maior área de visão possível, o suporte com a câmara e o espelho é fixado a uma torre instalada no centro da base do robô que, desta forma, posiciona o sistema de visão no topo do robô. Porém, a altura a que este fica é limitada pela altura máxima da plataforma, que de acordo com as regras é de 80 cm. MINHO TEAM 47 sendo o cliente um widget Qt responsável por fazer a interface entre o Qt e o Gazebo (servidor), isto de forma a possibilitar a interação do utilizador com o espaço simulado e oferecer uma melhor performance. O ambiente e toda a dinâmica de simulação é a três dimensões. Na Figura 4.6 é possível observar a interface gráfica do simulador para a MSL e o espaço de jogo em duas perspetivas diferentes. Através de movimentos e cliques do rato, é possível ao utilizador alterar a perspetiva de visualização do espaço e manipular os modelos (robôs, bola, entre outros) existentes no espaço de simulação. Figura 4.6 – Interface gráfica do simulador para a MSL e o espaço de jogo em duas perspetivas diferentes. 48 Capítulo 5 IMPLEMENTAÇÃO Este capítulo descreve todos os detalhes da implementação deste trabalho de dissertação. O primeiro subcapítulo 5.1 PLANEAMENTO DA TRAJETÓRIA , descreve todos os passos para obter a melhor trajetória, sendo que o segundo subcapítulo 5.2 CONTROLO DO MOVIMENTO , descreve todo o processo para obter os valores a enviar para a placa de controlo dos motores. Antes de iniciar a descrição dos dois processos supracitados, será apresentada a linguagem de programação usada, as ferramentas de apoio para o desenvolvimento deste trabalho, a visão geral do nó Controlo da rede ROS de um robô da Minho Team, as bibliotecas utilizadas no desenvolvimento deste trabalho, e para finalizar será apresentada a visão geral do sistema de controlo de movimento, desenvolvido neste trabalho. Linguagem de Programação. O software desenvolvido no trabalho desta dissertação, foi implementado com a linguagem de programação C++, tal como o software dos restantes processos (exceto Controlo do Hardware ), que constituem a arquitetura de software de um robô da Minho Team. A ferramenta desenvolvida para configuração, que será apresentada posteriormente neste capítulo, foi desenvolvida em Qt5. Ferramenta de Simulação. Para testar todo o software foi utilizado, inicialmente, o simulador da Minho Team, mencionado no subcapítulo 4.4 SIMULADOR . Esta ferramenta tem várias vantagens em relação aos robôs reais, uma delas é o tempo, pois é possível testar várias vezes em diversas situações num curto espaço de tempo. Outra vantagem é a possibilidade de utilizar menos vezes as baterias dos robôs e assim aumentar a vida útil destas. Pelo facto de a equipa não ter baterias suplentes, dificulta o teste com os robôs reais, sendo este, outro motivo, para a utilização do simulador. O software usado num robô real, para ser testado no simulador, exige apenas a calibração de alguns parâmetros que serão mencionados neste capítulo. Ferramenta de Configuração. Esta ferramenta foi desenvolvida para ser utilizada no computador pessoal dos elementos da equipa, pois o ROS permite a comunicação entre diferentes computadores IMPLEMENTAÇÃO 49 que estejam na mesma rede ROS, ou seja, é possível ter uma rede ROS com vários nós em diferentes computadores, desde que todos os nós comuniquem com o Master dessa rede. Desta forma, esta ferramenta de configuração é um nó que comunica com o Master da rede ROS de um robô real ou de um robô simulado, tendo cada robô real ou simulado uma rede ROS e o respetivo Master . Relativamente às funcionalidades desta ferramenta de configuração (ver Figura 5.1 ), esta permite para cada robô, ajustar os ganhos dos controladores PID das velocidades linear e angular, e ajustar as velocidades máximas linear e angular. Para efetuar alguns testes é possível definir a posição e orientação pretendida para o robô, definir a posição (x, y) pretendida para a bola, selecionar entre fazer um passe ou um remate, e definir a força aplicada pelo chuto na bola. Por último, é disponibilizado uma série de botões, que permitem selecionar a informação a enviar do nó Controlo para a ferramenta de visualização, que será apresentada de seguida. Figura 5.1 – Ferramenta de configuração. Ferramenta de Visualização. Esta ferramenta, denominada visualizer , permite visualizar em 2D toda a informação adquirida por um robô do espaço de jogo, tal como, a sua posição e orientação, posição da bola, posições de possíveis obstáculos e entre outras informações. Na Figura 5.2 é possível observar o visualizer , onde o robô é representado pela forma com a cor ciano, os obstáculos pelos círculos a preto e a bola pelo círculo ou ponto laranja. O visualizer foi também uma ferramenta fundamental para o desenvolvimento do processo de planeamento da trajetória, pois permite a visualização de todos os passos deste processo. Tal como a ferramenta de configuração, esta também é um nó ROS. IMPLEMENTAÇÃO 50 Figura 5.2 - Ferramenta de visualização ou visualizer . Nó Controlo . O nó Controlo é responsável pelos dois processos Planeamento da Trajetória e Controlo do Movimento . Este nó, tal como os outros nós da rede ROS de um robô da Minho Team, subscreve e publica mensagens através de tópicos ROS, e envia/recebe mensagens através de serviços ROS. Uma explicação mais detalhada sobre o ROS é apresentada no subcapítulo 3.2 . Na Figura 5.3 é possível observar todas as mensagens que o nó Controlo publica e subscreve, e que envia/recebe. Agora é apresentada uma breve descrição de cada mensagem: • robotInfo: contém informação sobre o espaço de jogo, tal como a posição (x, y) e orientação do robô, velocidade do robô e da bola, posições de possíveis obstáculos, posição da bola, uma variável que indica se o robô vê a bola e outra variável que indica se o robô tem a bola; • controlInfo: o nó Controlo é o único nó a publicar esta mensagem, que contém os valores para as velocidades linear e angular e a direção do movimento de translação do robô, sendo estes valores obtidos no processo Controlo do Movimento . Esta mensagem contém também uma variável para o controlo on/off do dribbler ; • controlConfig: esta é a única mensagem que o nó Controlo recebe através de um serviço ROS, sendo enviada pelo nó responsável pela ferramenta de configuração. A mensagem contém os valores dos ganhos dos controladores PID para as velocidades linear e angular, os valores das velocidades máximas linear e angular, e um conjunto de variáveis que permitem selecionar a informação a enviar do nó Controlo para o visualizer . O nó da ferramenta de configuração IMPLEMENTAÇÃO 51 também recebe uma mensagem, que é enviada apenas uma vez pelo nó Controlo no momento da inicialização do programa, sendo que esta mensagem contém os valores dos ganhos e das velocidades máximas, que se encontram guardados num ficheiro. Quando é feita alguma alteração destes valores pela ferramenta de configuração, estes são guardados/atualizados no ficheiro; • pathData: contém a informação obtida nos passos do processo Planeamento da Trajetória , sendo esta mensagem publicada apenas pelo nó Controlo e subscrita apenas pelo visualizer , isto é, o nó desta ferramenta de visualização é o único nó a subscrever o tópico desta mensagem; Figura 5.3 – Mensagens que o nó Controlo publica e subscreve, e que envia/recebe. Nó Controlo . pose robot_pose velocity robot_velocity pose ball_position velocity ball_velocity bool has_ball bool sees_ball obstacle[] obstacles interestPoint[] interest_points robotInfo . uint8 role uint8 action pose target_pose position target_kick bool target_kick_is_pass uint8 target_kick_strength aiInfo . uint8 max_linear_velocity uint8 max_angular_velocity float32 Kp_rot float32 Ki_rot float32 Kd_rot float32 Kp_lin float32 Ki_lin float32 Kd_lin bool send_voronoi_seg bool send_intersect_seg bool send_dijk_path bool send_dijk_path_obst_circle bool send_smooth_path bool send_smooth_path_obst_circle bool send_path bool send_path_interpolation bool send_obstacles_circle controlConfig . segment[] voronoi_seg segment[] intersect_seg position[] dijk_path position[] dijk_path_obst_circle position[] smooth_path position[] smooth_path_obst_circle position[] path position[] path_interpolation float32[] obstacles_circle pathData . uint8 linear_velocity int8 angular_velocity uint16 movement_direction bool dribbler_on bool is_teleop controlInfo Serviço: requestControlConfig . Nó: control_calib Mensagem: controlConfig Publica: pathData Publica: controlInfo Subscreve: robotInfo Subscreve: aiInfo ROS Master IMPLEMENTAÇÃO 52 • aiInfo: o nó Controlo subscreve esta mensagem, que contém informação que deve ser executada pelo robô, tal como o seu papel (defesa, avançado ou entre outros), a ação ( stop , slow , engage ball , fast move ou entre outras), a posição e orientação pretendida, a posição (x, y) pretendida para a bola, uma variável que indica se o robô deve fazer um passe ou um remate, e a força aplicada pelo chuto na bola. Esta mensagem é publicada pelo nó Inteligência Artificial ou pelo nó da ferramenta de configuração no caso de um teste (este último nó não define o papel a ser executado pelo robô). CGAL. A Computational Geometry Algorithms Library (CGAL) [51] é uma biblioteca em C++ de estruturas de dados e algoritmos de geometria computacional. Em 1995, um grupo de universidades e centros de investigação iniciaram o desenvolvimento da CGAL, com o objetivo de disponibilizar gratuitamente algoritmos geométricos eficientes, flexíveis e robustos [52]. Esta biblioteca é aplicada em diversas áreas, tais como, a robótica, visão por computador, sistemas de informação geográfica, design assistido por computador, biologia molecular, imagens médicas e computação gráfica. A biblioteca CGAL é constituída por um núcleo geométrico ou kernel , pela biblioteca básica e por uma biblioteca de suporte . O kernel contém objetos geométricos não modificáveis, tais como, ponto, segmento, linha, raio, retângulo orientado e entre outros. Para estes objetos existem dois conjuntos de funções, um denominado predicates e o outro constructions . As funções de predicates permitem testar se um ponto está no interior de um círculo ou de uma esfera, comparar distâncias entre objetos e entre outras funções em que o tipo de dados de retorno é bool (verdadeiro ou falso) ou enum (enumeração). Por outro lado, as funções de constructions permitem transformações geométricas, calcular e detetar uma interseção entre objetos, calcular distâncias, entre outras funções. Esta biblioteca oferece diversos modelos de kernel , que permitem optar por uma implementação com resultados exatos ou por uma implementação onde a velocidade para obter resultados é mais importante. A biblioteca básica é constituída por várias estruturas de dados e por vários algoritmos, sendo implementados neste trabalho a triangulação de Delaunay ( 2D Triangulation ), o diagrama de Voronoi ( 2D Voronoi Diagram Adaptor ) e arranjos ( 2D Arrangements ). No que diz respeito à biblioteca de suporte, esta contém estruturas de dados não geométricas para a interface com algoritmos de outras bibliotecas, tipos de números, I/O para depuração e para a interface com várias ferramentas de visualização. IMPLEMENTAÇÃO 53 Sistema de Controlo de Movimento. O sistema de controlo de movimento implementado neste trabalho (ver Figura 5.4 ) é constituído pelos dois processos já mencionados Planeamento da Trajetória e Controlo do Movimento , sendo o nó Controlo responsável por integrar estes dois processos na rede ROS de um robô da Minho Team. A comunicação entre estes dois processos é feita diretamente, sendo enviado do processo Planeamento da Trajetória para o processo Controlo do Movimento , um vetor de posições com a trajetória obtida no primeiro processo. Nos próximos dois subcapítulos 5.1 e 5.2 serão apresentados todos os detalhes da implementação destes dois processos. Figura 5.4 - Visão geral do sistema de controlo de movimento. 5.1. PLANEAMENTO DA TRAJETÓRIA O primeiro passo para a implementação deste processo, foi a análise do espaço de trabalho onde o robô se encontra e o conhecimento que o robô tem sobre o espaço de trabalho. Após esta análise foi feita a escolha do tipo de planeamento da trajetória e dos métodos associados ao tipo de planeamento escolhido. A estes métodos são adicionadas algumas estratégias/algoritmos, criando um modelo de planeamento da trajetória eficiente e robusto. Tal como já foi mencionado em capítulos anteriores, o espaço de trabalho ou de jogo da MSL é extramente dinâmico, onde os robôs deslocam-se a velocidades elevadas, por vezes atingindo os 4 m/s. Isto significa que no espaço de jogo existem obstáculos dinâmicos, sendo estes obstáculos, robôs adversários e robôs cooperativos (robôs da Minho Team). Na MSL, cada robô possui o seu sistema de visão e alguns sensores para a perceção do espaço de jogo á sua volta, não existindo uma observação total deste espaço, tornando assim tudo mais complexo. Desta forma, o hardware de um robô não permite um conhecimento completo do espaço de jogo, sendo por isso, um espaço parcialmente conhecido. Para obter um conhecimento completo do espaço de jogo, as equipas, normalmente, fazem a fusão da informação obtida de todos os robôs da equipa. Essa informação, geralmente, é constituída pela posição (x, y) de cada robô, as posições de Nó Controlo Planeamento da Trajetória Controlo do Movimento Trajetória IMPLEMENTAÇÃO 54 possíveis obstáculos percebidos por cada robô, a posição da bola, e as velocidades dos robôs adversários e da bola. A fusão de toda esta informação permite obter uma representação total do espaço de jogo com excelente precisão. A Minho Team também faz a fusão da informação, exceto das velocidades dos robôs adversários, tendo por isso de momento uma representação do espaço de jogo com pouca precisão em relação a outras equipas. Após esta análise foi escolhido o tipo de planeamento da trajetória a ser implementado nos robôs. De acordo com o que foi apresentado na secção 3.1.1.1 do Capítulo 3 , existem três tipos: global, local e a combinação dos dois (global e local). O planeamento local, sendo adequado para espaços dinâmicos e totalmente desconhecidos, não produz uma trajetória muito eficaz em relação ao planeamento global. Por isso, visto que é possível através da fusão da informação obter um espaço totalmente conhecido, mesmo com pouca precisão, o planeamento global foi, desta forma, o tipo de planeamento escolhido. O planeamento global e local, ou seja, a combinação dos dois, seria teoricamente a melhor opção, mas com os métodos escolhidos, associados ao planeamento global, e com as estratégias adicionadas a estes métodos, o planeamento da trajetória desenvolvido também se revela eficiente e robusto. O modelo de planeamento da trajetória desenvolvido neste trabalho é semelhante ao da equipa Tech United Eindhoven, apresentado no Capítulo 2 . Relativamente ao modo que o planeamento da trajetória é implementado, este pode ser centralizado ou descentralizado. Tal como já foi mencionado no subcapítulo 2.4 DISCUSSÃO DO ESTADO DA ARTE , todas as equipas da MSL, incluindo a Minho Team, usam o planeamento descentralizado. Isto significa que cada robô da Minho Team, ou de qualquer outra equipa, faz o planeamento da sua trajetória. Por isso, todos os passos que serão apresentados de seguida são para o planeamento da trajetória de um único robô, sendo igual para os restantes. Posto isto, a trajetória planeada deve permitir ao robô deslocar-se da posição atual para a posição pretendida, evitando colisões com possíveis obstáculos. Além disso, a trajetória tem um determinado custo que deve ser minimizado. Neste trabalho o custo é dividido entre encontrar a trajetória mais curta e a mais suave. 5.1.1. ESPAÇO DE CONFIGURAÇÃO A representação ou espaço de configuração do espaço de jogo da MSL é simples, pois trata-se de um espaço com robôs móveis sem braço robótico que se deslocam no plano (x, y). No planeamento da trajetória, a orientação do robô não é considerada pelo facto do robô ter um movimento holonómico, sendo o robô representado apenas pela sua posição no plano (x, y). O formato usado para representar IMPLEMENTAÇÃO 55 os obstáculos (robôs adversários e robôs cooperativos) no espaço de configuração é circular, pois é o mesmo formato da base dos robôs da Minho Team e o mais próximo das outras equipas, sendo as formas circular, triangular e quadrada as mais usadas por estas. Assim, o formato circular com o diâmetro configurável permite a melhor aproximação a todos os formatos, sendo também o mais adequado para as estratégias e os métodos implementados no planeamento da trajetória, tal como se poderá verificar posteriormente. A posição (x, y) de cada obstáculo fica situada, como é óbvio, no centro do respetivo círculo. Na discretização do espaço de configuração, que será apresentada na secção 5.1.3 , não será considerada para o espaço de configuração qualquer área circular para os obstáculos, mas apenas os pontos, ou seja, as posições destes. No entanto, neste passo, estes serão representados no visualizer pela área circular da base, apenas para ser mais representativo, pois não será usada qualquer área no algoritmo deste passo. Nos restantes passos do planeamento, incluindo a TRAJETÓRIA RETILÍNEA , cada obstáculo será representado no espaço de configuração por uma área circular com diâmetro configurável ou pela sua posição se o diâmetro da área for igual a zero. Esta área denominada área do obstáculo será explicada posteriormente. Relativamente à representação no visualizer , cada obstáculo será representado pela área circular da base e pela área do obstáculo. No que diz respeito ao robô e tal como já foi mencionado, este será representado no espaço de configuração pela sua posição e no visualizer pela área circular da base. Posto isto, o espaço de configuração (EC), tal como é possível observar pela Figura 5.5 , é constituído por dois tipos de locais: 𝐸𝐶𝑜𝑏𝑠𝑡 e 𝐸𝐶𝑙𝑖𝑣𝑟𝑒. Figura 5.5 - Espaço de configuração do espaço de jogo. Os círculos a preto representam a área da base dos obstáculos e a circunferência em cada obstáculo, representa a área do obstáculo. O robô é representado nesta ferramenta de visualização pela forma com a cor ciano. IMPLEMENTAÇÃO 56 A área do obstáculo de todos os obstáculos (𝐸𝐶𝑜𝑏𝑠𝑡) é espaço ocupado que o robô tem de evitar, enquanto que os locais não ocupados por obstáculos (𝐸𝐶𝑙𝑖𝑣𝑟𝑒) é espaço livre onde o robô pode moverse. Assim, o problema do planeamento da trajetória é encontrar a melhor trajetória entre a posição atual e uma posição pretendida no espaço de configuração livre (𝐸𝐶𝑙𝑖𝑣𝑟𝑒). 5.1.2. TRAJETÓRIA RETILÍNEA A trajetória retilínea é obtida quando não existem obstáculos a intersetarem com a linha reta entre a posição atual do robô e a posição pretendida para o mesmo, e quando o diâmetro da área do obstáculo, de todos os obstáculos, for superior a duas vezes o diâmetro da área circular da base. Quando existe esta trajetória, os próximos passos do planeamento apresentados de seguida, não são executados, sendo esta a trajetória final. Por outro lado, quando existem obstáculos na linha reta entre as duas posições, não existe trajetória retilínea e os próximos passos do planeamento são executados de forma a obter a melhor trajetória. Na Figura 5.6 é possível observar a trajetória retilínea para o exemplo do espaço de configuração apresentado. Figura 5.6 – Trajetória retilínea representada pelo segmento de reta azul escuro. 5.1.3. DISCRETIZAÇÃO DO ESPAÇO DE CONFIGURAÇÃO O espaço de configuração, consiste num mapa que faz a representação geométrica contínua do espaço de jogo. Este mapa é transformado num mapa discreto de forma a ser possível implementar o algoritmo escolhido para a pesquisa da trajetória. Para obter o mapa discreto foi implementado o IMPLEMENTAÇÃO 63 obtida da mesma forma como apresentado na secção 3.1.1.6 e guardada numa variável, que será utilizada no próximo passo do planeamento da trajetória. Figura 5.12 – Tipo de abordagem de conexão entre uma posição e o diagrama de Voronoi. As linhas vermelhas (a) e (b) representam o método usado nesta abordagem. Na Figura 5.14 é possível observar a trajetória mais curta para o exemplo do espaço de configuração apresentado. Figura 5.13 – Espaço de configuração igual ao da Figura 5.14 , sem a representação da trajetória mais curta. No modelo de planeamento da trajetória apresentado até ao momento, é possível que em algumas situações não exista qualquer trajetória entre a posição atual do robô e a posição pretendida para o mesmo. Isto pode acontecer, se não existir uma sequência de vértices entre estas duas posições. Na (a) (b) IMPLEMENTAÇÃO 64 Figura 5.15 é possível observar um exemplo deste problema, sendo que o posicionamento dos três obstáculos mais próximos do ponto laranja (posição pretendida para o robô) e as respetivas áreas, não permitem qualquer conexão do ponto com o diagrama de Voronoi. Figura 5.14 – Trajetória mais curta entre a posição atual do robô e a posição pretendida para o mesmo, representada pelos segmentos de reta azuis. Este tipo de problema foi resolvido com a diminuição do diâmetro da área do obstáculo, de alguns ou de todos os obstáculos existentes no espaço de jogo, ou caso não seja suficiente, pode ser excluída a área, sendo os obstáculos representados no espaço de configuração pelas suas posições. Isto é feito, se a função de pesquisa da trajetória mais curta, após ser executada, não retornar uma sequência de vértices da trajetória mais curta. Esta abordagem é apresentada no fluxograma da Figura 5.16 . Figura 5.15 – Exemplo de um problema do modelo de planeamento da trajetória apresentado até ao momento. IMPLEMENTAÇÃO 65 Através da análise do fluxograma, possibilita perceber que após a diminuição do diâmetro da área, é feita novamente a pesquisa pela trajetória mais curta. Como a diminuição do diâmetro é feita de forma progressiva, o ciclo é repetido até existir uma trajetória. Assim, a função Calcular o Diâmetro da Área de Cada Obstáculo atribui o diâmetro inicial para a área do obstáculo, posteriormente e se necessário, diminui o diâmetro. Esta função permite também outras funcionalidades que serão apresentadas posteriormente. Figura 5.16 - Fluxograma que permite diminuir a área de cada obstáculo. Na Figura 5.17(a) é possível observar o resultado obtido após o algoritmo apresentado ser executado, neste caso, para o exemplo da Figura 5.15 . O mesmo resultado, mas com a representação da trajetória mais curta, é apresentado na Figura 5.17(b) . Através da análise das figuras 5.15 e 5.17 , é possível perceber que foi diminuída a área do obstáculo, apenas para os robôs adversários, pois o algoritmo verifica se existem obstáculos com o diâmetro da área do obstáculo superior a duas vezes o diâmetro da área circular da base. Esta é a primeira condição deste algoritmo, se não for suficiente, será diminuído ainda mais o diâmetro para todos os obstáculos, até existir uma trajetória. É de salientar que Início Não Fim Sim Calcular o Diâmetro da Área de Cada Obstáculo Pesquisa Pela Trajetória Mais Curta Existe Trajetória ? Outros Passos IMPLEMENTAÇÃO 66 o motivo por ser duas vezes o diâmetro da área circular da base, deve-se por este ser o mínimo para evitar uma colisão. Diminuir ou aumentar o diâmetro da área do obstáculo, permite também obter um espaço de configuração mais adequado para o robô executar determinados comportamentos de jogo. Esta funcionalidade é controlada pela função apresentada anteriormente. Figura 5.17 – Resultado obtido após o algoritmo ser executado para o exemplo da Figura 5.15 . Na Figura 5.18 é possível observar dois tipos de comportamentos que podem ser atribuídos pelo processo Inteligência Artificial , sendo que (a) e (c) representam um comportamento, e (b) e (d) representam outro. Relativamente às duas trajetórias apresentadas para cada comportamento, a trajetória com os segmentos de reta azuis escuros é a trajetória mais curta, enquanto que a de segmentos de reta vermelhos é a trajetória mais curta e suave, que será apresentada posteriormente. Posto isto, a diferença entre os dois comportamentos tem a ver com a “agressividade” com que o robô se move para a posição pretendida, que neste exemplo, é a bola. Desta forma, o comportamento do robô para (a) (c) é mais “agressivo” e mais rápido a atingir a posição pretendida do que em (b) (d) . No entanto, considerando que neste exemplo é um robô adversário que tem bola, a probabilidade de o robô colidir para o primeiro comportamento é maior e assim, como está especificado nas regras de jogo da MSL, é marcada falta. É de salientar que o diâmetro da área do obstáculo em (a) (c) é igual a zero, sendo o obstáculo representado apenas pela sua posição no espaço de configuração. (a) (b) IMPLEMENTAÇÃO 67 Figura 5.18 – Exemplo de dois tipos de comportamentos. As trajetórias (a) e (c) representam um tipo de comportamento, as (b) e (d) representam outro. 5.1.6. TRAJETÓRIA MAIS CURTA E SUAVE A trajetória obtida pelo algoritmo de Dijkstra, sendo a mais curta de todas as trajetórias possíveis no mapa discreto implementado, não é a melhor trajetória por dois motivos. O primeiro, é a possibilidade de existirem alguns casos em que a trajetória é a mais curta no mapa discreto e não no espaço de configuração, isto é, como a trajetória obtida é constituída pelos segmentos de reta do diagrama de Voronoi, estes podem estar em alguns locais demasiado distantes dos obstáculos. O segundo motivo, é a possibilidade de a trajetória obtida conter cantos afiados, dificultando o movimento do robô. Posto isto, a solução é implementar estratégias/algoritmos para suavizar a trajetória e obter, ao mesmo tempo, a trajetória mais curta no espaço de configuração livre. Nas secções seguintes 5.1.6.1 a 5.1.6.4 , será apresentada a implementação para resolver este problema. 5.1.6.1. TRAJETÓRIA MAIS CURTA SIMPLIFICADA Neste passo, o objetivo é remover segmentos de reta desnecessários da trajetória obtida anteriormente, de forma a construir uma nova trajetória mais simples. Na Figura 5.21 é possível observar o resultado da implementação deste passo para o exemplo apresentado, sendo que a trajetória obtida anteriormente é constituída pelos 5 segmentos de reta azuis escuros e a nova trajetória simplificada (a) (b) (c) (d) IMPLEMENTAÇÃO 68 pelos 2 segmentos de reta azuis claros. O algoritmo desenvolvido neste passo será representado no fluxograma da Figura 5.20 , e para melhor se compreender o fluxograma, a Figura 5.19 representa uma trajetória a ser simplificada, com os pontos das extremidades dos segmentos de reta identificados por números. As posições (x, y) dos pontos encontram-se guardadas num vetor. Figura 5.19 - Exemplo de uma trajetória a ser simplificada e a representação do vetor de posições dos pontos da mesma. Figura 5.20 – Fluxograma para obter uma trajetória ainda mais curta e simplificada. 1 2 3 4 5 6 (𝑥,𝑦) 1 (𝑥,𝑦) 2 (𝑥,𝑦) 3 (𝑥,𝑦) 4 (𝑥,𝑦) 5 (𝑥,𝑦) 6 pontos Início nº pontos > 1 ? Fim p_A = pontos[1] p_B = pontos[2] p_B_anterior = p_B i = 2 Não Sim novos_pontos[] = p_A i < nº pontos ? i = i + 1 p_B = pontos[i] Sim Segmento de reta entre p_A e p_B interseta com algum obstáculo ? p_A = p_B_anterior novos_pontos[] = p_A Sim p_B_anterior = p_B novos_pontos[] = p_B Não Não IMPLEMENTAÇÃO 69 Figura 5.21 - Trajetória ainda mais curta e simplificada, representada pelos 2 segmentos de reta azuis claros. 5.1.6.2. TRAJETÓRIA SUAVE Neste passo, o objetivo é suavizar a trajetória obtida no passo anterior, pois existe a possibilidade de esta conter cantos afiados. No exemplo apresentado (ver Figura 5.21 ou Figura 5.22 ) a trajetória simplificada, tem aproximadamente um ângulo de 90º entre os dois segmentos de reta azuis claros, dificultando o movimento do robô para velocidades elevadas. Para suavizar a trajetória é utilizado o método de curvas paramétricas polinomiais apresentado na secção 3.1.1.7 , sendo escolhida a curva do tipo B-Spline. Este tipo de curva permite obter uma nova trajetória por aproximação aos pontos da trajetória simplificada. Desta forma, a nova trajetória passa apenas pelos pontos inicial e final da trajetória simplificada, sendo aproximada para os restantes. Na Figura 5.22 é possível observar o resultado da implementação deste passo para o exemplo apresentado, sendo a trajetória suave representada pelos segmentos de reta roxos. Figura 5.22 – Trajetória suave representada pelos segmentos de reta roxos. Para se obter a trajetória suave é necessário considerar alguns fatores para a construção da curva, tais como, o grau do polinómio e o número de pontos de amostragem. O grau do polinómio igual a 3, que corresponde a uma curva cúbica, é o que oferece melhores resultados e por isso é o grau utilizado, IMPLEMENTAÇÃO 70 no entanto, se o número de pontos da trajetória simplificada for inferior a 4, o grau terá de ser inferior a 3. Isto é, se o número de pontos for igual a 3, é atribuído o grau 2, que corresponde a uma curva quadrática, mas se o número de pontos for igual a 2, é atribuído o grau 1, que corresponde a uma curva linear. No exemplo da Figura 5.22 , a trajetória suave é uma curva quadrática, pois a trajetória simplificada contém apenas 3 pontos. Relativamente ao número de pontos de amostragem, este número define a suavidade da curva, pois tal como já foi mencionado na secção 3.1.1.7 , uma curva é representada analiticamente, sendo necessário determinar o número de pontos a serem extraídos da curva calculada, ou seja, a quantidade de amostras. Desta forma, para poucos pontos de amostragem a curva é pouco suave com possíveis cantos afiados, enquanto que para bastantes pontos é possível uma curva suave. É de salientar que na obtenção da trajetória suave não são considerados os obstáculos. 5.1.6.3. AJUSTAR TRAJETÓRIA Este passo tem como objetivos ajustar e simplificar a trajetória suave, obtida no passo anterior. O ajuste é feito apenas para o caso em que a trajetória interseta com algum obstáculo, tal como no exemplo apresentado na Figura 5.23 . Nesta figura, a trajetória com os segmentos de reta cor-de-rosa representa o ajuste feito à trajetória suave, representada pelos segmentos de reta roxos. Desta forma, o ajuste consiste em desviar a trajetória suave para fora da área do obstáculo caso esta intersete com algum. Este ajuste é necessário, pois não interessa ter uma trajetória que faça o robô colidir com os obstáculos. Figura 5.23 – Trajetória ajustada, representada pelos segmentos de reta cor-de-rosa. Na Figura 5.24 está representado um desenho para melhor se compreender o algoritmo de ajuste. Este algoritmo numa primeira fase, verifica se a trajetória suave interseta com algum obstáculo, se existir interseção, é feita a pesquisa pelos dois pontos de interseção da trajetória com a circunferência que representa o obstáculo. Estes dois pontos são representados na figura com as cores verde e vermelho, enquanto que a trajetória é representada pelos segmentos de reta roxos. IMPLEMENTAÇÃO 71 De seguida, é feita a pesquisa pelos pontos dos segmentos de reta da trajetória no interior do círculo do obstáculo. Em cada ponto, passa uma linha com origem num dos dois pontos de interseção. Desta forma, o conjunto de pontos no interior do círculo é dividido em duas partes. Na primeira metade, passam as linhas com origem no segundo ponto de interseção (ponto e linhas a vermelho na figura), enquanto que na segunda metade, passam as linhas com origem no primeiro ponto de interseção (ponto e linhas a verde na figura). Estas linhas intersetam com a circunferência do obstáculo, existindo assim um ponto de interseção para cada linha. No espaço onde não existem linhas, são adicionados alguns pontos. Contudo, é necessário fazer para cada ponto uma pequena translação para não intersetar com o obstáculo. Com estes novos pontos é construída a trajetória ajustada, sendo esta representada na figura pelos pontos e segmentos de reta a cor-de-rosa. Figura 5.24 – Desenho ilustrativo do ajuste da trajetória, sendo que a trajetória a ser ajustada é representada pelos segmentos de reta roxos e a trajetória ajustada pelos segmentos de reta cor-de-rosa. O outro objetivo deste passo é simplificar a trajetória suave, independentemente de esta ter sido ajustada ou não. Para isso, foi implementado o mesmo algoritmo apresentado na secção 5.1.6.1 . Na Figura 5.25 é possível observar o resultado da implementação deste algoritmo para o exemplo apresentado, sendo a trajetória ajustada constituída pelos segmentos de reta cor-de-rosa e a trajetória simplificada pelos segmentos de reta castanhos. Figura 5.25 – Trajetória simplificada, representada pelos segmentos de reta castanhos. IMPLEMENTAÇÃO 72 5.1.6.4. TRAJETÓRIA SUAVE - TRAJETÓRIA MAIS CURTA E SUAVE Após a construção de algumas trajetórias, a simplificada obtida no passo anterior é a trajetória mais curta possível no espaço de configuração. No entanto, existe a possibilidade de esta conter cantos afiados, dificultando o movimento do robô para velocidades elevadas. Desta forma, é necessário suavizar esta trajetória com a implementação do método de curvas paramétricas polinomiais, tal como na secção 5.1.6.2 . Contudo, foi escolhido outro tipo de curva, que permite obter uma nova trajetória por interpolação aos pontos da trajetória simplificada. Assim, a nova trajetória passa por todos os pontos da trajetória simplificada e os restantes pontos que a constituem são distribuídos com o intuito de formarem uma trajetória suave. Na Figura 5.26 é possível observar o resultado da implementação deste último passo para o exemplo apresentado, sendo a trajetória mais curta e suave representada pelos segmentos de reta vermelhos. Tal como na obtenção da trajetória suave na secção 5.1.6.2 , é necessário considerar os fatores, grau do polinómio e o número de pontos de amostragem para a construção da curva. A influência destes dois fatores na construção de uma curva por interpolação é equivalente a uma curva por aproximação. É de salientar, que na obtenção desta trajetória não são considerados os obstáculos, pois esta segue de perto a trajetória simplificada. Posto isto, esta trajetória é o melhor compromisso entre a trajetória mais curta e a trajetória mais suave. Figura 5.26 – Trajetória mais curta e suave, representada pelos segmentos de reta vermelhos. 5.1.7. VISÃO GERAL DO PLANEAMENTO DA TRAJETÓRIA Após a apresentação de todos os passos da implementação do processo Planeamento da Trajetória , é apresentado nesta secção o fluxograma da visão geral deste processo (ver Figura 5.27 ). Todas as condições e passos apresentados no fluxograma, foram descritos neste subcapítulo. É de IMPLEMENTAÇÃO 79 Figura 5.33 - Fluxograma para o cálculo da direção do movimento de translação em tempo real. Sim Início - Ângulo atual do robô - Ângulo pretendido para o movimento Direção do movimento >= 360 Direção do movimento Fim Direção do movimento = Direção do movimento - 360 Não Direção do movimento = 360 – ângulo atual do robô + ângulo pretendido para o movimento 80 Capítulo 6 RESULTADOS Este capítulo é constituído por quatro subcapítulos, onde serão apresentados os resultados obtidos após a implementação de todos os passos dos dois processos já apresentados. Assim, no primeiro subcapítulo é feita uma análise ao desempenho do planeamento da trajetória, sendo que no segundo subcapítulo serão apresentados exemplos da evolução do erro para os movimentos de rotação e de translação do robô, após o ajuste das variáveis dos algoritmos implementados. Posteriormente, no terceiro subcapítulo será apresentada a trajetória percorrida pelo robô em alguns exemplos do espaço de configuração do espaço de jogo, e também por dois robôs em simultâneo. Para finalizar, no quarto subcapítulo será feita a análise da participação no Festival Nacional de Robótica 2017. Os resultados apresentados nos três primeiros subcapítulos foram obtidos usando o simulador da Minho Team, num sistema com um processador Intel Core i5 a 2,4 GHz, 4 GB de memória RAM, e com o sistema operativo Ubuntu 16.04 de 64 bits. 6.1. DESEMPENHO DO PLANEAMENTO DA TRAJETÓRIA Como foi implementado e testado apenas um único algoritmo para cada passo deste processo, não sendo possível desta forma comparar com outros algoritmos existentes, o desempenho será assim analisado pelo tempo médio de 100 amostras. As dimensões do campo de jogo são as oficiais, já apresentadas no primeiro capítulo, e os obstáculos são 9 no total, sendo que destes, 5 são obstáculos de robôs adversários com 2 m de diâmetro na área de cada obstáculo e 4 são obstáculos de robôs cooperativos com 1,2 m de diâmetro. De seguida, será apresentado um exemplo para cada passo do planeamento da trajetória, onde é possível observar o espaço de configuração e o resultado obtido após a implementação do respetivo algoritmo. O tempo médio de 100 amostras, registado em cada passo, corresponde ao resultado do respetivo exemplo apresentado. Na Figura 6.1 é possível observar a trajetória retilínea obtida para o exemplo do espaço de configuração apresentado. RESULTADOS 81 Figura 6.1 - Trajetória retilínea. Neste passo, para este exemplo do espaço de configuração, o tempo médio de processamento para obter a trajetória retilínea foi de 0,292 ms. Considerando a complexidade dos algoritmos implementados nos próximos passos, este tempo é bastante baixo. De seguida, é apresentado na Figura 6.2 um exemplo da discretização do espaço de configuração, onde é possível observar o diagrama de Voronoi para as posições de 9 obstáculos reais e dos obstáculos artificiais, sobrepostos às linhas dos limites do campo. Tal como apresentado na secção 5.1.5 , os obstáculos artificiais não são apresentados no visualizer , porém as posições destes são sempre incluídas na construção do diagrama de Voronoi. O tempo médio de processamento obtido no exemplo apresentado foi de 5,156 ms. Este tempo poderia ser muito menor se não tivesse os obstáculos artificiais, que são em grande número e que fazem o diagrama ter muitas mais arestas e vértices. Contudo, estes são necessários para que existam segmentos de reta à volta de cada obstáculo. Figura 6.2 - Discretização do espaço de configuração através do diagrama de Voronoi. O algoritmo implementado no próximo passo do planeamento, que faz a pesquisa pela trajetória mais curta, foi analisado em duas etapas. A primeira etapa corresponde à construção de um grafo não direcionado, já mencionado na secção 5.1.5 , enquanto que a segunda etapa consiste na pesquisa pela RESULTADOS 82 trajetória mais curta através do algoritmo de Dijkstra. Posto isto, na Figura 6.3(a) é possível observar o resultado de um exemplo da primeira etapa, onde o tempo médio de processamento obtido foi de 88,057 ms. Este algoritmo tem um tempo médio de processamento muito mais elevado que todos os outros algoritmos implementados neste trabalho. Isto deve-se ao facto de este verificar para cada segmento de reta, se existe interseção com algum obstáculo, e também do tempo que demora para construir o objeto do grafo. Relativamente à segunda etapa, na Figura 6.3(b) é possível observar a trajetória mais curta entre a posição atual do robô e a posição pretendida para o mesmo, no exemplo do espaço de configuração apresentado. O tempo médio de processamento obtido nesta etapa foi de 12,367 ms. Figura 6.3 - Pesquisa pela trajetória mais curta. (a) Grafo com verificação da interseção dos segmentos de reta com os obstáculos. (b) Trajetória mais curta representada pelos segmentos de reta azuis. O último passo do planeamento, tal como já foi apresentado na secção 5.1.6 , tem como objetivo suavizar a trajetória encontrada pelo algoritmo de Dijkstra e obter, ao mesmo tempo, a trajetória mais curta no espaço de configuração livre. Na Figura 6.4 é possível observar as cinco trajetórias obtidas neste último passo, para o mesmo exemplo do espaço de configuração do passo anterior e para as mesmas posições (do robô e da pretendida para este). O tempo médio de processamento obtido neste último passo do planeamento, para o exemplo apresentado na figura, foi de 3,279 ms. (a) (b) (a) (b) RESULTADOS 83 Figura 6.4 - Trajetórias dos algoritmos implementados, para obter a trajetória mais curta e suave. (a) Trajetória mais curta simplificada. (b) Trajetória suave. (c) Trajetória ajustada. (d) Trajetória simplificada. (e) Trajetória mais curta e suave. De seguida, será apresentado na Tabela 6.1 um resumo dos tempos médios de processamento para os exemplos apresentados, e também para a função que calcula o diâmetro da área de cada obstáculo. Tabela 6.1 – Tempos médios de processamento do planeamento da trajetória para os exemplos apresentados. Algoritmo/Passo do Planeamento da Trajetória Tempo Médio de Processamento (ms) Calcular o Diâmetro da Área de Cada Obstáculo 0,015 Trajetória Retilínea 0,292 Discretização do Espaço de Configuração 5,156 Pesquisa Pela Trajetória Mais Curta (1ª etapa) 88,057 Pesquisa Pela Trajetória Mais Curta (2ª etapa) 12,367 Trajetória Mais Curta e Suave 3,279 Tempo Total: 109,166 (c) (d) (e) RESULTADOS 84 Na Figura 6.5 é possível observar a trajetória mais curta e suave para outro exemplo do espaço de configuração, onde as diferenças para o exemplo anterior é nas posições dos obstáculos, na posição do robô e na posição pretendida para este. O tempo médio de processamento obtido em todos os passos do planeamento da trajetória, para este exemplo, foi de 108,187 ms. Figura 6.5 – Trajetória mais curta e suave. Tal como é possível verificar pelos tempos médios obtidos nos dois exemplos, estes são muito próximos. Pois o que muda de um exemplo para outro é apenas as posições dos obstáculos, do robô e da posição pretendida. A dispersão dos obstáculos no espaço de configuração é idêntica, o que faz com que a quantidade de segmentos de reta também seja muito próxima. Com isto a complexidade de processamento no passo Pesquisa Pela Trajetória Mais Curta é equivalente. Noutros testes efetuados, com menos ou mais obstáculos, com outras dispersões ou com diâmetros das áreas dos obstáculos diferentes, verificaram-se tempos menores, mas também se verificou o oposto, pois depende totalmente do espaço de configuração. Os primeiros testes efetuados no simulador da Minho Team, logo após a implementação de todos os algoritmos, levantaram algumas dúvidas relativamente ao tempo médio de processamento do planeamento da trajetória, que poderia ser elevado para o controlo do movimento. Contudo, após testes com os robôs reais verificou-se que este seria o caminho a seguir. Pois tal como foi apresentado na secção 4.2.1.2 , o tempo necessário para a OMNI3D-MAX executar uma ordem de movimentação pode ir até 100 ms. No entanto, no futuro deve-se ter em conta uma possível melhoria na 1ª etapa do passo Pesquisa Pela Trajetória Mais Curta . RESULTADOS 85 6.2. MOVIMENTO APÓS AJUSTES DOS PARÂMETROS Os gráficos apresentados de seguida, correspondem ao valor do erro durante o teste realizado a cada algoritmo apresentado no subcapítulo 5.2 . Estes algoritmos fazem o cálculo das três variáveis necessárias para o movimento holonómico, enviadas em tempo real para a placa de controlo dos motores. Desta forma, são controlados os movimentos de rotação e de translação, e também a direção do movimento de translação. Na Figura 6.6 é possível observar o valor do erro angular durante a rotação do robô. Isto significa que o valor do erro num instante de tempo, corresponde à diferença entre o ângulo do robô nesse instante e o ângulo pretendido para o robô. Através da análise deste gráfico, é possível afirmar que o erro inicial neste teste era de aproximadamente -170°. Com o valor da velocidade angular determinado em tempo real, o robô roda até que fique direcionado no ângulo pretendido, ou seja, até que o erro seja igual a zero ou muito próximo. Neste teste, os ganhos do controlador PID foram ajustados, de modo a que o robô rodasse o mais rápido possível e sem grandes oscilações. Figura 6.6 – Valor do erro angular durante a rotação do robô. Nos gráficos apresentados nas figuras 6.7 , 6.8 e 6.9 , é possível observar a distância da trajetória durante a translação do robô até à posição pretendida. Assim, o valor do erro num instante de tempo, corresponde à distância da trajetória entre a posição do robô nesse instante e a posição pretendida para o robô. Através da análise destes três gráficos, é possível afirmar que o erro inicial, nestes testes, era de aproximadamente 7,5 m. Com o valor da velocidade linear determinado em tempo real, o robô move-se até chegar à posição pretendida, ou seja, até que o erro seja igual a zero ou muito próximo. -180 -160 -140 -120 -100 -80 -60 -40 -20 0 20 1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154 163 172 181 190 199 208 217 Erro Número de amostras Diferença angular RESULTADOS 86 Para determinar o valor da velocidade linear nestes testes, foram usados os algoritmos apresentados na secção 5.2.2 . Assim, a linha tracejada azul do gráfico da Figura 6.7 corresponde ao algoritmo com base no cálculo da tangente hiperbólica, a linha de pontos laranja do mesmo gráfico corresponde ao algoritmo com base no cálculo do logaritmo, e as duas linhas do gráfico da Figura 6.8 correspondem ao algoritmo com base num controlador PID em malha fechada. Figura 6.7 – Distância da trajetória durante a translação do robô até à posição pretendida, sendo que Erro corresponde a essa distância. A linha tanh corresponde ao algoritmo com base no cálculo da tangente hiperbólica e a linha log , ao algoritmo com base no cálculo do logaritmo. Considerando que para estes testes foi usada a mesma velocidade máxima linear e o mesmo fator multiplicativo para a velocidade máxima linear, é possível analisar a evolução do valor do erro entre gráficos e consequente comparação entre algoritmos. Analisando a evolução do valor do erro entre os dois algoritmos do gráfico da Figura 6.7 , é possível afirmar que os resultados são muito idênticos. Os tempos obtidos nestes dois testes também comprovam esta análise, pois no teste correspondente a tanh o robô demorou 4,63 s a percorrer a trajetória, e no teste correspondente a log demorou 4,79 s. Relativamente à evolução do valor do erro entre os dois testes do gráfico da Figura 6.8 , é possível afirmar que têm um resultado diferente entre eles. Pois o algoritmo com base num controlador PID em malha fechada, usado nestes dois testes, permite ajustar a velocidade para um comportamento de jogo, mais ou menos “agressivo”. Desta forma, no teste correspondente à linha PID_Teste1 , o robô moveu-se mais rapidamente para a posição pretendida, que no teste correspondente à linha PID_Teste2 . Os tempos obtidos também comprovam esta análise, pois no teste correspondente à linha PID_Teste1 o robô demorou 4,43 s a percorrer a trajetória e no teste 0 1 2 3 4 5 6 7 8 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103 109 115 121 127 133 139 Erro Número de amostras Distância à posição pretendida tanh log RESULTADOS 87 correspondente à linha PID_Teste2 demorou 5,39 s. Esta diferença deve-se aos ajustes feitos aos ganhos do controlador PID, sendo também possível obter resultados diferentes, através da alteração do fator velocidade máxima linear. Figura 6.8 – Distância da trajetória durante a translação do robô até à posição pretendida, sendo que Erro corresponde a essa distância. As duas linhas apresentadas, correspondem a dois testes efetuados ao algoritmo com base num controlador PID em malha fechada. Na Figura 6.9 é possível observar num único gráfico os mesmos resultados já apresentados, correspondentes a tanh , PID_Teste1 e PID_Teste2 . Figura 6.9 – Gráfico com os mesmos resultados já apresentados nos dois gráficos anteriores. Apenas a linha log não é apresentada. 0 1 2 3 4 5 6 7 8 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103 109 115 121 127 133 139 145 151 157 Erro Número de amostras Distância à posição pretendida PID_Teste1 PID_Teste2 0 1 2 3 4 5 6 7 8 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 103 109 115 121 127 133 139 145 151 157 Erro Número de amostras Distância à posição pretendida tanh PID_Teste1 PID_Teste2 RESULTADOS 88 Posto isto, o algoritmo com base num controlador PID em malha fechada, foi o algoritmo usado na implementação final para o cálculo do valor da velocidade linear. Pois, dos três algoritmos este é bastante flexível no ajuste, permitindo ajustar para diferentes comportamentos de jogo. Nos testes realizados no simulador e nos robôs reais, este foi o algoritmo mais eficaz. 6.3. TRAJETÓRIAS PERCORRIDAS Neste subcapítulo serão apresentadas as trajetórias percorridas pelo robô em diferentes exemplos do espaço de configuração, e também as trajetórias percorridas em simultâneo por dois robôs no mesmo espaço de configuração. No algoritmo desenvolvido para o controlo do movimento, foram determinados dois modos de movimento que dependem da ação que o robô tenha de executar. Desta forma, um dos modos é quando a ação implica mover o robô para se aproximar da bola e retê-la, o outro é quando a ação implica mover o robô para uma posição e direcionar a parte da frente numa determinada direção. Na Figura 6.10 é possível observar a trajetória mais curta e suave entre a posição atual do robô e a posição pretendida para o mesmo, no exemplo do espaço de configuração apresentado. Figura 6.10 – Trajetória mais curta e suave. A posição pretendida para o robô é representada pelo ponto vermelho e a direção pelo ponto laranja. No teste efetuado, o robô percorreu esta trajetória tal como apresentado na Figura 6.11 . O modo de movimento usado foi o modo “sem bola”, por isso o robô para percorrer a trajetória não fez qualquer movimento de rotação durante o movimento de translação até à posição pretendida (ponto vermelho na figura). Quando o robô atingiu a posição, o valor da velocidade linear foi a zero, e da velocidade de rotação diferente de zero até que ficasse direcionado para o ponto laranja representado na figura. Também é RESULTADOS 95 Relativamente aos pontos fracos na estrutura mecânica, hardware e software , neste evento foram encontrados alguns que podem ser melhorados no futuro. Por exemplo, na estrutura mecânica o sistema de manipulação de bola é pouco eficiente. Figura 6.20 - Robôs da Minho Team no Festival Nacional de Robótica 2017 em Coimbra. 96 Capítulo 7 CONCLUSÃO E TRABALHO FUTURO Este capítulo descreve as conclusões sobre o trabalho desenvolvido nesta dissertação e algumas ideias que poderiam ser implementadas no futuro. 7.1. CONCLUSÃO No trabalho desta dissertação foi desenvolvido um sistema de controlo de movimento, aplicado nos robôs da Minho Team. Neste sistema, constituído pelos dois processos Planeamento da Trajetória e Controlo do Movimento , foram implementados os métodos e respetivos conceitos apresentados no Capítulo 3 . O software desenvolvido neste trabalho foi testado no simulador da Minho Team, e com os robôs reais no campo de pequenas dimensões do LAR e em ambiente de competição (FNR 2017). Nos testes realizados verificou-se que a diferença entre utilizar o simulador e os robôs reais é apenas nos ajustes aos ganhos dos controladores PID para o controlo do movimento. Por isso, e por outras razões mencionadas em capítulos anteriores, o simulador foi uma ferramenta fundamental para o desenvolvimento do software . O ROS foi também essencial para a construção de uma arquitetura de software robusta, que permitiu a comunicação entre todos os módulos de software de um robô. No sistema de controlo de movimento, nomeadamente, no processo Planeamento da Trajetória , foram implementados métodos associados ao tipo de planeamento global com algumas estratégias/algoritmos adicionadas a esses métodos. Nos testes efetuados verificou-se que o modelo de planeamento desenvolvido é eficiente e robusto. No entanto, este depende muito da precisão do espaço de configuração para obter a melhor trajetória possível. Relativamente aos algoritmos implementados no processo Controlo do Movimento , foram obtidos os resultados pretendidos no que diz respeito ao seguimento das trajetórias. Por isso, pelos resultados de todos os testes efetuados, incluindo os jogos realizados no FNR 2017, conclui-se que o sistema de controlo de movimento cumpre os objetivos planeados. Para finalizar, este trabalho de dissertação é apenas um módulo de um conjunto de módulos de software desenvolvidos pelos elementos da Minho Team, sendo que alguns desses módulos incluem também ferramentas de configuração e simulação. Com todos os módulos de software e com o tempo CONCLUSÃO E TRABALHO FUTURO 97 despendido na reconstrução do hardware e da estrutura mecânica de cada robô, foi possível alcançar os objetivos delineados para este trabalho e também os objetivos da equipa. 7.2. TRABALHO FUTURO Durante o desenvolvimento deste trabalho e após os testes efetuados, surgiram algumas ideias para possíveis melhorias, não só no sistema de controlo de movimento, mas também na estrutura mecânica dos robôs. Uma primeira melhoria seria desenvolver um algoritmo na Base Station para o cálculo do diâmetro da área de cada obstáculo. Este algoritmo iria incluir a informação relativa à previsão das velocidades dos robôs adversários e dos robôs cooperativos. O algoritmo de previsão também teria de ser desenvolvido, pois este ainda não existe nos robôs da Minho Team. Outra possível melhoria seria no algoritmo da primeira etapa da pesquisa pela trajetória mais curta, que corresponde à construção do grafo não direcionado. Neste algoritmo poderia ser estudada outra estratégia, ou melhorar a existente, de modo que não fosse necessário verificar para cada segmento de reta se existe interseção com algum obstáculo. Pois esta verificação e posterior construção do objeto grafo, demora algum tempo em comparação com os restantes algoritmos do planeamento da trajetória implementados neste trabalho. Adicionar um método de planeamento local da trajetória, também poderia representar uma melhoria considerável, no caso em que o espaço de configuração tem pouca precisão, e também para diminuir a hipótese de uma colisão quando os robôs se deslocam para a mesma zona do campo a velocidades elevadas, ou quando as trajetórias se intersetam numa zona e estes passam nessa zona no mesmo momento. Para finalizar, o desenvolvimento de um algoritmo para controlar o movimento do robô quando tem a bola, também seria uma boa melhoria. No entanto, seria indispensável melhorar a estrutura mecânica e hardware do sistema de manipulação de bola, para reter e driblar a bola durante os movimentos de translação e rotação do robô. 98 BIBLIOGRAFIA [1] C. V. R. Coutinho, “Robótica Móvel - Sistema de Condução Autónoma,” Instituto Superior de Engenharia de Lisboa, 2014. [2] Business Wire, “Robôs de entrega autônomos da Panasonic – HOSPI – auxiliam operações hospitalares.” [Online]. Available: http://www.businesswire.com/news/home/20150724005247/pt/. [Accessed: 04-Nov-2016]. [3] International Federation of Robotics, “Industrial Robots.” [Online]. Available: http://www.ifr.org/industrial-robots/. [Accessed: 05-Nov-2016]. [4] J. A. M. F. De Souza, “Robótica.” [Online]. Available: http://webx.ubi.pt/~felippe/main_pgs/mat_didp.htm. [Accessed: 23-Jul-2019]. [5] RoboCup Federation, “RoboCup.” [Online]. Available: http://www.robocup.org/. [Accessed: 07Nov-2016]. [6] “RoboCup 2004 – Portugal.” [Online]. Available: http://www.robocup2004.pt/. [Accessed: 07Nov-2016]. [7] M. Asada et al. , “Middle Size Robot League - Rules and Regulations,” 2016. [8] F. Ribeiro, P. Braga, J. Monteiro, I. Moutinho, P. Silva, and V. Silva, “New improvements of minho team for robocup middle size league in 2003,” Proc. CD-ROM, Rob. , 2003. [9] F. Ribeiro, I. Moutinho, P. Silva, C. Fraga, and N. Pereira, “Three Omni-Directional Wheels Control on a Mobile Robot,” Control 2004 , 2004. [10] F. Ribeiro, I. Moutinho, N. Pereira, and F. Oliveira, “Cooperative Behaviour of specific tasks in multi-agent systems and robot control using dynamic approach,” 2006. [11] A. Ribeiro, G. Lopes, and J. Costa, “Minho MSL: a new generation of soccer robots,” 2011. [12] F. Ribeiro, P. Braga, I. Moutinho, P. Silva, and B. Martins, “Magnetically Impelled Kicker for Robotic Football in MSL RoboCup,” Most , pp. 2–5, 2004. [13] “CAMBADA - RoboCup MSL Soccer Team - Home.” [Online]. Available: http://robotica.ua.pt/CAMBADA/index.php?a=106a6c241b8797f52e1e77317b96a201. [Accessed: 20-Jun-2017]. [14] G. Corrente, “Arquitectura de controlo/coordenação de uma equipa de Futebol Robótico,” Universidade de Aveiro, 2008. [15] “libtcod.” [Online]. Available: http://roguecentral.org/doryen/libtcod/. [Accessed: 11-Jul-2017]. [16] “Carpe Noctem Cassel - Robotic Soccer: Home.” [Online]. Available: https://www.unikassel.de/eecs/carpe-noctem-cassel/home.html. [Accessed: 22-Jun-2017]. BIBLIOGRAFIA 99 [17] S. Opfer, H. Skubch, and K. Geihs, “Cooperative Path Planning for Multi-Robot Systems in Dynamic Domains,” Cdn.Intechopen.Com , pp. 237–258, 2011. [18] D. Bachmann et al. , “Carpe Noctem Cassel Team Description 2016,” 2016. [19] J. J. T. H. De Best, D. J. H. Bruijnen, R. Hoogendijk, R. J. M. Janssen, and K. J. Meessen, “Tech United Eindhoven Team Description 2010,” vol. 1, 2010. [20] C. Lopez et al. , “Tech United Eindhoven Team Description 2015,” 2015. [21] S. G. Tzafestas, Introduction to mobile robot control . 2013. [22] R. Jitendra and K. Ajith, Mobile Intelligent Autonomous Systems . 2007. [23] D. Nakhaeinia, S. H. Tang, S. B. M. Noor, and O. Motlagh, “A review of control architectures for autonomous navigation of mobile robots,” Int. J. Phys. Sci. , vol. 6, no. 2, pp. 169–174, 2011. [24] K. H. Sedighi, K. Ashenayi, T. W. Manikas, R. L. Wainwright, and H.-M. Heng-Ming Tai, “Autonomous local path planning for a mobile robot using a genetic algorithm,” Proc. 2004 Congr. Evol. Comput. (IEEE Cat. No.04TH8753) , vol. 2, pp. 1338–1345, 2004. [25] S. Russell and P. Norvig, Artificial Intelligence A Modern Approach . 2009. [26] R. Siegwart and I. R. Nourbakhsh, Introduction to Autonomous Mobile Robots , vol. 23. 2004. [27] J.-C. Latombe, Robot motion planning . 1991. [28] M. F. R. Queirós, “Planeamento de Caminhos para Robôs Móveis Autónomos em Ambientes Conhecidos e Estruturados,” Universidade do Minho, 2014. [29] B. Y. P. Bhattacharya and M. L. Gavrilova, “Roadmap-Based Path Planning,” no. June, 2008. [30] S. Fortune, “A Sweepline Algorithm for Voronoi Diagrams,” Algorithmica , vol. 2, no. 2, pp. 153– 174, 1987. [31] F. Aurenhammer, “Voronoi Diagrams — A Survey of a Fundamental Geometric Data Structure,” ACM Comput. Surv. , vol. 23, no. 3, pp. 345–405, 1991. [32] D. T. Lee and A. K. Lin, “Generalized delaunay triangulation for planar graphs,” Discrete Comput. Geom. , vol. 1, no. 1, pp. 201–217, 1986. [33] D. T. Lee and B. J. Schachter, “Two algorithms for constructing a Delaunay triangulation,” Int. J. Comput. Inf. Sci. , vol. 9, no. 3, pp. 219–242, 1980. [34] M. A. PITERI, A. G. DOS JUNIOR, MESSIAS MENEGUETTE SANTOS, and F. F. OLIVEIRA, “Triangulação De Delaunay E O Princípio De Inserção Randomizado,” Simpósio Bras. Geomática , no. 1999, pp. 655–663, 2007. [35] M. De Berg and M. Van Kreveld, “Voronoi Diagrams,” Comput. … , 1997. [36] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numer. Math. , vol. 1, no. 1, BIBLIOGRAFIA 100 pp. 269–271, 1959. [37] T. J. Misa, “An interview with Edsger W. Dijkstra,” Commun. ACM , vol. 53, no. 8, p. 41, 2010. [38] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Second Edition . 2001. [39] “Caminho de Custo Mínimo - Algoritmo de Dijkstra.” [Online]. Available: http://www.inf.ufsc.br/grafos/temas/custo-minimo/dijkstra.html. [Accessed: 22-Dec-2017]. [40] A. Conci and E. Azevedo, Computação Gráfica - Teoria e Prática . 2003. [41] M. E. Mortenson, Geometric Modeling , 2nd ed. 1997. [42] J. F. HUGHES et al. , Computer Graphics: Principles and Practice , 3rd ed. 2014. [43] K. Ogata, Modern Control Engineering 4th edtion By Katsuhiko Ogata: Modern Control Engineering . 2002. [44] J. Karl and T. Hagglund, PID Controllers, 2nd Edition . 1995. [45] Ros.org, “ROS.org | Powering the world’s robots,” website . [Online]. Available: http://www.ros.org/. [Accessed: 11-Sep-2017]. [46] M. Quigley et al. , “ROS: an open-source Robot Operating System,” Icra , vol. 3, no. Figure 1, p. 5, 2009. [47] F. Ribeiro et al. , “MinhoTeam ’2016 : Team Description Paper,” 2016. [48] H. Ribeiro et al. , “Fast Computational Processing for Mobile Robots’ Self-Localization,” Proc. - 2016 Int. Conf. Auton. Robot Syst. Compet. ICARSC 2016 , no. March, pp. 168–173, 2016. [49] J. L. Fernandes, “Desenvolvimento de hardware e software para robôs móveis,” Universidade do Minho, 2006. [50] “Omni-3MD.” [Online]. Available: http://botnroll.com/omni3md/. [Accessed: 05-Mar-2018]. [51] The CGAL Project, “The Computational Geometry Algorithms Library,” Web . [Online]. Available: https://www.cgal.org/. [Accessed: 19-Sep-2017]. [52] A. Fabri, “CGALThe computational Geometry algorithm library,” Proc. 10th Annu. Int. Meshing Roundtable , pp. 7–10, 2001.