This thesis project investigates a method for performing dynamic path planning in three dimensions, targeting the application of autonomous unmanned aerial vehicles (UAVs).  Three different path planning algorithms are evaluated, based on the framework of rapidly-exploring random trees (RRTs): the original RRT, RRT*, and a proposed variant called RRT-u, which differs from the two other algorithms by considering dynamic constraints and using piecewise constant accelerations for edges in the planning tree. The path planning is furthermore applied for unexplored environments. In order to select a path when there are unexplored parts between the vehicle and the goal, it is proposed to test paths to the goal location from every vertex in the planning graph to get a preliminary estimate of the total cost for each partial path in the planning tree. The path with the lowest cost given the available information can thus be selected, even though it partly goes through unknown space. For cases when no preliminary paths can be obtained due to obstacles, dynamic resizing of the sampling region is implemented increasing the region from which new nodes are sampled. This method using each of the three different algorithms variants, RRT, RRT*, and RRT-u, is tested for performance and the three variants are compared against each other using several test cases in a realistic simulation environment.  Keywords / Detta examensarbete undersöker metoder för att utföra dynamisk ruttplanering i tre dimensioner, med applicering på obemannade luftfarkoster. Tre olika ruttplaneringsalgoritmer testas, vilka är baserade på snabbt-utforskande slumpmässiga träd (RRT): den ursprungliga RRT, RRT*, och en föreslagen variant, RRT-u, vilken skiljer sig från dom två första algoritmerna genom att ta hänsyn till dynamiska begränsningar och använda konstanta accelerationer över delar av rutten. Ruttplaneraren används också i okända miljöer. För att välja en rutt när det finns outforskade delar mellan farkosten och målet föreslås det att testa rutten till målpunkten från varje nod i som ingår i planeringsträdet för att erhålla en preliminär total kostnad till målpunkten. Rutten med lägsta kostanden kan då väljas, givet tillgänglig information, även om den delvis går genom outforskade delar. För tillfällen när inga preliminära rutter kan erhållas på grund av hinder har dynamisk storleksjustering av samplingsområdet implementerats för att öka området från vilket nya noder samplas. Den här metoden har testats med dom tre olika algoritmvarianterna, RRT, RRT*, och RRT-u, och dom tre varianterna jämförs med avseende på prestanda i ett flertal testfall i en realistisk simuleringsmiljö.

This work presents a framework for the exploration and path planning for a collaborative UAV and UGV system. The system is composed of a UAV with a stereo system for obstacle detection and a UGV with no sensors for obstacle detection. Two exploration algorithms were developed to guide the exploration of the UAV. Both identify frontiers for exploration with the Dijkstra Frontier method using Dijkstra's Algorithm to identify a frontier with unknown space, and the other uses a bi-directional RRT to identify multiple frontiers for selection. The final algorithm developed was for to give the UGV partial plans when an entire plan is not yet found. This improves the overall mission tempo. The algorithm is designed to keep the UGV a safe distance from the unknown frontier to prevent backtracking. All the algorithms were tested in Gazebo using the ROS framework. The Dijkstra Frontier method was also tested on the hardware system. The results show the RRT Explore algorithm to work well for exploring the environment, performing equally or better than the Dijkstra Frontier method. The UGV partial plan method showed a decreased traveled distance for the UGV but increases in UGV mission time with more conservative distances from danger. Overall, the framework showed a good exploration of the environment and performs the intended missions. / Master of Science / This work presents a framework for the exploration and path planning for a collaborative aerial and ground vehicle robotic system. The system is composed of an aircraft with a camera system for obstacle detection and a ground vehicle with no sensors for obstacle detection. Two exploration algorithms were developed to guide the exploration of the aircraft. Both identify frontiers for exploration with the Dijkstra Frontier method using path planning algorithms to identify a frontier with unknown space (Dijkstra Frontier), and the other uses a sampling based path planning method (RRT Explore) to identify multiple frontiers for selection. The final algorithm developed was for to give the ground vehicle intermediate plans when an entire plan is not yet found. The algorithm is designed to keep the ground vehicle a safe distance from the unknown frontier to prevent backtracking. All the algorithms were tested in a simulation framework using Robot Operating System and one exploration method was tested on the hardware system. The results show the RRT Explore algorithm to work well for exploring the environment, performing equally or better than the Dijkstra Frontier method. The ground vehicle intermediate plan method showed a decreased traveled distance for the ground vehicle but increases in ground vehicle mission time with more conservative distances from danger. Overall, the framework showed a good exploration of the environment and performs the intended missions.

Inspired by the Rapidly-exploring Random Tree (RRT) data-structure and algorithm for path planning, we introduce an approach for spanning physical space with a group of simple mobile robots. Emphasizing minimalism and using only InfraRed and contact sensors for communication, our position unaware robots physically embody elements of the tree. Although robots are fundamentally constrained in the spatial operations they may perform, we show that the approach -implemented on physical robots- remains consistent with the original data-structure idea. In particular, we show that a generalized form of Voronoi bias is present in the construction of the tree, and that such trees have an approximate space-filling property. We present an analysis of the physical system via sets of coupled stochastic equations: the first being the rate-equation for the transitions made by the robot controllers, and the second to capture the spatial process describing tree formation. We also introduce a class of fixed edge length RRTs called lRRT and show that lRRT s have similar space-filling properties to that of RRTs. We are able to provide an understanding of the control parameters in terms of a process mixing-time and show the dependence of the Voronoi bias on an interference parameter which grows as O*sqrt(N).

In this thesis improvements, implementation and evaluation have been done on a motion planning algorithm for a full-sized reversing truck and trailer system. The motion planner is based on a motion planning algorithm called Closed-Loop Rapidly-exploring Random Tree (CL-RRT). An important property for a certain class of systems, stating that by selecting the input signals in a certain way the same result as reversing the time can be archived, is also presented. For motion planning this means that the problem of reversing from position A to position B can also be solved by driving forward from B to A and then reverse the solution. The use of this result in the motion planner has been evaluated and has shown to be very useful. The main improvements made on the CL-RRT algorithm are a faster collision detection method, a more efficient way to draw samples and a more correct heuristic cost-to-go function. A post optimizing or smoothing method that brings the system to the exact desired configuration, based on numerical optimal control, has also been developed and implemented with successful results. The motion planner has been implemented and evaluated on a full-scale truck with a dolly steered trailer prepared for autonomous operation with promising results.

This thesis work investigated the advantages and disadvantages of using superquadrics (SQ) to do the collision-checking part of the Rapidly-exploring Random Trees (RRT) motion planning algorithm for higher Degree of Freedom (DoF) motion planning, comparing it with an established proximity querying method known as the Gilbert-Johnson-Keerthi (GJK) algorithm. In the RRT algorithm, collision detection is the main bottleneck, making this topic interesting to research. The SQ-based collision detection method was compared to the GJK algorithm both qualitatively and quantitatively, comparing computational speed, memory requirements, as well as the ability to handle arbitrary shapes. Furthermore, how appropriate they are in modelling a 6 DoF arm was analyzed. A qualitative comparison between the RRT algorithm and the A* algorithm was also provided, comparing their suitability for searching in higher dimensional spaces. When there were no collisions the SQ-based algorithms performed roughly at parity with the GJK algorithm in terms of computational speed. However, when a collision had occurred, the SQ-based algorithms were able to return a positive faster than the GJK algorithm, outperforming it. From a memory standpoint the SQ-based algorithms required less memory as they could leverage the explicit and implicit representations of the SQ objects, whereas the GJK algorithm requires both objects being checked for collision to be explicitly represented as convex sets of points. Regarding handling arbitrary shapes, the SQ-based algorithms have an advantage in that they can allow for certain non-convex shapes to be. Conversely, the GJK algorithm is limited to convex shapes. The GJK algorithm would thus require more geometric primitives to accurately capture the same non-convex shape. Thus, it can be concluded that the SQ-based method is more suitable for modelling a 6 DoF arm. However, a GJK-based collision detection module would in most cases be a lot more straightforward than the alternative to set up, as it is very simple to collect a set of points. Finally, both collision detection method types were implemented with the RRT algorithm. Due to the inherently random nature of the RRT algorithm the results of this set of tests could not be used to make any further conclusions beyond showing that it is possible to combine the SQbased algorithm with the RRT algorithm. Instead, one should see the RRT algorithm as a multiplicative factor applied to the inherent properties of the previously examined collision detection methods. / Detta examensarbete undersökte fördelarna och nackdelarna med att använda n:tegradsytor (NY) för att utföra kollisionsdetektion i algoritmen Raskt-utforskande Slumpmässiga Träd (RST). RST används typiskt för planeringen av system med relativt många frihetsgrader. En etablerad metod för kollisionsdetektion, Gilbert-Johnson-Keerthi-algoritmen (GJK), implementerades även i jämförelsesyfte. Då GJK-algoritmens största flaskhals ligger i kollisionsdetektionen är detta ett intressant ämne att efterforska. Den NY-baserade kollinsdetektionsmetoden jämfördes med den GJK-baserade metoden både kvantitativt och kvalitativt. Kvalitativt jämfördes beräkningshastighet och minnesåtagande, medan de kvalitativt jämfördes i deras förmåga att representera godtyckliga geometriska former. På ett högre plan diskuterades det även hur lämpliga de är för att modellera en robotarm med 6 stycken frihetsgrader. RST-algoritmen jämfördes även med en annan planeringsalgoritm, A*. Framförallt fokuserade diskussionen kring planering av system med relativt många frihetsgrader. I det fall inga kollisioner fanns presterade GJK-algoritmen ungefär lika bra som NY algoritmerna i att fastslå detta, utifrån beräkningshastighet. Men när det kom till att upptäcka existerande kollisioner presterade GJK-algoritmen sämre. Minnesmässigt använder GJK-algoritmen mer minne, då den kräver att båda objekten är explicitrepresenterade (dvs, som ett punktmoln), medan man med en NY-metod endast behöver representera ena objektet explicit och den andra implicit. Gällande förmågan att representera godtyckliga geometriska former är NY-baserade metoder bättre. Till skillnad från GJK som är begränsad till konvexa mängder kan NY uppta ickekonvexa former, exempelvis flottyrmunkformade supertoroider. En metod som använder GJKalgoritmen skulle behöva bygga upp icke-konvexa former med flera mindre konvexa komponenter. NY-metoden är således bättre för att modellera robotarmar med 6 frihetsgrader. Det är dock i praktiken lättare att implementera GJK-metoden då den endast kräver punktmoln, medan NY kräver parametrar som måste bestämmas eller finjusteras. RST-algoritmen implementerades sist, utformad så att kollisionsdetektionsmetoderna är utbytbara. Det var dock inte möjligt att dra slutsatser utifrån det testdata som erhölls, ty RSTalgoritmens slumpmässiga karaktär. RST-algoritmen kan ses som en multiplikator som endast förstorar de inneboende egenskaperna hos kollisionsdetektionsmetoderna.

This paper deals with the problem of object path planning in 3D space. The goal is to create program which allows users to create a scene used for path planning, perform the planning and finally visualize path in the scene. Work is focused on probabilistic algorithms that are described in the theoretical part. The practical part describes the design and implementation of application. Finally, several experiments are performed to compare the performance of different algorithms and demonstrate the functionality of the program.

This thesis deals with robot path planning by means of selected methods. Specifically by the methods RRT, IGPPR and ISSD. The theoretical part contains the overview of existing methods for path planning and description of previously mentioned methods. The practical part describes implementation of each methods which are applied to nonholonomic mobile robot working in 2D workspace with static obstacles.

In this thesis we modified a sampling-based motion planning algorithm to improve sampling efficiency. First, we modify the RRT* motion planning algorithm with a local motion planner that guarantees collision-free state trajectories without explicitly checking for collision with obstacles. The control trajectories are generated by solving a sequence of quadratic programs with Control Barrier Functions (CBF) constraints. If the control trajectories satisfy the CBF constraints, the state trajectories are guaranteed to stay in the free subset of the state space. Second, we use a stochastic optimization algorithm to adapt the sampling density function of RRT* to increase the probability of sampling in promising regions in the configuration space. In our approach, we use the nonparametric generalized cross-entropy (GCE) method is used for importance sampling, where a subset of the sampled RRT* trajectories is incrementally exploited to adapt the density function. The modified algorithms, the Adaptive CBF-RRT* and the CBF-RRT*, are demonstrated with numerical examples using the unicycle dynamics. The Adaptive CBF-RRT* has been shown to yield paths with lower cost with fewer tree vertexes than the CBF-RRT*. / 2022-03-27T00:00:00Z

This thesis work contains a stabilization and a motion planning strategy for a truck and trailer system. A dynamical model for a general 2-trailer with two rigid free joints and a kingpin hitching has been derived based on previous work. The model holds under the assumption of rolling without slipping of the wheels and has been used for control design and as a steering function in a probabilistic motion planning algorithm. A gain scheduled Linear Quadratic (LQ) controller with a Pure pursuit path following algorithm has been designed to stabilize the system around a given reference path. The LQ controller is only used in backward motion and the Pure pursuit controller is split into two parts which are chosen depending on the direction of motion. A motion planning algorithm called Closed-Loop Rapidly-exploring Random Tree (CL-RRT) has then been used to plan suitable reference paths for the system from an initial state configuration to a desired goal configuration with obstacle-imposed constraints. The motion planning algorithm solves a non-convex optimal control problem by randomly exploring the input space to the closed-loop system by performing forward simulations of the closed-loop system. Evaluations of performance is partly done in simulations and partly on a Lego platform consisting of a small-scale system. The controllers have been used on the Lego platform with successful results. When the reference path is chosen as a smooth function the closed-loop system is able to follow the desired path in forward and backward motion with a small control error. In the work, it is shown how the CL-RRT algorithm is able to plan non-trivial maneuvers in simulations by combining forward and backward motion. Beyond simulations, the algorithm has also been used for planning in open-loop for the Lego platform. / <p>Links to movies:</p><p>Reference tracking on Lego platform:</p><p>https://www.dropbox.com/s/ebtfgfo7aq9ij8w/reference_tracking.m4v?dl=0</p><p></p><p>Motion planning simulation with CL-RRT:</p><p>https://www.dropbox.com/s/z9kk27cxdxc1llp/CL_RRT_motion_planning.wmv?dl=0</p>

Robôs manipuladores vem desempenhando um importante papel em operações orbitais, e isso foi possível devido ao grande avanço da robótica espacial nas últimas décadas. Porém, o planejamento do movimento ainda é considerado um dos maiores desafios nesse campo, embora diversos métodos e considerações tenham sido propostas para resolver esse problema. As primeiras contribuições na área de planejamento de movimento dependiam de uma representação explícita do espaço de configuração do robô. Dessa forma, o planejamento de movimento para sistemas robóticos com muitos graus de liberdade era impraticável. Para lidar com esse problema, surgiram os métodos baseados em amostragem, dentre eles, o método de Árvore Aleatória de Exploração Rápida - RRT (do inglês, Rapidly- Exploring Random Tree). Estes métodos, ao invés da construção de todo o conjunto de configurações livre de colisões, requerem apenas a verificação de colisão com obstáculos para um conjunto discreto e finito de configurações do robô. Consequentemente, para este tipo de problema, são métodos mais vantajosos em termos computacionais. Com esta motivação, o presente trabalho tem como objetivo o desenvolvimento de um planejador de rota e de um planejador de trajetória para um robô manipulador espacial de base livre flutuante com dois braços, ambos planejadores com suporte a desvio de obstáculos estáticos. O conceito de manipulador dinamicamente equivalente é utilizado para modelar o manipulador espacial. Isso permite que o planejamento seja feito para um manipulador de base fixa subatuado dinamicamente equivalente ao manipulador de base livre flutuante. Os algoritmos baseados em amostragem RRT* e RRTControl disponibilizados na biblioteca OMPL (do inglês, Open Motion Planning Library) foram adaptados para resolver este problema de planejamento. O algoritmo RRT* é usado para o planejamento de rota, e o RRTControl para o planejamento de trajetória. Ambos planejadores utilizam o espaço de configuração das juntas do robô. Para possibilitar que a orientação e posição final dos dois efetuadores do robô pudessem ser especificadas no espaço da tarefa, um algoritmo de cinemática inversa baseado em algoritmo genético também foi desenvolvido para encontrar a solução da cinemática inversa do manipulador. / Robot manipulator has played an important role in orbital missions and this was possible due to the advance of space robotics in recent decades. However, motion planning is still considered one of the biggest challenges of the field though various methods and considerations were proposed by researchers to handle this problem. The first contributions in this field were dependent on an explicit representation of the free configuration space. Consequently, it was impractical to solve the motion planning problem for robotic systems with many degrees of freedom. In order to cope with this limitation, sampling-based methods were proposed, in particular, the Rapidly-Exploring Random Tree &#8211; RRT. Sampling-based methods only requires a procedure to verify collision with obstacles for a discrete amount of robot configuration during planning. Therefore, they are more advantageous in computational terms. In this work a path planner and a trajectory planner were developed for a free-floating planar manipulator with two arms with support for static obstacle avoidance. The Dynamically Equivalent Manipulator approach was used for modelling the robot. Thus, the planners were developed based on a fixed-base underactuated manipulator model which is dynamically equivalent to the free-floating manipulator. The sampling-based algorithms RRT* and RRTControl of the Open Motion Planning Library (OMPL) were adapted to solve this motion planning problem. The RRT* were used for path planning, and the RRTControl for trajectory planning, both carried out in the robot joint space. As the desired orientations and positions of the two end-effectors were specified in the task-space, a genetic algorithm was also developed to compute the inverse kinematics of the manipulator.