Almost two thirds of the Earth's surface is covered in ocean, and yet, only about 5% of it is mapped. There are an unknown amount of sunken ships, planes, and other artifacts hidden below the sea. Extensive search via boat and a sonar tow fish following a standard lawnmower pattern is used to identify sites of interest. Then, if a site has been determined to potentially be historically significant, the most common next step is a survey by either a human dive team or remotely operated vehicle. These are time consuming, error prone, and potentially dangerous options, but autonomous underwater vehicles (AUVs) are a possible solution. This thesis introduces a system for automatically generating paths for AUVs to survey and map shipwrecks. Most AUVs include software to set a lawnmower path for a given region of ocean, and individualized paths can be set via specifying GPS encoded nodes for the AUV to pass through. This thesis presents an algorithm for generating an individualized path that permits the AUV, equipped with a camera to "see" all sides of a region of interest (i.e. a shipwreck). This allows the region of interest to be completely documented. Photogrammetry can then be used to reconstruct a three-dimensional model, but a path is needed to do so. Paths are generated by a probabilistic roadmap algorithm that uses a rapidly-exploring random tree to quickly cover the volume of exploration space and generate small maps with good coverage. The roadmap is constructed out of nodes, each having its own weight. The weight of a given node is calculated using an objective function which measures an approximate view coverage by casting rays from the virtual view and intersecting them with the region of interest. In addition, the weight of a node is increased if this node allows the AUV to see a new side of the region of interest. In each iteration of the algorithm, a node to expand off of is selected based off its location in space or its high weight, a new node with a given amount of freedom is generated, and then added to the roadmap. The algorithm has degrees of freedom in position, pitch, and yaw as well as the objective function to encourage the path to see all sides of the region of interest. Once all sides of the region of interest have been viewed, a path is determined to be complete. The algorithm was tested in a virtual world where the virtual camera acted as the AUV. All of the images collected from our automatically generated path were used to create 3D models and point clouds using photogrammetry. To measure the effectiveness of our paths versus the pre-packaged lawnmower paths, the 3D models and point clouds created from our algorithm were compared to those generated from running a standard lawnmower pattern. The paths generated by our algorithm captured images that could be used in a 3D reconstruction which were more detailed and showed better coverage of the region of interest than those from the lawnmower pattern.

M.Sc., Faculty of Sciences, University of the Witwatersrand, 2011 / Abstract This dissertation is concerned with discrete global optimization of nonlinear problems. These problems are constrained and unconstrained and are not easily solvable since there exists multiplicity of local and global minima. In this dissertation, we study the current methods for solving such problems and highlight their ine ciencies. We introduce a new local search procedure. We study the rapidly-exploring random tree (RRT) method, found mostly in the research area of robotics. We then design two global optimization algorithms based on RRT. RRT has never been used in the eld of global optimization. We exploit its attractive properties to develop two new algorithms for solving the discrete nonlinear optimization problems. The rst method is called RRT-Optimizer and is denoted as RRTOpt. RRTOpt is then modi ed to include probabilistic elements within the RRT. We have denoted this method by RRTOptv1. Results are generated for both methods and numerical comparisons are made with a number of recent methods.

<p>Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV.</p><p>Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT).</p><p>Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process.</p><p>The result of this work is twofold:</p><p>First, the described planners and extensions have been implemented and integrated into the software architecture of a UAV. A number of flight tests with these algorithms have been performed on a physical helicopter and the results from some of them are presented in this thesis.</p><p>Second, an empirical study has been conducted, comparing the performance of the different algorithms and extensions in this planning domain. It is shown that with the environment known in advance, the PRM algorithm generally performs better than the RRT algorithm due to its precompiled roadmaps, but that the latter is also usable as long as the environment is not too complex. The study also shows that simple geometric constraints can be added in the runtime phase of the PRM algorithm, without a big impact on performance. It is also shown that postponing the motion constraints to the runtime phase can improve the performance of the planner in some cases.</p> / Report code: LiU–Tek–Lic–2006:10.

This thesis deals with analyses of problems of path planning by means Rapidly-exploring Random Trees (RRT) algorithm. The teoretic part described of basic terms and navigation mobile robots. There are localization, mapping and path planning parts of navigation. Then it is description overview of localization of methods and overview of robot path planning methods. The practical describes implementation of proposed method in Delphi. The best method for path planning of robot using RRT algorithm. For reservation universal communications interface is application creation like dynamic library.

Many of the applications that have been proposed for future small unmanned aerial vehicles (UAVs) are at low altitude in areas with many obstacles. A vital component for successful navigation in such environments is a path planner that can find collision free paths for the UAV. Two popular path planning algorithms are the probabilistic roadmap algorithm (PRM) and the rapidly-exploring random tree algorithm (RRT). Adaptations of these algorithms to an unmanned autonomous helicopter are presented in this thesis, together with a number of extensions for handling constraints at different stages of the planning process. The result of this work is twofold: First, the described planners and extensions have been implemented and integrated into the software architecture of a UAV. A number of flight tests with these algorithms have been performed on a physical helicopter and the results from some of them are presented in this thesis. Second, an empirical study has been conducted, comparing the performance of the different algorithms and extensions in this planning domain. It is shown that with the environment known in advance, the PRM algorithm generally performs better than the RRT algorithm due to its precompiled roadmaps, but that the latter is also usable as long as the environment is not too complex. The study also shows that simple geometric constraints can be added in the runtime phase of the PRM algorithm, without a big impact on performance. It is also shown that postponing the motion constraints to the runtime phase can improve the performance of the planner in some cases. / <p>Report code: LiU–Tek–Lic–2006:10.</p>

No description available.

Robot path planning is a critical feature of autonomous systems. Rapidly-exploring Random Trees (RRT) is a path planning technique that randomly samples the robot configuration space to find a path between the start and end point. This thesis studies and compares the performance of four important RRT algorithms, namely, the original RRT, the optimal RRT (also termed RRT*), RRT*-Smart, and Informed RRT* for six different environments. The performance measures include the final path length (which is also the shortest path length found by each algorithm), time to find the first path, run time (of 1000 iterations) for each algorithm, total number of sampling nodes, and success rate (out of 100 runs). It is found that both RRT*-Smart and Informed RRT* algorithm result in shorter path lengths than the original RRT and RRT*. Typically, RRT*-Smart can find a suboptimal path in less number of iterations while the Informed RRT* is able to find the shortest path with increased number of iterations. On the other hand, the original RRT and RRT* are better suited for real-time applications as the Informed RRT* and RRT*-Smart have longer run time due to the additional steps in their processes.

Robot motion planning is one of the central problems in robotics, and has received considerable amount of attention not only from roboticists but also from the control and artificial intelligence (AI) communities. Despite the different types of applications and physical properties of robotic systems, many high-level tasks of autonomous systems can be decomposed into subtasks which require point-to-point navigation while avoiding infeasible regions due to the obstacles in the workspace. This dissertation aims at developing a new class of sampling-based motion planning algorithms that are fast, efficient and asymptotically optimal by employing ideas from Machine Learning (ML) and Dynamic Programming (DP). First, we interpret the robot motion planning problem as a form of a machine learning problem since the underlying search space is not known a priori, and utilize random geometric graphs to compute consistent discretizations of the underlying continuous search space. Then, we integrate existing DP algorithms and ML algorithms to the framework of sampling-based algorithms for better exploitation and exploration, respectively. We introduce a novel sampling-based algorithm, called RRT#, that improves upon the well-known RRT* algorithm by leveraging value and policy iteration methods as new information is collected. The proposed algorithms yield provable guarantees on correctness, completeness and asymptotic optimality. We also develop an adaptive sampling strategy by considering exploration as a classification (or regression) problem, and use online machine learning algorithms to learn the relevant region of a query, i.e., the region that contains the optimal solution, without significant computational overhead. We then extend the application of sampling-based algorithms to a class of stochastic optimal control problems and problems with differential constraints. Specifically, we introduce the Path Integral - RRT algorithm, for solving optimal control of stochastic systems and the CL-RRT# algorithm that uses closed-loop prediction for trajectory generation for differential systems. One of the key benefits of CL-RRT# is that for many systems, given a low-level tracking controller, it is easier to handle differential constraints, so complex steering procedures are not needed, unlike most existing kinodynamic sampling-based algorithms. Implementation results of sampling-based planners for route planning of a full-scale autonomous helicopter under the Autonomous Aerial Cargo/Utility System Program (AACUS) program are provided.

Motion planning problems are characterized by huge search spaces and complex obstacle structures with no concise mathematical expression. The fixed-wing airplane application considered in this thesis adds differential constraints and point-wise bounds, i. e. an infinite number of equality and inequality constraints. An optimal trajectory planning approach is presented, based on the randomized Rapidly-exploring Random Trees framework (RRT*). The local planner relies on differential flatness of the equations of motion to obtain tree branch candidates that automatically satisfy the differential constraints. Flat output trajectories, in this case equivalent to the airplane's flight path, are designed using Bézier curves. Segment feasibility in terms of point-wise inequality constraints is tested by an indicator integral, which is evaluated alongside the segment cost functional. Although the RRT* guarantees optimality in the limit of infinite planning time, it is argued by intuition and experimentation that convergence is not approached at a practically useful rate. Therefore, the randomized planner is augmented by a deterministic variational optimization technique. To this end, the optimal planning task is formulated as a semi-infinite optimization problem, using the intermediate result of the RRT(*) as an initial guess. The proposed optimization algorithm follows the feasible flavor of the primal-dual interior point paradigm. Discretization of functional (infinite) constraints is deferred to the linear subproblems, where it is realized implicitly by numeric quadrature. An inherent numerical ill-conditioning of the method is circumvented by a reduction-like approach, which tracks active constraint locations by introducing new problem variables. Obstacle avoidance is achieved by extending the line search procedure and dynamically adding obstacle-awareness constraints to the problem formulation. Experimental evaluation confirms that the hybrid approach is practically feasible and does indeed outperform RRT*'s built-in optimization mechanism, but the computational burden is still significant. / Bewegungsplanungsaufgaben sind typischerweise gekennzeichnet durch umfangreiche Suchräume, deren vollständige Exploration nicht praktikabel ist, sowie durch unstrukturierte Hindernisse, für die nur selten eine geschlossene mathematische Beschreibung existiert. Bei der in dieser Arbeit betrachteten Anwendung auf Flächenflugzeuge kommen differentielle Randbedingungen und beschränkte Systemgrößen erschwerend hinzu. Der vorgestellte Ansatz zur optimalen Trajektorienplanung basiert auf dem Rapidly-exploring Random Trees-Algorithmus (RRT*), welcher die Suchraumkomplexität durch Randomisierung beherrschbar macht. Der spezifische Beitrag ist eine Realisierung des lokalen Planers zur Generierung der Äste des Suchbaums. Dieser erfordert ein flaches Bewegungsmodell, sodass differentielle Randbedingungen automatisch erfüllt sind. Die Trajektorien des flachen Ausgangs, welche im betrachteten Beispiel der Flugbahn entsprechen, werden mittels Bézier-Kurven entworfen. Die Einhaltung der Ungleichungsnebenbedingungen wird durch ein Indikator-Integral überprüft, welches sich mit wenig Zusatzaufwand parallel zum Kostenfunktional berechnen lässt. Zwar konvergiert der RRT*-Algorithmus (im probabilistischen Sinne) zu einer optimalen Lösung, jedoch ist die Konvergenzrate aus praktischer Sicht unbrauchbar langsam. Es ist daher naheliegend, den Planer durch ein gradientenbasiertes lokales Optimierungsverfahren mit besseren Konvergenzeigenschaften zu unterstützen. Hierzu wird die aktuelle Zwischenlösung des Planers als Initialschätzung für ein kompatibles semi-infinites Optimierungsproblem verwendet. Der vorgeschlagene Optimierungsalgorithmus erweitert das verbreitete innere-Punkte-Konzept (primal dual interior point method) auf semi-infinite Probleme. Eine explizite Diskretisierung der funktionalen Ungleichungsnebenbedingungen ist nicht erforderlich, denn diese erfolgt implizit durch eine numerische Integralauswertung im Rahmen der linearen Teilprobleme. Da die Methode an Stellen aktiver Nebenbedingungen nicht wohldefiniert ist, kommt zusätzlich eine Variante des Reduktions-Ansatzes zum Einsatz, bei welcher der Vektor der Optimierungsvariablen um die (endliche) Menge der aktiven Indizes erweitert wird. Weiterhin wurde eine Kollisionsvermeidung integriert, die in den Teilschritt der Liniensuche eingreift und die Problemformulierung dynamisch um Randbedingungen zur lokalen Berücksichtigung von Hindernissen erweitert. Experimentelle Untersuchungen bestätigen, dass die Ergebnisse des hybriden Ansatzes aus RRT(*) und numerischem Optimierungsverfahren der klassischen RRT*-basierten Trajektorienoptimierung überlegen sind. Der erforderliche Rechenaufwand ist zwar beträchtlich, aber unter realistischen Bedingungen praktisch beherrschbar.