O objetivo deste trabalho é desenvolver um sistema de navegação global para que veículos agrícolas autônomos possam executar missões em campos de cultivo através de um sistema de planejamento de trajetórias. Missões podem ser entendidas como sendo tarefas (p.ex.: de monitoramento, coleta de amostras, etc.) através de pequenas rotas que os veículos devem seguir ao longo de seus trabalhos diários, percorrendo a menor distância possível entre os pontos de origem e destino. O planejamento de trajetória foi dividido em etapas para facilitar o entendimento de cada uma delas. O mapeamento apresentado neste trabalho foi feito em regiões de cultivo de café nos estados de São Paulo e Minas Gerais. Os pontos do mapa foram amostrados utilizando um módulo receptor de sinal GPS (Global Positioning System) ao longo dos caminhos onde é possível a passagem do veículo dentro da plantação. Uma etapa importante para o sucesso deste sistema é a etapa de pré-processamento dos dados. Nesta etapa são inseridas as relações entre os pontos do mapeamento da área. As missões foram pré-definidas de modo a testar o cálculo do caminho de custo mínimo que é realizado através do algoritmo de Dijkstra. A cada ponto da rota é fornecido o ângulo de direção com o qual o veículo deve estar em relação ao Norte geográfico. De acordo com a mudança pretendida do ângulo de direção é proposta uma suavização nesta mudança através da alteração do percurso para um arco de circunferência. Neste caso, o raio de giro é informado. A última etapa consiste em fornecer a velocidade máxima de deslocamento do veículo em função da mudança de direção e velocidade angular máxima do centro de massa do veículo. O sistema proposto neste trabalho foi capaz de determinar o caminho com a menor distância entre dois pontos do mapeamento (coordenadas geográficas) e o calcular da distância entre os pontos. Embora a fórmula utilizada para calcular a distância entre duas coordenadas geográficas considerar o formato da Terra como sendo uma esfera, isto não gerou erro significativo para a aplicação proposta. A suavização proposta possibilitou, em alguns pontos, o aumento da velocidade de deslocamento por fazer a mudança do ângulo de direção de forma menos abrupta. / The objective of this work is to develop a global navigation system for autonomous agricultural vehicles can perform missions in crop fields through a system of path planning. Missions can be understood as tasks (eg monitoring, sampling, etc.). Through small routes that vehicles must follow throughout their daily jobs, traveling the shortest possible distance between the points of origin and destination. The path planning was divided into steps to make it easy to understand each one. The mapping presented in this work was done in coffee-growing regions in the state of São Paulo and Minas Gerais. The map points have been sampled using a GPS receiver module along the path where it is possible to move the vehicle within the plantation. An important step for the success of this system is the data pre-processing step. In this step are inserted the relations between the points of the mapping. The missions are predefined in order to test if the calculation of the minimum cost path made by Dijkstra algorithm is correct. At each point of the route is given the vehicle heading angle (vehicle position towards the geographic North). According to the intended change of the heading angle is proposed a smoothing method to smooth this change by changing the route to an arc. In this case, the turning radius is reported. The last step is to provide the maximum speed of the vehicle due to the change of direction and maximum angular speed of the center of mass. The system proposed in this paper was able to determine the path with the shortest distance between two points of the mapping (geographic coordinates) and calculate the distance between these points. Although the formula used to calculate the distance between two geographical coordinates consider the shape of the Earth as a sphere, this did not generate significant errors for the proposed application. The proposed smoothing allowed, in some cases, to increase the vehicle speed by making the change of heading angle less abrupt.

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

Les travaux de cette thèse proposent une nouvelle approche pour le guidage assisté par robots d'aiguilles flexibles pour des procédures percutanées. La méthode est basée sur l'utilisation d'une rotation de l'aiguille avec un rapport cyclique variable pour réaliser une insertion avec des arcs de rayons de courbure différents. Elle combine un retour visuel avec une stratégie de planification adaptative pour compenser les incertitudes du système et les perturbations. Par rapport aux approches présentées précédemment dans la littérature, la stratégie de planification en boucle fermée est adaptée à des scènes dynamiques qui présentent des changements de position des obstacles et de la cible. Cette approche a été implémentée sur un système robotique et les résultats obtenus in vitro confirment tout l'intérêt de cette technique. / This thesis proposes a robot-assisted approach for automatic steering of flexible beveled needles in percutaneous procedures. The method uses duty-cycled rotation of the needle to perform insertion with arcs of adjustable curvature, and combines closed-loop imaging feedback with an intraoperative motion replanning strategy to compensate for system uncertainties and disturbances. Differently from previous approaches, the closed-loop replanning strategy is suitable for dynamic scenes that present changes of obstacles and target positions. Indeed, we implemented the proposed system using a robotic manipulator, and the results obtained from in vitro tests confirmed the viability of our method.

In this paper I describe a motion planning technique for intelligent ground vehicles. The technique is an implementation of a path selection algorithm based on fuzzy inference. The approach extends on the motion planning algorithm known as driving with tentacles. The selection of the tentacle (a drivable path) to follow relies on the calculation of a weighted cost function for each tentacle in the current speed set, and depends on variables such as the distance to the desired position, speed, and the closeness of a tentacle to any obstacles. A Matlab simulation and the practical implementation of the fuzzy inference rule on a Clearpath Husky robot within the Robot Operating System (ROS) framework are provided.

Research efforts on the development of autonomous vehicles date back to the 1920s and recent announcements indicate that those cars are close to becoming commercially available. However, the most successful prototypes that are currently being demonstrated rely on an expensive set of sensors. This study investigates the use of an affordable vision system as a planner for the Robocart, an autonomous golf cart prototype developed by the Wireless Innovation Laboratory at WPI. The proposed approach relies on a stereo vision system composed of a pair of Raspberry Pi computers, each one equipped with a Camera Module. They are connected to a server and their clocks are synchronized using the Precision Time Protocol (PTP). The server uses timestamps to obtain a pair of simultaneously captured images. Images are processed to generate a disparity map using stereo matching and points in this map are reprojected to the 3D world as a point cloud. Then, an occupancy grid is built and used as input for an A* graph search that finds a collision-free path for the robot. Due to the non-holonomic constraints of a car-like robot, a Pure Pursuit algorithm is used as the control method to guide the robot along the computed path. The cameras are also used by a Visual Odometry algorithm that tracks points on a sequence of images to estimate the position and orientation of the vehicle. The algorithms were implemented using the C++ language and the open source library OpenCV. Tests in a controlled environment show promising results and the interfaces between the server and the Robocart have been defined, so that the proposed method can be used on the golf cart as soon as the mechanical systems are fully functional.

The daVinci Research Kit (dVRK) is a research platform that consists of the clinical daVinci surgical robot, provided by Intuitive Surgical to Academic Institutions. It provides an open source software and hardware platform for researchers to study and analyze the current architecture and expand the capabilities of the existing technology. The line between general purpose robotics and medical robotics has segregated the two fields. A significant part of the segregation lies at the software end, where new tools and methods developed in general purpose robotics cannot make it to medical robotics in a short amount of time. This research focuses on the integration of a widely used software architecture for general purpose robotics with the dVRK with the hope of utilizing the research and development from one field to the other. As a first step towards this bridging, a motion planning framework and a dynamic simulator has been developed for the dVRK using ROS. The motion planning framework is aimed to assist the surgeon in performing task with additional safety and machine intelligence. A few use cases have been proposed as well. Lastly, a Matlab Interface has been developed that is standalone in terms of usage and provides capabilities to interact with dVRK.

<div>Previous studies have shown that implementing trajectory optimization can reduce state estimations errors. These navigation based path planning problems are often diffcult to solve being computationally burdensome and exhibiting other numerical issues, so former studies have often used lower-delity methods or lacked explanatory power.</div><div><br></div><div><div>This work utilizes indirect optimization methods, particularly optimal control theory, to obtain high-quality solutions minimizing state estimation errors approximated by a continuous-time extended Kalman lter. Indirect methods are well-suited to this because necessary conditions of optimality are found prior to discretization and numerical computation. They are also highly parallelizable enabling application to increasingly larger problems.</div></div><div><br></div><div><div>A simple one dimensional problem shows some potential obstacles to solving problems of this type including regions of the trajectory where the control is unimportant. Indirect trajectory optimization is applied to a more complex scenario to minimize location estimation errors of a single cart traveling in a 2-D plane to a goal location and measuring range from a xed beacon. This resulted in a 96% reduction of the location error variance when compared to the minimum time solution. The single cart problem also highlights the importance of the matrix that encodes the linearization of the vehicle's measurement with respect to state. It is shown in this case that the vehicle roughly attempts to maximize the magnitude of its elements. Additionally, the cart problem further illustrates problematic regions of a design space where the objective is not signicantly affected by the trajectory.</div></div><div><br></div><div><div>An aircraft descent problem demonstrates the applicability of these methods to aerospace problems. In this case, estimation error variance is reduced 28.6% relative to the maximum terminal energy trajectory. Results are shown from two formulations of this problem, one with control constraints and one with control energy cost, to show the benets and disadvantages of the two methods. Furthermore, the ability to perform trade studies on vehicle and trajectory parameters is shown with this problem by solving for dierent terminal velocities and different initial locations.</div></div>

O planejamento de movimento é um dos problemas fundamentais em navegação autônoma para robôs móveis. Uma vez planejado o caminho, o robô executa o acompanhamento da trajetória, frequentemente, com o auxílio de um controlador em malha fechada. Este controlador tem o objetivo de minimizar os erros de acompanhamento, a fim de que a trajetória executada se aproxime da trajetória planejada. Entretanto a maioria dos planejadores de movimento não levam em consideração o modelo dinâmico do robô, dificultando assim o trabalho do controlador que executa o acompanhamento da trajetória. Incluindo as restrições cinemáticas e dinâmicas do modelo do robô, o custo computacional durante a fase de planejamento de trajetória será mais alto. Isto ocorre pois são necessárias mais variáveis para representar o espaço de estados do robô. No entanto ao levar em consideração tais restrições durante a fase de planejamento, as trajetórias geradas serão factíveis de serem acompanhadas. Os planejadores probabilísticos de movimento podem ser usados para minimizar o impacto do alto custo computacional, devido ao aumento de variáveis que representam o espaço de estados. Tais planejadores também são chamados de planejadores de movimento baseados em amostragem. A busca por um caminho livre de colisões entre dois estados é feito de maneira aleatória. Caso exista uma solução, a probabilidade do algoritmo encontrá-la tende para 1 quanto do tempo de busca tende a infinito, isto é, quanto mais tempo o algoritmo possui para realizar a busca será mais provável que ele encontre a solução. Neste trabalho é proposto um planejador de movimentos baseado em amostragem que leva em consideração os aspectos cinemáticos e dinâmicos do robô. Além disto esta abordagem de planejamento desenvolvida permite conhecer e levar em consideração os efeitos do controlador que faz o acompanhamento da trajetória, ainda na fase de planejamento de movimento. As trajetórias planejadas foram executadas no robô Pioneer 3AT. Foram levantados os dados relacionados ao desempenho do algoritmo em termos de custo computacional. E na sequência são apresentados os resultados experimentais tanto na parte de planejamento de trajetórias quanto na fase de acompanhamento. / Motion planning is one of the fundamental problems in autonomous navigation for mobile robots. Once the path is planned, the robot performs the trajectory tracking, often with the aid of a closed loop controller. This controller is designed to minimize tracking errors, in order that tracked trajectory get closer to planned path. However, the most motion planners do not take into account the dynamic model of the robot, thus hindering the work of closed loop controller. When including the kinematic constraints and dynamic model of the robot, the computational cost during the planning phase trajectory will be increased. This is because more variables are needed to represent the state space of the robot. But when taking into account these constraints during the planning phase, the trajectories generated are feasible to be followed. The probabilistic motion planners can be used to minimize the impact of high computational cost due to the increase of variables that represent the state space. These planners are also called sampling based motion planners. The search for a collision-free path between two states is done randomly. If a solution exists, the probability of the algorithm to find it tends to one while the search time tends to infinity, that is, the longer time the algorithm has to perform the search will be more likely to find the solution. This paper proposes a sampling based motion planner that takes into account the kinematic and dynamic aspects of the robot. Furthermore this approach allows one to know and take into account the effects of the controller that perform the trajectory tracking, still in the motion planning phase. The planned trajectories were performed on the robot Pioneer 3AT. Data related to the computational cost of the algorithm were analyzed. Following the experimental results are presented both in the planning of trajectories and in the tracking phase.

Autonomous vehicles have increasingly become an attractive field due its promising capabilities of improvements regarding safety, comfort, traffic flow etc. A required attribute for those vehicles is the ability of autonomously compute its path towards a destination point. The path must be planned considering the constructive aspects of the vehicle in order to guarantee the maneuver feasibility. This work consists on computing a feasible path for autonomous vehicles with non-holonomic constraints. Piecewise linear continuouscurvature paths constituted of clothoids, circular arcs, and straight lines are used for this purpose, providing passenger\'s comfort. The road network is modeled from GPS (Global Positioning System) vehicle trajectories by defining lanes, roundabouts and intersections. GPS points are used later to parameterize lanes using clothoids and to extract roundabout centers and radii. This approach provides a sparse road network model since GPS points are replaced by parameterized curves. The information about connections between roads coming from the model is used by a global path planner, which computes a minimal length route from the vehicle current position to the destination point. After that, path planners compute intersection and roundabout paths depending on the nature of connections between roads. Also, lanes changes are performed to obey traffic rules. These three path planners that connects adjacent roads use clothoids, circular arc, and straight lines as interpolating curves whose curvature is constrained to that the vehicle can perform: the intersection path planner uses only a minimal amount of steering to perform the maneuver, increasing the comfort level; the roundabout path planner takes the roundabout center and radius as well as parameters that defines the entrance and exit maneuvers to compute the path; the lane change path planner connects lanes belonging to the same road with a prescribed longitudinal traveled distance depending on whether this maneuver is required. In the end, an global continuous-curvature path is generated. As the result of this work, a real urban scenario is modeled and the proposed approaches are validated. / Veículos autônomos têm cada vez mais se tornado um campo atraente de pesquisa devido às suas capacidades promissoras de melhorias em segurança, conforto, fluxo de tráfego, etc. Um atributo necessário para esses veículos é a capacidade de calcular, de forma autônoma, o seu caminho para um ponto de destino. O percurso deve ser planejado considerando os aspectos construtivos do veículo para que a viabilidade das manobras a serem executadas seja garantida. Este trabalho consiste no planejamento de trajetória para veículos autônomos com restrições não-holonômicas. Utilizam-se, para esse efeito, trajetórias cuja curvatura seja contínua e linear por partes, constituídas por clotóides, arcos de circunferência e retas, de forma a proporcionar conforto aos passageiros. A topologia de vias é modelada a partir de trajetórias definidas por pontos de GPS (Sistema de Posicionamento Global), definindo pistas, rotatórias e cruzamentos. Pontos de GPS são usados posteriormente para parametrizar as pistas usando clotóides a para extrair centros e raios das rotatórias. Essa abordagem proporciona um modelo esparso de topologia de vias uma vez que pontos de GPS são substituídos por curvas parametrizadas. A informação a cerca das conexões entre vias advinda do modelo é usada por um planejador de caminho global, o qual calcula a rota mais curta da posição atual do veículo até seu ponto de destino. Após essa etapa, planejadores calculam caminhos em cruzamentos e rotatórias dependendo do tipo de conexão entre as vias. Também, trocas de faixa devem ser executadas para obedecer regras de trânsito. Esses três planejadores de caminho usam clotóides, arcos de circunferência e retas como curvas interpoladoras, cuja curvatura é restrita a valores que o veículo é capaz de executar: o planejador de caminho em cruzamentos usa apenas um mínimo de velocidade de rotação do volante do veículo para executar a manobra, melhorando o nível de conforto; o planejador de caminho em rotatórias requer as coordenadas do centro e o raio da rotatória, bem como parâmetros que definem as manobras na entrada e na saída da rotatória para calcular o caminho; o planejador de caminho para troca de faixa conecta pistas pertencentes à mesma via com uma distância longitudinal do caminho previamente determinada. Ao final, um caminho com curvatura globalmente contínua é gerado. Como resultado deste trabalho, um cenário urbano real é modelado e os métodos propostos são validados.