Graduation Semester and Year
2021
Language
English
Document Type
Thesis
Degree Name
Master of Science in Computer Science
Department
Computer Science and Engineering
First Advisor
Manfred Huber
Abstract
Path finding on grid-based obstacle maps is an important and much studied problem with applications in robotics and autonomy. Traditionally, in the AI community, heuristic search methods (e.g. based on Dijkstra and A*, or based on random trees) are used to solve this problem. This search, however incurs significant computational cost that grows with the size and resolution of the obstacle grid and has to be mitigated with effective heuristics in order to allow path finding in real time. In this work we introduce a learning framework using deep neural networks with a stackable convolution kernel to establish a hierarchy of directional traversability representations with decreasing resolution that can serve as an efficient heuristic to guide a multi-resolution path planner. This path planner finds paths efficiently starting on the lowest resolution traversability representation and then refining the path incrementally through the hierarchy until it addresses the original obstacle constraints. We demonstrate the benefits and applicability of this approach on datasets of maps we created to represent both indoor and outdoor environments in order to represent different real world applications. The conducted experiments show that our method can improve the time of path planning by 30% in indoor environments and 66% in outdoor environments compared to the application of the same heuristic search method applied to the original obstacle map, which demonstrates the effectiveness of this method.
Keywords
Motion and Path Planning, AI-Enabled Robotics
Disciplines
Computer Sciences | Physical Sciences and Mathematics
License
This work is licensed under a Creative Commons Attribution-NonCommercial-Share Alike 4.0 International License.
Recommended Citation
Etemadi Idgahi, Reza, "LEARNING HIERARCHICAL TRAVERSABILITY REPRESENTATION FOR EFFICIENT MULTI-RESOLUTION PATH PLANNING" (2021). Computer Science and Engineering Theses. 439.
https://mavmatrix.uta.edu/cse_theses/439
Comments
Degree granted by The University of Texas at Arlington