Back to search

Georgia Institute of Technology

Path-planning algorithms in high-dimensional spaces

Abstract

dc:description.abstract

In this thesis, we discuss the problem of path-planning in high-dimensional spaces. Large search spaces tend to lead to slow algorithms in order to find a path or to converge towards the optimal solution of a path-planning problem. This thesis investigates both discrete and continuous search spaces. For discrete search spaces, the use of multi-scale data structure allows a planning algorithm to consider a region of space at different resolutions through the execution of the algorithm and to accelerate the execution of the algorithm. The proposed algorithm is proven to be complete, it will find a solution if one exists, or report that no solution exists. Multiple applications are presented with direct construction of the multi-scale map via perception algorithms, as well as a sampling approach for problems where constructing the multi-scale map is too expensive. For continuous search spaces, the thesis explores the use of classical optimization methods within the family of sampling-based planning algorithms. An experiment is first presented to show the convergence limits of sampling-based algorithms. Then an optimization formulation shows how samples of the search space can be repositioned in order to enhance the estimate of the value function of the problem. Finally, this optimization is integrated in the framework of Rapidly-exploring Random Trees to introduce the Deformable Rapidly-exploring Random Trees algorithm. This algorithm rapidly finds a feasible solution, similarly to the other RRT algorithms, and it also significantly increases the convergence rate of the solution thanks to the added optimization step. Analysis of the parameters and applications of the algorithm show significant improvement compared to the state-of-the-art algorithms.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Aerospace Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Hauer, Florian M.
Advisor dc:contributor.advisor
  • Tsiotras, Panagiotis
Committee members dc:contributor.committeemember
  • Feron, Eric
  • Vamvoudakis, Kyriakos
  • Vela, Patricio
  • Boots, Byron

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/61206

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Hauer, Florian M.. Path-planning algorithms in high-dimensional spaces. Doctoral thesis, Georgia Institute of Technology, 2019. http://hdl.handle.net/1853/61206