ORCID Identifier(s)

0000-0002-3253-765X

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

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS