A proposta deste trabalho é contribuir com a construção de uma plataforma de veículo autônomo para viabilizar as pesquisas na área pelo Departamento de Engenharia de Transportes da USP. Até o momento o departamento dispõe de uma plataforma que, a partir de sua posição conhecida, consegue navegar autonomamente até um ponto de destino utilizando apenas uma solução GNSS, no caso, GPS. Para ampliar a mobilidade da plataforma, está sendo sugerida aqui, a adição de sensores inerciais ao veículo, para que ele consiga obter uma solução de posição mesmo em áreas sem cobertura GNSS. Um Sistema de Navegação Inercial não depende de infraestrutura externa, exceto para inicializar suas variáveis, o que neste caso pode ser feito com auxílio de um receptor GPS. Sensores inerciais de alto desempenho são caros, tem alta complexidade mecânica e em geral são de grande porte. A alternativa é o uso de sensores do tipo MEMS que são pequenos, fáceis de serem manipulados e apresentam baixo consumo de energia. A contrapartida é que a solução é mais susceptível a ruído do que seus pares que custam na faixa de centena de milhões de dólares. / The proposal of this paper is to build an autonomous vehicle platform to enable the researches in this area by the Transport Engineering Department of the USP. Until now the Department has a platform that, once its initial position is known, it can navigate autonomously to a destination point using only the GNSS, in this case, GPS. To expand the mobility resources of the platform, it is being suggested here the addition of inertial sensors to the vehicle, enabling it to acquire a position solution even in areas where there is no coverage of the GNSS. An Inertial Navigation System does not depend on an external infra-structure, with the exception on the initial setup, where the GPS can be used to provide this kind of initialization. High performance inertial sensors are expensive, have high mechanical complexity and in general are big. The alternative is the usage of MEMS sensors, which are small, easy to handle and has low power consumption. In the opposite side this solution is more susceptible to noises in comparison to those High performance sensors that cost hundreds of thousands of dollars.

O projeto de mestrado, denominado de forma abreviada como GPUServices, se insere no contexto da pesquisa e do desenvolvimento de métodos de processamento de dados de sensores tridimensionais aplicados a robótica móvel. Tais métodos serão chamados de serviços neste projeto e incluem algoritmos de pré-processamento de nuvens de pontos 3D com segmentação dos dados, a separação e identificação de zonas planares (chão, vias), e detecção de elementos de interesse (bordas, obstáculos). Devido à grande quantidade de dados a serem tratados em um curto espaço de tempo, esses serviços utilizam processamento paralelo por GPU para realizar o processamento parcial ou completo destes dados. A área de aplicação em foco neste projeto visa prover serviços para um sistema ADAS: veículos autônomos e inteligentes, forçando-os a se aproximarem de um sistema de processamento em tempo real devido ao contexto de direção autônoma. Os serviços são divididos em etapas de acordo com a metodologia do projeto, mas sempre buscando a aceleração com o uso de paralelismo inerente: O pré-projeto consiste de organizar um ambiente que seja capaz de coordenar todas as tecnologias utilizadas e que explore o paralelismo; O primeiro serviço tem a responsabilidade de extrair inteligentemente os dados do sensor que foi usado pelo projeto (Sensor laser Velodyne de múltiplos feixes), que se mostra necessário devido à diversos erros de leitura e ao formato de recebimento, fornecendo os dados em uma estrutura matricial; O segundo serviço em cooperação com o anterior corrige a desestabilidade espacial do sensor devido à base de fixação não estar perfeitamente paralela ao chão e devido aos amortecimentos do veículo; O terceiro serviço separa as zonas semânticas do ambiente, como plano do chão, regiões abaixo e acima do chão; O quarto serviço, similar ao anterior, realiza uma pré-segmentação das guias da rua; O quinto serviço realiza uma segmentação de objetos do ambiente, separando-os em blobs; E o sexto serviço utiliza de todos os anteriores para a detecção e segmentação das guias da rua. Os dados recebidos pelo sensor são na forma de uma nuvem de pontos 3D com grande potencial de exploração do paralelismo baseado na localidade das informações. Porém, sua grande dificuldade é a grande taxa de dados recebidos do sensor (em torno de 700.000 pontos/seg.), sendo esta a motivação deste projeto: usar todo o potencial do sensor de forma eficiente ao usar o paralelismo de programação GPU, disponibilizando assim ao usuário serviços de tratamento destes dados. / The master\'s project, abbreviated hence forth as GPUServices, fits in the context of research and development of three-dimensional sensor data processing methods applied to mobile robotics. Such methods will be called services in this project, which include a 3D point cloud preprocessing algorithms with data segmentation, separation and identification of planar areas (ground track), and also detecting elements of interest (borders, barriers). Due to the large amount of data to be processed in a short time, these services should use parallel processing, using the GPU to perform partial or complete processing of these data. The application area in focus in this project aims to provide services for an ADAS system: autonomous and intelligent vehicles, forcing them to get close to a real-time processing system due to the autonomous direction of context.The services are divided into stages according to the project methodology, but always striving for acceleration using inherent parallelism: The pre-project consists of organizing an environment for development that is able to coordinate all used technologies, to exploit parallelism and to be integrated to the system already used by the autonomous car; The first service has a responsibility to intelligently extract sensor data that will be used by the project (Laser sensor Velodyne multi-beam), it appears necessary because of the many reading errors and the receiving data format, hence providing data in a matrix structure; The second service, in cooperation with the above, corrects the spatial destabilization due to the sensor fixing base not perfectly parallel to the ground and due to the damping of the vehicle; The third service separates the environment into semantics areas such as ground plane and regions below and above the ground; The fourth service, similar to the above, performs a pre-segmentation of street cruds; The fifth service performs an environmental objects segmentation, separating them into blobs; The sixth service uses all prior to detection and segmentation of street guides.The received sensor data is structured in the form of a cloud of points. They allow processing with great potential for exploitation of parallelism based on the location of the information. However, its major difficulty is the high rate of data received from the sensor (around 700,000 points/sec), and this gives the motivation of this project: to use the full potential of sensor to efficiently use the parallelism of GPU programming, therefore providing data processing services to the user, providing services that helps and make the implementation of ADAS systems easier and/or faster.

A proposta deste trabalho é contribuir com a construção de uma plataforma de veículo autônomo para viabilizar as pesquisas na área pelo Departamento de Engenharia de Transportes da USP. Até o momento o departamento dispõe de uma plataforma que, a partir de sua posição conhecida, consegue navegar autonomamente até um ponto de destino utilizando apenas uma solução GNSS, no caso, GPS. Para ampliar a mobilidade da plataforma, está sendo sugerida aqui, a adição de sensores inerciais ao veículo, para que ele consiga obter uma solução de posição mesmo em áreas sem cobertura GNSS. Um Sistema de Navegação Inercial não depende de infraestrutura externa, exceto para inicializar suas variáveis, o que neste caso pode ser feito com auxílio de um receptor GPS. Sensores inerciais de alto desempenho são caros, tem alta complexidade mecânica e em geral são de grande porte. A alternativa é o uso de sensores do tipo MEMS que são pequenos, fáceis de serem manipulados e apresentam baixo consumo de energia. A contrapartida é que a solução é mais susceptível a ruído do que seus pares que custam na faixa de centena de milhões de dólares. / The proposal of this paper is to build an autonomous vehicle platform to enable the researches in this area by the Transport Engineering Department of the USP. Until now the Department has a platform that, once its initial position is known, it can navigate autonomously to a destination point using only the GNSS, in this case, GPS. To expand the mobility resources of the platform, it is being suggested here the addition of inertial sensors to the vehicle, enabling it to acquire a position solution even in areas where there is no coverage of the GNSS. An Inertial Navigation System does not depend on an external infra-structure, with the exception on the initial setup, where the GPS can be used to provide this kind of initialization. High performance inertial sensors are expensive, have high mechanical complexity and in general are big. The alternative is the usage of MEMS sensors, which are small, easy to handle and has low power consumption. In the opposite side this solution is more susceptible to noises in comparison to those High performance sensors that cost hundreds of thousands of dollars.

O projeto de mestrado, denominado de forma abreviada como GPUServices, se insere no contexto da pesquisa e do desenvolvimento de métodos de processamento de dados de sensores tridimensionais aplicados a robótica móvel. Tais métodos serão chamados de serviços neste projeto e incluem algoritmos de pré-processamento de nuvens de pontos 3D com segmentação dos dados, a separação e identificação de zonas planares (chão, vias), e detecção de elementos de interesse (bordas, obstáculos). Devido à grande quantidade de dados a serem tratados em um curto espaço de tempo, esses serviços utilizam processamento paralelo por GPU para realizar o processamento parcial ou completo destes dados. A área de aplicação em foco neste projeto visa prover serviços para um sistema ADAS: veículos autônomos e inteligentes, forçando-os a se aproximarem de um sistema de processamento em tempo real devido ao contexto de direção autônoma. Os serviços são divididos em etapas de acordo com a metodologia do projeto, mas sempre buscando a aceleração com o uso de paralelismo inerente: O pré-projeto consiste de organizar um ambiente que seja capaz de coordenar todas as tecnologias utilizadas e que explore o paralelismo; O primeiro serviço tem a responsabilidade de extrair inteligentemente os dados do sensor que foi usado pelo projeto (Sensor laser Velodyne de múltiplos feixes), que se mostra necessário devido à diversos erros de leitura e ao formato de recebimento, fornecendo os dados em uma estrutura matricial; O segundo serviço em cooperação com o anterior corrige a desestabilidade espacial do sensor devido à base de fixação não estar perfeitamente paralela ao chão e devido aos amortecimentos do veículo; O terceiro serviço separa as zonas semânticas do ambiente, como plano do chão, regiões abaixo e acima do chão; O quarto serviço, similar ao anterior, realiza uma pré-segmentação das guias da rua; O quinto serviço realiza uma segmentação de objetos do ambiente, separando-os em blobs; E o sexto serviço utiliza de todos os anteriores para a detecção e segmentação das guias da rua. Os dados recebidos pelo sensor são na forma de uma nuvem de pontos 3D com grande potencial de exploração do paralelismo baseado na localidade das informações. Porém, sua grande dificuldade é a grande taxa de dados recebidos do sensor (em torno de 700.000 pontos/seg.), sendo esta a motivação deste projeto: usar todo o potencial do sensor de forma eficiente ao usar o paralelismo de programação GPU, disponibilizando assim ao usuário serviços de tratamento destes dados. / The master\'s project, abbreviated hence forth as GPUServices, fits in the context of research and development of three-dimensional sensor data processing methods applied to mobile robotics. Such methods will be called services in this project, which include a 3D point cloud preprocessing algorithms with data segmentation, separation and identification of planar areas (ground track), and also detecting elements of interest (borders, barriers). Due to the large amount of data to be processed in a short time, these services should use parallel processing, using the GPU to perform partial or complete processing of these data. The application area in focus in this project aims to provide services for an ADAS system: autonomous and intelligent vehicles, forcing them to get close to a real-time processing system due to the autonomous direction of context.The services are divided into stages according to the project methodology, but always striving for acceleration using inherent parallelism: The pre-project consists of organizing an environment for development that is able to coordinate all used technologies, to exploit parallelism and to be integrated to the system already used by the autonomous car; The first service has a responsibility to intelligently extract sensor data that will be used by the project (Laser sensor Velodyne multi-beam), it appears necessary because of the many reading errors and the receiving data format, hence providing data in a matrix structure; The second service, in cooperation with the above, corrects the spatial destabilization due to the sensor fixing base not perfectly parallel to the ground and due to the damping of the vehicle; The third service separates the environment into semantics areas such as ground plane and regions below and above the ground; The fourth service, similar to the above, performs a pre-segmentation of street cruds; The fifth service performs an environmental objects segmentation, separating them into blobs; The sixth service uses all prior to detection and segmentation of street guides.The received sensor data is structured in the form of a cloud of points. They allow processing with great potential for exploitation of parallelism based on the location of the information. However, its major difficulty is the high rate of data received from the sensor (around 700,000 points/sec), and this gives the motivation of this project: to use the full potential of sensor to efficiently use the parallelism of GPU programming, therefore providing data processing services to the user, providing services that helps and make the implementation of ADAS systems easier and/or faster.

A operação de veículos autônomos necessita de meios para evitar colisões quando obstáculos não conhecidos previamente são interpostos em sua trajetória. Algoritmos para executar o desvio e sensores apropriados para a detecção destes obstáculos são essenciais para a operação destes veículos. Esta dissertação apresenta estudos sobre quatro algoritmos de desvio de obstáculos e tecnologia de três tipos de sensores aplicáveis à operação de veículos autônomos. Após os estudos teóricos, um dos algoritmos foi testado para a comprovação da aplicabilidade ao veículo de teste. A etapa experimental foi a realização de um programa, escrito em linguagem de programação Java, que aplicou o algoritmo Inseto 2 para o desvio de obstáculos em uma plataforma robótica (Robodeck) com o uso de sensores ultrassônicos embarcados na referida plataforma. Os experimentos foram conduzidos em ambiente fechado (indoor), bidimensional e horizontal (plano), fazendo o Robodeck executar uma trajetória. Para os testes, obstáculos foram colocados para simular situações variadas e avaliar a eficácia do algoritmo nestas configurações de caminho. O algoritmo executou o desvio dos obstáculos com sucesso e, quando havia solução para a trajetória, ela foi encontrada. Quando não havia solução, o algoritmo detectou esta situação e parou o veículo. / The operation of autonomous vehicles need means to avoid collisions when unforeseen obstacles are posed in its trajectory. Algorithms to perform the deviation and suitable sensors for detecting these obstacles are essential for the operation of such vehicles. This dissertation presents studies on four obstacle avoidance algorithms and technology of three types of sensors applicable to the operation of autonomous vehicles. After the theoretical studies, one of the algorithms has been tested for evidence of applicability to the test vehicle. The experimental phase was the implementation of a program written in Java programming language, which applied the Insect 2 algorithm for obstacle avoidance in a robotic platform (Robodeck) using ultrasonic sensors embedded in the platform. The experiments were conducted in a closed environment (indoor), two-dimensional and flat, making Robodeck perform a trajectory. For testing, obstacles were placed to simulate various situations and evaluating the algorithm efficacy for these path configurations. The algorithm successfully performed the deviation of obstacles and, when there was a solution to the trajectory, it was found. When there was no solution, the algorithm has detected this situation and stopped the vehicle.

A operação de veículos autônomos necessita de meios para evitar colisões quando obstáculos não conhecidos previamente são interpostos em sua trajetória. Algoritmos para executar o desvio e sensores apropriados para a detecção destes obstáculos são essenciais para a operação destes veículos. Esta dissertação apresenta estudos sobre quatro algoritmos de desvio de obstáculos e tecnologia de três tipos de sensores aplicáveis à operação de veículos autônomos. Após os estudos teóricos, um dos algoritmos foi testado para a comprovação da aplicabilidade ao veículo de teste. A etapa experimental foi a realização de um programa, escrito em linguagem de programação Java, que aplicou o algoritmo Inseto 2 para o desvio de obstáculos em uma plataforma robótica (Robodeck) com o uso de sensores ultrassônicos embarcados na referida plataforma. Os experimentos foram conduzidos em ambiente fechado (indoor), bidimensional e horizontal (plano), fazendo o Robodeck executar uma trajetória. Para os testes, obstáculos foram colocados para simular situações variadas e avaliar a eficácia do algoritmo nestas configurações de caminho. O algoritmo executou o desvio dos obstáculos com sucesso e, quando havia solução para a trajetória, ela foi encontrada. Quando não havia solução, o algoritmo detectou esta situação e parou o veículo. / The operation of autonomous vehicles need means to avoid collisions when unforeseen obstacles are posed in its trajectory. Algorithms to perform the deviation and suitable sensors for detecting these obstacles are essential for the operation of such vehicles. This dissertation presents studies on four obstacle avoidance algorithms and technology of three types of sensors applicable to the operation of autonomous vehicles. After the theoretical studies, one of the algorithms has been tested for evidence of applicability to the test vehicle. The experimental phase was the implementation of a program written in Java programming language, which applied the Insect 2 algorithm for obstacle avoidance in a robotic platform (Robodeck) using ultrasonic sensors embedded in the platform. The experiments were conducted in a closed environment (indoor), two-dimensional and flat, making Robodeck perform a trajectory. For testing, obstacles were placed to simulate various situations and evaluating the algorithm efficacy for these path configurations. The algorithm successfully performed the deviation of obstacles and, when there was a solution to the trajectory, it was found. When there was no solution, the algorithm has detected this situation and stopped the vehicle.

A navegação autônoma é um dos problemas fundamentais na área de robótica móvel. Esse problema vem sendo pesquisado nessa área por décadas e ainda apresenta um grande potencial para pesquisas científicas. A maior parte dos algoritmos e soluções desenvolvidas nessa área foi concebida para que robôs operem em ambientes estruturados. No entanto, outra questão de grande interesse para pesquisadores da área é a navegação em ambientes externos. Em ambientes não estruturado os veículos autônomos (robôs de grande porte) devem ser capazes de desviar de obstáculos, que eventualmente apareçam no caminho. Esta dissertação aborda o desenvolvimento de um sistema inteligente capaz de gerar e executar um planejamento de caminho para o estacionamento de veículos autônomos em ambientes semi-estruturados. O sistema é capaz de reconhecer vagas de estacionamento por meio de sensores instalados no veículo, gerar uma trajetória válida que o conduza até a vaga e enviar os comandos de esterçamento e aceleração que guiam o veículo pelo caminho gerado / Autonomous navigation is one of the fundamental problems in mobile robotics. This problem has been addressed for decades and still has great potential for scientific research. Most solutions and algorithms developed in this field is designed for robots that operate in structured environments. However, another issue of great interest to researchers in this area is autonomous navigation in outdoor environments. In partially structured environments autonomous vehicles (large robots) must be able to avoid obstacles that may arise along the way. This dissertation addresses the development of an intelligent system able to generate and run a path planning for parking of autonomous vehicles in semi-structured environments. The system is able to recognize parking lots using sensors installed in the vehicle, generate a valid path that leads up to the parking lot and send the steering commands and acceleration that to guide the vehicle to its goal point

O emprego de veículos terrestres autônomos tem se tornado cada vez mais comum nos últimos anos em aplicações civis e militares. Eles podem ser úteis para as pessoas com necessidades especiais e para reduzir os acidentes de trânsito e o número de baixas em combate. Esta tese aborda o problema da classificação de obstáculos e da localização do veículo em relação a um mapa topológico, sem fazer uso de GPS e de mapas digitais detalhados. Um sensor laser 3D é usado para coletar dados do ambiente. O sistema de classificação de obstáculos extrai as features da nuvem de pontos e usam-nas para alimentar um classificador que separa os dados em quatro classes: veículos, pessoas, construções, troncos de árvores e postes. Durante a extração de features, um método original para transformar uma nuvem 3D em um grid 2D é proposto, o que ajuda a reduzir o tempo de processamento. As interseções de vias de áreas urbanas são detectadas e usadas como landmarks em um mapa topológico. O sistema consegue obter a localização do veículo, utilizando os pontos de referência, e identifica as mudanças de direção do veículo quando este passa pelos cruzamentos. Os experimentos demonstraram que o sistema foi capaz de classificar corretamente os obstáculos e localizar-se sem o uso de sinais de GPS. / The employment of autonomous ground vehicles, both in civilian and military applications, has become increasingly common over the past few years. Those vehicles can be helpful for disabled people and also to reduce traffic accidents. In this thesis, approaches to the problem of obstacles classification and the localization of the vehicle in relation to a topologic map are presented. GPS devices and previous digital maps are not employed. A 3D laser sensor is used to collect data from the environment. The obstacle classification system extracts features from point clouds and uses them to feed a classifier which separates data into four classes: vehicle, people, building and light poles/ trees. During the feature extraction, an original method to transform 3D to 2D data is proposed, which helps to reduce the processing time. Crossing roads are detected and used as landmarks in a topological map. The vehicle performs self-localization using the landmarks and identifying direction changes through the crossing roads. Experiments demonstrated that system was able to correctly classify obstacles and to localize itself without using GPS signals.

O emprego de veículos terrestres autônomos tem se tornado cada vez mais comum nos últimos anos em aplicações civis e militares. Eles podem ser úteis para as pessoas com necessidades especiais e para reduzir os acidentes de trânsito e o número de baixas em combate. Esta tese aborda o problema da classificação de obstáculos e da localização do veículo em relação a um mapa topológico, sem fazer uso de GPS e de mapas digitais detalhados. Um sensor laser 3D é usado para coletar dados do ambiente. O sistema de classificação de obstáculos extrai as features da nuvem de pontos e usam-nas para alimentar um classificador que separa os dados em quatro classes: veículos, pessoas, construções, troncos de árvores e postes. Durante a extração de features, um método original para transformar uma nuvem 3D em um grid 2D é proposto, o que ajuda a reduzir o tempo de processamento. As interseções de vias de áreas urbanas são detectadas e usadas como landmarks em um mapa topológico. O sistema consegue obter a localização do veículo, utilizando os pontos de referência, e identifica as mudanças de direção do veículo quando este passa pelos cruzamentos. Os experimentos demonstraram que o sistema foi capaz de classificar corretamente os obstáculos e localizar-se sem o uso de sinais de GPS. / The employment of autonomous ground vehicles, both in civilian and military applications, has become increasingly common over the past few years. Those vehicles can be helpful for disabled people and also to reduce traffic accidents. In this thesis, approaches to the problem of obstacles classification and the localization of the vehicle in relation to a topologic map are presented. GPS devices and previous digital maps are not employed. A 3D laser sensor is used to collect data from the environment. The obstacle classification system extracts features from point clouds and uses them to feed a classifier which separates data into four classes: vehicle, people, building and light poles/ trees. During the feature extraction, an original method to transform 3D to 2D data is proposed, which helps to reduce the processing time. Crossing roads are detected and used as landmarks in a topological map. The vehicle performs self-localization using the landmarks and identifying direction changes through the crossing roads. Experiments demonstrated that system was able to correctly classify obstacles and to localize itself without using GPS signals.

A navegação autônoma é um dos problemas fundamentais na área de robótica móvel. Esse problema vem sendo pesquisado nessa área por décadas e ainda apresenta um grande potencial para pesquisas científicas. A maior parte dos algoritmos e soluções desenvolvidas nessa área foi concebida para que robôs operem em ambientes estruturados. No entanto, outra questão de grande interesse para pesquisadores da área é a navegação em ambientes externos. Em ambientes não estruturado os veículos autônomos (robôs de grande porte) devem ser capazes de desviar de obstáculos, que eventualmente apareçam no caminho. Esta dissertação aborda o desenvolvimento de um sistema inteligente capaz de gerar e executar um planejamento de caminho para o estacionamento de veículos autônomos em ambientes semi-estruturados. O sistema é capaz de reconhecer vagas de estacionamento por meio de sensores instalados no veículo, gerar uma trajetória válida que o conduza até a vaga e enviar os comandos de esterçamento e aceleração que guiam o veículo pelo caminho gerado / Autonomous navigation is one of the fundamental problems in mobile robotics. This problem has been addressed for decades and still has great potential for scientific research. Most solutions and algorithms developed in this field is designed for robots that operate in structured environments. However, another issue of great interest to researchers in this area is autonomous navigation in outdoor environments. In partially structured environments autonomous vehicles (large robots) must be able to avoid obstacles that may arise along the way. This dissertation addresses the development of an intelligent system able to generate and run a path planning for parking of autonomous vehicles in semi-structured environments. The system is able to recognize parking lots using sensors installed in the vehicle, generate a valid path that leads up to the parking lot and send the steering commands and acceleration that to guide the vehicle to its goal point