The thesis deals with the path planning and movement of the holonomic robot in a dynamic environment. The aim of this work is implementation of several algorithms based on Rapidly-explored random tree algorithm and their comparison in designed dynamic environment.

This thesis investigates the design of a local planning method for a reversing single joint tractor-trailer system that can be used in a sampling-based motion planner. The motion planner used is a Rapidly-exploring Random Tree (RRT) developed by Scania. The main objective of a local planning method is to generate a feasible path between two poses, which is needed when expanding the search tree in an RRT. The local planning method described in this thesis uses a set of curves, similar to Reeds-Shepp curves, feasible for a single joint tractor-trailer system. The curves are found by solving a constrained optimization problem that adheres to the kinematic model of the system. The reference for the tractor is generated by discretizing the path between curves. The reference for the trailer is generated by simulating the mission backwards where the curve radiuses are used as input. Simulating the mission backwards circumvents the instability of the system when reversing. The generated references are then compared to references generated by a lattice-based motion planner. The length of the references generated by the RRT are smaller than those generated by the lattice-based motion planner in simple open environments. The RRT had issues finding a path in cases where the environment was complex while the lattice-based motion planner found a path in every scenario. The computational time was significantly lower for the RRT in all simulations. The RRT generates all references between any two given poses while the lattice-based motion planner approximate the start and goal poses to the closest vertex in the search-space.  The references generated by the RRT did not perform optimally when small turns were needed along the curves due to the distance needed for maneuvering the tractor. Therefore, a new optimization problem has to be defined for which the small turns are considered.

Robot path planning and dynamic obstacle avoidance are defined as a problem that robots plan a feasible path from a given starting point to a destination point in a nonlinear dynamic environment, and safely bypass dynamic obstacles to the destination with minimal deviation from the trajectory. Path planning is a typical sequential decision-making problem. Dynamic local observable environment requires real-time and adaptive decision-making systems. It is an innovation for the robot to learn the policy directly from demonstration trajectories to adapt to similar state spaces that may appear in the future. We aim to develop a method for directly learning navigation behavior from demonstration trajectories without defining the environment and attention models, by using the concepts of Generative Adversarial Imitation Learning (GAIL) and Sequence Generative Adversarial Network (SeqGAN). The proposed SeqGAIL model in this thesis allows the robot to reproduce the desired behavior in different situations. In which, an adversarial net is established, and the Feature Counts Errors reduction is utilized as the forcing objective for the Generator. The refinement measure is taken to solve the instability problem. In addition, we proposed to use the Rapidly-exploring Random Tree* (RRT*) with pre-trained weights to generate adequate demonstration trajectories in dynamic environment as the training data, and this idea can effectively overcome the difficulty of acquiring huge training data.

Unmanned air vehicles (UAVs) have become an important area of research. UAVs are used in many environments which may have previously unknown obstacles or sources of danger. This research addresses the problem of obstacle mapping and path planning while the UAV is in flight. Online obstacle mapping is achieved through the use of a multi-resolution map. As sensor information is received, a quadtree is built up to hold the information based upon the uncertainty associated with the measurement. Once a quadtree map of obstacles is built up, we desire online path re-planning to occur as quickly as possible. We introduce the idea of a quadtree rapidly-exploring random tree (RRT), which will be used as the online path re-planning algorithm. This approach implements a variable sized step instead of the fixed-step size usually used in the RRT algorithm. This variable step uses the structure of the quadtree to determine the step size. The step size grows larger or smaller based upon the size of the area represented by the quadtree it passes through. Finally this approach is tested in a simulation environment. The results show that the quadtree RRT requires fewer steps on average than a standard RRT to find a path through an area. It also has a smaller variance in the number of steps taken by the path planning algorithm in comparison to the standard RRT.

Robots moving about in complex environments must be capable of determining and performing difficult motion sequences to accomplish tasks. As the tasks become more complicated, robots with greater dexterity are required. An increase in the number of degrees of freedom and a desire for autonomy in uncertain environments with real-time requirements leaves much room for improvement in the current popular robot motion planning algorithms. In this thesis, state of the art robot motion planning techniques are surveyed. A solution to the general movers problem in the context of motion planning for robots is presented. The proposed robot motion planner solves the general movers problem using a sample-based tree planner combined with an incremental simulator. The robot motion planner is demonstrated both in simulation and the real world. Experiments are conducted and the results analyzed. Based on the results, methods for tuning the robot motion planner to improve the performance are proposed.

Metody plánování pohybu jsou významnou součástí robotiky, resp. mobilních robotických platforem. Technicky je realizace plánování pohybu z globální úrovně převedena do posloupnosti akcí na úrovni specifické robotické platformy a definovaného prostředí, včetně omezení. V rámci této práce byla provedena recenze mnoha metod určených pro plánování cest, přičemž hlavním těžištěm byly metody založené na tzv. rychle rostoucích stromech (RRT), prostorovém rozkladu (CD) a využití fuzzy expertních systémů (FES). Dosažené výsledky, resp. prezentované algoritmy, využívají dostupné informace z pracovního prostoru mobilního robotu a jsou aplikovatelné na řešení globální pohybové trajektorie mobilních robotů, resp. k řešení specifických problémů plánování cest s omezením typu úzké koridory či překážky s proměnnou polohou v čase. V práci jsou představeny nové plánovací postupy využívající výhod algoritmů RRT a CD. Navržené metody jsou navíc efektivně rozšířeny s využitím fuzzy expertního systému, který zlepšuje jejich chování. Práce rovněž prezentuje řešení pro plánovací problémy typu identifikace úzkých koridorů, či významných oblastí prostoru řešení s využitím přístupů na bázi dekompozice prostoru. V řešeních jsou částečně zahrnuty sub-optimalizace nalezených cest založené na zkracování nalezené cesty a vyhlazování cesty, resp. nahrazení trajektorie hladkou křivkou, respektující lépe předpokládanou dynamiku mobilního zařízení. Všechny prezentované metody byly implementovány v prostředí Matlab, které sloužilo k simulačnímu ověření efektivnosti vlastních i převzatých metod a k návrhu prostoru řešení včetně omezení (překážky). Získané výsledky byly vyhodnoceny s využitím statistických přístupů v prostředí Minitab a Matlab.

A novel, sampling-based exploration strategy is introduced for Unmanned Ground Vehicles (UGV) to efficiently map large GPS-deprived underground environments. It is compared to state-of-the-art approaches and performs on a similar level, while it is not designed for a specific robot or sensor configuration like the other approaches. The introduced exploration strategy, which is called Random-Sampling-Based Next-Best View Exploration (RNE), uses a Rapidly-exploring Random Graph (RRG) to find possible view points in an area around the robot. They are compared with a computation-efficient Sparse Ray Polling (SRP) in a voxel grid to find the next-best view for the exploration. Each node in the exploration graph built with RRG is evaluated regarding the ability of the UGV to traverse it, which is derived from an occupancy grid map. It is also used to create a topology-based graph where nodes are placed centrally to reduce the risk of collisions and increase the amount of observable space. Nodes that fall outside the local exploration area are stored in a global graph and are connected with a Traveling Salesman Problem solver to explore them later.

Tato diplomová práce práce se zabývá plánováním cesty všesměrového mobilního robotu pomocí algoritmu RRT (Rapidly-exploring Random Tree – Rychle rostoucí náhodný strom). Teoretická část popisuje základní algoritmy plánování cesty a prezentuje bližší pohled na RRT a jeho potenciál. Praktická část práce řeší návrh a tvorbu v zásadě multiplatformní C++ aplikace v prostředí Windows 7 za použití aplikačního frameworku Qt 4.8.0, která implementuje pokročilé RRT algoritmy s parametrizovatelným řešičem a speciálním dávkovým režimem. Tento mód slouží k testování efektivnosti nastavení řešiče pro dané úlohy a je založen na post-processingu a vizualizaci výstupu měřených úloh pomocí jazyka Python. Vypočtené cesty mohou být vylepšeny pomocí zkracovacích algoritmů a výsledná trajektorie odeslána do pohonů Maxon Compact Drive všesměrové mobilní platformy pomocí CANopen. Aplikace klade důraz na moderní grafické uživatelské rozhraní se spolehlivým a výkonným 2D grafickým engine.

Small UAVs are used for low altitude surveillance flights where unknown obstacles can be encountered. These UAVs can be given the capability to navigate in uncertain environments if obstacles are identified. This research presents an obstacle avoidance system for small UAVs. First, a mission waypoint path is created that avoids all known obstacles using a genetic algorithm. Then, while the UAV is in flight, obstacles are detected using a forward looking, onboard camera. Image features are found using the Harris Corner Detector and tracked through multiple video frames which provides three dimensional localization of the features. A sparse three dimensional map of features provides a rough estimate of obstacle locations. The features are grouped into potentially hazardous areas. The small UAV then employs a sliding mode control law on the autopilot to avoid obstacles. This research compares rapidly-exploring random trees to genetic algorithms for UAV pre-mission path planning. It also presents two methods for using image feature movement and UAV telemetry to calculate depth and detect obstacles. The first method uses pixel ray intersection and the second calculates depth from image feature movement. Obstacles are avoided with a success rate of 96%.

This thesis focuses on the design and development of a fixed wing micro air vehicle (MAV) and on the development of randomized sampling based motion planning and control algorithms for path planning and stabilization of the MAV. In addition, the thesis also contains probabilis-tic analyses of the algorithmic properties of randomized sampling based algorithms, such as completeness and asymptotic optimality. The thesis begins with a detailed discussion on aerodynamic design, computational fluid dy-namic simulations of propeller wake, wind tunnel tests of a 150mm fixed wing micro air ve-hicle. The vehicle is designed in such a way that in spite of the various adverse effects of low Reynolds number aerodynamics and the complex propeller wake interactions with the airframe, the vehicle shows a balance of external forces and moments at most of the operating conditions. This is supported by various CFD analysis and wind tunnel tests and is shown in this thesis. The thesis also contains a reasonably accurate longitudinal and lateral dynamical model of the MAV, which are verified by numerous flight trials. However, there still exists a considerable amount of model uncertainties in the system descrip-tion of the MAV. A robust feedback stabilized close loop flight control law, is designed to attenuate the effects of modelling uncertainties, discrete vertical and head-on wind gusts, and to maintain flight stability and performance requirements at all allowable operating conditions. The controller is implemented in the MAV autopilot hardware with successful close loop flight trials. The flight controller is designed based on the probabilistic robust control approach. The approach is based on statistical average case analysis and synthesis techniques. It removes the conservatism present in the classical robust feedback design (which is based the worst case de-sign techniques) and associated sluggish system response characteristics. Instead of minimizing the effect of the worst case disturbance, a randomized techniques synthesizes a controller for which some performance index is minimized in an empirical average sense. In this thesis it is shown that the degree of conservatism in the design and the number of samples used to by the randomized sampling based techniques has a direct relationship. In particular, it is shown that, as the lower bound on the number of samples reduces, the degree of conservatism increases in the design. Classical motion planning and obstacle avoidance methodologies are computationally expen-sive with the number of degrees of freedom of the vehicle, and therefore, these methodologies are largely inapplicable for MAVs with 6 degrees of freedom. The problem of computational complexity can be avoided using randomized sampling based motion planning algorithms such as probabilistic roadmap method or PRM. However, as a pay-off these algorithms lack algorith-mic completeness properties. In this thesis, it is established that the algorithmic completeness properties are dependent on the choice of the sampling sequences. The thesis contains analy-sis of algorithmic features such as probabilistic completeness and asymptotic optimality of the PRM algorithm and its many variants, under the incremental and independent problem model framework. It is shown in this thesis that the structure of the random sample sequence affects the solution of the sampling based algorithms. The problem of capturing the connectivity of the configuration space in the presence of ob-stacles, which is a central problem in randomized motion planning, is also discussed in this thesis. In particular, the success probability of one such randomized algorithm, named Obsta-cle based Probabilistic Roadmap Method or OBPRM is estimated using geometric probability theory. A direct relationship between the weak upper bound of the success probability and the obstacle geometric features is established. The thesis also contains a new sampling based algorithm which is based on geometric random walk theory, which addresses the problem of capturing the connectivity of the configuration space. The algorithm shows better performance when compared with other similar algorithm such as the Randomized Bridge Builder method for identical benchmark problems. Numerical simulation shows that the algorithm shows en-hanced performance as the dimension of the motion planning problem increases. As one of the central objectives, the thesis proposes a pre-processing technique of the state space of the system to enhance the performance of sampling based kino-dynamic motion plan-ner such as rapidly exploring random tree or RRT. This pre-processing technique can not only be applied for the motion planning of the MAV, but can also be applied for a wide class of vehicle and complex systems with large number of degrees of freedom. The pre-processing techniques identifies the sequence of regions, to be searched for a solution, in order to do mo-tion planning and obstacle avoidance for an MAV, by an RRT planner. Numerical simulation shows significant improvement over the basic RRT planner with a small additional computa-tional overhead. The probabilistic analysis of RRT algorithm and an approximate asymptotic optimality analysis of the solution returned by the algorithm, is also presented in this thesis. In particular, it is shown that the RRT algorithm is not asymptotically optimal. An integral part of the motion planning algorithm is the capability of fast collision detection between various geometric objects. Image space based methods, which uses Graphics Pro-cessing Unit or GPU hardware, and do not use object geometry explicitly, are found to be fast and accurate for this purpose. In this thesis, a new collision detection method between two convex/non-convex objects using GPU, is provided. The performance of the algorithm, which is an extension of an existing algorithm, is verified with numerous collision detection scenarios.