Made available in DSpace on 2016-08-29T15:33:20Z (GMT). No. of bitstreams: 1 tese_8364_dissertacao_stefano.pdf: 2078703 bytes, checksum: b7e3e083f76858033ffbf089d0223c49 (MD5) Previous issue date: 2014-11-27 / Utilizar robos autônomos capazes de planejar o seu caminho é um desafio que atrai vários pesqui quisadores na área de navegação de robôs. Neste contexto, este trabalho tem como objetivo implementar um algoritmo PSO híbrido para o planejamento de caminhos em ambientes dinâmicos. O mundo é discretizado em forma de mapas ladrilhados e cada quadrado representa ou não um obstáculo. O algoritmo proposto possui duas fases: a primeira utiliza o algoritmo A* para encontrar uma trajetória inicial viável que o algoritmo PSO otimiza na segunda fase. O ambiente de simulação de robótica CARMEN (Carnegie Mellon Robot Navigation Toolkit) foi utilizado para realização de todos os experimentos computacionais considerando cinco mapas gerados artificialmente com obstáculos estáticos ou dinâmicos. A análise dos resultados indicou que o algoritmo PSO híbrido proposto superou em qualidade de solução o PSO convencional, para essas instâncias.

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

Este trabalho aborda o problema de planejamento de caminhos em robótica móvel autônoma utilizando campos potenciais. Dentre as várias técnicas de campos potenciais para controlar robôs, encontram-se as técnica de Campos Potenciais de Khatib1 (CP), Campo Potencial Harmônico (CPH), Campo Potencial Orientado (CPO) e Campo Potencial Localmente Orientado (CPLO). As técnicas CPH, CPO e CPLO são chamadas de técnicas baseadas em Problema de Valor de Contorno (PVC), pois são obtidas a partir de soluções de Equações Diferenciais Parciais (EDP) Elípticas em uma determinada condição de contorno, é obtido um sistema planejador de caminhos. Tais técnicas necessitam de uma etapa de solução de sistemas lineares, na qual se utiliza métodos iterativos, decorrentes da aplicação do método de diferenças finitas como solucionador das EDP. No presente trabalho, as técnicas de Campos Potenciais baseados em PVC foram estudadas e implementadas (usando processamento sequencial e paralelo), de modo a obter resultados de forma mais rápida e confiável. Foram utilizadas arquiteturas paralelas do tipo manycore. Finalmente, são feitas análises comparativas entre os vários métodos implementados. Todos os métodos estão prontos para serem incorporados tanto no simulador quanto nos times de robôs em desenvolvimento pelo grupo Warthog Robotics / This works details the task o path planning in autonomous mobile robots using potential fields techniques. Among potential fields techniques to control robots, there are Khatibs Potential Field2 (KPF), Harmonic Potential Field (HPF), Oriented Potential Field (OPF) and Locally Oriented Potential Field (LOPF). The HPF, OPF and LOPF techniques are called Boundary Value Problem (BVP) based, bacause they are obtained from numerical solutions of Elliptic Partial Differential Equations (PDE) in a well-defined boundary condition. These techniques go through a step of solving linear systems, in which is used iterative methods, that came from numerical solution of PDE. In this work, potential fields BVP based was studied and coded (using sequential and parallel architectures), to obtain results more quickly and reliably. And, finally, a comparative analyses of the various methods implemented are made. All methods are ready to be incorporated in the intelligent systens that are being developed by Warthog Robotics

O planejamento probabilístico de mapa de rotas tem se mostrado uma poderosa ferramenta para o planejamento de caminhos para robôs móveis, devido a sua eficiência computacional, simplicidade de implementação e escalabilidade em diferentes problemas. Este método de planejamento possui duas fases. Na fase de construção, um mapa de rotas é gerado de forma iterativa e incremental, e armazenado na forma de um grafo G, cujos vértices são configurações livres, amostradas no espaço de configurações do robô e cujas arestas correspondem a caminhos livres de colisão entre tais configurações. Na fase de questionamento, dadas quaisquer configurações de origem e destino, \'alfa\' e \'beta\' respectivamente, o planejador conecta \'alfa\' e \'beta\' à G inserindo arestas que correspondem a caminhos livres de colisão, para então procurar por um caminho entre \'alfa\' e \'beta\' em G. Neste trabalho o foco reside principalmente na fase de construção do mapa de rotas. O objetivo aqui consiste em efetuar uma análise comparativa de diversas combinações de diferentes técnicas de amostragem das configurações livres e de diferentes técnicas de seleção de vértices em G, todas implementadas em um único sistema e aplicadas aos mesmos cenários. Os resultados propiciam um valioso auxílio aos usuários do planejamento probabilístico de mapas de rotas na decisão da melhor combinação para suas aplicações. / The probabilistic roadmap planning has emerged as a powerful framework for path planning of mobile robots due to its computational efficiency, implementation simplicity, and scalability in different problems. This planning method proceeds in two phases. In the construction phase a roadmap is incrementally constructed and stored as a graph G whose nodes are free configurations sampled on the robot\'s configuration space and whose edges correspond to collision-free paths between these configurations. In the query phase, given any start and goal configurations, \'alfa\' and \'beta\' respectively, the planner first connects \'alfa\' and \'beta\' to G by adding edges that correspond to collision-free paths, and then searches for a path in G between \'alfa\' and \'beta\'. In this work, we address mainly the roadmap construction phase. The goal here is to provide a comparative analysis of a number of combinations of different techniques for sampling free configurations and different node adding techniques, all implemented in a single system and applied to the same test workspace. Results help probabilistic roadmap planning users to choose the best combination for their applications.

Este trabalho aborda o problema de planejamento de caminhos em robótica móvel autônoma utilizando campos potenciais. Dentre as várias técnicas de campos potenciais para controlar robôs, encontram-se as técnica de Campos Potenciais de Khatib1 (CP), Campo Potencial Harmônico (CPH), Campo Potencial Orientado (CPO) e Campo Potencial Localmente Orientado (CPLO). As técnicas CPH, CPO e CPLO são chamadas de técnicas baseadas em Problema de Valor de Contorno (PVC), pois são obtidas a partir de soluções de Equações Diferenciais Parciais (EDP) Elípticas em uma determinada condição de contorno, é obtido um sistema planejador de caminhos. Tais técnicas necessitam de uma etapa de solução de sistemas lineares, na qual se utiliza métodos iterativos, decorrentes da aplicação do método de diferenças finitas como solucionador das EDP. No presente trabalho, as técnicas de Campos Potenciais baseados em PVC foram estudadas e implementadas (usando processamento sequencial e paralelo), de modo a obter resultados de forma mais rápida e confiável. Foram utilizadas arquiteturas paralelas do tipo manycore. Finalmente, são feitas análises comparativas entre os vários métodos implementados. Todos os métodos estão prontos para serem incorporados tanto no simulador quanto nos times de robôs em desenvolvimento pelo grupo Warthog Robotics / This works details the task o path planning in autonomous mobile robots using potential fields techniques. Among potential fields techniques to control robots, there are Khatibs Potential Field2 (KPF), Harmonic Potential Field (HPF), Oriented Potential Field (OPF) and Locally Oriented Potential Field (LOPF). The HPF, OPF and LOPF techniques are called Boundary Value Problem (BVP) based, bacause they are obtained from numerical solutions of Elliptic Partial Differential Equations (PDE) in a well-defined boundary condition. These techniques go through a step of solving linear systems, in which is used iterative methods, that came from numerical solution of PDE. In this work, potential fields BVP based was studied and coded (using sequential and parallel architectures), to obtain results more quickly and reliably. And, finally, a comparative analyses of the various methods implemented are made. All methods are ready to be incorporated in the intelligent systens that are being developed by Warthog Robotics

[pt] Há muitas aplicações de realidade virtual que requerem navegação em ambientes 3D. Em geral, esta facilidade é oferecida permitindo que o usuário controle todos os seis graus de liberdade da câmera virtual. No entanto, dessa forma é difícil, mesmo para usuários experientes, chegar a áreas de interesse com movimentos suaves e livres de colisão. Torna-se necessário prover uma navegação assistida, onde o usuário guia a câmera mais facilmente, sem restringir sua exploração do ambiente. Além disso, é interessante prover uma navegação totalmente automática, onde o usuário seleciona um alvo e o sistema calcula um caminho suave e livre de colisões através do ambiente. Este trabalho propõe uma solução específica para navegação em modelos usados para simulação numérica de reservatórios naturais de petróleo, baseada em grafos de guia probabilísticos. Utilizados comumente em aplicações de robótica, grafos de guia probabilísticos visam capturar, através de uma amostragem aleatória, a conectividade das áreas livres da cena, sendo construídos em pré-processamento e consultados em tempo de execução. Este trabalho propõe um algoritmo de construção de grafo de guia específico para reservatórios e duas técnicas para utilizar o grafo obtido como base para prover navegação automática e navegação assistida. / [en] There are many virtual reality applications that require navigation on 3D environments. Usually, this feature is offered by allowing the user to control all the six degrees of freedom of the virtual camera. However, it is difficult in this way, even for experienced users, to reach areas of interest with smooth and collision-free paths. It becomes necessary to provide an assisted navigation, in which the user guides the camera more easily, without restricting the environment exploration. Moreover, it is interesting to provide a fully automatic navigation, in which the user selects a target and the system computes a smooth, collision-free path throughout the environment. This work proposes a specific solution for navigation on models used in numerical simulations of black oil reservoirs, based on probabilistic roadmaps. Commonly used in robotics applications, probabilistic roadmaps tend to capture, by random sampling, the conectivity of the free space of the scene, being constructed in a pre-processing stage and queried in execution time. This work proposes a roadmap construction algorithm specific to reservoirs and two techniques to use the obtained roadmap as the basis to provide assisted and automatic navigation.

Nos últimos anos, a área de robôs aéreos vêm se tornando cada vez mais importantes no dia-a-dia, em diversos usos, em que se pode destacar: segurança pública e particular, agricultura de precisão, registro fotográfico de eventos, serviços de entregas e apoio a diversas outras áreas, como monitoramento ambiental.Para que tais robôs aéreos possam cumprir suas mais variadas tarefas, faz-se necessária uma etapa de planejamento de movimento, que consiste em encontrar um caminho factível entre a postura atual e uma postura final (também chamada de postura alvo ou meta) do robô aéreo. Neste trabalho, a tarefa de planejamento de movimento é abordada para o caso tridimensional em ambientes dinâmicos, nos quais não se assume que todos os obstáculos permanecerão fixos ao longo do trajeto. Derivado da Teoria de Campos Potenciais Harmônicos, os Campos Potenciais Modificados (CPM) permitem a distorção do campo potencial favorecendo uma direção específica de chegada a postura meta. Tais CPM resultam em um planejador de movimentos para ambientes dinâmicos e multidimensionais, em especial, o caso tridimensional. / In recent years, aerial robots have become increasingly important in day-to-day situations, in several uses, in which we can highlight: public and private security, precision agriculture, photographic record of events, delivery and support to several other areas, such as environmental monitoring. In order for aerial robots perform their broad range of tasks, a motion planning step is necessary. Motion planning consists in finding a feasible path between the current posture and a final posture (also called target posture or goal) of a robot. In this work, the task of motion planning is approached in three-dimensional and dynamic environments, in which it is not assumed that all the obstacles will remain fixed along the trajectory. Derived from Harmonic Potential Field Theory, Modified Potential Fields (MPF) allows a controlled distortion of the potential field, as an example, towards a specific direction of arrival to the target posture. Such MPF results in a motion planner for dynamic and multidimensional environments, especially the three-dimensional case.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-03-14T21:32:46Z No. of bitstreams: 1 DaviHenriqueDosSantos_DISSERT.pdf: 3943405 bytes, checksum: 5c8c6264a12d6d09afccf8adb3614371 (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-03-15T22:17:57Z (GMT) No. of bitstreams: 1 DaviHenriqueDosSantos_DISSERT.pdf: 3943405 bytes, checksum: 5c8c6264a12d6d09afccf8adb3614371 (MD5) / Made available in DSpace on 2017-03-15T22:17:57Z (GMT). No. of bitstreams: 1 DaviHenriqueDosSantos_DISSERT.pdf: 3943405 bytes, checksum: 5c8c6264a12d6d09afccf8adb3614371 (MD5) Previous issue date: 2016-07-13 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior (CAPES) / As pesquisas relacionadas ? automa??o de veleiros rob?ticos cresceram rapidamente nos ?ltimos 15 anos. Os principais desafios enfrentados nos projetos de veleiros aut?nomos s?o o controle, planejamento de caminho e trajet?ria, coleta de dados dos sensores e o suprimento energ?tico. Desta forma, o presente trabalho realiza um estudo sobre problemas de controle e planejamento de caminho comumente encontrados durante o projeto de veleiros aut?nomos. Os m?todos aqui desenvolvidos ser?o aplicados nos veleiros utilizados no projeto N-Boat, permitindo aos mesmos alcan?ar os pontos alvos, realizando a dif?cil tarefa de velejar contra o vento caso necess?rio. Para alcan?ar estes objetivos, primeiramente um m?todo para encontrar o controlador de baixo n?vel mais adequado ? aplica??o desejada foi desenvolvido. O m?todo utiliza um controlador PI com par?metros vari?veis, encontrando uma tabela que cont?m os melhores par?metros proporcional e integrativo adequados a cada situa??o, de acordo com o modelo utilizado. Um m?todo para a gera??o de caminho em situa??es de contravento foi modelado, implementado e testado em simula??o. Para gerar os pontos do caminho, o m?todo utiliza dois par?metros: a dist?ncia dispon?vel e a orienta??o desejada para o veleiro durante a manobra. Em seguida, um m?todo de otimiza??o foi implementado e testado em simula??o. O m?todo utiliza algoritmos gen?ticos para manipular os par?metros do m?todo de gera??o de caminhos, encontrando quais par?metros geram o trajeto de menor tempo ao destino. O trabalho apresenta diversos testes em simula??o para demonstrar a validade e robustez dos m?todos desenvolvidos. / The main challenges in the development of autonomous sailboats are: control, path and trajectory planning, sensor data acquitision, and power supply. Towards this direction, this paper introduces a study on the problems of control and path planning commonly found during the autonomous sailing projects. The methods developed here are to be applied in the sailboats used in the N-Boat project, allowing them to reach targets points accurately and quickly, and to perform one of the must difficult tasks in sailing that is navigating against the wind. To achieve these goals, at first, a method to find the most appropriate low level controller for the desired application is developed. This method uses a dynamic PI controller, coming up with a table that contains the best proportional and integrative parameters that are appropriate to each situation according to the model used. A method for generation of paths in situations contrary to wind is also modeled, implemented and tested (in simulation). To generate the way points, this method takes into account two parameters: the distance available for the maneuvering and the desired orientation of the boat during the maneuver. An optimization method is proposed, based on genethic algorithm, implemented, and also tested (in simulation) for getting the controller best parameters. The method manipulate some defined parameters for generating paths, finding the ones that generate the path in which the boat achieves the minimum time to destination. Results of various simulation experiments are shown to demonstrate the validity and robustness of the methods developed.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-03-27T13:16:05Z No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-03-27T13:40:24Z (GMT) No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) / Made available in DSpace on 2018-03-27T13:40:24Z (GMT). No. of bitstreams: 1 fabriciodeoliveiracoelho.pdf: 19075776 bytes, checksum: 5f9c07d95c6d348d64825d66fda1c6f3 (MD5) Previous issue date: 2018-02-08 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Esse trabalho apresenta uma metodologia para a concepção de missões autônomas utilizando robôs móveis com tração diferencial em ambientes internos. As missões consistem em deslocar o robô até uma posição objetivo partindo de uma pose inicial. Para que as missões ocorram com sucesso, são implementados algoritmos de localização e planejamento de caminhos. Para localização, foi utilizado Filtro de Kalman Estendido (do inglês, Extended Kalman Filter EKF) para fundir a odometria com visão computacional. A visão é responsável por encontrar marcadores artificiais conhecidos como Ar codes que são alocados no ambiente. O planejamento é caracterizado por uma forma híbrida que corresponde a união de um método deliberativo e reativo. No Planejamento deliberativo, foi proposto e utilizado o método Direct-DRRT* cuja base é oriunda do RRT (Rapidly Exploring Random Tree). Além do RRT, esse planejador também apresenta características de dois outros métodos já presentes na literatura: RRT* e DRRT. O planejador deliberativo enviará para o reativo um conjunto de sub-objetivos que conecta a posição em que o robô se encontra até o objetivo final. O planejamento reativo é aplicado durante a missão e é o responsável pelo desvio de obstáculos dinâmicos que não foram mapeados. No Reativo, é utilizado o método dos Campos Potenciais Artificiais (CPA), que também se comporta como o controlador do robô durante a navegação. Para encontrar os obstáculos, utilizou-se o sensor de profundidade Asus Xtion, pois, a partir das imagens geradas por esse sensor, é possível encontrar as distâncias que os bloqueios se encontram. As informações desse sensor também será de grande valia na atualização do mapa. O sistema é integrado através da framework ROS (Robot Operating System). Todos os algoritmos foram implementados por meio da linguagem de programação Python. Os resultados do trabalho foram apresentados por meio do simulador Gazebo e testes práticos a partir da plataforma P3DX. Foram analisados o comportamento do robô em alguns problemas que podem ocorrer durante a navegação, como o sequestro e aparecimento mínimos locais. Ao final desse trabalho, apresentou-se a melhoria nos resultados do planejador de caminhos Direct-DRRT*, onde foi possível constatar a queda no tempo para obter um caminho, a quantidade de iterações, de nós e do comprimento do caminho em comparação aos outros métodos. No que tange à localização, essa dissertação obteve significativas melhoras comparado com o método que utiliza somente a odometria. Além desse resultado, esse trabalho também obteve sucesso em apresentar uma solução para a implementação de missões autônomas. / This work presents a design methodology for autonomous missions using mobile robots with differential traction in indoor environments. The missions consist of moving the robot to a goal position starting from an initial pose. For missions success, it is necessary to implement localization and path planning algorithms. For localization, Extended Kalman Filters (EKF) used to fuse odometry with computational vision. The view is responsible for finding artificial markers known as Ar codes that are presented in the environment. The planning is characterized by a hybrid form that corresponds to the union of a deliberative and reactive methods. In the Deliberative Planning, the Direct-DRRT * method, whose base is derived from the Rapidly Exploring Random Tree (RRT), is proposed and used. In addition to the RRT, this planner also presents characteristics of two other methods already presented in the literature, i.e. RRT * and DRRT. The deliberative planner sends to the reactive a set of sub-objectives that connects the initial position to the final goal. Reactive planning is applied during the mission and it is responsible for the dynamic obstacles avoidance that have not been mapped. In the reactive, the Artificial Potential Fields (APF) method is used, which also behaves as the robot controller during navigation. To find the obstacles, we use the sensor Asus Xtion, due to the possibility to find the distances that the locks are in the images generated by this sensor. All the algorithms were implemented through the programming language Python. The results of the work were presented through the simulator Gazebo and practical tests using the P3DX platform. We analyzed the robot behavior in some problems that may occur during navigation, such as kidnapped and local minimum appearance. At the end, the improvement in the results of the Direct-DRRT * path planner is also presented. It is possible to verify the decrease in the time to obtain a path, the number of iterations of nodes and the path length in comparison to other methods. Regarding the location, this dissertation has obtained significant improvements when compared to the methods that use only odometry. Besides, the work was also successful in presenting a solution for the autonomous missions implementation.

Conselho Nacional de Desenvolvimento Científico e Tecnológico / Considering path planning problem for autonomous robots, the objective is to find a list of steps to be applied to obtain a path between the initial point and the goal. This work aims the investigation and implementation of cellular automata (CA) based models to path-planning. In an initial phase, a comparative study was conducted among the cellular automata-based methods to path-planning published in the literature. Subsequently, two published works were chosen to be implemented in simulation environments to verify the actual applicability of the proposed methods. The first model starts from an image captured from the environment and it applies a CA to perform the calculation of distances between free cells and the goal. The second model uses robot sensors to identify its neighborhood and it applies CA transition rules to determine the next movements. Some limitations which prevented the robots obtain good results in simulation were identified and improvements to the original models were applied. At the end, both new models exhibited better behaviors than their precursors in several scenarios. Aiming to validate our results, two simulation environments were employed (V-REP and Webots) and some experiments with e-puck robots were performed. / No problema do planejamento de caminhos para robôs autônomos, o objetivo é encontrar uma lista de passos a serem aplicados para se obter um caminho entre o ponto inicial e a meta. Este trabalho visa a investigação e implementação de modelos baseados em autômatos celulares (ACs) para o planejamento de caminhos. Em uma fase inicial, foi realizado um estudo comparativo entre os métodos de planejamento de caminhos baseados em autômatos celulares publicados na literatura. Posteriormente, foram escolhidos dois trabalhos publicados que foram implementados em ambientes de simulação para se verificar a real aplicabilidade dos métodos propostos. O primeiro modelo parte de uma imagem capturada do ambiente de navegação e utiliza um AC para fazer o cálculo das distâncias entre as células livres e a meta. O segundo modelo utiliza os sensores do robô para identificar sua vizinhança a cada instante e utiliza regras de transição de ACs para determinar os próximos movimentos. Algumas limitações que impossibilitaram que os robôs obtivessem bons resultados em simulação foram identificadas e melhorias foram aplicadas aos modelos originais. Ao final, os dois novos modelos propostos exibiram um melhor desempenho do que seus precursores em diversos cenários. Para validar nossos resultados, dois ambientes de simulação foram empregados (V-REP e Webots), além da execução de alguns experimentos com robôs e-puck. / Mestre em Ciência da Computação