Orientador: Prof. Dr. Rovílson Mafalda. / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Engenharia e Gestão da Inovação, 2018. / Nas últimas décadas, o problema da navegação autônoma tem sido o principal foco da robótica móvel. Este problema consiste em gerar trajetórias para guiar o deslocamento do robô num determinado ambiente a partir de informações provenientes de sistemas de sensores externos e/ou de informações constantes no mapa do ambiente. A partir destes pode saber sua localização e movimentar-se para quaisquer pontos do ambiente de trabalho de maneira segura, evitando colisões e regiões onde não há espaço suficiente para sua travessia. O planejamento de trajetórias é parte fundamental para o deslocamento de robôs móveis. A elaboração de um plano para movimentação autônoma é uma tarefa complexa. O planejamento de caminhos está relacionado ao planejamento geométrico da movimentação do robô no ambiente. Já o planejamento de trajetória é responsável por baseado no planejamento de caminhos, atuar sobre a movimentação dinâmica do robô [1]. A forma como o ambiente é mapeado no sistema é determinante na sua precisão e desempenho. Dentro deste contexto, neste trabalho é proposto um método para planejamento de caminhos para robôs móveis, considerando um ambiente interno, estruturado e estático, onde o ambiente e os obstáculos, entre os quais estes se movem, estão modelados como um Diagrama de Voronói para Circunferências. Algoritmos com a finalidade de encontrar o caminho de menor distância entre os caminhos disponíveis no mapa do ambiente discretizado de acordo com a modelagem acima são estudados e avaliados. Esta pesquisa também envolve estudos sobre problemas de tangências entre circunferências, estudos sobre a representação matemática do Diagrama de Voronoi e estudos sobre otimização de caminhos sobre estes Diagramas. / Over the last decades, researches in mobile robotics has focused on autonomous navigation problem. This problem consists on generating trajectories to guide the movement of a robot from a start point to an end point in a determined local. It is based on data from external sensor systems and /or information of the environment map. From this information, the robot is able to know its location and to move to another point in the working environment in a safe path, avoiding collisions and regions where there is not enough space for crossing. Trajectory planning is a fundamental part for movement of mobile robots. To elaborate a path planning for autonomous displacement is a complex task. Path planning relates to the geometric planning of robot movement in the environment. Already the trajectory planning is responsible for, based on path planning, to act on a dynamic movement of the robot. The approach applied to model an environment is determinant over accuracy and performance of a trajectory system. Within this context, in this work it is proposed a method to plan routes for mobile robots, where the environment map is model as a Voronói Diagram for Circumferences. Searching algorithms with the purpose of finding the shortest routes between the paths available in the map are studied and analyzed. This research also involves studies on circumferential tangency problems, studies on the mathematical representation of the Voronoi Diagram, and studies on path optimization on these Diagrams.

A Robótica tem iniciado uma transição de Robótica Industrial para Robótica de Serviço, movendo-se em direção as necessidades diárias dos seres humanos. Para realizar essa transição, robôs necessitam de mais autonomia para executar tarefas em espaços dinâmicos ocupados por humanos, diferente dos ambientes controlados das fábricas. Nesta tese, é investigado um problema no qual um time de robôs completamente autônomos deve visitar certos locais em um ambiente interno usado por humanos a fim de executar algum tipo de tarefa. Este problema está relacionado a três importantes questões da Robótica e Inteligência Artificial (IA), que são: coordenação, localização e navegação. Para coordenar as visitas nos locais desejados, um escalonamento deve ser realizado para encontrar as rotas para os robôs. Tal escalonamento deve minimizar a distância total viajada pelo time e também balancear as rotas. Este problema pode ser modelado como sendo uma instância do Problema dos Múltiplos Caixeiros Viajantes (PMCV). Como este problema é classificado como NP-Difícil, é proposto o uso de algoritmos aproximados para encontrar soluções satisfatórias para o problema. Uma vez que as rotas estão computadas, os robôs necessitam de se localizar no ambiente para que eles tenham certeza de que estão visitando os lugares corretos. Muitas técnicas de localização não são muito precisas em ambientes internos devido a diferentes tipos de ruídos. Desta forma, é proposto uma combinação de duas delas. Nesta abordagem, um algoritmo de localização WiFi rastreia a localização global do robô, enquanto um algoritmo de localização Kinect estima sua posição atual dentro da área delimitada pela localização global. Depois de visitar um dado local de sua rota, o robô deve navegar em direção ao próximo. A navegação em ambientes internos ocupados por humanos é uma tarefa difícil, uma vez que muitos objetos móveis e dinâmicos podem ser encontrados no caminho. Para isso, o robô deve possuir controles reativos para evitar colidir com objetos dinâmicos, como pessoas, enquanto ele navega. Além disso, objetos móveis, como mobílias, são passíveis de serem movidos frequentemente, o que muda o mapa utilizado para planejar o caminho do robô. Para resolver estes problemas, é proposto um algoritmo de desvio de obstáculos e um planejador dinâmico de caminho para ambientes internos ocupados por humanos. Desta forma, esta tese contribui com uma série de algoritmos para os problemas de coordenação, localização e navegação. São introduzidos: Algoritmos Genéticos (AGs) multi-objetivo para resolver o Problema dos Múltiplos Caixeiros Viajantes, abordagens de localização que utilizam a técnica de Filtro de Partículas (FP) com dispositivos Kinect e WiFi, um Sistema Híbrido Inteligente (SHI) baseado em Lógica Fuzzy (LF) e Redes Neuronais Artificiais (RNA) para desvio de obstáculos e uma adaptação do algoritmo D*Lite que permite o robô replanejar caminhos de forma eficiente e requisitar auxílio humano se necessário. Todos os algoritmos são avaliados em robôs reais e simuladores, demonstrando seus desempenhos em resolver os problemas abordados nesta tese. / Robotics has started the transition from industrial into service robotics, moving closer towards humans daily needs. To accomplish this transition, robots require more autonomy to perform tasks in dynamic spaces occupied by humans, different from well controlled environments of factory floors. In this thesis, we investigate a problem in which a team of completely autonomous robots needs to visit certain locations in an indoor human environment in order to perform some kind of task. This problem is related to three important issues of Robotics and \ac{AI}, namely: coordination, localization and navigation. To coordinate the visits in the desired locations, a scheduling must be performed to find routes for the robots. Such scheduling needs to minimize the total distance traveled by the team and also to balance the routes. We model this problem as being an instance of the multiple Traveling Salesmen Problem (mTSP). Since it is classified as NP-Hard, we propose the use of approximation algorithms to find reasonable solutions to the problem. Once the routes are computed, the robots need to localize themselves in the environment so they can be sure that they are visiting the right places. Many localization techniques are not very accurate in indoor human environments due to different types of noise. Therefore, we propose the combination of two of them. In such approach, a WiFi localization algorithm tracks the global location of the robot while a Kinect localization algorithm estimates its current pose on that area. After visiting a given location of its route, the robot must navigate towards the next one. Navigation in indoor human environments is a challenging task as many moving and movable objects can be found in the way. The robot should be equipped with a reactive controller to avoid colliding with moving objects, like people, while it is navigating. Also, movable objects, such as furniture, are likely to be moved frequently, which changes the map used to plan the robot's path. To tackle these problems, we introduce an obstacle avoidance algorithm and a dynamic path planner for navigation in indoor human environments. We contribute a series of algorithms for the problems of coordination, localization, and navigation. We introduce: multi-objective Genetic Algorithms (GAs) to solve the mTSP, localization approaches that use Particle Filters (PFs) with Kinect and WiFi devices, a Hybrid Intelligent System (HIS) based on Fuzzy Logic (FL) and Artificial Neural Network (ANN) for obstacle avoidance, and an adaptation to the D*Lite algorithm that enables robots to replan paths efficiently and also ask for human assistance if it is necessary. All algorithms are evaluated on real robots and simulators, demonstrating their performances to solve the problems addressed in this thesis. / Tese (Doutorado)